Дискретная математика. Элементы теории, задачи и упражнения. Часть 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