Составители:
6
1.2. Представление булевой функции в аналитическом виде
Для представления булевых функций в аналитическом виде обычно
используются нормальные формы.
В качестве элементов аналитических форм булевых функций исполь-
зуются буквы, объединяемые в выражения знаками булевых операций
(конъюнкции и дизъюнкции). Под буквой понимается булева переменная,
представляющая аргумент булевой функции, или ее отрицание.
Для пред-
ставления нормальных форм булевых функций используются простейшие
булевы выражения, называемые элементарной конъюнкцией (конъюнк-
тивным термом) и элементарной дизъюнкцией (дизъюнктивным термом).
Элементарной конъюнкцией (дизъюнкцией) или конъюнктивным
(дизъюнктивным) термом называется выражение, представляющее собой
конъюнкцию (дизъюнкцию) любого конечного множества попарно разли-
чимых букв или состоящее из одной буквы.
Для представления булевых
функций могут использоваться дизъюнк-
тивная и конъюнктивная нормальные формы .
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция
любого конечного множества попарно различимых элементарных конъ-
юнкций.
Конъюнктивной нормальной формой (КНФ) называется конъюнкция
любого конечного множества попарно различимых элементарных дизъ-
юнкций.
В частном случае, как ДНФ, так и КНФ могут состоять из одного
терма.
Элементарные конъюнкции (дизъюнкции) называются конституен-
тами единицы (нуля), если они содержат в прямом или инверсном виде все
переменные, являющиеся аргументами булевой функции. Конституента
единицы принимает единичное значение тогда и только тогда, когда все
входящие в конституенту буквы принимают значения, равные единице.
Конституента нуля принимает нулевое значение тогда и только
тогда, ко-
гда все входящие в конституенту буквы принимают значение, равное ну-
лю. Из этого следует, что конституента единицы (нуля) принимает еди-
ничное (нулевое) значение на одном и только одном наборе аргументов
булевой функции.
На основе конституент единицы (нуля) составляются канонические
дизъюнктивные (конъюнктивные) нормальные формы булевых функций.
ДНФ (КНФ) называется канонической
или совершенной, если все ее эле-
ментарные конъюнкции (дизъюнкции) являются конституентами единицы
(нуля).
Канонические дизъюнктивную нормальную форму (КДНФ) и конъ-
юнктивную нормальную форму (ККНФ) можно составить по таблице ис-
тинности следующим образом.
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
