Что такое сднф функции
Перейти к содержимому

Что такое сднф функции

  • автор:

СДНФ

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

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

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

Пример нахождения СДНФ

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

\mathbf \mathbf \mathbf \mathbf \mathbf<f>(,,,)» width=»» height=»» /></th>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>0</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>0</td>
<td>1</td>
<td>0</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>0</td>
<td>1</td>
<td>1</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>0</td>
<td>1</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>0</td>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>0</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
</table>
<p><img decoding=
  • \mathbf<x_1>» width=»» height=»» /> = 0</li>
<li><img decoding= в этом случае будет представлен без инверсии: \overline<x_1>\cdot\overline\cdot\overline\cdot» width=»» height=»» /></p>
<p><img decoding=

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

    \mathbf<f>(,,,)=(\overline\cdot\overline\cdot\overline\cdot\overline)» width=»» height=»» /> <img decoding=(\overline\cdot\overline\cdot\overline\cdot) \vee(\overline\cdot\overline\cdot\cdot\overline) \vee(\overline\cdot\cdot\cdot\overline) \vee(\cdot\cdot\cdot\overline) \vee(\cdot\cdot\cdot)

    См. также

    Ссылки

    Примечания

    • Булева алгебра

    Что такое сднф функции

    Пример ДНФ: [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] .

    См. также

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

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

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

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

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

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

    Определение

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

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

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

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

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

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

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

    Примечание

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

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

    Определение

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

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

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

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

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

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

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

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

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

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

    Таблица 1

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

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

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

    Таблица 2

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

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

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

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

    Таблица 3

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

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

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

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

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

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

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

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

    \(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))\;=\)

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

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

    Выделяют такие виды формы нормального типа:

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

    СКНФ

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

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

    Так и не нашли ответ на вопрос?
    Просто напишите,с чем нужна помощь
    Мне нужна помощь

    Построение СКНФ согласно таблице истинности

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

    СДНФ

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

    • отсутствие одинаковых элементарных конъюнкций;
    • конъюнкции не свойственно обладать одинаковыми переменными;

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

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

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

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

    Нахождение СКНФ и СДНФ: примеры

    Согласно таблице истинности записать логическую функцию:

    Прибегнем к правилу построения совершенной ДНФ

    Получаем такую СДНФ

    Задействовав правило её построения:

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

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

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

    Запишем логическую функцию в СКНФ.

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

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

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *