Составители:
Рубрика:
18
Закон противоречия: (7)
Закон “исключенного третьего”: (8)
Свойства констант:
х&1 = x, (9)
x&0 = 0, (10)
x v 1 = 1, (11)
x v 0 = 0, (12)
= 0, (13)
= 1. (14)
Правила де Моргана (для трех операций булевой алгебры):
а)
,
ху х у=∨
(15)
б)
.
хуху∨=
(16)
Рассмотренные свойства булевых операций используются для упро-
щения и доказательства тождественности формул булевой алгебры на
базе дизъюнктивных и конъюнктивных нормальных форм.
Пусть для множества переменных X = {x
1
, …, x
n
} через (∀х с вол-
ной”) обозначается х или
x
. Элементарной конъюнкцией (произведени-
ем) называется конструкция вида:
12
,
k
ii i
Uxx x
= …
если в ней каждая
буква встречается не более одного раза. Например,
12 123
,
xx xxx
– эле-
ментарные конъюнкции, а
11 32 3
,
xx xxx
– неэлементарные. Конститу-
ентой 1 называется n-местная элементарная конъюнкция, включающая
все переменные из набора Х (в виде либо x
i
... x
ik
, либо x
i
) в точности по
одному разу. Общее число таких конституент равно 2
n
, т. е. числу набо-
ров n-переменных.
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция
элементарных конъюнкций U
i
:
D = U
1
∨
U
2
∨ … ∨ U
m
,
не содержащая двух одинаковых конъюнкций, например:
12 123 23
хх хх х х х
∨∨
.
Совершенная ДНФ (СДНФ) – это ДНФ, состоящая только из консти-
туент 1, например:
123123123123
хх х хх х хх х хх х
∨∨∨
.
В булевой алгебре вследствие того, что при замене нуля единицей, а
единицы нулем, дизъюнкция превращается в конъюнкцию, и наоборот,
0
xx
=
v 1
xx
=
1
0
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
