Тема 1. Математическая логика

множествах М1 , М2 , ..., Мn , называется:
а)

тождественно истинным, если при любой подстановке вместо переменных х1 , х2 , ..., хn любых конкретных предметов a1 , a2 , ..., an из множеств М1 , М2 , ..., Мn соответственно он превращается в истинное высказывание Р(a1 , a2 , ..., an);

множествах М1 , М2 , ..., Мn , называется:
б)

тождественно ложным, если при любой подстановке вместо переменных х1 , х2 , ..., хn любых конкретных предметов из множеств М1 , М2 , ..., Мn соответственно он превращается в ложное высказывание;

множествах М1 , М2 , ..., Мn , называется:
в)

выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов a1 , a2 , ..., an из множеств М1 , М2 , ..., Мn соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат Р(х1 , х2 , ..., хn) последний превратится в истинное (ложное) высказывание Р(a1 , a2 , ..., an).

хn), заданного на множествах М1 , М2 , ..., Мn

, называется совокупность всех упорядоченных наборов (a1 , a2 , ..., an), в которых a1  М1 , a2  М2, …, an  Мn , таких, что данный предикат обращается в истинное высказывание Р(a1 , a2 , ..., an) при подстановке х1 = a1 , х2 = a2 , ..., хn = an .
Это множество будем обозначать Р+. Таким образом, Р+ = {(a1 , a2 , ..., an) : Р(a1 , a2 , ..., an) = 1}.

и Q(х1 , х2 , ..., хn), заданных над одними

и теми же множествами М1 , М2 , ..., Мn , называются равносильными, если набор предметов (элементов) a1  М1 , a2  М2, …, an  Мn превращает первый предикат в истинное высказывание Р(a1 , a2 , ..., an) в том и только в том случае, когда этот набор предметов превращает второй предикат в истинное высказывание Q(a1 , a2 , ..., an).
Другими словами (на языке множеств истинности), предикаты Р(х1 , х2 , ..., хn) и Q(х1 , х2 , ..., хn) равносильны тогда и только тогда, когда их множества истинности совпадают Р+ = Q+.
Утверждение о равносильности двух предикатов Р и Q символически будем записывать так: Р  Q.
Переход от предиката Р1 к равносильному ему предикату Р2 называется равносильным преобразованием первого.

множествами М1 , М2 , ..., Мn , называется следствием

предиката Р(х1 , х2 , ..., хn), заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат Р(х1 , х2 , ..., хn).
Другими словами (в терминах множеств истинности), можно сказать, что предикат Q является следствием предиката Р тогда и только тогда, когда Р+  Q+.
Утверждение о том, что предикат Q является следствием предиката Р, будем символически записывать так: Р  Q.

делится на 3» является следствием одноместного предиката, определенного на том

же множестве, «n делится на 6».
Язык множеств истинности позволяет установить взаимосвязь между понятиями равносильности и следования предикатов: два предиката, определенные на одних и тех же множествах, равносильны тогда и только тогда, когда каждый из них является следствием другого.

другого n -местного предиката, определенного на тех же множествах.
Каждый

n -местный предикат является следствием любого тождественно ложного n -местного предиката, определенного на тех же множествах.

, х2 , ..., хn) — два n -местных предиката,

определенные на одних и тех же множествах, такие, что Q(х1 , х2 , ..., хn) есть следствие Р(х1 , х2 , ..., хn). Тогда:
а) если Р(х1 , х2 , ..., хn) тождественно истинный (выполнимый), то и Q(х1 , х2 , ..., хn) тождественно истинный (выполнимый);
б) если Q(х1 , х2 , ..., хn) тождественно ложный (опровержимый), то и Р(х1 , х2 , ..., хn) тождественно ложный (опровержимый).

х, у, z, xi , … ;
нульместные предикатные переменные:

P, Q, Pi …;
n-местные предикатные переменные: R( , ...,), S( , ...,), Ri( , ..., ) с указанием числа свободных мест в них;
символы логических операций:      ;
кванторы: , ;
вспомогательные символы: ( , ) (скобки, запятая).

высказывание.
1 или 2 этапа:
1) Вместо каждой предикатной переменной подставим конкретный

предикат, определенный на некотором выбранном множестве М.
Формула превратится в конкретный предикат, заданный над множеством М.
Если формула логики предикатов не содержала свободных предметных переменных, то полученный конкретный предикат является нульместным, т.е. будет высказыванием (истинным или ложным). Второй этап не нужен.

свободные вхождения предметных переменных, то в результате подстановки получим предикат,

зависящий от некоторых предметных переменных. Если теперь подставить вместо этих предметных переменных конкретные предметы из множества М, то полученный предикат, а следовательно, и исходная формула превратятся в конкретное высказывание.

xM Q(x, y) = xM yN Q(x, y).
«для каждого y

существует x» = «для каждого x существует y».

Вывод: одноименные кванторы коммутативны

и 2)xM yN Q(x, y)?
Возьмем для примера m = n

= 2.
Обозначим Q(ai , bj) = pij . Тогда
1) yN xM Q(x, y) = (p11  p21)  (p12  p22) = p11 p21  p12 p22 = q.
2) xM yN Q(x, y) = (p11  p12)  (p21  p22) = p11 (p21  p22)  p12 (p21  p22) = p11 p21  p12 p22  p11 p22  p12 p21 . = q  r.

обратная – нет (например, (0  1)  0 =

1  0 = 0).
Следовательно, мы показали (для частного случая), что имеет место
yN xM Q(x, y)  xM yN Q(x, y).
Обратная импликация () в общем случае не верна.

всех предметов из множества M имеет место P(x)» = «существует

предмет из множества M, для которого имеет место P(x)».
xM P(x) = xM P(x)
«не существует предмета из множества M, для которого имеет место P(x)» = «для всех предметов из множества M имеет место P(x)».

указание на множество предметов M:
1) x (P(x)  Q(x)) 

x P(x)  x Q(x)
2) x (P(x)  Q(x))  x P(x)  x Q(x)
3) x (P(x)  Q(x))  (x P(x)  x Q(x))
4) (x P(x)  x Q(x))  x (P(x)  Q(x))

Q(x) для конечного множества предметов
x (P(x)  Q(x)) = (P(a1)

 Q(a1)) … (P(am)  Q(am)) = (P(a1) … P(am))  (Q(a1) … Q(am)) = x P(x)  x Q(x) ∎


Подобным образом для  и  .

(P(x)  Q(x)) = 1, т.е. существует (по крайней мере

один) предмет ak , такой, что P(ak)  Q(ak) = 1.
По свойствам конъюнкции должно быть P(ak) = 1 и Q(ak) = 1. Иначе говоря, xP(x) = 1 и xQ(x) = 1, т.е. x P(x)  x Q(x) = 1.
1  1. ∎

x P(x)  x Q(x) = 1, т.е. xP(x) =

1 и xQ(x) = 1. Следовательно, существует предмет ak , такой, что P(ak) = 1 и существует предмет al , такой, что Q(al) = 1. Может быть, ak  al . Может быть P(al) = 0 и Q(ak) = 0. Тогда P(ak)  Q(ak) = 0 и P(al)  Q(al) = 0 .
Таким образом, в общем случае не исключена ситуация, когда x(P(x)  Q(x)) = 0, т.е. 1  0, что противоречит определению импликации. ∎

 Q(x))
Пусть x P(x)  x Q(x) = 1. Тогда,

по крайней мере, один из предикатов, например, P(x), истинен на всем множестве M. Следовательно, формула P(x)  Q(x) истинна на всем множестве M и x (P(x)  Q(x)) = 1.
Иначе говоря, 1  1. ∎

(P(x)  Q(x))
Пусть P(ak) = 0 для некоторого предмета ak

и P(x) = 1 для остальных предметов множества M.
Пусть Q(al) = 0 для предмета al  ak и Q(x) = 1 для остальных предметов множества M.
Тогда x (P(x)  Q(x)) = 1, но x P(x)  x Q(x) = 0.
Иначе говоря, 1  0. ∎

Q»:
xM(P(x)  Q(x))
Имеют место импликации:
x (P(x)  Q(x))  (x

P(x)  x Q(x)),
x (P(x)  Q(x))  (x P(x)  x Q(x)),
но обратные – неверны.

P(x)  x Q(x)),
(x P(x)  x Q(x))  x

(P(x)  Q(x)).

М, если при некоторой подстановке вместо предикатных переменных конкретных предикатов,

заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат.
Другими словами, формула выполнима (опровержима) на М, если существует истинная (ложная) ее интерпретация на М.

ложной) на множестве М, если при всякой подстановке вместо предикатных

переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат.

ложной или противоречием), если при всякой подстановке вместо предикатных переменных

любых конкретных предикатов, заданных на каких угодно множествах, она превращается в тождественно истинный (тождественно ложный) предикат.

 y Р(y) является тождественно ложной.
Доказательство.
От противного: пусть на

некотором множестве М имеется конкретный предикат А(х), такой, что данная формула превращается в выполнимый предикат (от x) А(x)  y А(y). Иначе говоря, найдется предмет a  М, такой, что высказывание А(a)  y А(y) истинно.
Истинность конъюнкции дает истинность высказываний 1) А(a) и 2) y А(y). Из истинности 1 следует, что высказывание А(a) ложно, а из истинности 2 – что предикат А(y) тождественно истинный и, значит, для любого предмета из М в том числе и для a  М, высказывание А(a) истинно.
Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна.

и алгебры высказываний.
Но если в алгебре высказываний имеется общий

метод определения, является или нет данная формула тавтологией (это — метод составления таблицы истинности для формулы), то в логике предикатов такого общего метода не существует.
Каждая формула подлежит изучению индивидуальным методом на тождественную истинность. Дело здесь в том, что каждое высказывание имеет только одно из двух логических значений: «истина» или «ложь»», тогда как значение предиката зависит от выбора значений его предметных переменных, который, вообще говоря, можно сделать бесконечным числом способов.

Следующие формулы логики предикатов являются тавтологиями:
а) (х Р(х)) 

Р(у);
б) Р(у)   х Р(х).
Доказательство формулы а).
От противного. Предположим, что формула а) не тождественно истинна. Это значит: существует такой предикат А(х), определенный на некотором множестве M, что предикат (от у) (х A(х))  A(у) опровержим, т.е. превращается в ложное высказывание при подстановке вместо у некоторого a  М : (х A(х))  A(a) = 0. Последнее означает, что
1) (х A(х)) = 1 и 2) A(a) = 0.
Из соотношения (1) заключаем, что предикат А(х) тождественно истинный. Но это противоречит соотношению (2). Следовательно, сделанное предположение неверно, и данная формула — тавтология. ∎

называются равносильными на множестве М, если при любой подстановке в

эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на М, формулы превращаются в равносильные предикаты.
Если две формулы равносильны на любых множествах, то их будем называть просто равносильными. Равносильность формул будем обозначать так: F= Н.

другой. Переход от одной равносильной формулы к другой называется равносильным

преобразованием исходной формулы.
В процессе равносильных преобразований формул логики предикатов могут использоваться равносильности, известные из алгебры высказываний.
Равносильные преобразования позволяют приводить формулы к тому или иному более удобному виду. Один из таких видов носит название приведенной формы.

равносильная ей формула, в которой из операций алгебры высказываний имеются

только операции , , , причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.

видом формулы, к которому ее можно привести равносильными преобразованиями, является

предваренная нормальная форма.

такая ее приведенная форма, в которой все кванторы стоят в

ее начале, а область действия каждого из них распространяется до конца формулы, т. е. это формула вида (K1х1)...(Km хm) (F(х1 , х2 , ..., хn)), где Ki есть один из кванторов  или  (i = 1, ..., m), m < n, причем формула F не содержит кванторов и является приведенной формулой.
(Заметим, что кванторы в формуле могут отсутствовать вовсе.)