Формулы алгебры высказываний

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

Формулой алгебры высказываний (формулой) называется

1) любое высказывание (высказывательное переменное);

2) если и – формулы, то , , , , – тоже формулы;

3) кроме формул приведенных в п.п 1) и 2) других формул в алгебре высказываний нет.

Если формула образована, например, из формул (переменных) , и , то используем следующую запись: .

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

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

Формула называется противоречием (тождественно ложной), если она принимает только ложное значение на всех наборах значений входящих в неё переменных.

Формула называется выполнимой, если она не является ни тавтологией и ни противоречием.

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

Основные тавтологии

Приведем перечень равносильных формул и названий некоторых из них:

1. – коммутативность дизъюнкции;

2. – коммутативность конъюнкции;

3. – ассоциативность дизъюнкции;

4. – ассоциативность конъюнкции;

5. – дистрибутивность дизъюнкции относительно конъюнкции;

6. – дистрибутивность конъюнкции относительно дизъюнкции;

7. – идемпотентность дизъюнкции;

8. – идемпотентность конъюнкции;

9. – первый закон поглощения;

10. – второй закон поглощения;

11. ;

12. ;

13. ;

14. ;

15. – первый закон де Моргана;

16. – второй закон де Моргана;

17. – закон исключённого третьего;

18. – закон противоречия;

19. – первая формула расщепления;

20. – вторая формула расщепления;

21. – закон снятия дойного отрицания;

22. – формула, представляющая импликацию через отрицание и дизъюнкцию;

23. – формула, представляющая импликацию через отрицание и конъюнкцию;

24. – формула, представляющая эквиваленцию через импликацию и конъюнкцию;

25. – первая формула, представляющая эквиваленцию через отрицание, дизъюнкцию и конъюнкцию;

25. – вторая формула, представляющая эквиваленцию через отрицание, дизъюнкцию и конъюнкцию.

Приведем две равносильные формулы, используемые в разделе ДНФ и КНФ:

26. – первое правило Блейка;

27. – второе правило Блейка.

Справедливость этих равносильных формул можно проверить построив их таблиц истинности.

Если в этих равносильных формулах символ заменить символом , то получаются тавтологии, называемые основными.

Нормальные формы

Пусть

(*)

– высказывательные переменные.

Элементарной дизъюнкцией (ЭД)называется дизъюнкции любых переменных из (*) или их отрицания . Например, если и набор (*) имеет вид , то – элементарные дизъюнкции. Если в элементарной дизъюнкции участвует все переменные из (*) (либо сама, либо её отрицание), то она называется полной элементарной дизъюнкцией (ПЭД). Например, в случае , перечислим всех полных элементарных дизъюнкций: , , , , , , , .

Элементарной конъюнкцией (ЭК)называется конъюнкции любых переменных из (*) или их отрицания . Например, если и набор (*) имеет вид , то – элементарные конъюнкции. Если в элементарной конъюнкции участвует все переменные из (*) (либо сама, либо её отрицание), то она называется полной элементарной конъюнкцией (ПЭК). Например, в случае , перечислим всех полных элементарных конъюнкций: , , , , , , , .

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

(ЭК)Ú (ЭК)Ú (ЭК)Ú … .

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

(ПЭК)Ú (ПЭК)Ú (ПЭК)Ú … .

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

(ЭД)Ú (ЭД)Ú (ЭД)Ú … .

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

(ПЭД)Ú (ПЭД)Ú (ПЭД)Ú … .

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

Функции алгебры логики

Функцией алгебры логики переменных (функцией Буляили булевой функцией) называется функция переменных

,

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

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

Рассмотрим таблицу истинности всех различных булевых функций одной переменной:

Из таблицы следует, что эти функции можно представить как формулы исчисления высказываний:

.

Таблица истинности всех различных булевых функций двух переменных имеет вид:

Этим функциям соответствуют следующие формулы исчисления высказываний:

,

Каждой булевой функции можно сопоставить формулу алгебры высказываний. С этой целью введем обозначение

Следующий факт для булевой функции с любым количеством переменных. Приведем его для функции двух переменных.

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

.

Для краткости записи опустим символ конъюнкции: вместо будем писать :

.

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

Полагая , , , функцию можно представить следующим образом:

.

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

Многочлен Жегалкина

Операция арифметического умножения нами введена. Введем новую логическую операцию, называемую сложением по модулю 2. Сложение по модулю 2 обозначается . Она определяется как отрицание эквиваленции переменных и :

.

Таблица значений сложения по модулю 2 имеет вид

Отметим некоторые свойства сложения по модулю 2:

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

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

.

Примеры.

– многочлен Жегалкина первой степени;

– многочлен Жегалкина второй степени;

– многочлен Жегалкина второй степени.

При построении многочлена Жегалкина полезно использовать следующие преобразования:

.

Содержание

• ⇐ Назад
• 12