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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
105
В каждом столбце таблицы стоит знак «-». Поэтому, согласно крите-
рию Поста, система функций полная.
Базисом является функция
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