Определение 1. Формула вида (соответственно, вида ), где все фигурирующие в ней переменные попарно различны, называется элементарной конъюнкцией (соответственно, элементарной дизъюнкцией); – любой из литералов – x или .
Примеры: а) – элементарная дизъюнкция;
б) – элементарная конъюнкция.
Определение 2. Дизъюнктивная нормальная форма (ДНФ) – это формула вида ... , где , i = – элементарная конъюнкция, содержащая некоторые из литералов ,..., . В том случае, когда в каждую конъюнкцию для каждого номера j = входит в точности один из литералов , ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).
Теорема 1.5.1. Любая булева функция, отличная от константы 0 (соответственно, от константы 1) представима в виде СДНФ (соответственно, в виде СКНФ):
а) (,..., )СДНФ= ;
|
|
Алгоритм перехода от табличного задания
Булевой функции к СДНФ.
1. В таблице выбрать все конституенты единицы, т.е. те наборы =< > значений переменных ,..., , на которых =1.
|
|
2. Каждому набору поставить в соответствие элементарную конъюнкцию = .
3. Все полученные элементарные конъюнкции логически сложить, т.е. искомая СДНФ для заданной функции будет:
(,..., )СДНФ=
С использованием принципа двойственности для булевых алгебр определяется конъюнктивная нормальная форма (КНФ) и совершенная конъюнктивная нормальная форма (СКНФ).
Алгоритм перехода от табличного значения
Булевой функции к СКНФ.
1. В таблице выбрать все конституенты нуля, т.е. те наборы =< > значений переменных ,..., , на которых =0.
2. Каждому набору поставить в соответствие элементарную дизъюнкцию = .
3. Все полученные элементарные дизъюнкции логически умножить, т.е. искомая СКНФ для заданной функции будет:
(,..., )СКНФ= .
Пример 1. Построить СДНФ и СКНФ булевой функции, заданной таблицей 1.5.1.
Таблица 1.5.1 | ||||||
№ | x 1 | x 2 | x 3 | f (x 1, x 2, x 3) | Конституенты 1 | Конституенты 0 |
0 | 0 | 0 | 0 | 1 | x 1 x 2 x 3 | |
1 | 0 | 0 | 1 | 0 | x 1Ú x 2Ú x 3 | |
2 | 0 | 1 | 0 | 1 | x 1 x 2 x 3 | |
3 | 0 | 1 | 1 | 0 | x 1Ú x 2Ú x 3 | |
4 | 1 | 0 | 0 | 0 | x 1Ú x 2Ú x 3 | |
5 | 1 | 0 | 1 | 1 | x 1 x 2 x 3 | |
6 | 1 | 1 | 0 | 0 | x 1Ú x 2Ú x 3 | |
7 | 1 | 1 | 1 | 1 | x 1 x 2 x 3 |
(, , )СДНФ=
(, , )СКНФ=()()()()