ВУЗ:
Составители:
Рубрика:
15
3.1. Дизъюнктивная и конъюнктивная нормальные формы
Элементарной конъюнкцией называется конъюнкция переменных или их
отрицаний, в которой каждая переменная встречается не более одного раза.
Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид
дизъюнкции элементарных конъюнкций. Совершенная ДНФ – это ДНФ, каждая
элементарная конъюнкция которой включает все переменные с отрицанием или без.
Для получения СДНФ по таблице истинности, в ней
выделяют строки, в которых
функция принимает единичные значения. Для каждой выделенной строки составляется
конъюнкция всех входных переменных, причем сомножитель записывают со знаком
инверсии, если переменная принимает в этой строке нулевое значение. Записывается
логическая сумма всех составленных логических произведений, которые носят названия
конституент единицы, или минтермов. Таким образом, СДНФ функции f
содержит ровно
столько конъюнкций, сколько единиц в таблице истинности, и все полученные
конъюнкции соединяются знаками дизъюнкции. Для каждой функции СДНФ
единственна (с точностью до перестановок переменных или конъюнкций).
Пример. Пусть задана логическая функция трёх переменных, которая равна
единице в случае, если хотя бы две из входных переменных равны «1» (см. табл. 10).
Требуется записать СДНФ этой функции.
Для данной логической функции СДНФ имеет вид:
321321321321321
),,( xxxxxxxxxxxxxxxf ∨∨∨= .
Конъюнктивной нормальной формой (КНФ) называется логическое произведение
элементарных сумм, в каждую из которых аргумент или его отрицание входят один раз.
КНФ может быть получена из таблицы истинности: для каждого набора
аргументов на котором функция равна «0» составляют элементарную сумму,
причем
переменные, значение которых равно «1», записываются с отрицанием. Полученные
суммы, которые носят название конституент нуля, или макстермов, объединяют
операцией логического умножения.
Пример. КНФ для функции из табл. 10 имеет вид:
))()()((),,(
321321321321321
xxxxxxxxxxxxxxxf ∨∨∨∨∨∨∨∨= .
КНФ также называется совершенной, если каждая элементарная сумма содержит
все переменные с инверсией или без.
Иногда удобнее пользоваться не самой логической функцией, а ее инверсией. В
этом случае при использовании вышеописанных методик для записи СДНФ надо
использовать нулевые
, а для записи СКНФ – единичные значения функции.
Пример. Для логической функции из табл. 10 СДНФ и СКНФ инверсной функции
имеют вид:
СДНФ:
321321321321
)( xxxxxxxxxxxxxf +++= ,
СКНФ:
))()()(()(
321321321321
xxxxxxxxxxxxxf ++++++++= .
3.2. Переход от логической функции к логической схеме
Задача синтеза.
По заданной функции f требуется построить схему,
реализующую данную функцию. Задача синтеза решается неоднозначно. Можно
поставить в соответствие заданной функции f целое множество схем.
Для построения логической схемы необходимо элементы, предназначенные для
выполнения логических операций, указанных в логической функции, располагать в
порядке, указанном в булевом выражении.
Страницы
- « первая
- ‹ предыдущая
- …
- 13
- 14
- 15
- 16
- 17
- …
- следующая ›
- последняя »
