Составители:
Рубрика:
20
Теорема 2 (о представлении функции в СДНФ). Всякая булева
функция
12
(, , , )
n
fxx x
…
может быть единственным образом представ-
лена в СДНФ.
По таблице истинности функции
12
(, , , )
n
fxx x
…
легко получить ее
СДНФ и СКНФ в соответствии с теоремой 2 и двойственностью свойств
дизъюнкции и конъюнкции.
Каждому двоичному набору таблицы
12
(, ,, )
n
α= α α α
…
соответствует единственная конституента 1 вида:
12
n
хх х
…
, обра-
щающаяся на этом наборе в 1 по правилу:
, если 1,
, если 0 .
i
ii
i
ii
x
x
x
α
α=
=
α=
Все остальные конституенты 1 на данном наборе обращаются в 0.
Например, для функции
123
(, , )fxx x
набору (0, 1, 0) соответствует
конституента 1:
123
xxx
, а набору (1, 1, 0) –
123
xxx
.
Образуя дизъюнкцию конституент 1, соответствующих всем набо-
рам, на которых функция обращается в 1, получим СДНФ, равную дан-
ной функции.
xy )y,x(f
000
011
101
110
Каждому двоичному набору таблицы
12
(, ,, )
n
α= α α α
…
соответству-
ет единственная конституента 0 вида:
12
n
хх х
∨∨∨
…
, обращающаяся
xy )y,x(f 1ытнеутитснок xy )y,x(f 0ытнеутитснок
00 0 00 0
01 1 01 1
10 1 10 1
11 0 11 0
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
