Элементы математической логики. Нормальные виды формул. Совершенные нормальные формы, страница 3

4) Элементарные конъюнкции объединяются дизъюнкцией.

Пример:


л	л	л	л	и	и	и
л	л	и	и	л	и	л
л	и	л	л	и	и	и
и	л	л	и	л	л	л
л	и	и	и	л	и	л
и	л	и	и	л	л	л
и	и	л	и	л	и	л
и	и	и	и	л	и	л

- СДНФ

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

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

1) Составить таблицу истинности

2) Выделяется строки, в которых формула принимает значение «ложь»

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

4) Элементарные дизъюнкции объединяются конъюнкцией.

Пример:


л	л	л	л	и	и	и
л	л	и	и	л	и	л
л	и	л	л	и	и	и
и	л	л	и	л	л	л
л	и	и	и	л	и	л
и	л	и	и	л	л	л
и	и	л	и	л	и	л
и	и	и	и	л	и	л

- СКНФ

Булевы функции

Определение: Булевой функцией называется произвольная функция n-переменных из множества {0,1} в множество {0,1}.

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

Табличный способ задания

						эл. конъюнкции
1	1	1	1	0	1
1	1	0	0	1	0
1	0	1	0	1	1
1	0	0	1	0	0
0	1	1	1	0	0
0	1	0	0	1	1
0	0	1	1	0	1
0	0	0	0	1	0

Определение: Инверсией называется замена «1» на «0», а «0» на «1».

Определение: Функция , равная называется двойственной к функции .

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

Всего булевых функций от двух переменных 16:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Скачать файл


л	л	л	л	и	и	и
л	л	и	и	л	и	л
л	и	л	л	и	и	и
и	л	л	и	л	л	л
л	и	и	и	л	и	л
и	л	и	и	л	л	л
и	и	л	и	л	и	л
и	и	и	и	л	и	л


л	л	л	л	и	и	и
л	л	и	и	л	и	л
л	и	л	л	и	и	и
и	л	л	и	л	л	л
л	и	и	и	л	и	л
и	л	и	и	л	л	л
и	и	л	и	л	и	л
и	и	и	и	л	и	л


л	л	л	л	и	и	и
л	л	и	и	л	и	л
л	и	л	л	и	и	и
и	л	л	и	л	л	л
л	и	и	и	л	и	л
и	л	и	и	л	л	л
и	и	л	и	л	и	л
и	и	и	и	л	и	л


л	л	л	л	и	и	и
л	л	и	и	л	и	л
л	и	л	л	и	и	и
и	л	л	и	л	л	л
л	и	и	и	л	и	л
и	л	и	и	л	л	л
и	и	л	и	л	и	л
и	и	и	и	л	и	л


л	л	л	л	и	и	и
л	л	и	и	л	и	л
л	и	л	л	и	и	и
и	л	л	и	л	л	л
л	и	и	и	л	и	л
и	л	и	и	л	л	л
и	и	л	и	л	и	л
и	и	и	и	л	и	л


л	л	л	л	и	и	и
л	л	и	и	л	и	л
л	и	л	л	и	и	и
и	л	л	и	л	л	л
л	и	и	и	л	и	л
и	л	и	и	л	л	л
и	и	л	и	л	и	л
и	и	и	и	л	и	л