3. Основные направления и понятия символической (математической) логики	47

3.16. Построение секвенции

Секвенция А1, À2, À3, ..., Àn Â1, Â2, Â3, ..., Âm. Выражение А1, À2, À3, ..., Àn является антецедентом, а В1, Â2, Â3, ..., Âm — консеквентом данной секвенции. Секвенция

вида А А является исходной, а формула А — основной формулой исходной секвенции. Секвенции, содержащие одни и те же формулы как в антецеденте, так и в консеквенте, считаются тождественными.

Определение вывода секвенции S

Некоторое число секвенций, образующих фигуры заключения, представляют вывод секвенции при следующих условиях:

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

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

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

Так, например, необходимо определить: «Следует ли высказывание (р r) из

высказываний (р q) и (q

r) èëè íåò».

Для этого строится вывод секвенции ((p q) & (q

r)) (p r),

p → p

q → q

r → r

p → r, p

q → r, q

r, p → r

(q r), p → r, p

q, p → r, q

r, q, p → r

q, (q r), p

r

(p q), (q r), p → r

(p q), (q r) → (p r)

((p q) & (q r)) → (p r)

→ ((p q) & (q r)) → (p r)

Исходя из полученных результатов очевидно, что все верхние секвенции являются исходными. Следовательно, из высказываний (p q) и (q r) следует высказывание (p r). В случае, когда верхние секвенции вывода не будут исходными, тогда они будут представлять собой условия истинности данной секвенции.

Так, например, необходимо определить: «Из чего следует высказывание ((p q) p)

и при каком условии оно будет истинным».
Для этого строится вывод секвенции		((p	q) p)
	p	p q	q
	(p q)		p

((p q) p)

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

öèÿ q	p не является исходной. Следовательно, высказывание ((p q)	p)
следует из высказывания (истинно при условии истинности) (q p).

1 При изложении этого вопроса использован материал из книг: Клини С.К. Введение в математику. М., 1952. С. 424; Логика. СПб., 2001. С. 263, 264.

48I. Пропедевтика: предмет логики. Основные понятия и структура логики

3.17.Законы логики высказываний

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

Основные схемы тождественно-истинных формул:

1.Закон тождества:

ÀÀ.

2.Закон противоречия:

(À & À).

3.Закон исключенного третьего:

ÀÀ.

4.Законы удаления конъюнкции:

(А & В) А, (А & В) В. 5. Законы введения дизъюнкции:

À (À Â), Â (À Â).

6. Законы коммутативности конъюнкции и дизъюнкции:

(À & Â) (Â & À), (À Â) (Â À).

7. Законы ассоциативности конъюнкции и дизъюнкции:

((À & Â) & Ñ) (À & (Â & Ñ)), ((À Â) Ñ) (À (Â Ñ)).

8. Законы дистрибутивности конъюнкции относительно дизъюнкции, и наоборот:

	(À & (Â Ñ)) ((À & Â) (À & Ñ)),
	(À (Â & Ñ)) ((À Â) & (À Ñ)).
9.	Законы поглощения:
	(À & (À		Â))	À,
	(À	(À & Â))		À.
10.	Законы идемпотентности:
	(À & À)		À,
	(À	À)	À.
11.	Закон удаления истинного члена конъюнкции:
	À &		À.

12.Закон удаления ложного члена дизъюнкции:

ÀÀ.

13.Закон утверждения консеквента:

À(Â À).

14.Закон самодистрибутивности импликации:

(À (Â Ñ))		((À Â) (À Ñ)).
15. Законы транзитивности импликации:
(À Â)	((Â Ñ)		(À Ñ)),
(À Â)	((Ñ À)		(Ñ Â)).
16. Закон перестановочности антецедентов:
(À (Â Ñ))		(Â (À Ñ)).
17. Закон Пирса:
((À Â)	À)	À.

3. Основные направления и понятия символической (математической) логики	49

18. Закон импортации:
(À (Â Ñ))		((À & Â) Ñ).
19. Закон экспортации:
((À & Â)	Ñ)	(À (Â Ñ)).
20. Законы монотонности:
(À Â) ((À & Ñ) (Â & Ñ)),
(À Â)	((À Ñ) (Â Ñ)).

21.Законы введения конъюнкции:

À(Â (À & Â)),

(А В) ((А С) (А (В & С))). 22. Законы снятия и введения двойного отрицания:

À À, À À.

23.Закон отрицания антецедента:

À(À Â).

24.Законы введения отрицания:

(À	Â)	((À		Â)	À),
(À	À)		À.
25. Закон контрапозиции:
(À	Â)	(	Â	À).
26. Закон обратной корнтрапозиции:
( Â	À)		(À	Â).
27. Законы сложной контрапозиции:
((À & Â) Ñ) ≡ ((À & Ñ)						Â),
(À (Â Ñ)) ≡ ( Â ( À Ñ)).
28. Закон удаления		(«из противоречия следует все что угодно»)1:
	À.
29. Закон введения		(«логический закон следует из чего угодно»)1:

À.

30.Законы де Моргана:

(À & Â) ≡ ( À Â), (À Â) ≡ ( À & Â).

31. Закон отрицания импликации:

(À Â) ≡ (À & Â).

32. Законы взаимовыразимости пропозициональных связок:

(À Â) ≡ ( À Â), (À Â) ≡ (À & Â), (À & Â) ≡ (À Â),

(À & Â) ≡ ( À Â),

(À Â) ≡ À	Â,
(À Â) ≡ ( À & Â),
(À Â) ≡ ((À	Â) Â).

1 Знаки и являются формулами языка логики высказываний, причем значение «истина», а — значение «ложь».

постоянно принимает

50I. Пропедевтика: предмет логики. Основные понятия и структура логики

3.18.Классическая логика предикатов

Логика предикатов (функциональная логика, теория квантификации, кванторная логика) — основной раздел современной (символической, математической) логики, в котором описываются выводы, учитывающие субъектно-предикатную структуру высказываний.

Логика предикатов представляет собой расширенный вариант логики высказываний:

для выявления субъектно-предикатной структуры высказываний вводится ряд индивидных переменных: х, у, z, ..., х1, ó1, z1, ..., представляющих различ- ные объекты и ряд предикатных переменных: P, Q, R, ... P 1, Q1, R 1, ..., представляющих свойства и отношения объектов; в дополнение к средствам логики высказываний вводятся логические опера-

торы — квантор общности A («для всех») и квантор существования («для некоторых» или «существует»).

Запись AхР(х) означает «Всякий х обладает свойством Р»; хР(х) — «Некоторые х обладают свойством Р». Если переменная находится в области действия квантора, то она называется связанной; переменная, не являющаяся связанной, называется свободной.

Запись логической формы некоторого выражения на языке логики предикатов осуществляется следующим образом:

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

предикатов, а из этих символов строят формулу.

П р и м е р. Записать на языке логики предикатов логическую форму следующего выражения: «В каждом магазине есть товары, которые не нужны никому». «В каждом» — квантор общности (A), «магазин» — одноместный предикатор (Р1), «есть» — квантор существования ( ), «товары» — одноместный предикатор (Q1), «не» — отрицание ( ), «нужны» — двухместный предикатор (R2), «никому»

(«ни одному человеку») — квантор общности (	A	) и одноместный предикатор (S1).

(Общей областью всех предметных переменных является область неспецифированных объектов.) Из этих символов, согласно определению формулы, строим формулу:

A

õ(Ð 1(õ)

ó (Q 1(ó) & z(S 1(z) R 2(y,z)))).

П р и м е р. Записать на языке логики предикатов логическую форму следующего выражения: «Некоторые продавцы знают каждого покупателя лучше, чем каждого соседа»: Заменим термины «продавец», «знающий лучше, чем», «покупатель», «сосед» соответственно S1, R1, P1, Q1.

На языке логики предикатов это высказывание выражается формулой:

x

A

y

A

z (S(x) &

(P(y) (Q(z) R (x, y, z )))).