Как найти днф и кнф по таблице истинности

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

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

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

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

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

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

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

СДНФ обладает некоторыми определенными свойствами:

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

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

При построении таблицы истинности важно помнить, что логические переменные со значением «0» необходимо брать с отрицанием.

Что такое СКНФ

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

Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:

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

Правила построения по таблице истинности

Дизъюнктивная форма

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

Конъюнктивная форма

Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.

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

Рассмотрим логическую функцию в виде таблицы истинности.

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

Отметить наборы переменных, значение функции F на которых равно 1.
Записать для всех отмеченных наборов конъюнкцию всех переменных так: если значение некоторой переменной в этом наборе равняется 1, в конъюнкцию включается сама переменная. В случае противного результата, в конъюнкцию включается ее отрицание.
Связать полученные конъюнкции операциями дизъюнкции.

Построим совершенную ДНФ:

И как результат получим следующую СДНФ:

Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:

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

Построим совершенную КНФ:

И как результат получим следующую СКНФ:

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

Доказательство эквивалентности

Эквивалентность — понятие, означающее, что две и более формул представляют одну и ту же функцию. Для обозначения эквивалентности могут использоваться следующие знаки: $ \equiv , = , \Leftrightarrow .$

Доказать эквивалентность формул можно двумя способами.

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

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

Поглощение

Склеивание

Обобщенное склеивание

$xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z$

$xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z\;\vee\;xyz\;\vee\;xy\overline z\;=\;xz\;\vee\;y\overline z$

Расщепление

$x\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;xy\;\vee\;\overline xy\;=\;x\;\cdot\;l\;\;\vee\;y\;\cdot\;l\;=\;x\;\vee\;y$

Примеры с решением

Задача №1

Приведите к СКНФ $((((A\rightarrow B)\rightarrow\overline A)\rightarrow\overline B)\rightarrow\overline C)$ .

Через применение закона де Моргана и правила $ x\;\rightarrow\;y\;=\;\overline x\;\vee\;y$ упростим выражения:

$F\;=\;((((A\;\rightarrow\;B)\;\rightarrow\;\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;(((\overline A\;\vee\;B)\;\rightarrow\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\overline C\;)\;=$

$=\;((((\overline A\;\vee\;B)\;\rightarrow\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;((\overline<((\overline A\;\vee\;B)>\;\vee\;\overline A)\;\rightarrow\overline B)\;\rightarrow\overline C)\;=$

$=(((\overline A\;\vee\;B)\;\vee\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\;\overline C)\;=((\overline<(\overline<(\overline A\vee B)>\;\vee\;\overline A\;)>\;\vee\;\overline B)\;\rightarrow\;\overline C)\;=$

$=\;((\overline<(\overline A\;\vee\;B)>\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge B)\;\vee\;\overline C\;=$

$=((A\overline B\;\vee\;\overline A)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=$

$=\;((A\overline B\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(A\overline BB\;\vee\;\overline AB)\;\vee\;\overline C\;=\;(0\;\vee\;\overline AB)\;\vee\;\overline C\;=\;\overline AB\;\vee\;\overline C$

Далее приведем выражение к КНФ:

$F\;=\;\overline AB\;\vee\;\overline C\;\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)$

Далее приведем выражение к СКНФ:

$F\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)\;=\;(\overline A\;\vee\:\overline C\;\vee\;B\overline B)\;\wedge\;(A\overline A\;\vee\;B\;v\;\overline C)\;=$

$=\;(\overline A\;\vee\;\overline C\;\vee\;B)\;\wedge\;(A\;\vee\;B\;\vee\;\overline C)\;\wedge\;(\overline A\;\vee\;\overline C\;\vee\;\overline B)\;\wedge\;(\overline A\;\vee\;B\;\;\overline C)$

Задача №2

Используя эквивалентные преобразования, постройте ДНФ функции $f(\widetilde x^n)$

$f(\widetilde x^3) = (\overlinex_2\;\oplus\;x_3)\;\cdot\;(x_1x_3\;\rightarrow\;x_2)$

$f(\widetilde x^3) = (\overlinex_2\;\oplus\;x_3)\;\cdot\;(x_1x_3\;\rightarrow\;x_2) = ((\overlinex_2\;\cdot\;\overline\;)\;\vee\;(\overline<\overlinex_2>\;\cdot\;x_3))\;\cdot\;(\overline\;\vee\;x_2)\;=$

$=(\overlinex_2\overline\;\cdot(x_1\vee x_3\vee x_2)\;\vee\;x_1x_3\;\cdot\;(\overline\;\vee\;\overline\;\vee\;x_2)\;\vee\;\overlinex_3\;\cdot\;(\overline\;\vee\;\overline\;\vee\;x_2))\;=$

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

Базис =наиболее изучен и имеет самое широкое применение на практике.

Определение. Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) переменных или их отрицаний.

Пример 2.3.1 –

а) иэлементарные дизъюнкции;

б) иэлементарные конъюнкции;

в)одновременно является и элементарной дизъюнкцией и элементарной конъюнкцией.

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

Пример 2.3.2 –

а)ДНФ;

б) КНФ.

Теорема. Любая формула может быть приведена к ДНФ (КНФ) (т.е. любая формула эквивалентна некоторой ДНФ (КНФ)).

Правило приведения формулы к ДНФ:

а) все логические операции, присутствующие в формуле, выразить через , используя эквивалентности:

1);

2);

3);

4);

5);

б) перенести все отрицания к переменным по закону де Моргана:

;

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

Пример 2.3.3 — Приведём к ДНФ формулу . Для этого

заменим на, затем применим закон де Моргана и закон двойного отрицания:=.

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

а) (закон идемпотентности);

б) (закон исключённого третьего),(закон противоречия); в),— ( свойства констант).

Поэтому, используя закон идемпотентности, в последнем примере получим ДНФ: .

Приведение формулы к КНФ производится так же как к ДНФ, только вместо пункта в) применяется пункт в:

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

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

Заменим операцию , используя формулу:

[закон де Моргана, двойное

отрицание] — КНФ.

ДНФ и КНФ имеют тот недостаток, что они не обладают свойством единственности, т.е. одна и та же формула имеет несколько ДНФ и КНФ. Этим недостатком не обладают совершенные нормальные формы.

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

Пример 2.3.5 –

а) — СДНФ;

б) — СКНФ;

в) — не СДНФ, т.к. содержит две одинаковых элементарных конъюнкции;

г) — не СДНФ, т.к. в одной элементарной конъюнкции содержится и переменная и её отрицание:.

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

Для приведения формулы к СДНФ можно использовать один из двух методов:

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

Пример 2.3.6 — Получим СДНФ функции , заданной в ДНФ:

— СДНФ.

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

Пример 2.3.7 — Для функции , заданной в ДНФ, найти СДНФ. Построим таблицу истинности:

Т а б л и ц а 2.3.1

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

Приведение формулы к СКНФ аналогично приведению к СДНФ. Также существует два метода:

а) метод элементарных преобразований;

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

Пример 2.3.8 — Рассмотрим функцию из предыдущего примера . Приведём её к СКНФ двумя способами:

а)

б) из таблицы истинности выпишем нулевые наборы:, значит, по выше приведённому правилу,— СКНФ.

Минимизация булевых функций в классе ДНФ. Карты Карно

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

Определение. Минимальной ДНФ (МДНФ) называется ДНФ с наименьшим числом вхождений переменных.

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

Карта Карно – это таблица, каждая клетка (ячейка) которой соответствует некоторой элементарной конъюнкции всех переменных. Для функции n переменных существуетвозможных комбинаций их значений, состоящих из 0 и 1. То есть, например, для n=2 имеемэлементарные конъюнкции, которым соответствуют следующие наборы 0 и 1: (1,1), (1,0), (0,1), (0,0); для n=3 ——— (1,1,1), (1,1,0),…,(0,0,0) и т.д. Карты Карно строятся в виде таблицы размеромтак, что её столбцы соответствуют значениям переменных, строки — (или наоборот); вообще, для одной и той же функции может быть построено несколько карт, важно, чтобы соседние ячейки (как по вертикали, так и по горизонтали) отличались только значением одной переменной.

Мы будем рассматривать в основном функции двух, трёх и четырёх переменных. Для них карты Карно имеют следующий вид:

а) для функции двух переменных х, у — рисунок 2.3.1;

б)для функции трёх переменных — рисунок 2.3.2;

в) для функции четырёх переменных — рисунок 2.3.3.

Рисунок 2.3.1 Рисунок 2.3.2 Рисунок 2.3.3

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

Пример 2.3.9 — Функции изаданы в форме СДНФ. Карта Карно дляна рисунке 2.3.4; для— на рисунке 2.3.5.

Рисунок 2.3.4 Рисунок 2.3.5

Заметим, что, если в картах Карно две, четыре, восемь (для функции четырёх переменных) соседних ячеек по вертикали или по горизонтали содержат 1, то эти ячейки объединяют в блоки (на картах их отмечают овалами) и соответствующие этим блокам дизъюнкции элементарных конъюнкций можно упростить. Так, в примере 2.3.9 для функции имеем блок из двух ячеек, на рисунке он отмечен овалом. Этому блоку соответствует дизъюнкция, упрощая которую, получим:. Таким образом, блоку из двух ячеек функции двух переменных отвечает одна переменнаях, а именно та переменная, которая полностью «покрывает» этот блок. Формула упростилась .

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

Рассмотрим ещё несколько примеров.

Пример 2.3.10 — — СДНФ функции. Её карта Карно на рисунке 2.3.6. Так какz находится на обоих концах карты, то её (карту) можно «скрутить» и считать, что 1 в углах карты образуют блок из четырёх ячеек. Эти четыре ячейки полностью «покрывает» переменная z, т.о., МДНФ функции будет .

Рисунок 2.3.6 Рисунок 2.3.7 Рисунок 2.3.8

Пример 2.3.11 — — СДНФ функции. Её карта Карно на рисунке 2.3.7. На карте есть блок из четырёх ячеек, который покрывают переменныеи, поэтому МДНФ функции будет:.

Пример 2.3.12 — Карта Карно для функции

заданной в СДНФ на рисунке 2.3.8.

На карте имеем: блок из 8 ячеек покрывает переменная y; двум блокам из 4 ячеек соответствуют элементарные конъюнкции и, поэтому МДНФ будет:.

Таблица истинности

bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис.
Для булевой функции, заданной вектором значений (например, 00111011 ) используйте ввод данных через таблицу.

Правила ввода логической функции

Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
Максимальное количество переменных равно 10 .

словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
описание функции алгебры логики в виде таблицы истинности.
описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
1) в таблице выбираются те строки переменных для которых функция на выходе =1 .
2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
3) полученное произведение логически суммируется.
Fднф= X ₁*Х₂*Х₃ ∨ Х₁ x ₂Х₃ ∨ Х₁Х₂ x ₃ ∨ Х₁Х₂Х₃
ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
КНФ может быть получена из таблицы истинности по следующему алгоритму:
1) выбираем наборы переменных для которых функция на выходе =0
2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
3) логически перемножаются полученные суммы.
Fскнф=(X₁ V X₂ V X₃) ∧ (X₁ V X₂ V X ₃) ∧ (X₁ V X ₂ V X₃) ∧ ( X ₁ V X₂ V X₃)
КНФ называется совершенной, если все переменные имеют одинаковый ранг.

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина

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

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

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

Все эти примеры разобраны ниже. Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.

Другие примеры решений о булевых функциях:

Булевы формулы
Таблицы истинности
Минимизация ДНФ булевых функций
Полнота системы функций

Задачи и решения о представлении булевых функций

Нормальные формы (КНФ, СКНФ, ДНФ и СДНФ): примеры решений

Задача 1. Привести к КНФ и СКНФ.

$$((((A\to B)\to \bar A) \to \bar B) \to \bar C).$$

Задача 2. С помощью эквивалентных преобразований построить д.н.ф. функции:

$$f(x)=(\overlinex_2 \oplus x_3) \cdot (x_1 x_3 \to x_2) $$

Задача 3. Используя СКНФ, найдите наиболее простую формулу алгебры высказываний от четырех переменных, принимающую значение 0 на следующих наборах значений переменных, и только на них:

Задача 4. Привести данные выражения к ДНФ, пользуясь правилами де Моргана. Если возможно, сократить ДНФ, используя свойство поглощения и правило Блейка.

Многочлен Жегалкина: примеры решений

Задача 5. Представив функцию формулой над множеством связок $\<\&, -\>$, преобразовать затем полученную формулу в полином Жегалкина функции $f(x)$ (используя эквивалентности):

$$f(x) = (x_1 \vee x_2) \cdot (x_2 | x_3)$$

Задача 6. Задана булева функция: $$ f(x_1, x_2, x_3) = \overline \vee ((x_1 \wedge \overline ) | \overline<(x_2 | \overline )>$$ А) Построить таблицу истинности, найти двоичную форму булевой функции и привести ее к СДНФ и СКНФ.
Б) Найти многочлен Жегалкина.

Задача 7. Для заданной логической функции перейти к полиному Жегалкина.

Решение задач на заказ

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