Минимальная конъюнктивная нормальная форма — различия между версиями
Строка 4: | Строка 4: | ||
Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью '''[[Карта Карно|карт Карно]]'''. | Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью '''[[Карта Карно|карт Карно]]'''. | ||
Для этого нули карты Карно последовательно покрываются прямоугольниками 4х2, 2х4, 2х2, 4х1, 1х4, 2х1, 1х2 и 1х1. Затем строятся элементарные дизъюнкты МКНФ. | Для этого нули карты Карно последовательно покрываются прямоугольниками 4х2, 2х4, 2х2, 4х1, 1х4, 2х1, 1х2 и 1х1. Затем строятся элементарные дизъюнкты МКНФ. | ||
− | |||
== Формула == | == Формула == | ||
Введём обозначения: | Введём обозначения: | ||
Строка 27: | Строка 26: | ||
[[файл:МКНФ02.JPG]] | [[файл:МКНФ02.JPG]] | ||
− | |||
== Примеры построения МКНФ == | == Примеры построения МКНФ == | ||
=== Пример 1 === | === Пример 1 === | ||
Строка 38: | Строка 36: | ||
[[файл:МКНФ11.JPG]] | [[файл:МКНФ11.JPG]] | ||
− | |||
=== Пример 2 === | === Пример 2 === | ||
Строим [[Карта Карно|карту Карно]] для функции четырёх переменных | Строим [[Карта Карно|карту Карно]] для функции четырёх переменных | ||
Строка 48: | Строка 45: | ||
[[файл:МКНФ12.JPG]] | [[файл:МКНФ12.JPG]] | ||
− | |||
=== Пример 3 === | === Пример 3 === | ||
Строим [[Трёхмерная карта Карно|трёхмерную карту Карно]] для функции пяти переменных | Строим [[Трёхмерная карта Карно|трёхмерную карту Карно]] для функции пяти переменных | ||
Строка 58: | Строка 54: | ||
[[файл:МКНФ13.JPG]] | [[файл:МКНФ13.JPG]] | ||
− | |||
== Другие формы: == | == Другие формы: == | ||
*[[Совершенная дизъюнктивная нормальная форма]] ([[СДНФ]]); | *[[Совершенная дизъюнктивная нормальная форма]] ([[СДНФ]]); | ||
*[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]); | *[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]); | ||
*[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]). | *[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]). | ||
− | |||
== Ссылки == | == Ссылки == | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Дискретная математика]][[Категория:Логика]] | [[Категория:Дискретная математика]][[Категория:Логика]] |
Версия 16:18, 15 января 2016
Минимальная конъюнктивная нормальная форма (МКНФ) для логической функции – это конъюнкция с минимальным числом элементарных дизъюнкций с минимальным числом аргументов (либо самих, либо их отрицаний) данной функции. При этом таблицы истинности для логической функции и её МКНФ совпадают.
Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью карт Карно. Для этого нули карты Карно последовательно покрываются прямоугольниками 4х2, 2х4, 2х2, 4х1, 1х4, 2х1, 1х2 и 1х1. Затем строятся элементарные дизъюнкты МКНФ.
Содержание
Формула
Введём обозначения:
n – число аргументов функции;
k – число прямоугольников на карте Карно;
(x1,x2,…,xn) – набор аргументов функции;
f(x1,x2,…,xn) – логическая функция;
Pt(x1,x2,…,xn)={(i1,l1); (i2,l2); ...; (im,lm)} – множество клеток t-прямоугольника;
Pt(x1,x2,…,xn)=0 – множество клеток t-прямоугольника из нулей;
argj(i,l) – значение аргумента xj в наборе аргументов для клетки (i,l);
fМКНФ(x1,x2,…,xn) – МКНФ логической функции.
Примеры построения МКНФ
Пример 1
Строим карту Карно для функции трёх переменных
Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.
Пример 2
Строим карту Карно для функции четырёх переменных
Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.
Пример 3
Строим трёхмерную карту Карно для функции пяти переменных
Нули трёхмерной карты Карно минимально покрываются параллелепипедами вида 2х2х2, 1х4х1 (два), 2х2х1, 1х1х2, что соответствует одной элементарной дизъюнкции двух аргументов, трём элементарным дизъюнкциям трёх аргументов и одной элементарной дизъюнкции четырёх аргументов. Заметим, что соответствующие равные фигуры в разных таблицах объединяются.
Другие формы:
- Совершенная дизъюнктивная нормальная форма (СДНФ);
- Совершенная конъюнктивная нормальная форма (СКНФ);
- Минимальная дизъюнктивная нормальная форма (МДНФ).