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

Например, является простой конъюнкцией,

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

Например, выражение является ДНФ.

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

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

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

Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных , при этом каждая переменная входит не более одного раза (либо сама , либо ее отрицание ).Например, выражение - простая дизъюнкция,

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

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

Например, выражение является СКНФ.

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

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;

в) сокращение ДНФ (или СДНФ) по правилу Блейка

Применение этого правила состоит из двух частей:

Если среди дизъюнктных слагаемых в ДНФ имеются слагаемые , то ко всей дизъюнкции добавляем слагаемое К 1 К 2 . Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;

Если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

или

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z , вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

г) переход от КНФ к СКНФ

Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z , то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

Таким образом, из КНФ получена СКНФ.

Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.

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

Энциклопедичный YouTube

• 1 / 5

  Формулы в КНФ :

  ¬ A ∧ (B ∨ C) , {\displaystyle \neg A\wedge (B\vee C),} (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , {\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E),} A ∧ B . {\displaystyle A\wedge B.}

  Формулы не в КНФ :

  ¬ (B ∨ C) , {\displaystyle \neg (B\vee C),} (A ∧ B) ∨ C , {\displaystyle (A\wedge B)\vee C,} A ∧ (B ∨ (D ∧ E)) . {\displaystyle A\wedge (B\vee (D\wedge E)).}

  Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:

  ¬ B ∧ ¬ C , {\displaystyle \neg B\wedge \neg C,} (A ∨ C) ∧ (B ∨ C) , {\displaystyle (A\vee C)\wedge (B\vee C),} A ∧ (B ∨ D) ∧ (B ∨ E) . {\displaystyle A\wedge (B\vee D)\wedge (B\vee E).}

  Построение КНФ

  Алгоритм построения КНФ

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

  A → B = ¬ A ∨ B , {\displaystyle A\rightarrow B=\neg A\vee B,} A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . {\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).}

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

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , {\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,} ¬ (A ∧ B) = ¬ A ∨ ¬ B . {\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.}

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

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

  Пример построения КНФ

  Приведем к КНФ формулу

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . {\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).}

  Преобразуем формулу F {\displaystyle F} к формуле, не содержащей → {\displaystyle \rightarrow } :

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X) . {\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \neg Y\vee Z)\vee \neg X).}

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

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . {\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).}

  Например, следующая формула записана в 2-КНФ:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . {\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).}

  Определение 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. Запишите формулу в ДНФ и СДНФ.

  Решение

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

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

  Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение 1. Для каждой такой строки выпишем формулу, истинную на наборе переменных ,,данной строки:

  строка 1: ;

  строка 3: ;

  строка 5: .

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

  Пример 4. Приведите формулу к СКНФ двумя способами:

  а) с помощью равносильных преобразований;

  б) с помощью таблицы истинности.

  Решение:

  Преобразуем вторую элементарную дизъюнкцию:

  Формула имеет вид:

  б) составим таблицу истинности для данной формулы:

  Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение 0. Для каждой такой строки выпишем формулу, истинную на наборе переменных ,,данной строки:

  строка 2: ;

  строка 6: .

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

  Вопросы и задачи для самостоятельного решения

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

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

  3. С помощью второго дистрибутивного закона преобразуйте ДНФ в КНФ:

  а) ;

  4. Преобразуйте заданные ДНФ в СДНФ:

  5. Преобразуйте заданные КНФ в СКНФ:

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

  б) ;

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

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

  одного раза.

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

  Элементарными дизъюнкциями (дизъюнктами) называются дизъюнкции переменных с отрицаниями или без них.

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

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

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

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

  2. Перейти к формулам с тесными отрицаниями, то есть к формуле, в которой отрицания располагаются не выше, чем над переменными – применить законы де Моргана.

  3. Раскрыть скобки – применить законы дистрибутивности.

  4. Повторяющиеся слагаемые взять по одному разу – закон идемпотентности.

  5. Применить законы поглощения и полупоглощения.

  Пример 6. Найти ДНФ формулы: .

  В алгебре Буля справедлив принцип двойственности . Он заключается в следующем.

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

  Пример 7. Найти функцию, двойственную к .

  Среди элементарных функций алгебры логики 1 двойственна 0 и наоборот, х двойственна х, двойственна , двойственна и наоборот.

  Если в формуле F 1 представляющей функцию все конъюнкции заменить

  на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу F * , представляющую функцию * , двойственную .

  Конъюнктивная нормальная форма (КНФ) – двойственное для ДНФ понятие, поэтому ее легко построить по схеме:

  Пример 8. Найти КНФ формулы: .

  Воспользовавшись результатом примера 6, имеем

  Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы. В каждом из типов нормальных форм (дизъюнктивных и конъюнктивных) можно выделить класс совершенных форм СДНФ и СКНФ.

  Совершенной элементарной конъюнкцией называется логическое произведение всех переменных с отрицанием или без них, причем, каждая переменная входит в произведение только один раз.

  Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, т.е. добавлением для отсутствующей переменной x i множится с применением закона дистрибутивности

  Пример 9. Найти СДНФ для ДНФ примера 6

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

  Всякую КНФ можно привести к СКНФ, добавляя член конъюнкции, не содержащий какой – либо переменной X i конъюнкцией и применяя дистрибутивный закон

  Пример 10 . Привести КНФ к СКНФ:

  Для построения СКНФ можно воспользоваться схемой

  Пример 11. Найти СКНФ для формулы примера 6.

  Всякая функция имеет СДНФ и, притом, единственную . Каждая функция имеет СКНФ и, притом, единственную .

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

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

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

  Пример 12. Найти СДНФ и СКНФ по таблице истинности для формулы примера 6.

  В таблице 14 приведено лишь конечное значение F=10101101. В справедливости этого утверждения следует убедиться самостоятельно, построив развернутую таблицу истинности.

  Таблица 14

  x	y	z

  Введем понятие элементарной дизъюнкции.

  Элементарной дизъюнкцией называется выражение вида

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

  представляют собой конъюнкции элементарных дизъюнкций. Следовательно, они записаны в конъюнктивной нормальной форме.

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

  Использования правила инверсии, если операция отрицания применена к логическому выражению;

  Использования аксиомы дистрибутивности относительно умножения:

  Использования операции поглощения:

  Исключения в дизъюнкциях повторяющихся переменных или их отрицаний;

  Удаления всех одинаковых элементарных дизъюнкций, кроме одной;

  Удаления всех дизъюнкций, в которые одновременно входят переменная и ее отрицание.

  Справедливость перечисленных операций вытекает из основных аксиом и тождественных соотношений алгебры логики.

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

  Преобразование КНФ к совершенной КНФ осуществляется путем выполнения следующих операций:

  Прибавления к каждой элементарной дизъюнкции конъюнкций переменных и их отрицаний, если они не входят в данную элементарную дизъюнкцию;

  Использования аксиомы дистрибутивности;

  Удаление всех одинаковых элементарных дизъюнкций, кроме одной.

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

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

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

  Логическая функция константа нуля в совершенной КНФ представляется конъюнкцией 2nконституент нуля. Сформулируем правило составления СКНФ логической функции по таблице соответствия.

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

  
  

  Пример 3.4. Для логической функции z(x), заданной таблицей соответствия 2.2, определим совершенную конъюнктивную форму.

  Для первой строки таблицы, которая соответствует нулевому набору функции 000, находим конституенту нуля . Выполнив аналогичные операции для второй, третьей и пятой строк, определим искомую совершенную КНФ функции:

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