Разработка технологий повторения темы Логика высказываний (стр. 4 из 24)

1)

2)

3)

4)

5)

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

Две формулы А и В будем называть равносильными (А=В или

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

Пример:

x	y
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

В логике высказываний будем считать, что равносильные формулы задают одно и то же высказывание. Может оказаться, что в последнем столбце таблицы истинности стоят одни единицы или нули. Будем называть такое высказывание тождественно-истинным (тавтологией) соответственно тождественно-ложным (противоречием) и обозначать 1 и 0. Из определения следует, что для проверки равносильности формул нужно построить их таблицы истинности и сравнить

Пример:

Формулы

и являются тождественно-истинными

х		у
1		1		1	1
1		0		1	1
0		1		0	1
0		0		1	1
1	0		1
1	0		1
0	1		1
0	1		1

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

Свойства конъюнкции и дизъюнкции

1. Коммутативные (переместительные) законы

2. Ассоциативные (сочетательные) законы

3. Дистрибутивные (распределительные) законы

4. Законы поглощения

5. Законы склеивания

Свойства с отрицанием

1. Законы Де Моргана

2. Закон двойного отрицания

;

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

;

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

.

Свойства с логическими константами

1.

, ;

2.

3.

4.

Связь между логическими операциями

1.

;

2.

, ;

3.

, ;

4.

;

5.

1.2.2 Нормальные формы. Совершенные нормальные формы

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

Примеры элементарных конъюнкций

.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) и выглядит следующим образом:

где

и - различные элементарные конъюнкций.

Примеры ДНФ:

Алгоритм приведения к ДНФ может быть описан с привлечением приведенных выше равносильностей:

1. Используя закон двойного отрицания и законы Де Моргана все отрицания "спускаются" до переменных;

2. Раскрываются скобки по распределительному закону;

3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние конъюнкции и повторение переменных;

4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.

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

Примеры элементарных дизъюнкций:

Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) и выглядит следующим образом:

где

и - различные элементарные дизъюнкции.

Примеры КНФ:

Алгоритм приведения к КНФ может быть описан с помощью тех же соотношений и законов, которые использовались и в алгоритме для ДНФ.

1. Используя закон двойного отрицания и законы Де Моргана все отрицания "спускаются" до переменных;

2. Раскрываются скобки по распределительному закону;

3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние дизъюнкции и повторения переменных;

4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.

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

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

Замечание: Обратим внимание, что одно определение получается из другого заменой друг другом слов «слагаемое» и «сомножитель».

Примеры

— СДНФ некоторой формулы двух переменных

- СКНФ функции трех переменных

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

Опишем два способа приведения к совершенным нормальным формам.

1-Й СПОСОБ — АНАЛИТИЧЕСКИЙ

Алгоритм приведение к СДНФ:

1.Приводят к ДНФ с помощью равносильных преобразований;

2. Умножают на единицы, представленные в виде дизъюнкций каждой недостающей переменной, с ее отрицанием;

3.Раскрывают скобки — по первому распределительному закону;

4.Исключают повторения слагаемых.

Пример: