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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
106
3. Доказать полноту следующих систем функций, используя теорему о
полноте 2 х систем :
1)
{
}
;, xyxG
=
2)
{
}
;yxG ↓=
3)
{
}
;, 0yxG
=
4)
{
}
;,; 1 yxyxG
=
5)
{
}
;,~, xyxyxG
=
6)
{
}
.,; yxxG
=
1
4. Доказать неполноту систем функций:
1)
{
}
;x
=
φ
2)
{
}
.,,& yxyxyx
=
φ
5. Используя критерий полноты, выяснить, являются ли полными сле-
дующие системы функций. В полных системах выделить базис:
1)
(
)
{
}
zyxyxF ~,
=
;
2)
(
)
(
)
(
)
{
}
zxyzxzyxF →= ,| ;
3)
(
)
{
}
;, zyxyxzyxF
=
4)
(
)
(
)
(
)
{
}
;,, 00011000100101101001
=
F
5)
{
}
;,|,
2121
xxxxxxzyxF
=
6)
(
)
(
)
{
}
;, 110011101011011110
=
F
7)
(
)
(
)
(
)
;\\
10
TTLMSF UU
=
8)
(
)
(
)
(
)
;\\ SLTTMF UU
10
=
9)
(
)
(
)
(
)
;\\ SLTTMF UI
10
=
10)
(
)
(
)
{
}
;,~|, xyzxyxyzxF
=
11)
(
)
{
}
;,, zxyxzyxxF
=
6. Полна ли система
(
)
(
)
{
}
;...,,,...,
212211
xxfxxfF
=
если:
1) ;,,\ 1
2121
=∉∈ ffSLfMSf U
2) ;,, 1
21201
∉∈ ffSfLTf U
3) .ffTMfTTf 1
2112101
,\, I
9. ПРЕДИКАТЫ . ОПЕРАЦИИ НАД ПРЕДИКАТАМИ
Понятие предиката обобщает понятие высказывания.