Дискретная математика. Прокушев Л.А. - 26 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

24
Поглощение:
,
ххух
∨=
(17)
().
хх у х∨=
(18)
Докажем равенство (17), используя соотношения (9, 4, 11):
1(1)1.
ххух хух у х х∨=⋅∨= ∨=⋅=
Равенство (18) доказывается с помощью соотношений (4, 3, 17):
() .
хх у хх ху х ху х∨=∨=∨=
Склеивание / расщепление:
.
ху ху х
∨=
(19)
Доказательство склеивания:
()1.
ху ху х у у х х
∨= ∨=⋅=
Расщепление обратно склеиванию и используется для доказатель-
ства эквивалентности преобразований сложных формул.
Обобщенное склеивание (исключение лишних членов дизъюнкции) /
расщепление:
.
хz уz xy хz уz
∨∨=∨
(20)
Доказывается (20) с помощью расщепления (19) и поглощения (17):
()
хz
у
zx
y
хz
у
zx
y
zz
хz
у
zx
y
zx
y
zхz
у
z
∨∨=∨∨ ∨=
=∨∨ ∨ =∨
Исключение отрицания: (21)
Доказывается (21) с помощью расщепления, идемпотентности
(
хх х∨=
) и закона “исключенного третьего” (
1
хх
∨=
):
()
()()11 .
хуу хухухуху хухухуху
ху у ух х х у х у
∨∨=∨∨=∨∨∨=
=∨∨∨=⋅∨⋅=∨
Приведение булевой формулы к ДНФ (в том числе к СДНФ) выпол-
няется с помощью соотношений и правил (1–21). Сначала с помощью
правила двойного отрицания (6) и правил де Моргана (15, 16) все отри-
цания “спускаются” до переменных. Затем раскрываются скобки, с по-
мощью правила идемпотентности (3), законов противоречия (7) и “ис-
ключенного третьего” (8) удаляются лишние конъюнкции и повторения
переменных в конъюнкциях, а с помощью свойств констант (9–14) уда-
ляются константы. С помощью правил упрощения формул (17–21) при-
водят формулу к сокращенной ДНФ, которая может оказаться тупико-
вой ДНФ или, возможно, минимальной ДНФ.
Пример. Упростить булеву формулу:

Страницы