Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

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

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

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

Ниже приведён пример ДНФ:

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

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

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

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

Ниже приведён пример СДНФ:

Значение СДНФ состоит в том, что

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

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

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

0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

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

Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так:

Переменные второго члена:

в этом случае будет представлен без инверсии:

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

Совершенная ДНФ этой функции:

См. также

Примечания

  1. Виноградова М.С., Ткачев С.Б. Булевы функции. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. — 32 с.
  2. Математическая логика. — Пермь: Изд-во ПГТУ, 1998. — 17 с.
Эта страница в последний раз была отредактирована 11 апреля 2021 в 13:20.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).