Реферат: Конспект лекций по дискретной математике
Рангом терма называется количество букв входящих в него.
Дизъюнктивной (конъюнктивной) нормальной формой Булевой функции называется дизъюнкция (конъюнкция) конечного числа попарно различимых конъюнктивных (дизъюнктивных) термов.
Каноническая нормальная форма.
Конституентой единицы (нуля) называется конъюнктивный (дизъюнктивный) терм максимального ранга. Т.е. для Булевой функции от n переменных конституента включает в себя n букв.
Свойство конституенты: Конституента единицы (нуля) принимает значение единицы (нуля) на одном и только одном наборе аргументов.
Пример: _ _
n=4 x1 x2 x3 x4 (1010)=1
_ _ _
x1 Úx2 Úx3 Úx4 =0
Определение: Дизъюнктивная (конъюнктивная) нормальная форма называется канонической, если все ее дизъюнктивные (конъюнктивные) термы представляют собой конституенты единицы (нуля). Иногда канонические формы называют совершенными.
Пример получения канонических форм:
y=x1 Åx2
| x1 | x2 | y | Конституента единицы | Конституенты нуля |
| 0 | 0 | 0 | - | x1 Úx2 |
| 0 | 1 | 1 |  1 x2 | - |
| 1 | 0 | 1 | x1 2 | - |
| 1 | 1 | 0 | - | 1 Ú2 |
КДНФ - каноническая дизъюнктивная нормальная форма:
_ _
y=x1 x2 Úx1 x2
ККНФ - каноническая конъюнктивная нормальная форма:
_ _
y=(x1 Úx2 )(x1 Úx2 )
1) С помощью канонических форм наиболее просто осуществляется переход от табличной формы задания Булевой функции к аналитической.
2) С помощью канонических форм можно осуществить преобразование любой функции в Булев базис.
3) Любая Булева функция за исключением логического нуля и логической единицы имеет единственные КДНФ и ККНФ. Логическую единицу можно представить в виде КДНФ и логический ноль в виде ККНФ.
4) Правило перехода от табличной формы задания Булевой функции к аналитической:
а) в таблице истинности выделяются все наборы аргументов, при которых функция равна единице (нулю).
б) для каждого из этих наборов составляют конституенты единицы (нуля).
в) объединением конституенты единицы (нуля) знаками дизъюнкции (конъюнкции) получается аналитическая форма в виде КДНФ (ККНФ).
Пояснение: при составлении конституент единицы (нуля) используют следующее правило:
Если некоторый аргумент принимает на наборе значение равное нулю, то в конституенту единицы он входит с отрицанием, а в конституенту нуля без него.
5) КДНФ и ККНФ представляют собой две различные, но эквивалентные аналитические формы булевой функции. Это означает, что из одной формы можно получить другую, используя законы Булевой алгебры.
_ _ _ _ _ _ _ _ _ _