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

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 6Следующая ⇒

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

Примеры: а)  – элементарная дизъюнкция;

                     б)  – элементарная конъюнкция.

Определение 2. Дизъюнктивная нормальная форма (ДНФ) – это формула вида ... , где , i =  – элементарная конъюнкция, содержащая некоторые из литералов ,..., . В том случае, когда в каждую конъюнкцию  для каждого номера j =  входит в точности один из литералов , ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).

Теорема 1.5.1. Любая булева функция, отличная от константы 0 (соответственно, от константы 1) представима в виде СДНФ (соответственно, в виде СКНФ):

а) (,..., )_СДНФ= ;

б) (,..., )_СКНФ= ,

где =                         i =

Алгоритм перехода от табличного задания

Булевой функции к СДНФ.

1. В таблице выбрать все конституенты единицы, т.е. те наборы =< > значений переменных ,..., , на которых =1.

2. Каждому набору  поставить в соответствие элементарную конъюнкцию = .

3. Все полученные элементарные конъюнкции логически сложить, т.е. искомая СДНФ для заданной функции будет:

(,..., )_СДНФ=

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

Алгоритм перехода от табличного значения

Булевой функции к СКНФ.

1. В таблице выбрать все конституенты нуля, т.е. те наборы =< > значений переменных ,..., , на которых =0.

2. Каждому набору  поставить в соответствие элементарную дизъюнкцию = .

3. Все полученные элементарные дизъюнкции логически умножить, т.е. искомая СКНФ для заданной функции будет:

(,..., )_СКНФ= .

Пример 1. Построить СДНФ и СКНФ булевой функции, заданной таблицей 1.5.1.

Таблица 1.5.1