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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
70
Принцип двойственности. Пусть
(
)
m
x,,xf K
1
,
(
)
n
x,,xg K
11
, … ,
(
)
nm
x,,xg K
1
— булевы функции и пусть
(
)
(
)
(
)
(
)
nmnn
x,,xg,,x,,xgfx,,x KKKK
1111
=
Φ
— суперпозиция функ-
ций
m
g,,g,f K
1
. Тогда двойственная функция от суперпозиции функций
равна суперпозиции двойственных функций:
(
)
(
)
(
)
(
)
nmnn
x,,xg,,x,,xgfx,,x KKKK
1111
∗∗∗∗
= Φ .
Из определения двойственной функции следует , что две булевы
функции равны тогда и только тогда , когда равны двойственные им
функции. Используя этот факт , а также принцип двойственности, из уже
известных равносильностей легко получить новые .
Пример. Пусть
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
.
Действительно, любая булева функция от
n
переменных однозначно
задается столбцом своих значений, длина которого равна
n
строк, а число
различных столбцов равно числу всех размещений с повторениями из 0 и
1 длины
n
, т.е.
nn
A
22
2
2 =
, что и доказывает теорему.
Примечание. Задание булевой функции в виде функциональной
схемы будет рассмотрено далее.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Рассмотреть различные способы задания булевой функции от трех пе -
ременных, которая:
a) принимает значение 1 в том и только в том случае, когда ровно две
переменные равны нулю ;
b) принимает такое же значение, как большинство (или меньшество)
переменных .
2. Найти множество истинности
f
E для булевой функции
f
, заданной
формулой: 
                                           70
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
        Принцип двойственности. Пусть f ( x1 , , x m ) , g1 ( x1 , , x n ) , …,
g m ( x1 , , x n )       —           булевы             функции              и    пусть
Φ(x1 , , x n ) = f (g1 (x1 , , x n ),  , g m (x1 , , x n )) — суперпозиция функ-
ций f , g1 ,  , g m . Тогда двойственная функция от суперпозиции функций
равна суперпозиции двойственных функций:
                                    (                                      )
              Φ ∗(x1 , , x n ) = f ∗ g1∗(x1 , , x n ),  , g m∗ (x1 , , x n ) .

      Из определения двойственной функции следует, что две булевы
функции равны тогда и только тогда, когда равны двойственные им
функции. Используя этот факт, а также принцип двойственности, из уже
известных равносильностей легко получить новые.

       Пример. Пусть f =x ∨ x y , g = x ∨ y . Доказать, что f =g .
       Доказательство. Построим f ∗ и g ∗:
 f ∗ = f ( x , y ) = x ∨ x y = x ∨ x y = x & xy = x & (x ∨ y ) = x & (x ∨ y ) = x & y ;
 g ∗ = g (x , y ) = x ∨ y = x & y = x & y .

Видим, что f ∗ =g ∗. Следовательно, f =g , т.е. x ∨ xy = x ∨ y .
      Доказывается теорема, что число всех булевых функций от n пе-
                  n
ременных равно 2 2 .
      Действительно, любая булева функция от n переменных однозначно
задается столбцом своих значений, длина которого равна 2 n строк, а число
различных столбцов равно числу всех размещений с повторениями из 0 и
                       n     n
1 длины 2 n , т.е. A22 =2 2 , что и доказывает теорему.
      Примечание. Задание булевой функции в виде функциональной
схемы будет рассмотрено далее.


                           ЗАДАЧИ И УПРАЖНЕНИЯ

1. Рассмотреть различные способы задания булевой функции от трех пе-
   ременных, которая:
     a) принимает значение 1 в том и только в том случае, когда ровно две
        переменные равны нулю;
     b) принимает такое же значение, как большинство (или меньшество)
        переменных.

2. Найти множество истинности E f               для булевой функции f , заданной
   формулой:

Страницы