Совершенные нормальные формы СДНФ, СКНФ

Лекция 2. Формы представления высказываний

План лекции:

Дизъюнктивные и конъюнктивные нормальные формы ДНФ, КНФ.

Совершенные нормальные формы СДНФ, СКНФ

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

Нормальная форма – это синтаксически однозначный способ записи формулы, реализующей данную функцию.

Любая n-членная операция, обозначаемая, например, , будет полностью определена, если установлено, при каких значениях высказываний результат будет истинным или ложным. Один из способов задания такой операции – заполнение таблицы значений:


1	1	1	1 или 0

0	0	0	1 или 0

В таблице значений высказывания, образованного от n простейших высказываний , имеется строк. Столбец значений имеет также позиций. Следовательно, имеется различных вариантов его заполнения, и, соответственно, число всех n-членных операций равно . При n =1 число одночленных операций равно 4, при n =2 число двучленных – 16, при n =3 количество трехчленных – 256 и т.д.

Рассмотрим некоторые специальные виды формул.

Формулу называют элементарной конъюнкцией, если она является конъюнкцией переменных и отрицаний переменных. Например, формулы , , , – элементарные конъюнкции.

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

Теорема 2.1.(о приведении к ДНФ). Для любой формулы U можно найти равносильную ей формулу V, являющуюся ДНФ.

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

Пример.

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

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

Теорема 2.2.(о приведении к КНФ). Для любой формулы U можно найти равносильную ей формулу V, являющуюся КНФ.

Пример.

Отдельный элемент КНФ называется элементарной дизъюнкцией или конституентой нуля.

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

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

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

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

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

Примеры.

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

Преобразуем формулу F к формуле, не содержащей импликацию:

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

По закону дистрибутивности получим КНФ:

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

Выразим логические операции импликации и стрелку Пирса через конъюнкцию, дизъюнкцию и инверсию:

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

Используя закон дистрибутивности, приводим формулу к ДНФ:

Совершенные нормальные формы СДНФ, СКНФ

Рассмотрим произвольную -членную операцию , заданную своей таблицы значений, не являющуюся противоречием. Рассмотрим строки таблицы, в которых f принимает значения “1”. Для каждой строки составим элементарные конъюнкции из n множителей, где i-й множитель равен (в этой строке принимает значение “1”) или (в этой строке принимает значение “0”). Далее возьмем дизъюнкцию всех полученных конъюнкций. В итоге получится формула (ДНФ), задающая операцию, равносильную . Действительно, каждая из построенных конъюнкций будет истинна только при тех значениях истинности высказываний , которые стоят в соответствующей строчке. Поскольку была взята дизъюнкция по всем наборам значений истинности высказываний , на которых истинна, то построенное высказывание истинно на всех этих наборах и только на них. На остальных наборах оно ложно.

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

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

Пример.

Аналогично, рассматривая строки, в которых операция , не являющаяся тавтологией, принимает значения “0”, и составляя конъюнкцию (число множителей равно числу отмеченных строк таблицы) дизъюнкций изn слагаемых, гдеi-е слагаемое равно (в этой строке принимает значение “0”) или (в этой строке принимает значение “1”). В итоге получится формула, задающая операцию, равносильную . Построенная формула называется совершенной конъюнктивной нормальной формой (СКНФ) операции .

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

Пример.

Каждая формула имеет одну единственную СДНФ и одну единственную СКНФ. Тавтология не имеет СКНФ, а противоречие – СДНФ.

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

Пример.

Рассмотрим частный случай. Пусть только в одном единственном случае.

x	y	z	f(x,y,z)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

Тогда этой формуле будет соответствовать функция .

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

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

Пример.

x	y	z	f(x,y,z)
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

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

(2.1)

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

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

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

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

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

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

т.е. (2.2)

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

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

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

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

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

(2.3)

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

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

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

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

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

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

т.е. (2.4)

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

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

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

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

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

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

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

Пример. Найти отрицание формулы:

Руководствуясь утверждением 2.3, выпишем отрицание для формулы .

Пример. Перейдите от СДНФ к СКНФ:

.Согласно утверждению 2.1 имеем: отрицание формулы имеет следующую СДНФ: .Теперь применяя утверждение 2.3, находим отрицание этой формулы . Это и есть СКНФ данной формулы.

Пример. Перейдите от СКНФ к СДНФ: . Согласно утверждению 2.2 имеем: отрицание формулы имеет следующую СКНФ: . Теперь применяя утверждение 2.3, находим отрицание этой формулы . Это и есть СКНФ данной формулы.

А теперь сформулируем основные определения и понятия, касающиеся нормальных и совершенных форм.

Вернемся к понятию конъюнкта и дизъюнкта. Конъюнкции , , 1 являются элементарными. Причем первая элементарная конъюнкция имеет ранг (число литералов) 2, вторая - 3, а третья - 0. Дизъюнкции , , 1 являются элементарными. Причем первая элементарная дизъюнкция имеет ранг (число литералов) 2, вторая - 3, а третья - 0.

Следующие дизъюнкции: , , , , 0 не являются элементарными.

Определение 2.3. Элементарная конъюнкция булевой функции содержащая n литералов, называется полной (или min-термом). Элементарная дизъюнкция булевой функции , содержащая n литералов, называется полной (max-термом).

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

Пример. Определить длину данной ДНФ и КНФ. ДНФ имеет длину, равную 3. КНФ имеет длину, равную 3.

Определение 2.5. Две (или несколько) ДНФ, реализующих одну и ту же булеву функцию F , называются эквивалентными (или равносильными). Две (или несколько) КНФ, реализующих одну и ту же булеву функцию F , называются эквивалентными (или равносильными).

Дата добавления: 2021-04-06; просмотров: 379; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!