Для всякой логической формулы с помощью тождественных преобразований можно построить бесконечно много равносильных ей формул. В алгебре логики одной из основных задач является поиск канонических форм (т. е. формул, построенных по единому правилу, канону).
Если логическая функция выражена через дизъюнкцию, конъюнкцию и отрицание переменных, то такая форма представления называется нормальной.
Среди нормальных форм выделяются совершенные нормальные формы (такие формы, в которых функции записываются единственным образом).
Совершенная дизъюнктивная нормальная форма (СДНФ)
Определение. Формулу называют элементарной конъюнкцией, если она образованна конъюнкцией некоторого числа переменных или их отрицаний.
Определение. Формула называтся дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией неповторяющихся элементарных конъюнкций.
Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х1, х2, …, хk, причем на i-м месте этой конъюнкции стоит либо переменная хi, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.
Совершенная конъюнктивная нормальная форма (СКНФ)
Определение. Формулу называют элементарной дизъюнкцией, если она образована дизъюнкцией некоторого числа переменных или их отрицаний.
Определение. Формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией неповторяющихся элементарных дизъюнкций.
Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х1, х2, …, хk, причем на i-м месте этой дизъюнкции стоит либо переменная хi, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.
Алгоритм построения СДНФ по таблице истинности
Алгоритм построения СКНФ по таблице истинности
Пример: Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.
| 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, Урок информатики
Все права защищены
Что значит нормальна форма:
Нормальная форма логической формулы не содержит знаков импликации, эквиваленции и отрицания неэлементарных формул.
Существует два вида нормальной формы: конъюнктивная нормальная форма, т. е. конъюнкция нескольких дизъюнкций (КНФ) и дизъюнктивная нормальная форма, т. е. дизъюнкция нескольких конъюнкций (ДНФ), пример:
КНФ: \(\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 |
РЕШЕНИЕ
СДНФ составляется на основе таблицы истинности по следующему правилу:
Получаем СДНФ:
СКНФ составляется на основе таблицы истинности по правилу:
Построение СКНФ и СДНФ по таблице истинности
Вы будете перенаправлены на Автор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.
2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные:
а) если значение переменной равно 0, то записывается сама переменная,
б) если значение переменной равно 1, то записывается инверсия этой переменной
3. Соединить элементарные дизъюнкции знаком конъюнкции.
Алгоритм образования СКНФ и СДНФ по таблице истинности
1. Выделить в таблице истинности все строки, в которых функция принимает значения 1.
2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие переменные:
а) если значение переменной равно 0, то записывается инверсия этой переменной,
б) если значение переменной равно 1, то записывается сама переменная.
3. Соединить элементарные конъюнкции знаком дизъюнкции.
Совершенные нормальные формы СДНФ, СКНФ
Определение. СДНФ (совершенная ДНФ) – это такая ДНФ, в которой каждая элементарная конъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу, элементарные конъюнкции не повторяются.
Определение. СКНФ (совершенная КНФ) – это такая КНФ, в которой каждая элементарная дизъюнкция содержит все элементарные высказывания, либо их отрицания по одному разу, элементарные дизъюнкции не повторяются.
Каждая формула имеет одну единственную СДНФ и одну единственную СКНФ. Тавтология не имеет СКНФ, а противоречие – СДНФ.
Как известно, каждая формула логики высказываний представляет некоторую булеву функцию. Возникает обратный вопрос: можно ли всякую булеву функцию представить некоторой формулой логики высказываний? Можно указать алгоритм, который позволяет по таблице истинности произвольной булевой функции от любого числа переменных построить некоторую формулу логики высказываний в СДНФ.
Если рассматривать произвольную функцию, то необходимо выделить все наборы переменных, для которых функция принимает значение 1 и каждому набору поставить в соответствие конъюнкцию переменных и их отрицаний. Рассматриваемая функция будет представлена дизъюнкцией этих конъюнкций.
Таким образом, установлена процедура, которая позволяет для всякой булевой функции записать соответствующую ей формулу.
| x | y | z | f(x,y,z) |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
Также для построения СДНФ и СКНФ используется семантическое дерево.
ПРИМЕР. Построить СДНФ и СКНФ функции заданной своим семантическим деревом.
Так как СДНФ сохраняет 1, то будем рассматривать листы на которых изображены 1. Листья просматриваются слева направо.
Путь от корня дерева к первому листу с единицей определяет конституенту единицы 
, это соответствует значению функции F(0,1,c). Путь от корня дерева ко второму листу с единицей определяет конституенту единицы 
. Путь от корня дерева к третьему листу с единицей определяет конституенту единицы 
. Путь от корня дерева к четвертому листу с единицей определяет конституенту единицы 
.
Дизъюнкция конституент единицы образует СДНФ 
.
Для того чтобы построить СКНФ будет рассматривать листья на которых изображен 0, так как СКНФ сохраняет 0, Снова просматривает листья слева направо. Путь от корня дерева к первому листу с нулем определяет конституенту нуля 
Путь от корня дерева ко второму листу с нулем определяет конституенту нуля 
Путь от корня дерева к третьему листу с нулем определяет конституенту нуля 
Путь от корня дерева к четвертому листу с нулем определяет конституенту нуля 
.
Конъюнкция конституент нуля образует СКНФ
Полином Жегалкина
Пусть M – некоторое произвольное подмножество булевого куба 
, 
, 
– номер вектора 
, 
– его вес, 
– номера отличных от нуля координат вектора 
.
Определение. Формула вида 
, (4.1)
где суммирование ведется по модулю два, а коэффициенты 
равны либо 0, либо 1, называется полиномом Жегалкина от n переменных.
Если суммирование в формуле (4.1) ведется по всем булевым векторам длины n, слагаемые идут в порядке возрастания номеров булевых векторов и 
, то говорят, что полином Жегалкина записан в канонической форме.
Теорема 4.3.Каждая булева функция от n переменных может быть реализована в виде канонического полинома Жегалкина от n переменных, причем единственным образом.
Например, полином Жегалкина от двух переменных 
в канонической форме запишется так: 
.
Для представления булевой функции в форме полинома Жегалкина воспользуемся треугольником Паскаля.
ПРИМЕР. Построим полином Жегалкина для функции f = (10011110).
Полином Жегалкина можно получить с помощью треугольника Паскаля по единицам его левой стороны по таблице следующим образом Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю для двух соседних элементов предыдущей строки. Левая сторона треугольника для функции f содержит шесть единиц. Многочлен Жегалкина будет содержать шесть слагаемых. Первая единица треугольника соответствует набору (000). Первое слагаемое многочлена есть 1. Третья снизу единица в левой стороне треугольника соответствует набору (101). В качестве слагаемого многочлена берем x1x3. Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.
| N | x1x2x3 | f | Треугольник Паскаля |
| 1 x3 x2 x2x3 x1 x1x3 x1x2 x1x2x3 | 000 001 010 011 100 101 110 111 | 1 0 0 1 1 1 1 0 | 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 |
Тогда 