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

UptoLike

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

53
В каждом столбце таблицы стоит знак «». Поэтому, согласно крите-
рию Поста, система функций полная.
Базисом является функция
3
f , т. к. подсистема
{
}
3
f полна в Б.
Замечание 1. Для исследования полноты вовсе не обязательно за-
полнять все клетки таблицы. Если получили, что одна из функций не при-
надлежит какому-либо из классов, то принадлежность остальных функций
этому классу можно не исследовать.
Замечание 2. При исследовании полноты системы полезно исполь-
зовать следующее утверждение: если некоторая система функций
F
со-
держит в себе как часть полную систему функций FFF
Ì
11
, , то систе-
ма
F
полна.
Например, рассмотренная выше в примере система
F
является пол-
ной, т. к. содержит в себе полную подсистему
{
}
yx ¯ .
Замечание 3. Если в одном из столбцов таблицы получены все «+»,
т. е. все функции
i
f системы
F
принадлежат какому-то классу, то система
функций не является полной.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Выразить с помощью суперпозиций:
1) «
&
»и «
®
» через «
Ú
» и «»;
2) «&» и «
Ú
» через
®
и «»;
3) «
Ú
» и «
Ù
» через «
»;
4) «» через «
®
» и «0»;
5) «» через «
Å
» и «1»;
6) «
Ú
» через «
®
».
2. Доказать, что нельзя выразить с помощью суперпозиций:
1) «» через «&», «
Ú
», «
®
» и «~»;
2) «
®
» через «&», и «
Ú
».
классы
функции
0
T
1
T
S
M
L
1
1
Å
=
yf
+ + + + +
zxyf
®
=
2
+
yxf ¯=
3