что такое скнф и сднф
Построение СКНФ и СДНФ по таблице истинности
Вы будете перенаправлены на Автор24
Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.
Нормальная форма существует в двух видах:
не содержит одинаковых элементарных дизъюнкций;
ни одна из дизъюнкций не содержит одинаковых переменных;
каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.
Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.
Правила построения СКНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.
не содержит одинаковых элементарных конъюнкций;
ни одна из конъюнкций не содержит одинаковых переменных;
каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.
Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.
Правила построения СДНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.
Примеры нахождения СКНФ и СДНФ
Записать логическую функцию по ее таблице истинности:
Решение:
Воспользуемся правилом построения СДНФ:
\[F\left(x_1,\ x_2,\ x_3\right)=\left(\overline
Воспользуемся правилом построения СКНФ:
\[F\left(x_1,\ x_2,\ x_3\right)=\left(x_1\vee \overline
Готовые работы на аналогичную тему
Функция задана таблицей истинности:
Представить эту функцию в виде СДНФ и СКНФ.
Решение:
Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.
Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 0. Инвертировать нулевые значения переменных обязательно, т.к. иначе они превратят значения конъюнкций в нули основной функции.
Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:
\[F\left(x_1,x_2,x_3,x_4\right)=\left(\overline
Запишем логическую функцию в СКНФ.
Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.
Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:
\[F\left(x_1,x_2,x_3,x_4\right)=\left(x_1\vee x_2\vee x_3\vee x_4\right)\wedge \left(x_1\vee x_2\vee x_3\vee \overline
Совершенная нормальная форма — дизъюнктивная и конъюнктивная, правило построения
Что такое СДНФ
Нормальная форма логической формулы характеризуется тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации.
Существует две формы нормального типа: КНФ (конъюнктивная нормальная форма) и ДНФ (дизъюнктивная нормальная форма).
СДНФ — совершенная дизъюнктивная нормальная форма формулы. СДНФ — способ написания функции алгебры логики в качестве логического выражения.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
СДНФ формулы — это равнозначная ей формула, которая представляет собой дизъюнкцию элементарных конъюнкций, при которых функция достигает показателя «1».
ДНФ выглядит следующим образом:
СДНФ обладает некоторыми определенными свойствами:
К СДНФ возможно привести любую формулу алгебры логики. Исключение составляет только тождественно ложная формула. СДНФ можно получить как используя таблицы истинности, так и через равносильные преобразования.
При построении таблицы истинности важно помнить, что логические переменные со значением «0» необходимо брать с отрицанием.
Что такое СКНФ
СКНФ — совершенная конъюнктивная нормальная форма. Формулу можно назвать таковой, когда она — конъюнкция неповторяющихся элементарных дизъюнкций.
Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:
Правила построения по таблице истинности
Дизъюнктивная форма
Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.
Конъюнктивная форма
Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.
Алгоритм приведения к СДНФ и СКНФ
Рассмотрим логическую функцию в виде таблицы истинности.
Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:
Построим совершенную ДНФ:
И как результат получим следующую СДНФ:
Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:
Построим совершенную КНФ:
И как результат получим следующую СКНФ:
Рассмотрев алгоритмы построения СДНФ и СКНФ ясно, что в случае подавляющей части наборов значений переменных функция равна 0, то значительно легче построить и СДНФ для получения ее формулы, а в обратном случае — СКНФ.
Доказательство эквивалентности
Доказать эквивалентность формул можно двумя способами.
Далее следуют примеры с некоторыми эквивалентными преобразованием в булевой алгебре и новыми эквивалентностями, которые возможно получить с их помощью.
Поглощение
Склеивание
Обобщенное склеивание
\(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
Через применение закона де Моргана и правила \( 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) = (\overline
\(f(\widetilde x^3) = (\overline
\(=(\overline
Что значит нормальна форма:
Нормальная форма логической формулы не содержит знаков импликации, эквиваленции и отрицания неэлементарных формул.
Существует два вида нормальной формы: конъюнктивная нормальная форма, т. е. конъюнкция нескольких дизъюнкций (КНФ) и дизъюнктивная нормальная форма, т. е. дизъюнкция нескольких конъюнкций (ДНФ), пример:
КНФ: \(\left (x\vee \bar
ДНФ: \( \left (x\wedge \bar
СКНФ: \( (x\vee y\vee \bar
СДНФ: \( ( x\wedge y\wedge \bar
| Логика | булева алгебра |
| ∨ | + |
| ∧ | ∙ |
Правила построения СДНФ и СКНФ по таблице истинности
Пример: Восстановите логическую функцию по ее таблице истинности:
| x | y | z | F |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
РЕШЕНИЕ
СДНФ составляется на основе таблицы истинности по следующему правилу:
Получаем СДНФ:
СКНФ составляется на основе таблицы истинности по правилу:
Что такое скнф и сднф
СДНФ и СКНФ
Нормальная форма логической функции – если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией.
Ранг элементарной конъюнкции или дизъюнкции — это число аргументов ее образующих.
Пример: 
Элементарная конъюнкция третьего порядка.
Элементарная дизъюнкция второго порядка.
Конъюнктивная нормальная форма (КНФ) содержит элементарные дизъюнкции, связанные между собой операциями конъюнкции.
Пример:
Дизъюнктивная нормальная форма (ДНФ) содержит элементарные конъюнкции, связанные между собой операциями дизъюнкции.
Совершенная конъюнктивная нормальная форма (СКНФ):
Совершенная дизъюнктивная нормальная форма (СДНФ)
Убедиться, является ли данная формула ДНФ, КНФ, СДНФ или СКНФ:
а) Данная формула является КНФ (конъюнкция элементарных дизъюнкций), но не СКНФ, так как элементарные дизъюнкции не являются полными.
б) Формула не является ДНФ, так как последняя конъюнкция не является элементарной. Но формулу можно с помощью закона Де Моргана преобразовать к равносильному виду 
который является ДНФ, но не СДНФ (не все элементарные конъюнкции полны).
в) Формула не является ни ДНФ, ни КНФ, поскольку содержит импликацию.
г) СДНФ, состоящая из одной элементарной полной конъюнкции; либо КНФ, но не СКНФ, так как состоит из трех элементарных неполных дизъюнкций.
Алгоритм образования СКНФ и СДНФ по таблице истинности
1. Выделить в таблице истинности все строки, в которых функция принимает значения 0.
2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные:
а) если значение переменной равно 0, то записывается сама переменная,
б) если значение переменной равно 1, то записывается инверсия этой переменной
3. Соединить элементарные дизъюнкции знаком конъюнкции.
Алгоритм образования СКНФ и СДНФ по таблице истинности
1. Выделить в таблице истинности все строки, в которых функция принимает значения 1.
2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие переменные:
а) если значение переменной равно 0, то записывается инверсия этой переменной,
б) если значение переменной равно 1, то записывается сама переменная.
3. Соединить элементарные конъюнкции знаком дизъюнкции.