Как привести к днф

ДНФ и КНФ

Стандартный базис. Элементарные формулы — литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Полнота стандартного базиса. Примеры полных базисов: базис Жегалкина, штрих Шеффера, стрелка Пирса.

Стандартный базис — это набор из трех исходных операций булевой алгебры: сложения (объединения), умножения (пересечения) и отрицания.

Здесь мы будем называть литералом переменную x или ее отрицание x и обозначать xˆ. Булево пересечение нескольких литералов, определяемых различными переменными, т.е. выражение вида X = xˆ₁xˆ₂ . . . xˆ_л, называется элементарной конъюнкцией. Требование, чтобы все переменные были различны обусловливается следующим. Если в конъюнкцию входит несколько одинаковых литералов, то в силу коммутативности, ассоциативности и идемпотентности конъюнкции можно, переходя к эквивалентной формуле, оставить лишь один литерал (например, x ₁ x ₁ = x ₁). Если в конъюнкцию входит переменная и ее отрицание, то формула эквивалентна константе 0, поскольку x x = 0 и для любой формулы Y имеем Y x x = 0.

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

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

есть совершенная форма.

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

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

◀Условимся под x σ понимать формулу x, если σ = 1, и формулу x , если σ = 0. Пусть функция f(y₁, . . . , y_n) принимает значение 1 на векторе (t₁, . . . , t_n) (такой вектор называют конституэнтой единицы). Тогда элементарная конъюнкция также принимает значение 1 на этом наборе, но обращается в нуль на всех остальных n-мерных булевых векторах. Рассмотрим формулу

в которой сумма (объединение) распространяется на все те наборы (t₁, . . . , t_n) значений аргументов, на которых заданная функция принимает значение 1. Отметим, что множество таких наборов не пусто, так что в сумме есть по крайней мере одно слагаемое.

Нетрудно заметить, что формула Φ обращается в 1 при тех, и только при тех значениях переменных, при которых обращается в 1 рассматриваемая функция. Значит, формула Ψ представляет функцию f. ▶

Следствие 1.1. Стандартный базис является полным.

◀ Действительно, если функция не является константой 0, то она представима либо в виде СДНФ, которая является формулой над стандартным базисом. Константу 0 можно представить, например, формулой f(x₁, x₂, . . . , x_n) = x₁ x ₁. ▶

Пример 1.2. Рассмотрим функцию трех переменных m(x₁, x₂, x₃) (табл. 1.4), называемую мажоритарной функцией. Эта функция принимает значение 1, если больше половины ее аргументов имеют значение 1. Поэтому ее часто называют функцией голосования. Построим для нее СДНФ.

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

Аналогично строится СКНФ. Выбираем конституэнты нуля и для каждой составляем элементарную дизъюнкцию. Получим:

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

Пример 1.3. Множество из операций сложения по модулю 2, умножения и константы 1 называют базисом Жегалкина. Сложение по модулю 2 и умножение — базовые операции кольца Z2, выражения, составленные с их помощью — это многочлены над кольцом Z2. Кон- станта 1 в данном случае необходима для записи свободного члена. Поскольку xx = x, то все сомножители в многочлене имеют степень 1. Поэтому при записи многочлена можно обойтись без понятия степени. Примеры формул над базисом Жегалкина:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Любую такую формулу называют полиномом Жегалкина. Фактически полином Жегалкина — это многочлен над кольцом Z2.

Нетрудно сконструировать формулы над базисом Жегалкина, представляющие операции сложения и отрицания стандартного базиса (умножение у двух базисов общее):

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

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

Пример 1.4. Рассмотрим множество из единственной функции — штриха Шеффера*. Это множество полно, что следует из следующих легко проверяемых тождеств:

x =x|x, xy= x|y =(x|y)|(x|y), x+y= x | y =(x|x)|(y|y).

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

*Штрих Шеффера — бинарная, но не ассоциативная операция. Поэтому при использовании инфиксной формы следует быть внимательным: результат зависит от порядка выполнения операций. В этом случае рекомендуется явно указывать порядок операций при помощи скобок, например писать (x | y) | z, а не x | y | z, хотя обе формы равнозначны.

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

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

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

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

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

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

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

ДНФ записывается в следующей форме: F₁ ∨ F₂ ∨ . ∨ F_n, где F_i — элементарная конъюнкция

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой конъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.

Совершенная конъюнктивная нормальная форма (СКНФ)

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

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

КНФ записывается в следующей форме: F₁ ∧ F₂ ∧ . ∧ F_n, где F_i — элементарная дизъюнкция

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой дизъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.

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

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

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

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

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

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

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

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, Урок информатики
Все права защищены

КАК ПРИВЕСТИ ФУНКЦИЮ К ДНФ

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

Процесс приведения функции к ДНФ может быть выполнен следующими шагами:

1. Составление таблицы истинности для заданной функции. В таблице указывается значение функции для всех возможных комбинаций значений переменных.
2. Выделение строк таблицы, для которых функция равна единице.
3. Построение конъюнкции литералов для каждой выделенной строки. Литералы берутся из значений переменных, и если значение переменной в таблице равно нулю, то используется отрицание этой переменной.
4. Объединение всех конъюнкций в дизъюнкцию и получение ДНФ.

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

Расширяемся! Арендовал новые площади! Новости на ферме!

Пример сведения булевой функции к СДНФ и СКНФ

A.2.15 Построение совершенных дизъюнктивной и конъюнктивной нормальных форм (СДНФ и СКНФ)

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

Как преобразовать булеву функцию в СДНФ? Душкин объяснит

Приведение булевой функции к ДНФ

Что нужно знать о СДНФ — основные сведения

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

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

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

Примечание 1

Булева формула — формула из логики высказываний. В нее могут входить логические переменные, а также пропозициональные связки, такие как конъюнкцию \((«\vee»)\) , дизъюнкцию \((«\wedge»)\) , отрицание \((«\neg»)\) и иные.

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

Краткая теория

ДНФ является «суммой произведений». Более того, в качестве алгебраического действия «умножения» будет выступать операция И (то есть конъюнкция), а алгебраическим действием «сложения» выступает операция ИЛИ (то есть дизъюнкция). Сомножителями можно считать разные переменные, более того они могут входить в произведение как в инверсном, так и в прямом виде.

Представим пример простой ДНФ:

В структуре ДНФ могут быть повторяющиеся слагаемые, а в структуре каждого слагаемого могут находиться повторяющиеся сомножители. К примеру:

С точки зрения алгебры подобное клонирование лишено всякого смысла, потому что в булевой алгебре действие «умножения» любого выражения на само себя, а также действие сложения выражения с самим собой не изменяет результата \((x+x=x; x\times=x)\) . Действие сложения выражения со своей инверсией, а также умножение на свою инверсию производит константы \((x+\overline=1; x\times<\overline>=0)\) .

Возможно удалить из последнего выражения повторяющиеся сомножители и слагатели таким способом:

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

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

Приведем пример СДНФ:

Значение СДНФ проявляется в том, что:

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

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

Что нужно делать, чтобы найти СДНФ по таблице истинности? Основная схема построения:

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

Примечание 2

Таблица истинности — вид таблицы, который описывает логическую функцию, отражающую все значения функции с помощью вероятных значений аргументов функции. Таблица сформирована из n+1 столбцов и \(2^\) , где n будет числом используемых переменных. В таблице истинности в первых n-столбцах записывают все величины аргументов функции, а в n+1 столбце записываются значения функции, которая она принимает на этом наборе аргументов.

Алгоритм построения СДНФ для булевой функции

Булева функция (или по-другому логическая функция\функция в алгебре логики) от n переменных — отображение \(B^\rightarrow\) , где \(B=\) является булевым множеством.

Элементы булева множества 0 и 1 обычно рассматривают в качестве логических значений «ложно» и «истинно». В общем случае их рассматривают в качестве формальных символов, которые не обладают конкретным смыслом. Элементы декартова произведения \(B^\) можно назвать булевыми векторами. Множество булевых функций от каждого числа переменных обычно обозначают \(P^\) , а от n переменных — \(P^(n)\) . Булевы функции носят свои названия по имени известного английского математика Джорджа Буля.

Так выглядел Джордж Буль:

Для любой булевой функции \(f(\overrightarrow)\) , которая не равна тождественному нулю, есть СДНФ, которая задает ее.

Доказательство этой теоремы:

Для каждой булевой функции будет выполняться такое соотношение, которое называют в алгебре разложением Шеннона:

Такое соотношение просто проверить при помощи подстановки возможных значений \(x_ (0 \) и \(1)\) . Данная формула помогает вынести \(x_\) за знак функции. Шаг за шагом вынося \(x_, x_, x_\) за знак \(f(\overrightarrow)\) , можно получить такую формулу: \(f(\overrightarrow)=\neg\wedge>\wedge. \wedge>\wedge>\wedge(0,0. 0,0)\vee\wedge>\wedge. \wedgex_\wedge\wedge(0,0. 0,1)\vee. \vee\wedge\wedge. \wedge\wedgex_n\wedge(1,1. 1,0)\vee\wedge\wedge. \wedge\wedge\wedge(1,1. 1)\) .

Из-за использования этого соотношения к каждой из переменных увеличивается число конъюнктов в два раза. Так для функции от n переменных получается \(2^\) возможных наборов величин n переменных. Если на каком-то наборе \(f(\overrightarrow)=0\) , тогда весь соответствующий конъюнкт будет также равняться нулю и из представления этой функции он может быть исключен. Если \(f(\overrightarrow)=1\) , тогда в конъюнкте значение функции возможно опустить. В итоге для произвольной функции была построена СДНФ.

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

Представим пример построения СДНФ для медианы

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