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

3.12. Алгоритм приведения формул к КНФ и ДНФ

Алгоритм приведения формул к конъюнктивной нормальной форме (КНФ)

èдизъюнктивной нормальной форме (ДНФ) следующий.

1.Все элементы исходной формулы, содержащей знаки ≡ и ≡ (эквивалентность и ее отрицание) заменяются на равнозначные им со знаками конъюнкции

(&) и дизъюнкции ( ), т.е. удаляется эквиваленция.

2.Все элементы исходной формулы, имеющие вид (А В), заменяются на ( А В) или (А & В), т.е. удаляется импликация.

3.Ограничивается область действия знака , т.е. уменьшается область действия всех отрицаний, находящихся при сложных элементах (состоящих из двух или более переменных). Знак должен находиться только при переменных.

4.Удаляются все двойные отрицания при переменных.

5.Осуществляется раскрытие всех скобок по закону дистрибутивности дизъюнкции относительно конъюнкции (при приведении к КНФ) или по закону

дистрибутивности конъюнкции относительно дизъюнкции (при приведении

ê ÄÍÔ).

Ïр и м е р. Дано выражение (А & (А В)) В.

1.Удаляем импликацию. Согласно правилу (А В) ≡ ( А В) имеем:

(À & ( À Â)) Â.

2.Удаляем отрицания. Согласно правилу (А & В) ≡ ( А В) (закон де Моргана) имеем:

( À ( À Â)) Â.

3. Удаляем другие отрицания. Согласно правилу (А В) ≡ ( А & В) (закон де Моргана) имеем:

( À ( À & Â)) Â.

4. Применяем закон дистрибутивности дизъюнкции относительно конъюнкции. Имеем:

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

5. Применяем его снова. Имеем:

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

В данном случае итоговая формула и есть КНФ, тождественно-истинная формула.

Критерии КНФ и ДНФ таковы.

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

Критерий ДНФ: если в каждой конъюнкции, составляющей ДНФ, некоторая переменная входит один раз с отрицанием, а другой — без него, то эта формула — тождественно-ложна (например, выражение ((В & А & В) (В & А & А)(В & С & С) — тождественно-ложное). Если этого нет хотя бы в одной конъюнкции, то выражение — тождественно-истинно или нейтрально (собственно выполнимо).

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

3.13.Аксиоматические исчисления

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

Кроме таких разрешающих процедур, как а) построение таблицы истинности для данной формулы; б) приведение формулы к конъюнктивной (КНФ) и дизъюнктивной (ДНФ) нормальной форме, существуют и другие логические исчисления: а) аксиоматические; б) системы натурального вывода и д) секвенциальные.

Аксиоматические исчисления для классической логики высказываний

Исчисление включает в себя аксиомы и правила вывода.

Аксиомы:

1.ð (q p)

2.((p (q r)) ((p q) (p r))

3.(p & q) p

4.(p & q) q

5.p ((q (p & q))

6.p (p q)

7.q (p q)

8.(p q) ((r q) ((p r) q)

9.(p q) ((p q) p)

10.p päà:

Правила вывода:
1. p q; p			2. A		a
					b .
	q	;
			правило
modus ponens			подстановки

Правило (2) — это разрешение замены собственной подформулы а формулы А формулой b во все вхождения а в формулу А. В конкретном случае аксиомы сформулированы на предметном языке. Если же они формулируются на метаязыке, то правило подстановки не вводится.

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

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

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

3.14. Натуральные исчисления

Натуральные исчисления для классической логики высказываний

Исчисление высказываний строится на основе языка логики высказываний. В качестве дедуктивных принципов теории задаются правила получения формул из других формул, разделяемые на правила введения (индекс «в»), правила исключения (индекс «и»), логических связок (&, , ) и логических символов (констант).

	1. Правила введения:
		A, B			.
	Конъюнкция — & в:	A & B
			A
	Дизъюнкция — в:			,
		A B
			B
	Импликация — в:
		C		B

где С — последняя посылка.

Отрицание — в: B, B ,

C

где С — последняя посылка .

B . A B

,

2. Правила исключения:

& è:	A & B ,	A & B .
	A		B
è:	A B,	A	.
	B

	A B,A .
è:		B
		A	.
è:		A

По каждому из этих правил можно получить из формул того вида, что стоят над чертой (посылки правил), формулы вида, стоящие под чертой (заключение правила). Например, правило введения конъюнкции (&в) позволяет объединить произвольные правильно построенные формулы А и В в конъюнкцию — А & В. Допустим, что А будет формулой (p q), B – (r p), тогда, применяя к ним правило введения конъюнкции (&в), получим формулу (p q) & (r p).

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

Выводом формулы В (заключения) из формул А1, À2, ..., Àn (посылок) называется непустая конечная последовательность формул, каждая из которых является либо посылкой, либо допущением, либо получается по одному из правил вывода из предыдущих формул, и последняя формула этой последовательности есть формула В. Если в процессе вывода удается избавиться от всех допущений, то вывод называется доказательством, а формула В — доказуемой (или теоремой).

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

и доказательства.

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

3.15.Секвенциальные исчисления1

Секвенцией называется выражение вида:

À1, À2, ..., Àn Â1, Â2, ..., Âm,

где А и В — произвольные формулы, содержательно означающее

(À1 & À2 & … & Àn ) (Â1 Â2 … Âm).

Правила вывода (фигуры заключения):

1. Структурные:

	ó			Ã	,
Уточнение:		Ã			, À,
		n		Ã	, À, Â,
Перестановка:				Ã	, Â, À,
Сокращение:		c		Ã	, À, À,
				Ã	, À,

2. Логические:

ó		, Ã	.
	, À, Ã
n		, À, Â, Ã			.
	, Â, À, Ã
c	, À, À, Ã			.
	, À, Ã

&

Ã

, À

, Â

.

Введение конъюнкции в консеквенте:

Ã,

,

, (À & Â)

Введение конъюнкции в антецеденте: &

À, Â, Ã

.

(À &

Â), Ã

Ã

, À, Â

.

Введение дизъюнкции в консеквенте:

Ã

, (À Â)

À, Ã

Â,

.

Введение дизъюнкции в антецеденте:

(À

Â), Ã,

,

Введение импликации в консеквенте:

À, Ã

, Â

.

Ã

, (À

Â)

Ã

, À,

Â,

.

Введение импликации в антецеденте:

(À Â), Ã,

,

À, Ã

Ã

, À

.

Введение отрицания:

Ã

, À

À, Ã

1 Здесь приведен один из вариантов секвенциальных исчислений — исчисление Gl для класси- ческой логики высказываний.