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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

54
3. Доказать полноту следующих систем функций, используя теорему о
полноте 2-х систем:
1)
{
}
;, xyxG
®
=
2)
{
}
;yxG ¯=
3)
{
}
;,0yxG
®
=
4)
{
}
;,; 1yxyxG
Ú
Å
=
5)
{
}
;,~, xyxyxG
®
=
6)
{
}
.,; yxxG
Å
=
1
4. Доказать неполноту систем функций:
1)
{
}
;x
=
f
2)
{
}
.,,& yxyxyx
®
Ú
=
f
5. Используя критерий полноты, выяснить, являются ли полными сле-
дующие системы функций. В полных системах выделить базис:
1)
(
)
zyxyxF ~,
®
®
=
;
2)
(
)
(
)
(
)
}
zxyzxzyxF ¯®Å®= ,|
;
3)
(
)
{
}
;, zyxyxzyxF
®
Å
®
Ú
Ú
=
4)
(
)
(
)
(
)
{
}
;,, 00011000100101101001
=
F
5)
{
}
;,|,
2121
xxxxxxzyxF
Ú
Å
=
6)
(
)
(
)
{
}
;, 110011101011011110
=
F
7)
(
)
(
)
(
)
;\\
10
TTLMSF
U
U
=
8)
(
)
(
)
(
)
;\\ SLTTMF
U
U
10
=
9)
(
)
(
)
(
)
;\\ SLTTMF
U
I
10
=
10)
(
)
(
)
{
}
;,~|, xyzxyxyzxF
®
Ú
®
=
11)
.
F=xxy,zxy,xЪz

6. Полна ли система
(
)
(
)
{
}
;...,,,...,
212211
xxfxxfF
=
если:
1) ;,,\ 1
2121
=
®
Ï
Î
ffSLfMSf
U
2) ;,, 1
21201
º
®
Ï
Î
ffSfLTf
U
3) .ffTMfTTf 1
2112101
º
®
Î
Î
,\,
I
3. Доказать полноту следующих систем функций, используя теорему о
   полноте 2-х систем:
         1) G � �x � y , x�;
         2) G � �x � y�;
         3) G � �x � y ,0�;
         4) G � �x � y; x � y ,1�;
         5) G � �x � y , x ~ y , x �;
         6) G � �1; x , x � y�.
4. Доказать неполноту систем функций:
         1) � � �x �;
         2) � � �x & y , x � y , x � y�.

5. Используя критерий полноты, выяснить, являются ли полными сле-
   дующие системы функций. В полных системах выделить базис:
        1) F � �x � y , x � � y ~ z �� ;
            2) F � �x | � y � z �, �� x � z � � xy � � z �;
            3) F � �x � y � z � � x � y �, xy � z�;
            4) F � ��01101001�, �10001001�, �0001��;
            5) F � �x � yz , x | x , x 1 x 2 � x 1 x 2 �;
            6) F � ��10 �, �1010110111 110011 ��;
            7) F � � S \ M � � � L \ �T0 � T1 ��;
            8) F � � M \ �T0 � T1 �� � � L \ S �;
            9) F � � M \ �T0 � T1 �� � � L \ S �;
            10) F � �� x � z � � y , � x | y � x � ~ z , xy�;
            11) F =  x   x  y  , z x y, xЪz .

6. Полна ли система F � � f 1 � x1 ,..., x 2 �, f 2 � x1 ..., x 2 ��; если:
        1) f 1 � S \ M , f 2 � L � S , f 1 � f 2 � 1;
        2) f 1 � T0 � L, f 2 � S , f 1 � f 2 � 1;
        3) f 1 � T0 � T1 , f 2 � M \ T1 , f 1 � f 2 � 1.




                                                54

Страницы