Дискретная математика. Элементы теории задачи и упражнения. Часть 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. ПРЕДИКАТЫ . ОПЕРАЦИИ НАД ПРЕДИКАТАМИ
Понятие предиката обобщает понятие высказывания. 
                                            106
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
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 ), x y → z};
           4) F ={(01101001), (10001001), (0001)};
           5) F ={x ⊕ yz , x | x , x 1 x 2 ∨ x 1 x 2 };
           6) F ={(10 ), (1010110111110011)};
           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 ={f1 (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.




          9. ПРЕДИКАТЫ. ОПЕРАЦИИ НАД ПРЕДИКАТАМИ

       Понятие предиката обобщает понятие высказывания.

Страницы