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