Изменения
Восстановление статей Logic-samara
'''Минимальная конъюнктивная нормальная форма (МКНФ)''' для '''[[Логическая функция|логической функции]]''' – это конъюнкция с минимальным числом элементарных дизъюнкций с минимальным числом аргументов (либо самих, либо их отрицаний) данной функции.
При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её МКНФ совпадают.
Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью '''[[Карта Карно|карт Карно]]'''.
Для этого нули карты Карно последовательно покрываются прямоугольниками 4х2, 2х4, 2х2, 4х1, 1х4, 2х1, 1х2 и 1х1. Затем строятся элементарные дизъюнкты МКНФ.
== Формула ==
Введём обозначения:
'''n''' – число аргументов функции;
'''k''' – число прямоугольников на карте Карно;
'''(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – набор аргументов функции;
'''f(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – логическая функция;
'''P<sub>t</sub>(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)={(i<sub>1</sub>,l<sub>1</sub>); (i<sub>2</sub>,l<sub>2</sub>); ...; (i<sub>m</sub>,l<sub>m</sub>)}''' – множество клеток '''t'''-прямоугольника;
'''P<sub>t</sub>(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)=0''' – множество клеток '''t'''-прямоугольника из нулей;
'''arg<sub>j</sub>(i,l)''' – значение аргумента '''x<sub>j</sub>''' в наборе аргументов для клетки '''(i,l)''';
'''f<sub>МКНФ</sub>(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – МКНФ логической функции.
[[файл:МКНФ01.JPG]]
[[файл:МКНФ02.JPG]]
== Пример 1 ==
Строим карту Карно для функции трёх переменных
[[файл:ЛФ31.JPG]]
[[файл:МКНФ21.JPG]]
Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.
[[файл:МКНФ11.JPG]]
== Пример 2 ==
Строим карту Карно для функции четырёх переменных
[[файл:ЛФ41.JPG]]
[[файл:МКНФ22.JPG]]
Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.
[[файл:МКНФ12.JPG]]
== Другие формы: ==
*[[Совершенная дизъюнктивная нормальная форма]] ([[СДНФ]]);
*[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]);
*[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]).
== Ссылки ==
* [[Участник:Logic-samara]]
[[Категория:Дискретная математика]][[Категория:Логика]]
При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её МКНФ совпадают.
Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью '''[[Карта Карно|карт Карно]]'''.
Для этого нули карты Карно последовательно покрываются прямоугольниками 4х2, 2х4, 2х2, 4х1, 1х4, 2х1, 1х2 и 1х1. Затем строятся элементарные дизъюнкты МКНФ.
== Формула ==
Введём обозначения:
'''n''' – число аргументов функции;
'''k''' – число прямоугольников на карте Карно;
'''(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – набор аргументов функции;
'''f(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – логическая функция;
'''P<sub>t</sub>(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)={(i<sub>1</sub>,l<sub>1</sub>); (i<sub>2</sub>,l<sub>2</sub>); ...; (i<sub>m</sub>,l<sub>m</sub>)}''' – множество клеток '''t'''-прямоугольника;
'''P<sub>t</sub>(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)=0''' – множество клеток '''t'''-прямоугольника из нулей;
'''arg<sub>j</sub>(i,l)''' – значение аргумента '''x<sub>j</sub>''' в наборе аргументов для клетки '''(i,l)''';
'''f<sub>МКНФ</sub>(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)''' – МКНФ логической функции.
[[файл:МКНФ01.JPG]]
[[файл:МКНФ02.JPG]]
== Пример 1 ==
Строим карту Карно для функции трёх переменных
[[файл:ЛФ31.JPG]]
[[файл:МКНФ21.JPG]]
Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.
[[файл:МКНФ11.JPG]]
== Пример 2 ==
Строим карту Карно для функции четырёх переменных
[[файл:ЛФ41.JPG]]
[[файл:МКНФ22.JPG]]
Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.
[[файл:МКНФ12.JPG]]
== Другие формы: ==
*[[Совершенная дизъюнктивная нормальная форма]] ([[СДНФ]]);
*[[Совершенная конъюнктивная нормальная форма]] ([[СКНФ]]);
*[[Минимальная дизъюнктивная нормальная форма]] ([[МДНФ]]).
== Ссылки ==
* [[Участник:Logic-samara]]
[[Категория:Дискретная математика]][[Категория:Логика]]
