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

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

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

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

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

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

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

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

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

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

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

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

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

Главные тавтологии

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

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

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

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

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

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

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

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

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

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

10. – 2-ой закон поглощения;

11. ;

12. ;

13. ;

14. ;

15. – 1-ый закон де Формулы алгебры высказываний Моргана;

16. – 2-ой закон де Моргана;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обычные формы

Пусть

(*)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

.

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

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

,

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

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

Случайная булева функция 2-ух переменных представима в виде:

.

Ради сокращенности записи опустим знак конъюнкции: заместо будем писать :

.

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

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

.

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

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

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

.

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

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

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

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

.

Примеры.

– многочлен Жегалкина первой степени Формулы алгебры высказываний;

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

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

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

.


Содержание

Правила выполнения и дизайна контрольных работ………….
Задания для контрольных работ……………………………………..
Задание № 1………………………………………………...
Задание № 2………………………………………………...
Задание № 3………………………………………………...
Задание № 4………………………………………………...
Задание № 5………………………………………………...
Задание № 6………………………………………………...
Задание № 7………………………………………………...
Задание № 8………………………………………………...
Эталоны решения и дизайна заданий…………………………..
Задание № 1………………………………………………...
Задание № 2………………………………………………...
Задание № 3………………………………………………...
Задание № 4………………………………………………...
Задание № 5………………………………………………...
Задание № 6………………………………………………...
Задание № 7………………………………………………...
Задание № 8………………………………………………...
Лаконичный теоретический материал……….…………………………..
1. Главные Формулы алгебры высказываний понятия теории множеств…………………..
2. Операции над огромными количествами……………………………
3. Бинарное отношение……………………………………
4. Деяния над высказываниями…………………………
5. Формулы алгебры выражений………………………
6. Главные тавтологии…………………………………...
7. Обычные формы……………………………………..
8. Функции алгебры выражений……………………….
9. Многочлен Жегалкина…………………………………..




fotografii-sostoyaniya-doma-po-adresu-ul-oboronnaya-d6.html
fotografiya-dlya-nachinayushih.html
fotografiya-pokazavshaya-chto-i-u-geniev-est-chuvstvo-yumora-ejnshtejn-pokazivayushij-yazik-artur-sejss-1951.html