Совершенная конъюнктивная нормальная форма — различия между версиями
м |
м |
||
| Строка 1: | Строка 1: | ||
'''Совершенная конъюнктивная нормальная форма (СКНФ)''' для '''[[Логическая функция|логической функции]]''' – это конъюнкция различных элементарных дизъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. | '''Совершенная конъюнктивная нормальная форма (СКНФ)''' для '''[[Логическая функция|логической функции]]''' – это конъюнкция различных элементарных дизъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. | ||
При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её СКНФ совпадают. | При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её СКНФ совпадают. | ||
| − | == | + | == Обозначения == |
'''n''' – число аргументов функции; | '''n''' – число аргументов функции; | ||
| Строка 13: | Строка 13: | ||
'''arg<sub>j</sub>[f(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)=0]''' – значение аргумента '''x<sub>j</sub>''' в фиксированном наборе аргументов. | '''arg<sub>j</sub>[f(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)=0]''' – значение аргумента '''x<sub>j</sub>''' в фиксированном наборе аргументов. | ||
| − | + | == Формула == | |
[[файл:СКНФ01.JPG]] | [[файл:СКНФ01.JPG]] | ||
Текущая версия на 10:27, 13 января 2024
Совершенная конъюнктивная нормальная форма (СКНФ) для логической функции – это конъюнкция различных элементарных дизъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. При этом таблицы истинности для логической функции и её СКНФ совпадают.
Содержание
Обозначения
n – число аргументов функции;
(x1,x2,…,xn) – набор аргументов функции;
f(x1,x2,…,xn) – логическая функция;
fСКНФ(x1,x2,…,xn) – СКНФ логической функции;
arg[f(x1,x2,…,xn)=0] – фиксированный набор аргументов функции, обращающий функцию в 0;
argj[f(x1,x2,…,xn)=0] – значение аргумента xj в фиксированном наборе аргументов.
Формула
– элементарная дизъюнкция.
- Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние нуля.
В элементарную дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
Пример
