Матлогика(Лагодинский)

Формальный вывод секвенции A→B, B→C|–A→C.

1) A→B	– допущение;
2) B→C	– допущение;
3) (B→C)→(A→(B→C))	– A1;
4) A→(B→C)	– MP 2, 3;
5) (A→( B→C))→ ((A→B)→ (A→C))	– A2;
6) (A→B)→ (A→C)	– MP 4, 5;
7) (A→C)	– MP 1, 6.

Построение выводов бывает достаточно сложным. Его часто облегчает следующая теорема [4].

Теорема о дедукции. Если A1, A2, …, An–1, An|–G, то A1, A2, …, An–1|– An→G. В частности, если F |–G, то |–F→G.

Рассмотрим теперь другое исчисление высказываний, которое обозначают обычно ИС. Это исчисление генценовского типа, в нем одна схема аксиом A|–A и много правил вывода. Выводом секвенции

A|–B из набора секвенций {F1|–G1, F2|–G2,..., Fn|–Gn} в этом исчислении называется последовательность секвенций, каждая из кото-

рых либо представляет собой аксиому, либо секвенцию из исходного набора, либо получается из предыдущих секвенций с помощью правил вывода этого исчисления.

Основные правила вывода:

1)

Γ|- A,Γ|-B

(введение );

Γ|- AÙB

2)

Γ|-( AÙB)

,

Γ|-( AÙB)

(удаление );

Γ|- A

Γ|-B

3)

Γ|- A

,

Γ|-B

(введение );

Γ|-( AÚB)

Γ|-( AÚB)

4)

Γ, A|-C;Γ,B|-C; Γ|-( AÚB)

(удаление , разбор случаев);

Γ|-C

5)

Γ, A|-B

(введение →);

Γ|-( A® B)

6)

Γ1 |- A, Γ2 |-( A® B)

(удаление →);

Γ1,Γ2 |-B

Γ,

|-

(удаление ¬, или доказательство от противного);

7)

A

Γ|- A

31

8)  Γ|- A, Γ|- A (выведение противоречия);

Γ|-

9)  Γ, A,B, Γ1 |-C (перестановка посылок);

Γ,B, A, Γ1 |-C

	10)	Γ|- A	(утончение, или правило лишней посылки).
		Γ,B|- A

Пример 3. Вывод в ИС секвенции A, A→B, B→C, C→D|–D. 1) A|–A – аксиома,

2) A→B|– A→B – аксиома;

3) A, A→B|–B – удаление →, 1, 2; 4) B→C|– B→C – аксиома;

5) A, A→B, B→C|–C – удаление →, 3, 4; 6) C→D|– C→D – аксиома;

7) A, A→B, B→C, C→D|–D – удаление →, 5, 6.

Полнота, разрешимость и непротиворечивость исчисления высказываний. Независимость системы аксиом исчисления высказываний

Исчисление высказываний полно (обладает свойством полноты), если всякая доказуемая в этом исчислении формула является тождественно истинной формулой (тавтологией) алгебры высказываний, и наоборот, любая тавтология алгебры высказываний является доказуемой формулой этого исчисления, т. е. |–F~|=F. Существуют доказательства [1], что исчисления ИВ и ИС полны.

Аксиоматическая теория называется разрешимой, если существует алгоритм, позволяющий для любого утверждения, сформулированного в терминах этой теории, ответить на вопрос, является ли это утверждение теоремой этой теории. Для доказательства разрешимости исчисления высказываний надо предъявить такой алгоритм. И он действительно существует и состоит в составлении таблицы истинности формулы. Если она содержит лишь единицы, то является тавтологией, а значит, поскольку исчисление полно, теоремой исчисления. Если есть хотя бы один ноль, это не тавтология, следовательно, не теорема.

Аксиоматическая теория называется непротиворечивой, если ни для какого утверждения A, сформулированного в терминах этой теории, само утверждение A и его опровержение A не могут быть одновременно теоремами этой теории. Можно показать [1], что исчисления ИВ и ИС непротиворечивы.

32

Система аксиом называется независимой, если ни одну из аксиом этой системы нельзя вывести из остальных. Системы аксиом исчислений ИВ и ИС независимы [1].

4. Логика предикатов

Высказывание с точки зрения исчисления высказываний – предельно простой объект, оно имеет лишь одну характеристику, оно может либо истинным, либо ложным. Высказывания совершенно не структурированы. Но реальные суждения всегда говорят что-то о чем-то или ком-то. Главные члены предложения – подлежащее и сказуемое. Подлежащее означает тот объект, о котором говорится в предложении, а сказуемое – то, что в предложении говорится об этом объекте. Сказуемое иначе называется предикатом.

В математической логике определенным на множествах M1, M2,..., Mn n-местным предикатом называется выражение Pn(x1, x2,..., xn), содержащее n переменных x1, x2,..., xn, и превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств M1, M2,..., Mn соответственно. Переменные x1, x2,..., xn называют предметными, а

элементы множеств M1, M2,..., Mn – конкретными предметами.

Всякий n-местный предикат, определенный на множествах M1, M2,..., Mn, является функцией n аргументов, заданной на этих множествах и принимающей значения во множестве всех высказываний.

Рассмотрим пример. Предложение “Река x впадает в Каспийское море” является одноместным предикатом, определенным на множестве всех названий рек. Подставив вместо x названия “Волга”, “Урал” или “Терек”, получим истинные высказывания, а подставив “Днепр”, “Нил” или “Ориноко”, получим ложные высказывания.

Примером двухместного предиката является неравенство x2+y2<9. Этот предикат задан на двух экземплярах множества вещественных чисел R. Он превращается в истинное высказывание, в частности, при x=1, y=2, а в ложное – при x=2, y=3.

Классификация предикатов

Предикат Pn(x1, x2,..., xn), определенный на множествах

M1, M2,..., Mn, называется a) тождественно истинным, если при любой подстановке вместо переменных x1, x2,..., xn любых кон-

33

кретных предметов a1, a2,..., an из множеств M1, M2,..., Mn соответственно он превращается в истинное высказывание; b) тождественно ложным, если при любой подстановке вместо переменных x1, x2,..., xn любых конкретных предметов a1, a2,..., an из множеств M1, M2,..., Mn соответственно он превращается в ложное высказывание; c) выполнимым (опровержимым), если существует по крайней мере один набор конкретных предметов a1, a2,..., an из множеств M1, M2,..., Mn, при подстановке которых вместо соответствующих предметных переменных в этот предикат он превратится в истинное (ложное) высказывание.

Например, предикат x2≥0, определенный на множестве вещественных чисел R, является тождественно истинным, предикат sinx>1, определенный на R, является тождественно ложным, а предикат “Город x расположен на берегу Волги” является выполнимым и одновременно опровержимым.

Множество истинности предиката

Множеством истинности предиката Pn(x1, x2,..., xn),

определенного на множествах M1, M2,..., Mn, называется совокупность всех упорядоченных наборов конкретных предметов a1, a2,..., an из множеств M1, M2,..., Mn соответственно, таких, что Pn(a1, a2,..., an) – истинное высказывание.

Обозначим множество истинности предиката Pn(x1, x2,..., xn)

через P+. Таким образом, P+={(a1, a2,..., an): P(a1, a2,..., an)=1}.

Равносильность и следование предикатов

Два n-местных предиката Pn(x1, x2,..., xn) и Qn(x1, x2,..., xn), заданных над одними и теми же множествами M1, M2,..., Mn,

называются равносильными, если набор конкретных предметов a1, a2,..., an из множеств M1, M2,..., Mn соответственно превращает первый предикат в истинное высказывание Pn(a1, a2,..., an) в том и только том случае, когда этот же набор превращает второй предикат в истинное высказывание Qn(a1, a2,..., an). Иначе говоря,

предикаты равносильны, если их множества истинности совпада-

ют: P+ = Q+.

Например, равносильны предикаты: x+y>5 и x>5–y. Предикат Qn(x1, x2,..., xn), заданный над множествами

M1,M2,...,Mn,называетсяследствиемпредикатаPn(x1,x2,...,xn), заданногонадтемижемножествами,еслионпревращаетсявистинное высказывание в наборах значений предметных переменных из

34

соответствующих множеств, на которых в истинное высказывание превращается предикат Pn(x1, x2,..., xn). Иначе говоря, P+ ÍQ+ .

Например, предикат x2>4 является следствием предиката x>2, но эти предикаты не равносильны, поскольку первое неравенство справедливо и при x<–2.

Логические операции над предикатами

Отрицанием предиката Pn(x1, x2,..., xn), заданного над множествами M1, M2,..., Mn, называется новый предикат, заданный над теми же множествами, обозначаемый Pn(x1,x2, ,xn) (читается: “неверно, что Pn(x1, x2,..., xn)”), который превращается в истинное высказывание при всех тех и только тех значениях предметных

переменных, при которых предикат Pn(x

1

, x

2

,..., x

n

) превращается

в ложное высказывание.

Например, предикат x≥3 является отрицанием предиката x<3.

Для предиката Pn(x

1

, x

2

,...,

x

n

), определенного на множествах

M

1

, M

2

,..., M

n

, множество истинности предиката Pn(x ,x , ,x )

1 2

n

является

дополнением

множества

истинности предиката

Pn(x , x ,..., x

):

P

+

=(M ´M ´ ´M ) \ P

+ .

1

2

n ( )

1

2

n

Конъюнкцией n-местного предиката Pn(x1, x2,..., xn), опреде-

ленного на множествах M1, M2,..., Mn, и m-местного предиката Qm(y1, y2,..., ym), определенного на множествах N1, N2,..., Nm, называется новый (n+m)-местный предикат, определенный

на множествах M1, M2,..., Mn, N1, N2,..., Nm, обозначаемый
Pn(x ,x , ,x ) ÙQm(y ,y , ,y )				(читается “ Pn(x	, x	,..., x	) и
1 2	n	1 2	m	1	2	n
Qm(y ,y , ,y ) ”), который превращается в истинное высказыва-
1 2	m

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

Например, конъюнкцией предикатов x>3 и x<10 является пре-

дикат 3<x<10.

Дизъюнкцией n-местного предиката Pn(x1, x2,..., xn), определенного на множествах M1, M2,..., Mn, и m-местного предиката Qm(y1,y2, ,ym) , определенного на множествах N1, N2,..., Nm, называется новый (n+m)-местный предикат, определенный

на множествах M1, M2,..., Mn, N1, N2,..., Nm, обозначаемый Pn(x1,x2, ,xn) ÚQm(y1,y2, ,ym) (читается “ Pn(x1, x2,..., xn) или Qm(y1,y2, ,ym) ”), который превращается в истинное высказыва-

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

35

Например, дизъюнкцией предикатов x>3 и x<10 является предикат “x>3 или x<10”.

Импликация Pn(x1, x2,..., xn)→Qm(y1, y2,..., ym) опре-

деляется	как		такой			предикат,			что для любых		предметов
a1 ÎM1,a2 ÎM2, ,an ÎMn,b1 ÎN1,b2 ÎN2, ,bn ÎNn											высказыва-
ние Pn(a	, a	,..., a		n	)→Qm(b		, b	,..., b	m	) является импликацией вы-
1	2					1	2
сказываний Pn(a1, a2,..., an) и Qm(b1, b2,..., bm).

Например, импликацией предикатов x>10 и x>1 является предикат “Если x>10, то и x>1”.

Эквиваленция Pn(x1, x2,..., xn) ~ Qm(y1, y2,..., ym) опре-

деляется	как		такой			предикат,			что для любых		предметов
a1 ÎM1,a2 ÎM2, ,an ÎMn,b1 ÎN1,b2 ÎN2, ,bn ÎNn											высказыва-
ние Pn(a	, a	,..., a		n	) ~ Qm(b		, b	,..., b	m	) является эквиваленцией вы-
1	2					1	2
сказываний Pn(a1, a2,..., an) и Qm(b1, b2,..., bm).

Например, эквиваленцией предикатов x>10 и 10<x является предикат “Если и только если x<10, то 10>x”.

Кванторные операции над предикатами

Операцией связывания квантором общности по переменной x называется правило, по которому каждому одноместному предикату P1(x), определенному на множестве M, ставится в соответствие высказывание ("x)P1(x) (читается “для всякого xP1(x)”), которое истинно в том и только том случае, когда предикат P1(x) тождественно истиннен, и ложно в противоположном случае, а n-местному (n>1) предикату Pn(x1, x2,..., xn), определенно-

му на множествах M1, M2,..., Mn, ставится в соответствие но-

вый (n-1)-местный предикат, обозначаемый

("x )Pn(x ,x , ,x )

(читается “для всех x

Pn(x ,

x

,..., x

1

1 2

n

1

2

n

)”),

который для любых

a2

1

предметов

ÎM2, , an ÎMn

превращается в

высказывание

("x )Pn(x ,a , ,a ), истинное в том и только том случае, когда од-

1

1

2

n

номестный предикат Pn(x1, a2,..., an), определенный на множестве

M1, тождественно истиннен и ложное в противоположном случае.

Операцией связывания квантором существования по перемен-

ной x называется правило, по которому каждому одноместному предикату P1(x), определенному на множестве M, ставится в соответствие высказывание ($x)P1(x) (читается “существует x, такое, что P1(x) ”), которое ложно в том и только том случае, когда предикат P1(x) тождественно ложен, и истинно в противоположном случае, а n-местному (n≥2) предикату Pn(x1, x2,..., xn), определенному на множествах M1, M2,..., Mn, ставится в соответствие новый (n-1)-местный предикат, обозначаемый ($x1) Pn(x1,x2, ,xn) (чита-

36

ется “существует x1, такое, что Pn(x1, x2,..., xn)”), который для любых предметов a2 ÎM2, , an ÎMn превращается в высказывание ($x1) Pn(x1,a2, ,an), ложное в том и только том случае, когда одноместный предикат Pn(x1, a2,..., an), определенный на множестве

M1, тождественно ложен и истинное в противоположном случае. В выражениях типа ("x1)Pn(x1,x2, ,xn) и ($x1) Pn(x1,x2, ,xn)

переменная x1 называется связанной. Остальные переменные на-

зываются свободными.

Формулы логики предикатов

Алфавит логики предикатов состоит из следующих символов: предметные переменные: x, y, z, xi, yi, zi (iÎN);

нульместные предикатные переменные: P, Q, R, Pi, Qi, Ri (iÎN); n-местные предикатные переменные: Pn(,…,), Qn(,…,), Rn(,…,), Pin(,…,), Qin(,…,), Rin(,…,)(iÎN); с указанием числа свободных мест в них; символы логических операций: ¬, , , ~; кванторы: , ;

вспомогательные символы: (, ),,.

Каждая нульместная предикатная переменная есть формула, если Pn(,...,)– n-местная предикатная переменная, то Pn(x1, x2,..., xn) – формула, в которой все переменные x1, x2,..., xn свободны, если F – формула, то F – тоже формула, свободные (связанные) предметные в этой формуле те же, что и в формуле F; если

F1, F2 – формулы, то выражения F1 F2, F1 F2, F1→F2, F1~F2 также являются формулами, при этом предметные переменные, сво-

бодные (связанные) хотя бы в одной из формул F1, F2, являются свободными (связанными) и в новых формулах; если F – формула, а x – предметная переменная, входящая в F свободно, то выражения ( x)(F) и ( x)(F) – тоже формулы, в которых переменная x связанная, а все остальные предметные переменные, входящие в формулу F свободно или связанно, остаются и в новых формулах такими же. Никаких других формул логики предикатов нет.

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

37

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

Превращениеформулылогикипредикатовввысказываниеэтим способом и само получаемое высказывание называется интерпретацией этой формулы на множестве M.

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

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

Формула логики предикатов называется общезначимой, или

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

Например, формула P(x) Ù("y)(P(y)) является противоречием (тождественно ложной).

Тавтологии логики предикатов

Нахождение тавтологий является одной из важнейших задач логики предикатов, как и логики высказываний. Но если в логике высказываний имеется общий метод определения, является ли данная формула тавтологией (таблицы истинности), то в логике предикатов такого метода не существует, поскольку каждое высказывание имеет только одно из значений: “истина” или “ложь”, а значение предиката зависит от выбора значений его предметных переменных, который можно (вообще говоря) сделать бесконечным числом способов. Простейшие тавтологии логики предикатов получаются из тавтологий логики высказываний.

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

Специфичны для логики предикатов тавтологии, которые являются выражениями, содержащими кванторы.

38

Законы де Моргана для кванторов. Следующие формулы явля-

ются тавтологиями логики предикатов: 1) ("x)(P(x) ~ ($x)(P(x));

2) ($x)(P(x) ~ ("x)(P(x).

Следствия этих формул:

1) ("x)(P(x)) ~ ($x)(P(x));

2) ($x)(P(x)) ~ ("x) P(x).

Законы пронесения кванторов через конъюнкцию и дизъюнк-

цию. Следующие формулы являются тавтологиями логики предикатов:

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)(P(x)) ÚQ;

4) ($x)(P(x) ÙQ) ~ ($x)(P(x)) ÙQ.

Законы пронесения кванторов через импликацию. Следующие формулы являются тавтологиями логики предикатов:

1) ("x)(P(x) ®Q) ~ (($x)(P(x)) ®Q); 2) ($x)(P(x) ®Q) ~ (("x)(P(x)) ®Q); 3) ("x)(Q® P(x)) ~ (Q®("x)(P(x)));

4) ($x)(Q® P(x)) ~ (Q®($x)(P(x))).

Законы удаления квантора общности и введения квантора су-

ществования. Следующие формулы являются тавтологиями логики предикатов:

1) ("x)(P(x)) ® P(y); 2)  P(y) ®($x)(P(x)).

Законы коммутативности для кванторов. Следующие форму-

лы являются тавтологиями логики предикатов: 1) ("x)("y)(P(x, y)) ~ ("y)("x)(P(x, y));

2) ($x)($y)(P(x, y)) ~ ($y)($x)(P(x, y)); 3) ($x)("y)(P(x, y)) ®("y)($x)(P(x, y)).

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

Две формулы логики предикатов F и G называются равносильными на множестве M, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то они называются равносильными.Равносильность обозначается так: F≡G. Переход от

39

одной равносильной формулы к другой называется равносильным преобразованием исходной формулы. Формулы F и G равносильны, если формула F~G – тавтология. Например, ( x)( y)(P(x, y))≡( y) ( x)(P(x, y)).

Логическое следование логики предикатов

Формула G логики предикатов называется логическим следствием формулы F, если при всякой интерпретации, при которой F превращается в тождественно истинный предикат, формула G также превращается в тождественно истинный предикат. Это обозначается записью: F|=G. Как и в алгебре высказываний, если и только если F|=G, то |=F→G. Две формулы равносильны тогда и только тогда, когда каждая из них является логическим следствием другой. Но возможны случаи, когда логическим следствием формулы является неравносильная ей формула, например:

($x)(P(x) ÙQ(x)) |=($x)(P(x)) Ù($y)(Q(y)).

Правило удаления квантора общности (правило универсальной конкретизации):

("x)F(x) |=F(y).

Правило введения квантора существования (правило экзистенциального обобщения):

F(y) |=($x)F(x).

Вэтих правилах предполагается, что переменная y не входит в формулу F(x) свободно.

Проблема разрешимости для общезначимости и выполнимости формул логики предикатов

В логике предикатов, в отличие от алгебры высказываний, не существует алгоритма, позволяющего для каждой формулы определить, будет ли она выполнимой или общезначимой. Это было доказано в 1936 г. американским математиком А. Чёрчем. Проблема разрешимости в логике предикатов допускает решение лишь для некоторых частных видов формул. Задача о выполнимости или общезначимости формул логики предикатов на конечном множестве сводится к задаче о выполнимости или тождественной истинности алгебры высказываний, которая разрешима.

40