Как сделать сднф

Обновлено: 08.07.2024

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

Нормальная форма существует в двух видах:

· конъюнктивная нормальная форма (КНФ) -- конъюнкция нескольких дизъюнкций, например, (A∨B¯∨C)∧(A∨C);

· дизъюнктивная нормальная форма (ДНФ) -- дизъюнкция нескольких конъюнкций, например, (A∧B¯∧C)∨(B∧C).

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

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

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

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

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

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

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

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

Пример 1 Записать логическую функцию по ее таблице истинности:

Решение: Воспользуемся правилом построения СДНФ:

Воспользуемся правилом построения СКНФ:

Получим СКНФ: F(x1, x2, x3)=(x1∨x2¯∨x3)∧(x1∨x2¯∨x3¯)∧(x1¯∨x2¯∨x3)

Пример 2

Функция задана таблицей истинности:

Представить эту функцию в виде СДНФ и СКНФ.

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

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

Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ: F(x1,x2,x3,x4)=(x¯∧y¯∧z∧f)∨(x1¯∧x2∧x3¯∧x4¯)∨(x1¯∧x2∧x3∧x4)∨(x1∧x2¯∧x3¯∧x4¯).

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

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

Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:

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

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

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

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math] 1 [/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] \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] .

Коммуникативный педагогический тренинг: способы взаимодействия с разными категориями учащихся

Сертификат и скидка на обучение каждому участнику

Построение СДНФ и СКНФ.

Нормальные формы логических функций.

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

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

Элементарная конъюнкция – логическое произведение аргументов или их отрицаний. Например, А ∧ ¬В ∧ С – элементарная конъюнкция, а ¬ (А ∧ ¬В) – нет, т.к. присутствует отрицание выражения.

Элементарная дизъюнкция – логическая сумма аргументов или их отрицаний, например, А ∨ ¬В ∨ С – элементарная дизъюнкция, а ¬ (А ∨ ¬В) – нет, т.к. присутствует отрицание выражения. Выражение А ∨ ¬В ∧ С также не является элементарной дизъюнкцией, т.к. в него входит конъюнкция.

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

Ранг элементарной конъюнкции или дизъюнкции – число аргументов ее образующих.

Дизъюнктивная нормальная форма (ДНФ) – это дизъюнкция попарно различных правильных элементарных конъюнкций (логическая сумма логических произведений), например, (X ∧ Y) ∨ (¬X ∧ Y ∧ Z) ∨ (X ∧ ¬Y ∧ Z).

Конъюнктивная нормальная форма (КНФ) – это конъюнкция попарно различных правильных элементарных дизъюнкций (логическое произведение логических сумм), например, (X ∨ Y) ∧ (¬X ∨ Y ∨ Z) ∧ (X ∨ ¬Y ∨ Z).

Любая логическая функция приводится к ДНФ или КНФ с помощью следующего алгоритма:

1) избавляются от импликации, эквивалентности, исключающего ИЛИ;

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

3) раскрывают скобки, применяя дистрибутивные (распределительные) законы логики.

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

Укажите, какое логическое выражение равносильно выражению ¬( А ∧ ¬B ∧ ¬C)

1) ¬A ∨ B ∨ C 2) ¬A ∨ B ∨ ¬C 3) ¬A ∧ B ∧ C 4) A ∧ B ∧ ¬C

Логическое выражение ¬(А ∧ (В ∨ ¬С) ∨ ¬А ∧ В) равносильно выражению

Запишем эти же преобразования, используя другие обозначения логических операций:

При решении заданий можно использовать любую форму записи. Определите, какая форма более наглядна и удобна для Вас.

СДНФ и СКНФ.

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

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

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

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

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

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

3. Соединить элементарные дизъюнкции знаком конъюнкции.

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

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

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

3. Соединить элементарные конъюнкции знаком дизъюнкции.

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

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

Рассмотрим решение задач на примере. Пусть две логические функции трех переменных заданы таблицей истинности.

Для функции F ₁ (A,B,C) построим СДНФ. По определению количество полных конъюнкций (слагаемых, представляющих собой произведение всех аргументов функции с отрицанием или без) равно количеству единиц в таблице истинности. В данном примере три единицы – на наборах 3, 5, 7.

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

2) Запишем дизъюнкцию конъюнкций (сумму произведений)

F1(A,B,C) = ¬А ∧ В ∧ С ∨ А ∧ ¬В ∧ С ∨ А ∧ В ∧ С

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

Построим СКНФ функции F2(A,B,C) по таблице истинности

1) Для каждой строки таблицы истинности с нулевым значением функции (наборы 2, 6, 7) запишем полную дизъюнкцию (логическую сумму аргументов), переменные, имеющие значения 1 в строке, входят в эту сумму с отрицанием, а переменные со значением 0 – без отрицания:

2) Все полученные дизъюнкции (логические суммы) связываются операциями конъюнкции.

F ₂ (A,B,C) = (А ∨ ¬В ∨ С) ∧ (¬А ∨ ¬В ∨ С) ∧ (¬А ∨ ¬В ∨ ¬С).

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

Анализ, упрощение и синтез логических схем.

Анализ логических схем.

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

Схеме соответствует логическая функция: .

По полученной формуле строится таблица истинности, проводится анализ данной схемы:

Определяются исходные данные X и Y, при которых значение логической функции равно 1.

Упрощение логической схемы.

Упрощение логической схемы сводится к упрощению соответствующей ей формулы с использованием законов логики.

Синтез логической схемы.

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

$A \or B$
$(A \and B) \or \neg A$
$(A \and B \and \neg C) \or (\neg D \and E \and F) \or (C \and D) \or B$

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

$A \rightarrow B = \neg A \vee B$
$A \leftrightarrow B = (A \wedge B) \vee (\neg A \wedge \neg B)$

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

$\neg (A \vee B) = \neg A \wedge \neg B$
$\neg (A \wedge B) = \neg A \vee \neg B$

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

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

$F = ((X \rightarrow Y) \downarrow \neg (Y \rightarrow Z))$

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

$\vee \wedge \neg$

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

$F = ((\neg X \vee Y) \downarrow \neg(\neg Y \vee Z)) = \neg ((\neg X \vee Y) \vee \neg (\neg Y \vee Z))$

$F = \neg ((\neg X \vee Y) \vee \neg (\neg Y \vee Z)) = (\neg \neg X \wedge \neg Y) \wedge (\neg Y \vee Z) = (X \wedge \neg Y) \wedge (\neg Y \vee Z)$

$F = (X \wedge \neg Y \wedge \neg Y) \vee (X \wedge \neg Y \wedge Z)$

$F = (X \wedge \neg Y ) \vee (X \wedge \neg Y \wedge Z)$

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

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

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

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

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

$\overline<x_1></p> <p>Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: \cdot \overline \cdot \overline$

в этом случае будет представлен без инверсии: \cdot \overline \cdot x_3" />

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

$f(x_1, x_2, x_3) = (\overline</p> <p>\and \overline \and \overline) \vee (\overline \and \overline \and x_3) \vee (\overline \and x_2 \and \overline) \vee (x_1 \and x_2 \and \overline)$

Переход от ДНФ к СДНФ

$Z \vee \neg Z = 1$

$Z \vee Z = Z$

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

Читайте также: