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

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

· в ней нет одинаковых множителей (элементарных дизъюнкций);

· в каждом множителе нет повторяющихся переменных;

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

Любая булева формула, не являющаяся тождественно истинной, может быть приведена к СКНФ.^[1].

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

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

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

В ячейках строки́ $f(x_{1},x_{2},x_{3},x_{4})$ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.

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

$x_{1}=0$
$x_{2}=0$
$x_{3}=1$
$x_{4}=1$

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так: $x_{1}\vee x_{2}\vee {\overline {x_{3}}}\vee {\overline {x_{4}}}$

Остальные члены СКНФ составляются по аналогии:^[2]

({x_{1}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land

({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land

({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})

См. также

Примечания

↑ Математическая логика. Методические указания по курсу "Основы дискретной математики для студентов специальности 220220" (неопр.). Дата обращения: 25 марта 2016. Архивировано 9 апреля 2016 года.
↑ В.И. Игошин. Задачник-практикум по математической логике. 1986

Похожие исследовательские статьи

Алгебра логики — раздел математической логики, в котором изучаются логические операции над высказываниями. Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика, в отличие от, например, троичной логики.

<span class="mw-page-title-main">Дизъюнкция</span> логическая связка ИЛИ

Дизъю́нкция, логи́ческое сложе́ние, логи́ческое ИЛИ, включа́ющее ИЛИ; иногда просто ИЛИ — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу».

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

<span class="mw-page-title-main">Законы де Моргана</span>

Законы де Мо́ргана — логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана. В краткой форме звучат так:

Отрицание конъюнкции есть дизъюнкция отрицаний.

Отрицание дизъюнкции есть конъюнкция отрицаний.

Зада́ча выполни́мости бу́левых фо́рмул — важная для теории вычислительной сложности алгоритмическая задача.

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

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

Замкнутый класс в теории булевых функций — такое множество $\text{[math]}$ функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: $\text{[math]}$ . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества $\text{[math]}$ , снова входит в это же множество.

Бу́лева фу́нкция от $\text{[math]}$ аргументов — в дискретной математике — отображение $\text{[math]}$ , где $\text{[math]}$ — булево множество. Элементы булева множества $\text{[math]}$ обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число $\text{[math]}$ , обозначающее количество аргументов, называется арностью или местностью функции, в случае $\text{[math]}$ булева функция превращается в булеву константу. Элементы декартова произведения $\text{[math]}$ называют булевыми векторами. Множество всех булевых функций от любого числа аргументов часто обозначается $\text{[math]}$ , а от $\text{[math]}$ аргументов — $\text{[math]}$ . Переменные, принимающие значения из булева множества, называются булевыми переменными. Булевы функции названы по фамилии математика Джорджа Буля.

<span class="mw-page-title-main">Карта Карно</span> графический способ представления переключательных булевых функций с целью наглядной и удобной их минимизации

Ка́рта Ка́рно — графический способ представления булевых функций с целью их удобной и наглядной ручной минимизации.

Конъюнкти́вный одночле́н — булева формула, представляющая собой конъюнкцию литералов:

\text{[math]}

Дизъюнкти́вный одночле́н — дизъюнкция литералов :

\text{[math]}

Полином Жегалкина — многочлен над полем $\text{[math]}$ , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).

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

на первом этапе осуществляется переход от канонической формы к так называемой сокращённой форме;
на втором этапе — переход от сокращённой формы к минимальной форме.

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

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

Комбинационная логика в теории цифровых устройств — двоичная логика функционирования устройств комбинационного типа. У комбинационных устройств состояние выхода однозначно определяется набором входных сигналов, что отличает комбинационную логику от секвенциальной логики, в рамках которой выходное значение зависит не только от текущего входного воздействия, но и от предыстории функционирования цифрового устройства. Другими словами, секвенциальная логика предполагает наличие памяти, которая в комбинационной логике не предусмотрена.

Схема функциональной целостности (СФЦ) — это логически универсальное графическое средство структурного представления исследуемых свойств системных объектов. Описание аппарата схем функциональной целостности было впервые опубликовано Можаевым А. С. в 1982 году. По построению аппарат СФЦ реализует все возможности алгебры логики в функциональном базисе «И», «ИЛИ» и «НЕ». СФЦ позволяют корректно представлять как все традиционные виды структурных схем, так и принципиально новый класс немонотонных (некогерентных) структурных моделей различных свойств исследуемых систем. В настоящее время СФЦ применяются для построения структурных схем для расчета показателей надежности, стойкости, живучести, технического риска, реальной эффективности систем.

В математике разложением Шеннона или декомпозицией Шеннона по переменной $\text{[math]}$ называется метод представления булевой функции от $\text{[math]}$ переменных в виде суммы двух подфункций от $\text{[math]}$ остальных переменных. Хотя этот метод часто приписывают Клоду Шеннону, но Буль доказал его гораздо раньше, а сама возможность такого разложения по любой из переменной непосредственно вытекает из возможности определения любой булевой функции с помощью таблицы истинности.

Алгебра Жегалкина — множество булевых функций, на котором определены нульарная операция взятия единицы $\text{[math]}$ , бинарная операция конъюнкции $\text{[math]}$ и бинарная операция суммы по модулю два $\text{[math]}$ . Константа ноль вводится как $\text{[math]}$ . Операция отрицания вводится соотношением $\text{[math]}$ . Операция дизъюнкции следует из тождества $\text{[math]}$ .

Двойственная булева функция к булевой функции $\text{[math]}$ — функция $\text{[math]}$ , определяемая соотношением

\text{[math]}

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1