Днф и сднф в чем разница

В чем разница Днф и Сднф

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

1. Что такое ДНФ и СДНФ
2. Для чего нужен СДНФ
3. Каким условиям должна удовлетворять СДНФ
4. Отличия между КНФ и ДНФ
5. Советы и выводы

Что такое ДНФ и СДНФ

ДНФ и СДНФ — это логические выражения, используемые для представления логических функций. Они состоят из логических операций «ИЛИ», «И» и отрицаний переменных или их комбинаций.

Однако, главное отличие между ДНФ и СДНФ заключается в количестве и длине конъюнкций. СДНФ — это форма ДНФ, в которой все простые конъюнкции полные и не повторяются.

Для чего нужен СДНФ

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

Каким условиям должна удовлетворять СДНФ

СДНФ считается совершенной, если она удовлетворяет следующим условиям:

• в ней нет одинаковых простых конъюнкций;
• каждая простая конъюнкция полная.

Отличия между КНФ и ДНФ

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций. Например, выражение «А ИЛИ B ИЛИ С» является КНФ.

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

• в каждую конъюнкцию входят все переменные (либо сами, либо их отрицания);
• каждая простая конъюнкция полная;
• нет одинаковых простых конъюнкций.

Советы и выводы

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

• Кому принадлежат гипермаркеты Окей
• Почему не дают Кубышку
• Как отправить документы через Сбербанк

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

Все права защищены © 2024

Что нужно знать о СДНФ — основные сведения

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

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

Любая булева формула, которая не является тождественно ложной, способна быть приведена к СДНФ. Более того, единственным способом, то есть для любой выполнимой функции в алгебре логики есть собственная СДНФ, притом единственная.

Примечание 1

Булева формула — формула из логики высказываний. В нее могут входить логические переменные, а также пропозициональные связки, такие как конъюнкцию \((«\vee»)\) , дизъюнкцию \((«\wedge»)\) , отрицание \((«\neg»)\) и иные.

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

Краткая теория

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

Представим пример простой ДНФ:

В структуре ДНФ могут быть повторяющиеся слагаемые, а в структуре каждого слагаемого могут находиться повторяющиеся сомножители. К примеру:

С точки зрения алгебры подобное клонирование лишено всякого смысла, потому что в булевой алгебре действие «умножения» любого выражения на само себя, а также действие сложения выражения с самим собой не изменяет результата \((x+x=x; x\times=x)\) . Действие сложения выражения со своей инверсией, а также умножение на свою инверсию производит константы \((x+\overline=1; x\times<\overline>=0)\) .

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

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

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

Приведем пример СДНФ:

Значение СДНФ проявляется в том, что:

• для каждой определенной функции СДНФ обладает единичным и однозначным характером;
• СДНФ обладает точным соответствием с таблицей истинности функции. Каждое слагаемое СДНФ будет соответствовать одной графе в таблице истинности, в которой функция равняется единице. Так получится, что количество слагаемых в СДНФ будет равно числу единичных значений, которые способна принимать булева функция в собственной области определения;
• СДНФ можно просто получить, исходя из таблицы истинности функции;
• СДНФ крайне удобна как базовое выражение для минимизации функции, просто в ней находятся слагаемые, которые пригодные для «склейки».

Построение СДНФ по таблице истинности

Что нужно делать, чтобы найти СДНФ по таблице истинности? Основная схема построения:

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

Примечание 2

Таблица истинности — вид таблицы, который описывает логическую функцию, отражающую все значения функции с помощью вероятных значений аргументов функции. Таблица сформирована из n+1 столбцов и \(2^\) , где n будет числом используемых переменных. В таблице истинности в первых n-столбцах записывают все величины аргументов функции, а в n+1 столбце записываются значения функции, которая она принимает на этом наборе аргументов.

Алгоритм построения СДНФ для булевой функции

Булева функция (или по-другому логическая функция\функция в алгебре логики) от n переменных — отображение \(B^\rightarrow\) , где \(B=\) является булевым множеством.

Элементы булева множества 0 и 1 обычно рассматривают в качестве логических значений «ложно» и «истинно». В общем случае их рассматривают в качестве формальных символов, которые не обладают конкретным смыслом. Элементы декартова произведения \(B^\) можно назвать булевыми векторами. Множество булевых функций от каждого числа переменных обычно обозначают \(P^\) , а от n переменных — \(P^(n)\) . Булевы функции носят свои названия по имени известного английского математика Джорджа Буля.

Так выглядел Джордж Буль:

Для любой булевой функции \(f(\overrightarrow)\) , которая не равна тождественному нулю, есть СДНФ, которая задает ее.

Доказательство этой теоремы:

Для каждой булевой функции будет выполняться такое соотношение, которое называют в алгебре разложением Шеннона:

Такое соотношение просто проверить при помощи подстановки возможных значений \(x_ (0 \) и \(1)\) . Данная формула помогает вынести \(x_\) за знак функции. Шаг за шагом вынося \(x_, x_, x_\) за знак \(f(\overrightarrow)\) , можно получить такую формулу: \(f(\overrightarrow)=\neg\wedge>\wedge. \wedge>\wedge>\wedge(0,0. 0,0)\vee\wedge>\wedge. \wedgex_\wedge\wedge(0,0. 0,1)\vee. \vee\wedge\wedge. \wedge\wedgex_n\wedge(1,1. 1,0)\vee\wedge\wedge. \wedge\wedge\wedge(1,1. 1)\) .

Из-за использования этого соотношения к каждой из переменных увеличивается число конъюнктов в два раза. Так для функции от n переменных получается \(2^\) возможных наборов величин n переменных. Если на каком-то наборе \(f(\overrightarrow)=0\) , тогда весь соответствующий конъюнкт будет также равняться нулю и из представления этой функции он может быть исключен. Если \(f(\overrightarrow)=1\) , тогда в конъюнкте значение функции возможно опустить. В итоге для произвольной функции была построена СДНФ.

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

Представим пример построения СДНФ для медианы

1. В таблице истинности отметим список переменных, на которых значение функции будет равным единице.

ДНФ и СДНФ: какие различия?

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

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

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

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

Определение ДНФ и СДНФ

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

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

Значения переменных	Значение функции	ДНФ
0 0 0	0	¬A¬B¬C
0 0 1	1	¬A¬BC
0 1 0	0	¬ABC
0 1 1	1	¬AB¬C
1 0 0	0	A¬B¬C
1 0 1	1	A¬BC
1 1 0	1	ABC
1 1 1	0	AB¬C

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

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

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

Определение и сокращения

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

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

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

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

№	ДНФ
1	(AB̅C̅)
2	(A̅BC)
3	(A̅B̅C)
4	(ABC)

СДНФ для этой же функции будет выглядеть следующим образом:

№	СДНФ
1	(AB̅C̅)
2	(A̅BC)
3	(A̅B̅C)
4	(ABC)

Здесь мы видим, что ДНФ и СДНФ идентичны, потому что в данном примере все конъюнкции содержат только один литерал. Однако в общем случае СДНФ может содержать только одну колонку соответствующих литералов.

Что такое ДНФ?

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

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

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

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

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

Что такое СДНФ?

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

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

Вход A	Вход B	Выход Y
0	0	1
0	1	0
1	0	0
1	1	1

В данном примере первая строка означает, что при значениях входных переменных A=0 и B=0, выходная переменная Y принимает значение 1. Аналогично для остальных строк. Отметим, что в каждой строке присутствуют отрицания входных переменных, если соответствующий вход принимает значение 0.

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

Структура ДНФ и СДНФ

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

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

Пример ДНФ для булевой функции F(x, y, z):

F(x, y, z) = (x * y * z) + (x * y * ¬z) + (x * ¬y * z) + (x * ¬y * ¬z)

Пример СДНФ для той же булевой функции:

F(x, y, z) = (x * y * z) + (x * ¬y * z) + (x * ¬y * ¬z)

В обоих примерах переменные x, y и z могут принимать значения 0 или 1. Символ ¬ обозначает отрицание значения переменной.

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

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

В примере булевой функции F(x, y, z) в ДНФ присутствуют четыре комбинации значений переменных, но только три из них являются существенными: (x * y * z), (x * ¬y * z) и (x * ¬y * ¬z). Последняя комбинация (x * y * ¬z) является лишней, так как не влияет на истинность функции.

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

Структура ДНФ

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

Структура ДНФ имеет следующий вид:

1. Выражение состоит из нескольких термов.
2. Каждый терм состоит из переменных и их отрицаний, объединенных операцией ИЛИ.
3. Переменные и их отрицания в каждом терме объединяются операцией И.

Примером ДНФ может быть следующее выражение:

Переменные	Термы
A	A
B	B
C	C
A + B + C

В данном примере переменные A, B и C являются членами каждого терма и объединяются через операцию И. Все термы объединяются операцией ИЛИ. Таким образом, данное выражение является ДНФ.

Структура СДНФ

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

Структура СДНФ выглядит следующим образом:

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

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

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

Вопрос-ответ

Чем отличается ДНФ от СДНФ?

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

В чем состоит разница между ДНФ и СДНФ?

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

Каковы отличия между ДНФ и СДНФ?

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

Днф и сднф в чем разница

«Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Днф и сднф в чем разница

Пример ДНФ: [math]f(x,y,z) = (x \land y) \lor (y \land \neg )[/math] .

СДНФ

Пример СДНФ: [math]f(x,y,z) = (x \land \neg \land z) \lor (x \land y \land \neg )[/math] .

Для любой булевой функции [math]f(\vec )[/math] , не равной тождественному нулю, существует СДНФ, ее задающая.

Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона:

[math]f(\vec) = \neg x_i \wedge f(x_1, \ldots ,x_,0,x_, \ldots ,x_n) \vee x_i \wedge f(x_1, \ldots ,x_,1,x_, \ldots ,x_n)[/math] .

Данное соотношение легко проверить подстановкой возможных значений [math]x_i[/math] ( [math]0[/math] и [math]1[/math] ). Эта формула позволяет выносить [math]x_i[/math] за знак функции. Последовательно вынося [math]x_1[/math] , [math]x_2[/math] . [math]x_n[/math] за знак [math]f(\vec)[/math] , получаем следующую формулу: [math] f(\vec) = \neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_ \wedge \neg x_n \wedge f(0,0,\ldots,0,0)~\vee~[/math]

[math]\neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_ \wedge x_n \wedge f(0,0,\ldots,0,1) ~\vee~ \\ \ldots \\ ~\vee~ x_1 \wedge x_2 \wedge \ldots \wedge x_ \wedge \neg x_n \wedge f(1,1,\ldots,1,0) ~\vee~\\ x_1 \wedge x_2 \wedge \ldots \wedge x_ \wedge x_n \wedge f(1,1,\ldots,1) [/math]

Алгоритм построения СДНФ по таблице истинности

1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math] 1 [/math] .
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math] 1 [/math] , то в конъюнкцию включаем саму переменную, иначе ее отрицание.
3. Все полученные конъюнкции связываем операциями дизъюнкции.

Пример построения СДНФ для медианы

Построение СДНФ для медианы от трех аргументов

1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math] 1 [/math] .

[math] x [/math]	[math] y [/math]	[math] z [/math]	[math] \langle x,y,z \rangle [/math]
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math] 1 [/math] , то в конъюнкцию включаем саму переменную, иначе ее отрицание.

[math] x [/math]	[math] y [/math]	[math] z [/math]	[math] \langle x,y,z \rangle [/math]
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1	[math](\neg \land y \land z)[/math]
1	0	0	0
1	0	1	1	[math](x \land \neg \land z)[/math]
1	1	0	1	[math](x \land y \land \neg )[/math]
1	1	1	1	[math](x \land y \land z)[/math]

3. Все полученные конъюнкции связываем операциями дизъюнкции:

[math] \langle x,y,z \rangle = (x \land y \land z) \lor (\neg \land y \land z) \lor (x \land \neg \land z) \lor (x \land y \land \neg )[/math] .

Построение СДНФ для медианы от пяти аргументов

[math] x_1 [/math]	[math] x_2 [/math]	[math] x_3 [/math]	[math]x_4[/math]	[math] x_5 [/math]	[math] \langle x_1, x_2, x_3, x_4, x_5 \rangle [/math]
0	0	0	0	0	0
0	0	0	0	1	0
0	0	0	1	0	0
0	0	0	1	1	0
0	0	1	0	0	0
0	0	1	0	1	0
0	0	1	1	0	0
0	0	1	1	1	1	[math](\neg \land \neg \land x_3 \land x_4 \land x_5)[/math]
0	1	0	0	0	0
0	1	0	0	1	0
0	1	0	1	0	0
0	1	0	1	1	1	[math](\neg \land x_2 \land \neg \land x_4 \land x_5)[/math]
0	1	1	0	0	0
0	1	1	0	1	1	[math](\neg \land x_2 \land x_3 \land \neg \land x_5)[/math]
0	1	1	1	0	1	[math](\neg \land x_2 \land x_3 \land x_4 \land \neg )[/math]
0	1	1	1	1	1	[math](\neg \land x_2 \land x_3 \land x_4 \land x_5)[/math]
1	0	0	0	0	0
1	0	0	0	1	0
1	0	0	1	0	0
1	0	0	1	1	1	[math](x_1 \land \neg \land \neg \land x_4 \land x_5)[/math]
1	0	1	0	0	0
1	0	1	0	1	1	[math](x_1 \land \neg \land x_3 \land \neg \land x_5)[/math]
1	0	1	1	0	1	[math](x_1 \land \neg \land x_3 \land x_4 \land \neg )[/math]
1	0	1	1	1	1	[math](x_1 \land \neg \land x_3 \land x_4 \land x_5)[/math]
1	1	0	0	0	0
1	1	0	0	1	1	[math](x_1 \land x_2 \land \neg \land \neg \land x_5)[/math]
1	1	0	1	0	1	[math](x_1 \land x_2 \land \neg \land x_4 \land \neg )[/math]
1	1	0	1	1	1	[math](x_1 \land x_2 \land \neg \land x_4 \land x_5)[/math]
1	1	1	0	0	1	[math](x_1 \land x_2 \land x_3 \land \neg \land \neg )[/math]
1	1	1	0	1	1	[math](x_1 \land x_2 \land x_3 \land \neg \land x_5)[/math]
1	1	1	1	0	1	[math](x_1 \land x_2 \land x_3 \land x_4 \land \neg )[/math]
1	1	1	1	1	1	[math](x_1 \land x_2 \land x_3 \land x_4 \land x_5)[/math]

[math] \langle x_1, x_2, x_3, x_4, x_5 \rangle = (\overline \land \overline \land x_3 \land x_4 \land x_5) \lor (\overline \land x_2 \land \overline \land x_4 \land x_5) \lor (\overline \land x_2 \land x_3 \land \overline \land x_5) \lor (\overline \land x_2 \land x_3 \land x_4 \land \overline ) \lor (\overline \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline \land \overline \land x_4 \land x_5) \lor (x_1 \land \overline \land x_3 \land \overline \land x_5) \lor (x_1 \land \overline \land x_3 \land x_4 \land \overline ) \lor (x_1 \land \overline \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land \overline \land \overline \land x_5) \lor (x_1 \land x_2 \land \overline \land x_4 \land \overline ) \lor (x_1 \land x_2 \land \overline \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land \overline \land \overline ) \lor (x_1 \land x_2 \land x_3 \land \overline \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline ) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5)[/math] .

Примеры СДНФ для некоторых функций

Стрелка Пирса: [math] x \downarrow y = (\neg \land \neg )[/math] .

Исключающее или: [math] x \oplus y \oplus z = (\overline \land \overline \land z) \lor (\overline \land y \land \overline) \lor (x \land \overline \land \overline) \lor (x \land y \land z)[/math] .

См. также

• Сокращенная и минимальная ДНФ
• КНФ

Источники информации

• СДНФ — Википедия
• Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика

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

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

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

Среди нормальных форм выделяются совершенные нормальные формы (такие формы, в которых функции записываются единственным образом).

Совершенная дизъюнктивная нормальная форма (СДНФ)

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

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

ДНФ записывается в следующей форме: F₁ ∨ F₂ ∨ . ∨ F_n, где F_i — элементарная конъюнкция

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой конъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.

Совершенная конъюнктивная нормальная форма (СКНФ)

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

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

КНФ записывается в следующей форме: F₁ ∧ F₂ ∧ . ∧ F_n, где F_i — элементарная дизъюнкция

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой дизъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.

Заметим, что любую логическую функцию, не равную тождественно 0 или 1, можно представить в виде СДНФ или СКНФ .

Алгоритм построения СДНФ по таблице истинности

1. Выбрать все строки таблицы, в которых значение функции равно единице.
2. Для каждой такой строки записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.
3. Все полученные конъюнкции связываем операциями дизъюнкции.

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

1. Выбрать все строки таблицы, в которых значение функции равно нулю.
2. Для каждой такой строки записать дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.
3. Все полученные дизъюнкции связываем операциями конъюнкции.

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

Пример: Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.

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

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

x	y	z	¬ x	¬ x ∨ y ∨ z	¬ z	¬ x ∨ y ∨ ¬ z	F (x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

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

Copyright © 2014-2021, Урок информатики
Все права защищены

For Informatics

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

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

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

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

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

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

Выразим логические операции → и ↓ через :

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

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

Используя идемпотентность конъюкции, получаем ДНФ:

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

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ , которая удовлетворяет трём условиям:

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

Для любой функции алгебры логики существует своя СДНФ, причём единственная.

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

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

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

Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:

• 
• 
• 

в этом случае будет представлен без инверсии:

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

Совершенная ДНФ этой функции:

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