Минимальная конъюнктивная нормальная форма — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
м |
||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 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. Затем строятся элементарные дизъюнкты МКНФ. | ||
| − | + | == Обозначения == | |
| − | == | + | |
| − | + | ||
| − | + | ||
'''n''' – число аргументов функции; | '''n''' – число аргументов функции; | ||
| Строка 23: | Строка 20: | ||
'''f<sub>МКНФ</sub>(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – МКНФ логической функции. | '''f<sub>МКНФ</sub>(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – МКНФ логической функции. | ||
| − | + | == Формула == | |
[[файл:МКНФ01.JPG]] | [[файл:МКНФ01.JPG]] | ||
[[файл:МКНФ02.JPG]] | [[файл:МКНФ02.JPG]] | ||
| − | + | == Примеры построения МКНФ == | |
| − | == Пример 1 == | + | === Пример 1 === |
| − | Строим карту Карно для функции трёх переменных | + | Строим [[Карта Карно|карту Карно]] для функции трёх переменных |
[[файл:ЛФ31.JPG]] | [[файл:ЛФ31.JPG]] | ||
| Строка 37: | Строка 34: | ||
[[файл:МКНФ11.JPG]] | [[файл:МКНФ11.JPG]] | ||
| − | + | === Пример 2 === | |
| − | == Пример 2 == | + | Строим [[Карта Карно|карту Карно]] для функции четырёх переменных |
| − | Строим карту Карно для функции четырёх переменных | + | |
[[файл:ЛФ41.JPG]] | [[файл:ЛФ41.JPG]] | ||
| Строка 47: | Строка 43: | ||
[[файл:МКНФ12.JPG]] | [[файл:МКНФ12.JPG]] | ||
| + | === Пример 3 === | ||
| + | Строим [[Трёхмерная карта Карно|трёхмерную карту Карно]] для функции пяти переменных | ||
| + | [[файл:ЛФ51.JPG]] | ||
| + | |||
| + | [[файл:МКНФ23.JPG]] | ||
| − | + | Нули трёхмерной карты Карно минимально покрываются параллелепипедами вида 2х2х2, 1х4х1 (два), 2х2х1, 1х1х2, что соответствует одной элементарной дизъюнкции двух аргументов, трём элементарным дизъюнкциям трёх аргументов и одной элементарной дизъюнкции четырёх аргументов. Заметим, что соответствующие равные фигуры в разных таблицах объединяются. | |
| − | + | ||
| − | + | ||
| − | + | ||
| + | [[файл:МКНФ13.JPG]] | ||
| + | == [[Логическая функция|Другие формы:]] == | ||
| + | {{Список ЛФор}} | ||
== Ссылки == | == Ссылки == | ||
| − | * [[Участник:Logic-samara]] | + | *[[Участник:Logic-samara]] |
| − | [[Категория:Дискретная математика]][[Категория:Логика]] | + | [[Категория:Математика]][[Категория:Дискретная математика]][[Категория:Логика]] |
Текущая версия на 10:26, 13 января 2024
Минимальная конъюнктивная нормальная форма (МКНФ) для логической функции – это конъюнкция с минимальным числом элементарных дизъюнкций с минимальным числом аргументов (либо самих, либо их отрицаний) данной функции. При этом таблицы истинности для логической функции и её МКНФ совпадают.
Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью карт Карно. Для этого нули карты Карно последовательно покрываются прямоугольниками 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, что соответствует одной элементарной дизъюнкции двух аргументов, трём элементарным дизъюнкциям трёх аргументов и одной элементарной дизъюнкции четырёх аргументов. Заметим, что соответствующие равные фигуры в разных таблицах объединяются.
