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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

52
Система (множество) булевых функций называется базисом, если
она полна и любая ее подсистема не является полной на множестве буле-
вых функций.
Для выделения базиса из полной системы функций
{
}
,...,,
321
fffF
=
нужно упорядочить по числу функций множество подсистем системы F:
121213
,,...,,,,,...
ffffff
и, начиная с первой, исследовать их на полноту. Первая из полных в этой
последовательности подсистем будет базисом.
Пример. Исследовать полноту системы функций
{
}
zxyyxyF ®¯Å= ;;1 и, если она полна, выделить из нее базис.
Решение. Пусть 1
1
Å
=
yf , zxyf
®
=
2
, yxf ¯=
3
.
Составим таблицы истинности для заданных функций:
Исследуем функцию zxyf
®
=
2
на принадлежность классам
0
T ,
1
T ,
S
,
,
L
:
,
02
Tf
Ï
т.к.
(
)
;, 100
2
=
f ,
12
Tf
Î
т.к.
(
)
;, 111
2
=
f
12
Sf
Ï
, т.к. на противоположных наборах (000) и (111) функция
принимает одинаковое значение, равное 1.
12
Mf
Ï
, т.к. есть предшествующие наборы, например (000)
£
(110),
на которых
(
)
1000
2
=
,,f ,
(
)
0011
2
=
,,f , где неравенство 1
£
0 ложное,
12
Lf
Ï
, т.к.
( )
.& 11
2
ÅÅ=Å==Ú=Ú=®= xyxyzzxyzxyzxyzxyzxyf
Аналогично исследуем функции
1
f и
3
f на принадлежность классам
.,,,,
11110
LMSTT
Заполним таблицу
y
y
1
1
f
0 1 1 0
1 0 1 1
x y z xy
2
f
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1
x y
y
x
Ú
3
f
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
1
2
3
      Система (множество) булевых функций называется базисом, если
она полна и любая ее подсистема не является полной на множестве буле-
вых функций.
      Для выделения базиса из полной системы функций F � � f 1 , f 2 , f 3 ,...�
нужно упорядочить по числу функций множество подсистем системы F:
                       f1 ,  f 2 , ...,  f1 , f 2 ,  f1 , f3 , ...
и, начиная с первой, исследовать их на полноту. Первая из полных в этой
последовательности подсистем будет базисом.

     Пример.         Исследовать        полноту      системы       функций
F � �y � 1; x � y; xy � z� и, если она полна, выделить из нее базис.
     Решение. Пусть f 1 � y � 1 , f 2 � xy � z , f 3 � x � y .
             1                           2                             3
   y     y       1    f1        x    y       z   xy   f2     x     y       x� y   f3
   0     1       1    0         0    0       0   0    1
   1     0       1    1         0    0       1   0    1      0     0        0     1
                                0    1       0   0    1      0     1        1     0
                                0    1       1   0    1      1     0        1     0
                                1    0       0   0    1      1     1        1     0
                                1    0       1   0    1
                                1    1       0   1    0
                                1    1       1   1    1

Составим таблицы истинности для заданных функций:
        Исследуем функцию f 2 � xy � z на принадлежность классам T0 ,
T1 , S , M , L :
         f 2 � T0 , т.к. f 2 �0,0 � � 1; f 2 � T1 , т.к. f 2 �1,1� � 1;
         f 2 � S 1 , т.к. на противоположных наборах (000) и (111) функция
принимает одинаковое значение, равное 1.
         f 2 � M 1 , т.к. есть предшествующие наборы, например (000) � (110),
на которых f 2 �0,0,0 � � 1 , f 2 �1,1,0 � 0 � , где неравенство 1 � 0 ложное,
f 2 � L1 , т.к. f 2 � xy � z � xy � z � xy � z � xy & z � xy � z � 1� � xyz � xy � 1.
         Аналогично исследуем функции f 1 и f 3 на принадлежность классам
T0 , T1 , S 1 , M 1 , L1 .
         Заполним таблицу




                                         52

Страницы