Mat_Logika_Algebra_i_ischislenie_vyskazyvany

11

будут чувствовать себя в опасности (B), а наш народ получит ложное пред-

ставление о своей безопасности (C). Если другие страны будут чувствовать себя в опасности, то они смогут начать превентивную войну (D). Если наш народ получит ложное представление о своей безопасности, то он ослабит свои усилия, направленные на сохранение мира (E). Если же не строить про-

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

Выразим рассуждение в виде логических формул. Обозначим через

P1=А (В & C); P2= В D; P3= C E; P4= ¬A F.

Тогда рассуждение имет вид:

(P1 & P2 & P3 & P4 ) ((D & E) F).

Проверим, существует ли оценка списка переменных, при которой эта формула примет Ложное значение. Для этого должны выполняться равенства:

(P1 & P2 & P3 & P4 ) = И; ((D & E) F) = Л.

Для первого равенства необходимо выполнение

P1 = И; P2 = И; P3 = И; P4 = И,

а из второго следует, что

F = Л; (D & E) = Л.

Тогда для P4 = И необходимо A = И; для P1 = И необходимо B = И и

C = И. Тогда для P2 = И необходимо D = И; для P3 = И необходимо E = И.

Получаем противоречие с (D & E) = Л. Значит, формула не может ни при каких значениях переменных принимать значение Ложно, и рассуждение является правильным.

Упражнение. Если курс ценных бумаг растет или процентная ставка снижается, то либо падает курс акций, либо налоги не повышаются. Курс акций пони-

12

жается тогда и только тогда, когда растет курс ценных бумаг и налоги растут. Если процентная ставка снижается, то либо курс акций не понижается, либо курс ценных бумаг не растет. Следовательно, либо повышаются налоги, либо курс акций понижается и снижается процентная ставка.

1.3. Полнота в логике высказываний

Булевой функцией f (x1 , x2 ,..., xn ) называется n-местная функция из

множества {0; 1} в множество {0; 1}.

Замечание.

1.Каждая булева функция от n переменных может быть задана таблицей из 2n строк с различными оценками списка переменных.

2.Если значению Истина поставить в соответствие 1, а значению Ложь – 0, то каждой логической формуле соответствует единственная булева функция.

Сдругой стороны имеет место следующая

Теорема. (о представимости булевых функций).

Каждая булева функция порождается некоторой формулой, в которую кроме пропозициональных переменных входят только пропозициональные связки из множества {¬; &; }.

Доказательство.

Пусть f (x1 , x2 ,..., xn ) задана таблицей:

I. Если она является тождественным нулем, то формула:

(А1 & ¬А1) (А2 & ¬А2) ... (Аn & ¬Аn) явля-

ется такой порождающей формулой.

II. Пусть среди значений функции есть хотя бы одна 1. Пусть это строка таблицы истинности с номером j.

x1	x2	.	xn	f
0	0	.	0	?
0	0	.	1
.	.	.	.	.
1	0	.	1	1
.	.	.	.	.
1	1	1	1	?

13

Обозначим через Dj =u1 & u2	A , при x =1
	& ... & un , где ui = i	i	0	.
	¬Ai , при xi =

Эта формула принимает значение Истина только на «своей» строке таблицы истинности. На всех остальных она принимает значение Ложь. Это вытекает из определения конъюнкции принимать инстинное значение тогда и только тогда, когда истинны все операнды. А они – ui , составлены так, чтобы на

«своей» оценке списка переменных принимать Истина.

Формула A = Dj1 Dj2 ... Djk , составленная по всем строкам со значением 1, является формулой, порождающей исходную булеву функцию. ■

Упражнение. Для 3–х местной произвольной функции построить порождающую формулу. В качестве такой функции взять три произвольные строки в таблице истинности, определяющей эту функцию, и поставить в столбец для значения функции 1. В оставшиеся строки поставить 0.

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

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

1. M0 = {¬; &; }. 2. M1 = {¬; &}. 3. M2 = {¬; }. 4. M3 = {¬; }.

1.4. Совершенные формы

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

14

Пример.

1.A3 .

2.¬A2 .

3.A1 & ¬A2 & A3 .

Формула A записана в дизъюнктивной нормальной форме (ДНФ), ес-

ли она является дизъюнкцией элементарных конъюнкций.

Пример.

1.X1.

2.¬X1 & X2 .

3.(X1 & ¬X2 ) (X2 & ¬X3 ).

Формула A записана в совершенной дизъюнктивной нормальной форме (СДНФ), если она удовлетворяет условиям:

1)она записана в ДНФ;

2)каждая ее элементарная конъюнкция зависит от всех пропозициональ-

ных переменных, от которых зависит формула A, и все элементарные конъюнкции различны.

Пример.

1.X1.

2.¬X1 & X2 .

3.(X1 & ¬X2 & ¬X4 ) (X1 & X2 & X4 ).

Теорема. (о представимости формул в ДНФ).

Для любой формулы A, не являющейся противоречием, существует равносильная ей формула B, находящаяся в ДНФ.

Доказывается методом математической индукции по числу связок. Упражнение. Привести к ДНФ: (¬A1 A2 )& (¬A2 A1 ).

(¬A1 A2 )& (¬A2 A1 )≡ (под знаком ≡ указан номер равносильности)

4.1

15

4≡.1 (¬A1 & ¬A2 ) (¬A1 & A1 ) (A2 & ¬A2 ) (A2 & A1 )15≡.1 15≡.1 (¬A1 & ¬A2 ) Л Л (A2 & A1 )13≡.2

13≡.2 (¬A1 & ¬A2 ) (A2 & A1 )2≡.1 (¬A1 & ¬A2 ) (A1 & A2 ).

Последнее преобразование (перестановка переменных во вторых скобках) необязательное, но полезное для дальнейшего получения совершенной формы.

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

Пример.

1.A3 .

2.¬A2 .

3.A1 ¬A2 A3 .

Формула A записана в конъюнктивной нормальной форме (КНФ), ес-

ли она является конъюнкцией элементарных дизъюнкций.

Пример.

1.X1.

2.¬X1 & X2 . (эта формула является и ДНФ, и КНФ)

3.(X1 ¬X2 )& (X2 ¬X3 ).

Формула A записана в совершенной конъюнктивной нормальной форме (СКНФ), если она удовлетворяет условиям:

1)она записана в КНФ;

2)каждая ее элементарная дизъюнкция зависит от всех пропозициональ-

ных переменных, от которых зависит формула A, и все элементарные дизъюнкции различны.

16

Теорема. (о представимости формул в КНФ).

Для любой формулы A, не являющейся тавтологией, существует равносильная формула B, находящаяся в КНФ.

Теорема. (о приведении к СДНФ).

Если формула A не является противоречием, то существует равносильная ей формула B, находящаяся в СДНФ, зависящая от того же списка переменных. Такая СДНФ единственна с точностью до порядка элементарных конъюнкций.

Теорема. (о приведении к СКНФ).

Если формула A не является тавтологией, то существует равносильная ей формула B, находящаяся в СКНФ, зависящая от того же списка переменных. Такая СКНФ единственна с точностью до порядка элементарных дизъюнкций.

Двойственные формулы

Связки & и называются двойственными.

Формула A*, содержащая лишь пропозициональные связки из множест-

ва {¬; &; }, называется двойственной формуле A, если она получена из A

заменой & на и наоборот. Для таких формул есть свойство:

A*(Х1, ..., Хn) ≡ ¬A (¬Х1, ..., ¬Хn)

Если формула A в СДНФ, то формула A* в СКНФ и наоборот.

Алгоритм построения СДНФ по таблице истинности

1. В таблице истинности берем строки с Истинным (единичным) значением формулы (функции).

17

2.Для каждой такой строки записываем элементарную конъюнкцию по следующему правилу:

•если значение пропозициональной переменной Хi равно И (1), то в элементарную конъюнкцию записываем Хi;

•если значение пропозициональной переменной Хi равно Л (0), то в элементарную конъюнкцию записываем ¬Xi .

3.Все элементарные конъюнкции объединяем дизъюнкциями.

Алгоритм построения СКНФ по таблице истинности

1.В таблице истинности берем строки с Ложным (нулевым) значением формулы (функции).

2.Для каждой такой строки записываем элементарную дизъюнкцию по следующему правилу:

•если значение пропозициональной переменной Хi равно Л (0), то в элементарную конъюнкцию записываем Хi;

•если значение пропозициональной переменной Хi равно И (1), то в элементарную конъюнкцию записываем ¬Xi .

3.Все элементарные дизъюнкции объединяем конъюнкциями.

Можно построить совершенные формулы и без таблиц истинности.

Алгоритм построения СДНФ и СКНФ с использованием равносильностей

Приведение к ДНФ:

1.По формулам равносильностей 9 и 10 заменяем эквиваленции и импликации через отрицания, конъюнкции и дизъюнкции.

2.По формулам де Моргана 6.1 – 6.2 вносим отрицания к пропозициональным переменным, чтобы они оставались лишь перед пропозициональными переменными, но не перед скобками.

18

3.По формуле дистрибутивности 4.1 вносим конъюнкции к пропозициональным переменным.

4.Отбрасываем все конъюнкции, содержащие пропозициональную переменную и ее отрицание и доводим вхождение каждой пропозициональной переменной в конъюнкцию до одного (на основании равносильностей 15.1; 13.1; 13.2 и 1.2).

Приведение к СДНФ:

5.Для каждой конъюнкции возможны два варианта:

а) элементарная конъюнкция С содержит переменную Хi или ее отрицание;

б) элементарная конъюнкция С не содержит переменную Хi и ее отрицание, тогда

C≡(C & Xi ) (C & ¬Xi ).

6.Повторяем п.5 для всех элементарных конъюнкций, пока для любой пропозициональной переменной из списка переменных не выполнится п.5а.

7.Упорядочиваем каждую элементарную конъюнкцию, чтобы переменная Хi или ее отрицание стояли на i–ом месте и затем выбрасываем все вхождения, кроме одного, для одинаковых элементарных конъюнкций.

Приведение к СКНФ аналогично, только вместо конъюнкций С рассматриваются дизъюнкции D, и в п.3 применяется равносильность 7.2, в п.5б замена имеет вид:

D≡ (D Xi )& (D ¬Xi ).

Упражнения.

1. (A B) (A (¬B & C )) привести к ДНФ и КНФ; к СДНФ и

СКНФ.

(A B)	(	A (¬B & C )			)	≡ ¬(¬A B)		(	¬A (¬B & C )			)	≡
						10.2							6.2
≡ (¬¬A & ¬B)			(	¬A (¬B & C )			≡ (A & ¬B)			(	¬A (¬B & C )			)	≡
6.2						)	8								3.2

											19
≡		(A & ¬B) ¬A		(¬B & C )≡
3.2	(		)					4.2
≡		(A ¬A)& (¬B ¬A)				)	(¬B & C ) ≡
4.2	(										15.2
≡			И & (¬B ¬A)	)	(¬B & C ) ≡						(¬B ¬A) (¬B & C )≡
15.2 (								14.1					2.2
≡ (¬A ¬B) (¬B & C )≡¬A									(	¬B (¬B & C )		)	≡ ¬A ¬B .
2.2					3.2								5.2
Эта формула является ДНФ и КНФ. Расширим ее до совершенных форм.
¬A ¬B ≡ (¬A & B) (¬A & ¬B) (A & ¬B) (¬A & ¬B)≡
			7.2										1.2
≡	(¬A & B) (¬A & ¬B) (A & ¬B)≡
1.2											7.2
≡	(¬A & B & C ) (¬A & B & ¬C ) (¬A & ¬B & C )
7.2
(¬A & ¬B & ¬C ) (A & ¬B & C ) (A & ¬B & ¬C ).
Это – СДНФ.
Полученную КНФ расширим до СКНФ.
¬A ¬B ≡(¬A ¬B C )& (¬A ¬B ¬C ).
			7.1
			По элементарным конъюнкциям в СДНФ можно составить оценки спи-

ска переменных, на которых каждая из них принимает значение Истина. Это,

соответственно, (Л, И, И); (Л, И, Л); (Л, Л, И); (Л, Л, Л); (И, Л, И); (И, Л, Л).

Правильность созданной СДНФ можно проверить по этим оценкам – в таблице истинности значение исходной формулы на них должно быть Истина.

Аналогично, по элементарным дизъюнкциям составляем оценки списка переменных, на которых каждая из них принимает значение Ложь. Это, соот-

ветственно, (И, И, Л); (И, И, И).

2.Составить таблицы истинности для 2-х местных булевых функций.

20

Двухместные булевы функции

Булевы функции двух переменных

ПП			Константы			Отодной ПП				1 на одной					0 на одной					≡
																				или	или
											оценке					оценке					¬
X	Y		f0		f1	f2	f3	f4	f5	f6	f7	f8	f9	f10		f11	f12	f13		f14	f15
0	0		0		1	0	0	1	1	0	0	0	1	0		1	1		1	1	0
0	1		0		1	0	1	1	0	0	0	1	0	1		0	1		1	0	1
1	0		0		1	1	0	0	1	0	1	0	0	1		1	0		1	0	1
1	1		0		1	1	1	0	0	1	0	0	0	1		1	1		0	1	0
f0	= 0 ;		f1 =1;

f2	= X ; f3 =Y ; f4 = ¬X ; f5 = ¬Y ;
f6	= X & Y ; f7 = X & ¬Y ; f8 = ¬X &Y ; f9 = ¬X & ¬Y ;
f10	= X Y ; f11 = X ¬Y ; f12 = ¬X Y ; f13 = ¬X ¬Y ;
f14	=(X & Y ) (¬X & ¬Y ); f15 =(¬X & Y ) (X & ¬Y ).

Замечание. Некоторые из булевых функций имеют свое наименование и обозначение:

f6 = X Y – логическое умножение; f13 = X | Y – «штрих Шеффера»;

f9 = X ↓ Y – «стрелка Пирса»; f14 = X Y – эквиваленция;

f15 = X Y – сложение по модулю 2 или разделительное «или»; f12 = X Y – импликация; аналогично: f11 = Y X.

Теорема. (об единственности представления формул булевыми функциями). Каждой логической формуле соответствует единственная булева функ-