Построение таблицы истинности онлайн | СКНФ | СДНФ | Полином Жегалкина | Таблица истинности булевой функции онлайн

Содержание

Что такое таблица истинности?
Что такое булева функция
Что умеет калькулятор
.1.2. Теорема Блейка и алгоритм Блейка –Порецкого
Алгебраическая нормальная форма (анф, полином жегалкина)
Алгоритм построения полинома жегалкина булевой функции
Алгоритм построения сднф для булевой функции
Алгоритм построения скнф для булевой функции
Задачи
Используемые символы
Как задать логическую функцию
Как пользоваться калькулятором
Логические операции
Многочлены жегалкина
Обозначения логических операций
Определение днф и кнф
Построение полинома жегалкина:
Построение совершенной дизъюнктивной нормальной формы:
Построение совершенной конъюнктивной нормальной формы:
Примеры построения различных представлений логических функций
Совершенные днф и кнф
Сокращенные днф
Способы представления булевой функции

Что такое таблица истинности?

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

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

Что такое булева функция

Булева функция f(x1, x2, … xn) — это любая функция от n переменных x1, x2, … xn, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1.

Что умеет калькулятор

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

.1.2. Теорема Блейка и алгоритм Блейка –Порецкого

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

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

Рассмотрим основанный на теореме Блейка алгоритм, который организует поиск сокращенной ДНФ эффективнее, чем это предложено в теореме.

Алгоритм Блейка –Порецкого.

Начало. Задана произвольная ДНФ булевой функции.

Шаг 1. Построим список троичных векторов, представляющих конъюнкции ДНФ. Удалим из списка все векторы, поглощаемые другими. Если останется лишь один вектор, пойдем на конец. Иначе обозначим второй из оставшихся векторов через α.

Шаг 2. Найдем для вектора α очередной смежный вектор β среди векторов, расположенных в списке выше α. Если такого вектора β нет, то идем на шаг 5. Иначе обобщенно склеим α и β и полученный вектор γ припишем к списку последним.

Шаг 3. Если вектор γ поглощается хотя бы одним вектором из списка, то удалим γ (в частном случае γ может совпадать с одним из векторов списка, тогда удалим именно приписанный вектор γ, иначе произойдет «зацикливание» алгоритма, так как вектор γ будет вновь появляться в списке) и идем на шаг 2. Если вектор γ не поглощается, то удалим все векторы, поглощаемые им.

Шаг 4. Если вектор α не удален, то идем на шаг 2.

Шаг 5. Если вектор α был не последним в списке, то выберем в качестве нового α следующий по списку вектор и вернемся на шаг 2.

Конец. Неудаленные векторы задают сокращенную ДНФ функции.

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

Пример. Продемонстрируем алгоритм Блейка-Порецкого, сопровождая его выполнение матрицами Грея.

Начало. Задана произвольная ДНФ функции из примера к алгоритму Квайна –МакКласки:

Шаг 1. ДНФ представляем списком векторов и нумеруем их.

Вычеркиваем из списка третий вектор, поглощаемый шестым (левая из матриц на следующей странице демонстрирует это поглощение). Остальные векторы не поглощаются (правая матрица демонстрирует состояние списка). Выбираем в качестве α второй вектор.

Шаг 2. Для α нет смежного вектора среди предыдущих, идем на шаг 5.

Шаг 5. Так как вектор α был не последним в списке, то в качестве нового α рассматриваем следующий по списку (четвертый) вектор (см. ниже) и возвращаемся на шаг 2.

Шаг 2. Вектор α не смежен первому вектору, но смежен второму (по первой компоненте). Обозначаем второй вектор через β. Обобщенно склеиваем α и β и записываем результат – вектор γ в список седьмым. Отмечаем, что он получен из четвертого и второго (левая нижняя матрица показывает склеивание).

Шаг 3. Вектор γ не поглощается ни одним вектором, поэтому остается в списке. Удаляется второй вектор как поглощаемый вектором γ.

Шаг 4. Так как вектор α не был удален, идем на шаг 2.

Шаги 2, 5. Так как для вектора α перебраны все предыдущие, то идем на шаг 5. Так как α был не последним в списке, то в качестве нового α рассматриваем пятый вектор (см. ниже) и возвращаемся на шаг 2.

Шаги 2 –4. Вектор α не смежен первому, но смежен четвертому вектору β.
Обобщенно склеиваем α и β и записываем результат γ в список восьмым. Вектор γ не поглощается ни одним вектором, поэтому остается в списке. Вектор γ не поглощает ни один вектор, в том числе α. Идем на шаг 2.

Шаги 2, 5. Для вектора α перебраны все предыдущие, поэтому новым α становится шестой вектор, идем на шаг 2.

Шаги 2 –3. Вектор α смежен четвертому вектору β (см. ниже). Обобщенно склеиваем α и β и записываем результат γ в список девятым. Вектор γ совпадает с восьмым вектором, то есть поглощается им, поэтому тут же удаляем вектор γ из списка. Идем на шаг 2.

Шаги 2, 5. Для вектора α больше нет смежных среди предыдущих, поэтому новым α будет седьмой вектор, идем на шаг 2.

Шаги 2 –4. Вектор α смежен пятому вектору β. Обобщенно склеиваем их и записываем результат γ в список десятым. Вектор γ не поглощается ни одним из предыдущими векторов списка и не поглощает ни один вектор, поэтому идем на шаг 2.

Шаги 2 –3. Вектор α смежен шестому вектору β. Обобщенно склеиваем их и записываем результат γ в список одиннадцатым. Вектор γ совпадает с десятым вектором, поэтому тут же удаляем γ из списка. Идем на шаг 2.

Шаги 2, 5. Так как для α перебраны все предыдущие, то в качестве нового α рассматриваем восьмой вектор и идем на шаг 2.

Шаги 2 –4. Вектор α смежен только седьмому вектору β. Обобщенно склеиваем их и записываем результат γ в список двенадцатым. Вектор γ поглощает четвертый, седьмой, восьмой и десятый векторы, поэтому удаляем их из списка. Так как вектор α оказался вычеркнутым, идем на шаг 5.

Другие сокращения: Что такое КБК в реквизитах. КБК на 2020 год

Шаг 5. Выбираем в качестве нового α двенадцатый вектор и идем на шаг 2.

Шаги 2, 5. Так как для двенадцатого вектора нет смежных среди предыдущих, то идем на шаг 5. Вектор был последним в списке, поэтому идем на конец.

Конец. Невычеркнутые из списка векторы задают сокращенную ДНФ:

Результат совпадает с сокращенной ДНФ, полученной ранее (подраздел 11.1.1) алгоритмом Квайна-МакКласки, и это естественно, так как сокращенная ДНФ булевой функции единственна.

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

Оставшиеся в списке векторы образуют решение. •

Итак, нами изучен первый этап минимизации булевых функций – построение сокращенной ДНФ:

– из совершенной ДНФ (алгоритм Квайна-МакКласки);

– из произвольной ДНФ (алгоритм Блейка –Порецкого).

Алгебраическая нормальная форма (анф, полином жегалкина)

Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.

Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм построения полинома жегалкина булевой функции

Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.

Построить таблицу истинности для функции
Добавить новый столбец к таблице истинности и записать в 1, 3, 5… ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6… прибавить по модулю два значения из соответственно 1, 3, 5… строк.
Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10… строк, а к 3, 4, 7, 8, 11, 12… строкам аналогично предыдущему пункту прибавить переписанные значения.
Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
Выписать булевы наборы, на которых значение последнего столбца равно единице
Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.

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

Построить таблицу истинности для функции
Найти все наборы аргументов, на которых функция принимает значение 1
Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
Объединить все простые конъюнкции с помощью дизъюнкции

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

Построить таблицу истинности для функции
Найти все наборы аргументов, на которых функция принимает значение 0
Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
Объединить все простые дизъюнкции с помощью конъюнкции

Задачи

Задача 4.1.
Проверьте все приведенные в
«лекции 4»

эквивалентности (1) — (8), непосредственно вычисляя функции, представляемые их
левыми и правыми частями.

Задача 4.2. Назовем логическим произведением формулу вида подформулысомножителями.
Аналогично, логической суммой назовем формулу вида подформулыслагаемыми.

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

Если в логическом произведении один из сомножителей равен 0, то и все произведение равно 0.
Если в логической сумме одно из слагаемых равно 1, то и вся сумма равна 1.
Если в логическом произведении n >= 2 и есть сомножитель, равный 1, то его можно вычеркнуть.
Если в логической сумме n >= 2 и есть слагаемое, равное 0, то его можно вычеркнуть.

Задача 4.3. Используя основные тождества, доказать эквивалентность
следующих пар формул.

Задача 4.4. Докажите теорему 4.1, проверив, что
для любого набора значений аргументов $f( sigma_1, ldots , sigma_n) = mathcal{D}_f( sigma_1, ldots , sigma_n)$ $f( sigma_1, ldots , sigma_n) = mathcal{C}_f( sigma_1, ldots , sigma_n)$

Задача 4.5.

Предложите процедуру, которая по произвольной элементарной конъюнкции строит эквивалентную ей совершенную ДНФ.
Предложите процедуру, которая по произвольной элементарной дизъюнкции строит эквивалентную ей совершенную КНФ.

Задача 4.6.
Докажите, что для любого k <= n каждую булеву функцию $f in mathcal{P}_n$ представление называется разложением k=n из него получается совершенная ДНФ из теоремыЗадача 4.7. Докажите предложение 4.1, используя индукцию по общему количеству функций в формуле.

Задача 4.8. Как изменить (3)-ий, (4)-ый и (5)-ый этапы процедуры «Приведение к совершенной ДНФ «, чтобы в результате получить процедуру «Приведение к совершенной КНФ «, которая по произвольной формуле строит эквивалентную совершенную КНФ.

Задача 4.9. Найти эквивалентные сокращенные ДНФ и доказать эквивалентность следующих пар формул:

Задача 4.10. Используя основные эквивалентности, найти эквивалентные многочлены Жегалкина и доказать эквивалентность следующих формул:

Задача 4.11. Найти сокращенную дизъюнктивную нормальную форму и многочлен Жегалкина (методом неопределенных коэффициентов) для следующих функций от трех аргументов. Считаем, что наборы их аргументов упорядочены
лексикографически и значения на них задаются последовательностью 8 нулей и единиц.

Используемые символы

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a, x, a1, B, X, X1, Y1, A123 и так далее.

Для записи логических операций можно использовать
как обычные символы клавиатуры (*, , !, ^, ->, =), так и символы, устоявшиеся в литературе (∧, ∨, ¬, ⊕, →, ≡).

Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.

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

Как задать логическую функцию

Есть множество способов задать булеву функцию:

таблица истинности
характеристические множества
вектор значений
матрица Грея
формулы

Рассмотрим некоторые из них:

Чтобы задать функцию через вектор значений необходимо записать вектор из 2n нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).

Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c

Как пользоваться калькулятором

Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
Укажите действия, которые необходимо выполнить с помощью переключателей
Укажите, требуется ли вывод решения переключателем «С решением»
Нажмите на кнопку «Построить»

Логические операции

Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).

Другие сокращения: Спэк | Производитель пожарных линейных извещателей

Многочлены жегалкина

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

Определение 4.4. Многочленами Жегалкина
назваются формулы над множеством функций FJ={ 0, 1, *, }
(здесь * — это другое обозначение конъюнкции).

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

Поскольку для и * справедливы законы
ассоциативности, мы будем при записи многочлена Жегалкина опускать
скобки, считая, что * связывает аргументы сильнее, чем

Нетрудно проверить, что справедливы следующие эквивалентности:

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

Теорема 4.3.
Для любой булевой функции существует задающий ее многочлен Жегалкина.
Он единственен с точностью до перестановок слагаемых и порядка переменных
в конъюнкциях.

Доказательство Существование такого многочлена следует из того,
что для любой ДНФ или КНФ можно с помощью указанных эквивалентностей
найти эквивалентный многочлен Жегалкина: (J1)-(J3) позволяют заменять все
вхождения и *, а (J4) — перемножать получившиеся после такой замены многочлены.Для доказательства единственности представления подсчитаем
число различных многочленов Жегалкина от элементарная конъюнкция имеет вид X_i1 * … * X_ik,
где 1 <= i₁ < … < i_k <= n
.
Таких конъюнкций столько же, сколько подмножеств множества $mathbf{X}={X_1,ldots, X_n}$ 2_n.
(Конъюнкция, соответствующая пустому подмножеству переменных равна 1).
Упорядочим их произвольным образом (например, лексикографически): $K_1, K_2,ldots, K_{2^n}$ многочлен Жегалкина единственным образом можно представить как суммугде каждый из коэффициентов $alpha _{i}$ многочленов Жегалкина равно $2^{2^n}$ n переменных. Поэтому каждая функция задается в
точности одним многочленом Жегалкина.Пример 4.3. Пусть функцияf(X₁,X₂,X₃)
задается ДНФполином Жегалкина, который также задает эту функцию.Сначала заменяем *, а затем,применяя
эквивалентность (J1), устраняем отрицания и получаем:

Перемножив по правилам (J4), получим:

Эквивалентность (J3) позволяет устранить

Снова, используя (J4), перемножим первые две скобки и устраним повторения
переменных в конъюнкциях:

Упростим эту сумму, используя эквивалентности: многочлен Жегалкинаэквивалентный исходной ДНФфункцияf(X₁, …, X_n)
задана таблично, то для построения реализующего ее многочлена Жегалкина можно применить метод
неопределенных коэфициентов. Сопоставим i -ому набору значений переменных $K_i=bigwedge_{sigma_i^j=1} X_j$ K₁ — пустая конъюнкция, K₂ = X_n,
K₃ = X_n-1,
K₄ = (X_n * X_n-1).
и т.д. Тогда для получения нужного многочлена Жегалкина достаточно
определить все коэффициенты $alpha _{i}, i = 1, dots , 2^{n}$ равенство значения переменных из набора $sigma _{i}, i = 1, dots , 2^{n}$ 2ⁿлинейных уравнений относительно 2ⁿ
неизвестных коэффициентов $alpha _{i}$ многочлен
Жегалкина. Эта система треугольная и легко решается «сверху-вниз»:
каждое $alpha _{i}$ $alpha _{1}, dots , alpha _{i-1}$ $sigma _{i}$

Пример 4.4. Рассмотрим в качестве примера функцию f(X1, …, Xn), заданную
следующей таблицей.

Многочлен Жегалкина для нее (как и для любой функции от 3-х переменных)
представляется в виде

В этом представлении в индексах у коэффициентов

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

Следовательно, функцияf(X1, X2, X3) представляется многочленом Жегалкина

Обозначения логических операций

И (AND):&•∧*
ИЛИ (OR):∨
НЕ (NOT):¬!
Исключающее ИЛИ (XOR):⊕^
Импликация:->→=>
Эквивалентность:=~≡<=>
Штрих Шеффера:↑|
Стрелка Пирса:↓

Определение днф и кнф

В этом разделе мы интересуемся представлением произвольной булевой
функции посредством формул специального вида, использующих только
операции $mathbf{X}={X_1,ldots, X_n}$ i=1,…,n обозначения: $X_{i_1}^{sigma_1}wedge X_{i_2}^{sigma_2}wedge ldots wedge X_{i_k}^{sigma_k}(X_{i_1}^{sigma_1}vee X_{i_2}^{sigma_2}vee ldots vee X_{i_k}^{sigma_k})$ $sigma_{i_j} in {0,1}$ $X_{i_j} neq X_{i_r}$ элементарной конъюнкцией ( элементарной дизъюнкцией ).Определение 4.2. Формула дизъюнктивной нормальной формой (ДНФ),
если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид $mathcal{D}= K_1 vee K_2vee ldots vee K_r$ элементарная конъюнкция . совершенной ДНФ, если в каждую из
ее конъюнкций конъюнктивной нормальной формой (КНФ),
если она является конъюнкцией элементарных дизъюнкций,
т.е. $mathcal{C}= D_1 vee D_2vee ldots vee D_r$ D_j (j=1,…,r)
— это элементарная дизъюнкция . Она является совершенной КНФ,
если в каждую D_j входят все n переменных из

Построение полинома жегалкина:

Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:

Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:

Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:

Окончательно получим такую таблицу:

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

{ 0, 0, 1 } — c, { 0, 1, 0 } — b, { 0, 1, 1 } — bc, { 1, 1, 0 } — ab, { 1, 1, 1 } — abc

Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc

Построение совершенной дизъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает истинное значение: { 0, 0, 1 } { 0, 1, 0 } { 0, 1, 1 } { 1, 0, 1 } { 1, 1, 1 }

В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:

K1: { 0, 0, 1 } — ¬a¬bcK2: { 0, 1, 0 } — ¬ab¬cK3: { 0, 1, 1 } — ¬abcK4: { 1, 0, 1 } — a¬bcK5: { 1, 1, 1 } — abc

Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:

K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 = ¬a¬bc ∨ ¬ab¬c ∨ ¬abc ∨ a¬bc ∨ abc

Построение совершенной конъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает ложное значение: { 0, 0, 0 } { 1, 0, 0 } { 1, 1, 0 }

В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:

D1: { 0, 0, 0 } — a∨b∨cD2: { 1, 0, 0 } — ¬a∨b∨cD3: { 1, 1, 0 } — ¬a∨¬b∨c

Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:

D1 ∧ D2 ∧ D3 = (a∨b∨c) ∧ (¬a∨b∨c) ∧ (¬a∨¬b∨c)

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

Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬ab∨¬bc∨ca

1. Построим таблицу истинности для функции

Совершенные днф и кнф

Рассмотрим произвольную булеву функцию f(X₁,…,X_n)
, зависящую
от переменных из N_f
множество наборов значений переменных, на которых f принимает значение 1, а через N_f^— множество наборов, на которых f принимает значение 0,
т.е. $N_f^ = {(sigma_1,ldots, sigma_n) | f(sigma_1,ldots, sigma_n)=1}$ $N_f^-= {(sigma_1,ldots, sigma_n) | f(sigma_1,ldots, sigma_n)=0}$

Определим по этим множествам две формулы:

Теорема 4.1.

Если функция f не равна тождественно 0, то
формула $mathcal{D}_f$ — это совершенная ДНФ, задающая функцию f.
Если функция f не равна тождественно 1, то
формула $mathcal{C}_f$ — это совершенная КНФ, задающая функцию f.

Доказательство получается непосредственным вычислением значения каждой из указанных
формул с учетом того, что для любого $1^{sigma } = sigma$ $0^{sigma } = neg sigma$

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

Приведенные выше формулы для $mathcal{D}_f$ $mathcal{C}_f$ совершенные ДНФ и КН по табличному представлению
функции f (Каким образом?). Можно ли получить такие специальные
представления по произвольной формуле, задающей f, не выписывая ее
полной таблицы? Приводимая ниже процедура позволяет это сделать, используя основные эквивалентности формул.

Процедура Приведение к совершенной ДНФ

Вход: формула .

Используя эквивалентность (7), заменить все вхождения
функции в на и
затем использовать эквивалентность (8) для замены всех вхождений функции
на и
Используя законы де Моргана (5) и снятия двойного отрицания (4),
внести все знаки отрицания внутрь скобок так, чтобы все оставшиеся
отрицания находились непосредственно перед переменными.
Получившаяся после шага (2) формула имеет одну из
двух форм:
Поскольку каждая из формул $Phi _{1}$ , $Phi _{2}$ имеет
меньшую глубину, чем формула , то предположим по индукции, что для них
уже построены эквивалентные ДНФ
и , соответственно.
Тогда в случае (а) имеем:
Каждый член этой дизъюнкции представляет собой
конъюнкцию переменных и их отрицаний. Применяя эквивалентности групп (1), (2) и
(6), можно удалить из нее повторения переменных, после чего она превратится
в некоторую элементарную конъюнкцию или константу. Проделав такие
преобразования со всеми парами (i,j), 1 <= i <= r, 1 <= j <= s, и удалив, если
потребуется, константы 0,
мы получим ДНФ, эквивалентную исходной формуле
В случае (б) формула
сама уже является ДНФ.
Используя эквивалентности групп (1), (2) и (6), удалить
из получившейся после шага (3) формулы повторные вхождения одинаковых
конъюнкций.
Пусть после шага (4) получилась ДНФ $Phi^{primeprime}= K_1 vee K_2 vee ldots vee K_m$ .
Чтобы получить эквивалентную совершенную ДНФ, построим для
каждой K_i (i=1,…, m)
, эквивалентную совершенную ДНФ
(см. задачу 4.5),заменим ею K_i, а затем устраним повторения одинаковых
конъюнкций.

Другие сокращения: Спасательные подразделения - Учреждения системы МЧС России - МЧС России

Из формулировок эквивалентностей (7) и (8) непосредственно вытекает

Предложение 4.1.
На этапе (1) процедуры при последовательном выполнении преобразований
(7), а затем — (8), до тех пор, пока ни одно из них не применимо, полученная
в результате формула не будет содержать функций .

Доказательство этого предложения оставляем в виде упражнения (см. задачу 4.7).

Следующее утверждение гарантирует корректность этапа (2).

Предложение 4.2. На этапе (2) процедуры при любом порядке выполнения преобразований
групп (4) и (5) до тех пор, пока ни одно из них не применимо, в полученной
в результате формуле все знаки отрицания будут стоять непосредственно
перед переменными.

Перед доказательством этого утверждения введем некоторые обозначения.
Напомним, что в определениях 3.2 и 3.3 для каждой формулы глубинаподформулы вида высоту $3^{dep(Psi )}-1$ высота всей формулыподформул. Например, для приведенной выше формулы $H(Phi )= h(neg (X Y)) h(neg (X vee neg Z)) h(neg Z) = (3^{1}-1) (3^{2}-1) (3^{0}-1) = 10$

Доказательство предложения 4.2 проведем
индукцией по высоте формул.

Базис индукции. Если Шаг индукции. Предположим, что при n <= k для всех
формул высоты n Предложение 4.2 выполнено.
Пусть подформулуснятие двойного отрицания (4),
либо один из законов де Моргана (5). ( Объясните почему.)
Пусть эквивалентную формулуn=k 1, что завершает индукционный шаг и все доказательство.

Рассмотрим применение процедуры приведения к совершенной ДНФ на примере.

Пример 4.1. Пусть формула

На (1)-ом этапе процедуры получаем следующую цепочку эквивалентностей:

На (2)-ом этапе вносим отрицание внутрь первой скобки и получаем формулу

Устранив двойное отрицание, получим

Нетрудно видеть, что это уже ДНФ.
Удалим на (4)-ом этапе повторное вхождение первой конънкции и получим ДНФ

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

Подставив эти формулы в $Phi _{1}$ совершенную ДНФ, эквивалентную исходной формуле ДНФ $Phi _{1}$ совершенная ДНФ $Phi _{2}$ совершенные ДНФ и КНФ обладают важным свойством единственности,
которое следует из их конструкции в теореме 4.1.

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

Это следствие позволяет предложить следующую процедуру для проверки эквивалентности формул

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

Замечание. Аналогичную процедуру можно построить с использованием совершенных КНФ.

Сокращенные днф

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

Напомним, что мы рассматриваем булевы функции над переменными $mathbf{X}={X_1,ldots, X_n}$ элементарной конъюнкцией $K=X_{i_1}^{sigma_1}wedge X_{i_2}^{sigma_2}wedge ldots wedge X_{i_k}^{sigma_k}$ K принимает значение 1. Нетрудно понять, что это множество содержит 2_(n-k)
наборов, в которых каждая из входящих в K переменных $X_{i_r} (1 leq rleq k)$ $sigma _{r}$ (n-k) переменных произвольны.Определение Пусть f — произвольная булева функция над Элементарная конъюнкцияK называется допустимой дляf, если Элементарная конъюнкцияK называется максимальной дляf, если для любой элементарной конъюнкцииL из условия

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

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

Примером сокращенной ДНФ является формула

Сокращенную ДНФ можно получить из произвольной ДНФD,
используя процедуру, называемую методом Блейка.

Применять, сколько возможно, закон поглощения
(П3):
слева направо при условии, что конъюнкция $(K_{1} wedge K_{2})$
непротиворечива, т.е. не содержит одновременно некоторую переменную и ее отрицание.
(Заметим, что на этом этапе число элементарных конъюнкций в ДНФ, вообще говоря, увеличивается).
Применять, сколько возможно, правило поглощения
(П1): .
Затем удалить повторные вхождения конъюнкций.

Теорема 4.2. В результате применения метода Блейка к произвольной ДНФ
через конечное число шагов будет получена эквивалентная ей сокращенная ДНФ.

Доказательство
Пусть после (1)-го этапа процедуры ДНФD функции f
преобразовалась
в эквивалентную ДНФD₁. Покажем, что
для всякой допустимой для fэлементарной конъюнкцияK в D₁ найдется такая
конъюнкция K’, что $N_K^ subseteq N_{K'}^$ K.Базис индукции. Пусть K содержит все n
переменных из $N_K^ subseteq N_{D_1}^$ K’, для которой $N_K^ subseteq N_{K'}^$

Шаг индукции. Пусть для некоторого k < n утверждение
верно для всех допустимых для f конъюнкций, содержащих
не менее (k 1) -ой переменной.

Пусть допустимая для fэлементарная конъюнкцияK
содержит k переменных и пусть K. Тогда обе элементарные конъюнкциидопустимыми для f и
по предположению индукции для них в $Phi _{1}$ $K_1^{prime}$ $K_2^{prime}$ $N_{K_1}^ subseteq N_{K_1'}^$ $N_{K_2}^ subseteq N_{K_2'}^$ X, то ее можно выбрать в
качестве K’. В противном случае, их можно представить в виде $K_1^{prime}= (X wedge K_1^{primeprime})$ $K_2^{prime}= (neg X wedge K_2^{primeprime})$ $N_{K}^ subseteq N_{K_1"}^$ $N_{K}^ subseteq N_{K_2"}^$ D₁ тогда содержит и конъюнкцию $K^{prime}= (K_1^{primeprime}wedge K_2^{primeprime})$ $N_{K}^ subseteq N_{K'}^$ Kмаксимальна для f, то $N_{K}^ = N_{K'}^$ максимальные конъюнкции входят в D₁.

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

Пример 4.2. Применим метод Блейка к совершенной ДНФ
функции f(X₁,X₂,X₃)
,
принимающей значение 1 на наборах множества $N_f^ ={(001), (010), (011), (101)}$ совершенная ДНФ

После применения преобразований (П3) на (1)-ом этапе получим

После поглощений (П1) на втором этапе останется сокращенная ДНФ

Заметим, что она не является самой короткой ДНФ для f,
т.к.

Способы представления булевой функции

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

Совершенная дизъюнктивная нормальная форма (СДНФ)
Совершенная конъюнктивная нормальная форма (СКНФ)
Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Построение таблицы истинности онлайн | СКНФ | СДНФ | Полином Жегалкина | Таблица истинности булевой функции онлайн | Programforyou