Тема 3. 2 совершенная днф. Совершенная кнф.

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

1. различны все члены дизъюнкции;

2. различны все члены каждой конъюнкции;

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

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

,

где дизъюнкция берется по всем наборам с=(с₁, с₂, …, с_n) из 0 и 1, для которых F(c)=1.

Теорема (о СДНФ). Для всякой не равной тождественному нулю формулы логики высказываний F(x₁, x₂, …, x_n) существует такая формула F₁, зависящая от того же списка переменных и находящаяся в СДНФ относительно этого списка, что F₁ выражает собой формулу F. Формула F₁ определена однозначно с точностью до перестановки дизъюнктивных членов.

Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:

1. различны все члены конъюнкции;

2. различны все члены каждой дизъюнкции;

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

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

,

где конъюнкция берется по всем наборам с=(с₁, с₂, …, с_n) из 0 и 1, для которых F(c)=0.

Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x₁, x₂, …, x_n) существует такая формула F₁, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F₁ выражает собой формулу F. Формула F₁ определена однозначно с точностью до перестановки конъюнктивных членов.

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

1-й способ – аналитический.

Приведение к СДНФ. Алгоритм приведения.

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

2. удалить члены дизъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);

3. из одинаковых членов дизъюнкции (если такие окажутся) удалить все, кроме одного;

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

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

6. если в полученной дизъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.

Полученная формула и является СДНФ данной формулы.

 

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

1. ;

2. ;

3. .

Решение.

1. .

2.

3.

 

Приведение к СКНФ. Алгоритм приведения.

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

2. удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);

3. из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного;

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

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

6. если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.

Полученная формула и является СКНФ данной формулы.

 

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

1. ;

2. .

Решение.

1.

2.

2-й способ – табличный.

Составляем таблицу истинности для данной функции.

Приведение к СДНФ. Алгоритм приведения.

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

 

Построить СДНФ для данных формул логики высказываний.

1. .

2.

Решение.

1. .

Строим таблицу истинности для формулы F:

№	x	y	z

Рассматриваем только 4, 5 и 7 наборы, так как только на этих наборах формула принимает значение равное единице.

СДНФ имеет вид:

2. 2.

Строим таблицу истинности для формулы F:

№	x	y	x® y	F=(x® y)ÙxÙy

СДНФ (1): № 3:

F = x y.

 

Приведение к СКНФ. Алгоритм приведения.

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

 

Построить СКНФ для данных формул логики высказываний.

1. .

2.

Решение.

3. Строим таблицу значений, используя предыдущий пример.

№	x	y	z

Рассматриваем только наборы, на которых формула принимает значение ноль.

СКНФ (0): № 0, 1, 2, 3, 6:

4. Строим таблицу значений, используя предыдущий пример.

№	x	y	F=(x® y)ÙxÙy

СКНФ (0): № 0, 1, 2:

Самостоятельная работа №5.

Тема 3.3 Минимальная ДНФ.

 

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

Минимальной ДНФ (МДНФ) функции f(x₁, x₂, …, x_n) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими ДНФ, реализующими функцию f.

Минимальную ДНФ данной формулы можно найти, перебрав конечное число равносильных ей ДНФ и выбрав среди них ту, которая содержит минимальное число переменных. Однако при большом числе переменных такой перебор практически невыполним. Существуют эффективные способы нахождения минимальной ДНФ. Рассмотрим два из них.

Каждый из рассмотренных ниже методов состоит из двух этапов:

· построение сокращенной ДНФ;

· построение матрицы покрытий. Построение МДНФ.

Если для всякого набора а = (а₁, а₂, …, a_n) значений переменных условие g(a)=1 влечет f(a)=1, то функция g называется частью функции f (или функция f накрывает функцию g). Если при этом для некоторого набора с = (с₁, с₂, …, с_n)функция g(c)=1, то говорят, что функция g накрывает единицу функции f на наборе с (или что g накрывает конституенту единицы функции f).

Конституента единицы функции f есть часть функции f, накрывающая единственную единицу функции f.

Элементарная конъюнкция К называется импликантом функции f, если для всякого набора а = (а₁, а₂, …, a_n) из 0 и 1 условие К(а)=1 влечет f(a)=1.

Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f.

Всякий импликант функции f есть часть функции f.

Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.

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

Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Минимизация формул алгебры логики на кубе. Рассмотрим проблему минимизации для геометрического способа задания формул алгебры логики на кубе.

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

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

Каждая конъюнкция большего ранга покрывается всеми конъюнкциями меньшего ранга.

Геометрические эквиваленты называют интервалами.

Интервал L-го ранга – подмножество вершин куба, соответствующих конъюнкции ранга L.

Например:

Kонъюнкции x соответствует 4 вершины: 100, 101, 110, 111.

На кубе отмечают вершины, где формула алгебры логики равна 1. Эти вершины образуют подмножество Т₁. Для того, чтобы задать ДНФ на кубе, необходимо задать покрытие всех вершин.

Максимальный интервал J – интервал, для которого не существует никакого другого интервала J’ с рангом меньше, чем у J, и такого, что выполняется следующее соотношение .

Например:

Пусть есть функция, которая равна 1 в отмеченных точках.
J₁ и J₃ – максимальные интервалы,

J₂ – не является максимальным

 

где r_i – ранги конъюнкции, образующих покрытие множества T_1.

Необходимо найти Т₁, при котором R будет минимальным.

Сокращенная ДНФ(СДНФ) – ДНФ, которая соответствует покрытию множества Т₁ всеми максимальными интервалами. В данном примере СДНФ = .

Минимальная ДНФ получается из СДНФ путем выбрасывания из покрытия множества Т₁ максимальными интервалами некоторых “лишних” интервалов.

 

Тема 3.4 Представление булевой функции в виде минимальной ДНФ.