дизъюнктивные и конъюнктивные нормальные формы алгебры

Дизъюнктивные и конъюнктивные нормальные формы

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

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

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

Согласно принципу двойственности, СКНФ для той же функции будет иметь вид

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

Рассмотрим в качестве примера построение СДНФ и СКНФ для мажоритарной функции. Конституентами единицы для нее служат наборы:

Им соответствуют элементарные конъюнкции:

Тогда СДНФ, представляющая мажоритарную функцию, имеет вид

Для получения СКНФ для той же функции выпишем все конституенты нуля данной функции:

Сопоставим им элементарные дизъюнкции:

В результате получим СКНФ для мажоритарной функции в виде

Заметим, что если в формуле СКНФ (6.10) мы раскроем скобки и преобразуем полученное выражение согласно законам булевой алгебры, проведя тем самым эквивалентные преобразования СКНФ, то придем к формуле СДНФ (6.9).

Источник

Определение 2.2. Формула, в которую входят только операции конъюнкции, дизъюнкции и отрицания, причем операция отрицания относится непосредственно к высказывательным переменным, называетсяприведенной.

1) — является приведенной;

2) — не является приведенной, так как содержит операцию импликации;

3) — не является приведенной, так как операция отрицания отнесена к формуле, а не к высказывательной переменной.

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

Пусть задана система высказывательных переменных (1).

Определение 2.3. Элементарной дизъюнкциейвысказывательных переменных из системы (1) называется дизъюнкция некоторых переменных этой системы или их отрицаний.

Определение 2.4. Элементарной конъюнкциейназывается конъюнкция некоторых переменных этой системы или их отрицаний.

1) Пусть задана система . Формулыявляются элементарными дизъюнкциями; первые две из них – одночленными.

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

Теорема 2.1. Элементарная дизъюнкция (элементарная конъюнкция) является тождественно истинной (тождественно явной) тогда и только тогда, когда она наряду с некоторой высказывательной переменнойсодержит отрицание этой переменной.

Доказательство.(э. стр. 37).

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

ДНФ можно записать в виде , где каждое— элементарная дизъюнкция.

Например: ;– являются ДНФ.

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

Например: – является КНФ.

Теорема 2.2. КНФ (ДНФ) является тождественно истинной (тождественно ложной) тогда и только тогда, когда каждая составляющая её элементарная дизъюнкция (элементарная конъюнкция) содержит некоторую высказывательную переменнуювместе с ее отрицанием.

Доказательствовытекает из Т. 2.1.

Теорема 2.3. Для любой формулы алгебры высказываний существует эквивалентная ей КНФ (ДНФ).

Доказательствопроведем для случая КНФ. Пусть задана формула А. Вначале получим для данной формулы А эквивалентную ей приведенную формулу В. Применяя к В дистрибутивный закон, получим КНФ.

Схема приведения формулы к КНФ и ДНФ:

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

1) Приведите к конъюнктивной нормальной форме (КНФ) .

. Заменим в приве-денной формулена,наи раскроем скобки:.

Сделав обратную замену, получим КНФ формулы А:

.

2) Привести к ДНФ формулу .

– приведенная формула.

Заменим в приведенной формуле на,наи раскроем скобки:

.

Сделав обратную замену, получим ДНФ формулы А:.

Определение 2.7.Элементарная конъюнкция (дизъюнкция) называется полной, если каждая переменная входит в нее один и только один раз.

Пусть задана система переменных .,являются, а,– полными элементарными конъюнкциями.

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

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

Пусть задана система переменных .

Формула – СКНФ, а– СДНФ.

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

Доказательство: (э. стр.40).

Алгоритм получения СДНФ:

1. Для формулы Аполучаем любую ДНФ.

2. Если в ДНФ есть слагаемое, не содержащее , то заменяем.

3. Если в ДНФ два одинаковых слагаемых В, то лишнее можно отбросить, так как.

4. Если в некоторое слагаемое ВДНФАвходит дважды, то лишнююможно отбросить, так как.

5. Если слагаемое Вв ДНФАсодержит конъюнкцию, тои, и это слагаемое можно отбросить.

Например: привести к СДНФ формулу .

Алгоритм получения СКНФ путем равносильных преобразований похож на алгоритм получения СДНФ:

1. Для формулы Аполучаем любую КНФ.

2. Если элементарная дизъюнкция В, входящая в КНФ, не содержит, то.

3. если в некоторую элементарную дизъюнкцию Ввходит дважды, то лишнюю переменнуюможно отбросить, так как.

4. Если КНФ содержит два одинаковых сомножителя В, то лишнюю элементарную дизъюнкцию можно отбросить, так как.

5. Если в элементарную дизъюнкцию Ввходит пара, то ее можно отбросить, так как, а.

Например: привести к СКНФ .

Если же будет задана таблица истинности формулы, то алгоритм построения СДНФ следующий:

1. В таблице истинности отмечаем наборы переменных, для которых значение формулы равно 1.

2. Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если , то конъюнкция включает саму переменную, а противном случае – ее отрицание.

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

Например: Задана таблица истинности функции .

Источник

2.5. Дизъюнктивные и конъюнктивные нормальные формы булевых функций

Определение 1. Конъюнктивным одночленом (элементарной конъюнкцией) от переменных называется конъюнкция этих переменных или их отрицаний.

Например, – элементарная конъюнкция.

Определение 2. Дизъюнктивным одночленом (элементарной дизъюнкцией) от переменных называется дизъюнкция этих переменных или их отрицаний.

Например, – элементарнаядизъюнкция.

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

Например, – ДНФ.

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

Например, – КНФ.

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

Алгоритм построения нормальных форм

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

;

;

.

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

; .

Избавиться от знаков двойного отрицания.

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

2.6. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы

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

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

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

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

ДНФ не содержит двух одинаковых конъюнкций;

ни одна конъюнкция не содержит одновременно двух одинаковых переменных;

ни одна конъюнкция не содержит одновременно некоторую переменную и ее отрицание;

каждая конъюнкция содержит либо переменную , либо ее отрицаниедля всех переменных, входящих в формулу.

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

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

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

КНФ не содержит двух одинаковых дизъюнкций.

Ни одна конъюнкция не содержит одновременно двух одинаковых переменных.

Ни одна из дизъюнкций не содержит одновременно некоторую переменную и ее отрицание.

Каждая дизъюнкция СКНФ содержит либо переменную , либо ее отрицаниедля всех переменных, входящих в формулу.

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

Способы нахождения СДНФ

1-й способ – с помощью равносильных преобразований:

получаем одну из ДНФ;

если в полученной ДНФ входящая в нее элементарная конъюнкция не содержит переменную, то используем равносильностьи получаем две элементарных конъюнкции;

если в ДНФ входят две элементарные конъюнкции, то лишнюю можно отбросить.

2-й способ – с помощью таблиц истинности:

выделяем строки, где формула принимает значение 1;

составляем дизъюнкцию конъюнкций при условии, что если переменная входит в конъюнкцию со значением 1, то записываем эту переменную, если со значением 0, то ее отрицание. Получаем СДНФ.

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

Способы нахождения СКНФ

1-й способ – с помощью равносильных преобразований:

получаем одну из КНФ;

если в полученной КНФ входящая в нее элементарная дизъюнкция не содержит переменную, то используем равносильностьи получаем две элементарных дизъюнкции;

если в КНФ входят две элементарные дизъюнкции, то лишнюю можно отбросить.

2-й способ – с помощью таблиц истинности:

выделяем строки, где формула принимает значение 0;

составляем конъюнкцию дизъюнкций при условии, что если переменная входит в дизъюнкцию со значением 0, то записываем эту переменную, если со значением 1, то ее отрицание. Получаем СКНФ.

Пример 1. Постройте КНФ функции .

Исключим связку «» с помощью законов преобразования переменных:

= /законы де Моргана и двойного отрицания/ =

/дистрибутивные законы/ =

.

Пример 2. Приведите к ДНФ формулу .

Выразим логические операции ичерез,и:

= /отнесем отрицание к переменным и сократим двойные отрицания/ =

= /закон дистрибутивности/ .

Пример 3. Запишите формулу в ДНФ и СДНФ.

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

Для построения СДНФ составим таблицу истинности для данной формулы:

Источник