Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 19 стр.

UptoLike

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

19
(
)
.xxxxxxxx,xf 1
121212121
Å
Å
=
Ú
=
®
=
Равносильность формул доказывается:
1. с помощью таблиц истинности;
2. методом эквивалентных (равносильных) преобразований.
Существует еще один способ доказательства равносильности фор-
мул, основанный на применении так называемого принципа двойственно-
сти.
Булева функция
(
)
n
x,,xf
K
1
*
называется двойственной к функции
n
x,,xf
K
1
, если
(
)
(
)
nn
x,,xfx,,xf
K
K
11
=
*
. Так, функция
(
)
yxyxf &,
=
*
,
двойственна к
(
)
yxyxf
Ú
=
, :
(
y&xy&xyxy,xf ==Ú=
*
.
Принцип двойственности. Пусть
m
x,,xf
K
1
,
(
)
n
x,,xg
K
11
, ,
(
)
nm
x,,xg
K
1
булевы функции и пусть
1
,,
n
xx
F
K
111
,,,,,,
nmn
fgxxgxx
KKK
суперпозиция функций
m
g,,g,f
K
1
. То-
гда двойственная функция от суперпозиции функций равна суперпозиции
двойственных функций:
(
)
(
)
(
)
(
)
nmnn
x,,xg,,x,,xgfx,,x
K
K
K
K
1111
****
=F .
Из определения двойственной функции следует, что две булевы
функции равны тогда и только тогда, когда равны двойственные им
функции. Используя этот факт, а также принцип двойственности, из уже
известных равносильностей легко получить новые.
Пример. Пусть
y
x
x
f
Ú
=
,
y
x
g
Ú
=
. Доказать, что
g
f
=
.
Доказательство. Построим
*
f и
*
g :
(
)
(
)
( )
.y&xy&xyxy,xgg
;y&xyx&xyx&xyx&xyxxyxxy,xff
==Ú==
=Ú=Ú==Ú=Ú==
*
*
Видим, что
**
= gf . Следовательно,
g
f
=
, т. е.
y
x
y
x
x
Ú
=
Ú
.
Доказывается теорема, что число всех булевых функций от
n
пе-
ременных равно
n
2
2
.
Действительно, любая булева функция от
n
переменных однозначно
задается столбцом своих значений, длина которого равна
n
2
строк, а число
различных столбцов равно числу всех размещений с повторениями из 0 и
1 длины
n
2
, т.е.
nn
A
22
2= , что и доказывает теорему.
Примечание. Задание булевой функции в виде функциональной
схемы будет рассмотрено далее.