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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
104
В силу критерия Поста для полноты системы F=
{
}
,...,
21
ff необхо -
димо и достаточно, чтобы хотя бы в одной клетке каждого столбца стоял
знак «-».
Система (множество) булевых функций называется базисом , если
она полна и любая ее подсистема не является полной на множестве буле-
вых функций.
Для выделения базиса из полной системы функций
{
}
,...,,
321
fffF
=
нужно упорядочить по числу функций множество подсистем системы F:
{
}
{
}
{
}
{
}
....,,,,...,,,
312121
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