Составители:
Рубрика:
28
1. Прежде всего приведем все конъюнктивные члены к одному и тому же рангу
r=3. Для этого умножим первый член xz на y
∨ y=1. Имеем
xz = xz
1 = xz(y ∨ y) = xzy ∨ xzy = xzy ∨ xzy.
Тогда исходная функция f примет вид
f(x,y,z)=xyz
∨ xyz ∨ xyz ∨ xyz ∨ xyz (13)
2. Приведем все возможные операции неполного склеивания в два
приема:
а) склеим (полное склеивание) каждую из конституент единицы ДНФ (13)
с последующими.
1-ый член склеивается со 2-м по y, получим xz,
1-й
»
с 5-м по х,
»
yz,
2-й ни с чем не склеивается,
3-й член склеивается с 4-м по y, получим xz,
4-й
»
с 5-м по z,
»
xy.
б) конъюнкции, полученные в результате полного склеивания, выпишем
вначале ДНФ, соединив их между собой и с ДНФ знаками дизъюнкций.
f(x,y,z)=xz
∨ yz ∨ xz ∨ xy ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz
3. Проведем все возможные операции поглощения в соответствии с
формулой
β∨β⋅γ=β. Первый член xz поглощает xyz и xyz, т.е.
xz
∨ xyz = xz ∨ (xz)y =xz ,
xz
∨ xyz = xz ∨ (xz)y =xz .
Аналогичным образом член yz поглощает xyz. Далее, xz поглощает xyz и xyz. В
итоге получим
f(x,y,z)=xz
∨ yz ∨ xz ∨ xy. (14)
4. Непосредственной проверкой убеждаемся, что применение операций
склеивания и поглощения невозможно. Полученное соотношение (14) является
сокращенно ДНФ заданной функции. Конъюнктивные члены (14) представляют
собой простые импликанты функции f.
Перейдем ко второму этапу построения минимальной ДНФ.
Нахождение тупиковых и минимальных ДНФ
Определение. Тупиковой
ДНФ булевой функции называется дизъюнкция
из некоторых простых импликант этой функции, равная самой функции, и
такая, что исключение из нее одной из импликант нарушает это равенство.
Произвольная булева функция может иметь несколько тупиковых форм.
Те из них, которые имеют наименьшую сумму рангов, являются
минимальными ДНФ. Следовательно, для отыскания минимальных ДНФ
функции достаточно получить все ее тупиковые формы и выбрать среди них
формы, обладающие наименьшей суммой рангов.
Страницы
- « первая
- ‹ предыдущая
- …
- 26
- 27
- 28
- 29
- 30
- …
- следующая ›
- последняя »
