X-PDF

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

Поделиться статьей

 

Рассмотрим произвольную -членную операцию , заданную своей таблицы значений, не являющуюся противоречием. Рассмотрим строки таблицы, в которых 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.

Представленная информация была полезной?
ДА
58.65%
НЕТ
41.35%
Проголосовало: 989

Теорема 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, называются эквивалентными (или равносильными).

 

 

 

 


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
58.65%
НЕТ
41.35%
Проголосовало: 989

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

Поделиться статьейЭтические проблемы современной науки являются чрезвычайно актуальными и значимыми. В связи с экспоненциальным ростом той силы, которая попадает в


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

Поделиться статьейВключает 30 родов, около 1000 видов. Распространение: горные и умеренные области Северного полушария . многие виды произрастают в горах


Поделиться статьей

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

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет