<<
>>

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

Ведем обозначение

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

Выражения вида называют буквами. Число букв в элементарной конъюнкции называют рангом элементарной конъюнкции.

Элементарная конъюнкция

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

– полная относительно переменных , если в нее каждая переменная (или ее отрицание) входит ровно один раз;

– монотонная, если она не содержит отрицаний переменных.

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

Теорема. Каждую булеву функцию при любом () можно представить в виде

(*)

Это представление называется разложением функции по переменным .

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

Левая часть дает , а правая

Следствие 1. Разложение по переменной . Пусть . Тогда

Следствие 2. Разложение по всем переменным. Пусть. Тогда

При получаем выражение

т.е.

Разложение (**) носит название совершенной дизъюнктивной нормальной формы (СДНФ).

Замечания 1. Поскольку существует взаимно однозначное соответствие между таблицей истинности и СДНФ функции , то СДНФ функции единственна.

2. Единственная функция, не имеющая СДНФ, – константа 0.

3. Длина СДНФ функции равна числу наборов, на которых функция принимает значение, равное 1.

Пример. Построить СДНФ функций:

а) ;

б) .

Табл. 1.9

0 0 1
0 1 1
1 0 0
1 1 1

Решение. а) Из таблицы 1.9 получаем, что на наборах . Поэтому

Табл. 1.10

0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

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

Замечание. По данной ДНФ функции можно построить ее СДНФ. Для этого достаточно «пополнить» каждую конъюнкцию недостающими буквами , применяя соотношение , а затем устранить повторения, применив эквивалентность .

Теорема. Каждая функция алгебры логики может быть выражена в виде отрицания, конъюнкции и дизъюнкции.

Доказательство. Пусть , тогда .

Если , то выразим ее в виде СДНФ

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

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

Элементарная дизъюнкция

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

– полная относительно переменных , если в нее каждая переменная (или ее отрицание) входит ровно один раз.

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

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

Для доказательства этого рассмотрим функцию, двойственную к функции . В соответствии с формулой (*) для нее получим:

Из тождества для двойственных формул получим

Поскольку и , то получаем формулу (***).

Для и получаем выражение

которое носит название совершенной конъюнктивной нормальной формы (СКНФ).

Замечания: 1. СКНФ функции единственна.

2. Единственная функция, не имеющая СКНФ, – константа 1.

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

Пример. Построить СДНФ функции .

Решение. Исходя из таблицы 1.9, получим, что на одном наборе . Поэтому

Замечание. По данной КНФ функции можно построить СКНФ функции. Для этого достаточно «пополнить» каждую из дизъюнкций недостающими буквами , применяя соотношение , а затем устранить повторения с помощью эквивалентности .

<< | >>
Источник: Дискретная математика. Лекции. 2016

Еще по теме Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы:

  1. 2.1. Рабочая программа (объем дисциплины 150 часов)
  2. 3.3. Элементы алгебры логики
  3. Глава II. Классификация суждений
  4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  5. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  6. 2.1.5.Совершенные нормальные формы
  7. 1.7. Формы представления высказываний