Признак равносильности формул 2 страница

После выполнения указанных действий 1), 2), 3), 4), 5) получим СДНФ.

Замечание 9. При приведении к СДНФ нет необходимости знать заранее, является ли формула тождественно ложной или нет. Если выполняя операции пункта 5), будут удалены все слагаемые, то не получим СДНФ.

Таким образом, справедливо:

Свойство 1. У противоречий не существует СДНФ.

Пример. Привести формулу к СДНФ:

;

– ДНФ;

;

;

– CДНФ.

 

Совершенная конъюнктивная нормальная форма

Аналогичным образом определяется СКНФ. Определение дается в терминах, двойственных тем, которые были использованы в определении 18.

Определение 19. Совершенной конъюнктивной нормальной формой (СКНФ) формулы , содержащей n различных переменных, называется ее КНФ, удовлетворяющая следующим условиям:

1) в ней нет двух одинаковых множителей;

2) ни один множитель не содержит двух одинаковых слагаемых;

3) никакой множитель не содержит какой-нибудь переменной вместе с ее отрицанием;

4) каждый множитель содержит в себе в качестве слагаемых либо переменную , либо ее отрицание .

Правила приведения к СКНФ аналогичны тем, которые описаны выше для нахождения СДНФ, и выражаются в двойственных терминах (то есть конъюнкцию меняем на дизъюнкцию, дизъюнкцию на конъюнкцию, 0 на 1, 1 на 0).

Замечание 10. Если множители содержат какую-нибудь переменную вместе с ее отрицанием ( истина), то их удаляем. Если все множители такие, то всё произведение тождественно истинно. Формула не имеет СКНФ.

Таким образом, справедливо:

Свойство 2. У тавтологий не существует СКНФ.

Пример. Привести формулу к СКНФ:

;

– КНФ;

;

;

– CКНФ.

Свойство 3. Каждая формула алгебры высказываний, не являющаяся тавтологией или противоречием, имеет СКНФ и СДНФ, причем единственные.

Доказательство. Существование СКНФ, СДНФ для формулы, не являющейся тавтологией или противоречием, следует из свойств 1,2. Доказательство единственности проводится методом от противного.

Можно дать следующее определение СКНФ, СДНФ:

Определение 20. Конъюнктивная (дизъюнктивная) НФ называется совершенной, если выполняются условия:

1) каждая переменная из полного набора содержится во всех элементарных дизъюнкциях (конъюнкциях) ровно один раз с отрицанием или без;

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

Совершенные нормальные формы позволяют дать критерий равносильности двух произвольных формул f и . Каковы бы ни были формулы f и , можно предположить, что они содержат одни и те же переменные. Если, например, формула f не содержит переменной , то можно ее заменить равносильной формулой:

.

Любые две формулы можно заменить равносильными им формулами, содержащими одинаковые переменные. Эти формулы надо привести к СКНФ или СДНФ.

Если формулы f и равносильны, то в силу единственности СНФ должны совпадать. Таким образом, сравнение СНФ формул f и решает вопрос об их равносильности.

Построение СДНФ, СКНФ на основе таблиц истинности

СДНФ: На основе 5-ого пункта процедуры приведения к СДНФ слагаемые, равные 0, отбрасываются, то есть в СДНФ входят слагаемые, соответствующие наборам переменных, при которых формула имеет значение 1. Следовательно, можно предложить следующую процедуру получения СДНФ:

1) По каждому набору переменных, при которых формула принимает значение 1, составить элементарные конъюнкции;

2) В эти элементарные конъюнкции записать без инверсии переменные, заданные 1 в наборе, и с инверсией – переменные, заданные 0;

3) Соединить элементарные конъюнкции знаком дизъюнкции.

Процедура получения СКНФ:

1) По каждому набору переменных, при которых формула принимает значение 0, составить элементарные дизъюнкции;

2) В элементарные дизъюнкции записать без инверсии переменные, заданные 0 в наборе, и с инверсией – переменные, заданные 1;

3) Элементарные дизъюнкции соединить знаком конъюнкции.

Пример. Привести к СДНФ, СКНФ с помощью таблицы истинности

;

 

x	y	z		СДНФ	СКНФ

 

СДНФ: f = ;

СКНФ: f = .

 

Другое определение совершенных

нормальных форм

Замечание 11. Определения 18, 20 можно объединить.

ДО или КО называется совершенным, если в нем каждая переменная встречается один раз с отрицанием или без отрицания.

СДО:

СКО:

Определение 21. КНФ (ДНФ) называется совершенной, если в ней все ДО (КО) являются совершенными.

1.5. Логическое следование

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

Если формула G является логическим следствием формулы F, то используется обозначение ├ .

Теорема 6. ├ ╞ .

Доказательство следует непосредственно из определений.

Определение 23. Формула G называется логическим след­ствием формул , если для любых конкретных высказыва­ний из одновременной истинности формул следует истинность формулы .

Если G является логическим следствием , то это обстоятельство обозначается через ├ . Формулы называются посылками, a G – следствием этих посылок.

Теорема 7. Следующие утверждения

1) ├ ,

2) ├ ,

3) ╞

являются равносильными.

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

1. Даны посылки . Требуется найти все возможные следствия из этих посылок.

2. Дано следствие, то есть формула G, найти все возможные посылки, из которых G является следствием.

Сформулированные задачи можно решить, используя таблицы истинности заданных формул. При решении прямой задачи строим таблицы истинности для формул и отмечаем в таблице все строки, в которых одновременно истинны. Очевидно, поскольку искомые G должны быть следствиями посылок , то G в отмеченных строках обязаны принимать значение 1, а в остальных какие угодно значения. Перебирая все возможные варианты значений в неотмеченных строках, мы получим все иско­мые следствия.

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

Х 1 Х 2	F 1	F 2	G 1	G 2	G 3	G 4
0 0
0 1
1 0
1 1

Пусть наоборот дано следствие G. Требуется найти все воз­можные посылки, из которых следует G. При решении обратной за­дачи строим таблицу истинности G и отмечаем строки, в которых G ложно, то есть принимает значение 0. Очевидно, если G является след­ствием некоторой посылки F, то F в отмеченных строках обязана принимать значение 0. В остальных строках F может принимать лю­бые значения. Посредством перебора всех вариантов значений F в неотмеченных строках построим все возможные посылки для G.

Пример. Пусть таблица истинности для следствия задана. Представленная ниже таблица отражает описанный процесс нахождения всех возможных посылок для G.

Х 1 Х 2	G	F 1	F 2	F 3	F 4
0 0
0 1
1 0
1 1

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

Теорема 8. Для того чтобы формула G, не являющаяся тавтологией, была логическим следствием формул , из которых, по крайней мере, одна не является тавтологией, необходимо и достаточно, чтобы в СКНФ формулы G все дизъюнк­тивные одночлены были из СКНФ формулы .

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

Очевидно, для решения прямой задачи, то есть для нахождения всех возможных следствий из посылок необходимо по­строить СКНФ формулы и затем из ее дизъюнктивных одночленов построить всевозможные их конъюнкции, которые и будут искомыми следствиями. Очевид­но, число таких следствий будет , то есть число подмножеств без единицы из множества .

При решении обратной задачи строим СКНФ для заданной формулы следствия .

Поскольку общее число совершенных дизъюнктивных од­ночленов от n переменных равно , то, добавляя к имеющимся в СКНФ дизъюнктивным одночленам все­возможные подмножества дизъюнктивных одночленов из множества остальных дизъюнктивных одночленов, мы получим таким об­разом все искомые посылки.

1.6. Правила вывода

Если в процессе дедуктивного рассуждения некоторое ут­верждение G выводится из утверждений , то говорят, что справедливо правило вывода

.

Это равносильно тому, что ├ .

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

	– правило заключения (modus pones, MP);
	– правило цепного заключения;
	– закон контрапозиции;
	– правила разъединения и объединения посылок;
	– законы Моргана;
	– правило сведения к абсурду;
	– правила удаления и введения конъюнкции.

Пример. Проверить правильность умозаключения: "Если формула является выполнимой, то она является тавтологией или не является противоречием. Если формула – тавтология, то она не является противоречием. Следовательно, если формула выполнимая, то она не является противоречием".

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

"Формула является выполнимой" – А, "Формула является тавтологией" – В, "Формула является противоречием" – С. Тогда наши рассуждения выглядят следующим образом:

.

 

A B C
0 0 0		1	1
0 0 1		1	1
0 1 0		1	1
0 1 1
1 0 0		1	1
1 0 1
1 1 0		1	1
1 1 1

 

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

Упражнения

1. Пусть А и В обозначают соответственно "Сергей – студент" и "Юра – студент". Записать приведенные ниже высказывания в символической форме, то есть используя только обозначения для высказываний (А, В), символы , , Ú, ®, «:

а) "Сергей – студент" и "Юра не студент";

б) "Юра – студент", а "Сергей не студент";

в) "Юра и Сергей оба не студенты";

г) "Ни Юра, ни Сергей не студенты";

д) "Либо Юра, либо Сергей студент";

е) "Неверно, что Юра и Сергей оба студенты";

ж) "Если Юра студент, то Сергей не студент";

з) "Сергей студент тогда и только тогда, когда Юра студент".

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

a) ; б) ;

в) ; г) ;

д) ; e) ;

ж) ; з) .

3. Построить таблицы истинности для формул и определить тип формулы:

a) ; б) ;

в) ; г) .

4. Для следующих формул найти равносильные им ДНФ:

a) ; б) ;

в) ; г) ;

д) ; е) ;

ж) ; з) .

5. Для следующих формул найти равносильные им КНФ:

a) ;

б) ;

в) ;

г) .

6. Определить, являются ли заданные формулы выполнимыми:

a) ; б) ;

в) ; г) .

7. Найти совершенные ДНФ и КНФ для формул:

a) ; б) ;

в) ; г) ;

д) ; е) .

8. Для следующих формул найти все вытекающие из них следствия.

a) ; б) ;

в) ; г) .

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

а) Если 6 – составное число, то 12 – составное число; если 12 – составное число, то существует простое число, большее 12; если существует простое число большее 12, то существует составное число большее 12; если 6 делится на 2, то 6 – составное число; число 12 – составное. Следовательно, 6 – составное число.

б) Если число a делится на 8, то оно делится на 4 и если число a делится на 9, то оно делится на 3; если число a делится на 3 и на 8, то оно делится на 24; число a не делится на 24. Следовательно, число a не делится на 4 или не делится на 3.