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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
101
1)
(
)
00111001
=
f ;
2)
(
)
;zyxtzyxf
∨
∨
∨
=
3)
(
)
(
)
;zxyxf ⊕→↓=
4)
t
z
yt
xz
xy
f
∨
∨
∨
=
.
11. Выяснить, каким из множеств
0110
TTTT \,U принадлежат перечислен -
ные ниже функции:
1)
(
)
(
)
(
)
(
)
(
)
;~| xzyyzxyx →↓→∨
2)
(
)
(
)
(
)
(
)
.| xyzzxzxy ⊕↓→→
12. Сколькими способами можно расставить скобки в выражении
12121
xxxxx
, чтобы получилась формула , реализующая
функцию из
.0
T
13. Подсчитать число функций, зависящих от переменных
n
xxx ,...,,
21
, в
каждом из следующих множеств:
1)
;
01
TT I
2) ;LT I
0
3) ;LT U
1
4)
(
)
;\
10
TTL I
5) ;ST I
1
6) ;
1
TSL II
7)
;
10
TTS II
8) ;
10
TT U
9)
(
)
;\
10
TTS I
14. Найти функцию
(
)
,,..., xxf если:
1)
(
)
;\...,
011
TTxxf
n
∈
2)
(
)
(
)
;\,..., STLxxf
n
I
11
∈
3)
(
)
;\,...,
01
TSxxf
n
∈
15. Какие из перечисленных ниже функций являются монотонными:
1)
(
)
;yxx
2)
(
)
;xyx
3)
(
)
;yxxy
⊕
4)
;
x
zx
yz
xy
⊕
⊕
⊕
5)
(
)
;00110111
=
f
6)
(
)
;011001111
=
f
7)
(
)
;0101110001010101
=
f
8)
(
)
1111110000000010
=
f 
                                           101
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
           1) f =(00111001) ;
           2) f =( x ∨ y ∨ z )t ∨ xyz ;
           3) f =(x ↓ y ) → ( x ⊕ z );
           4) f = xy ∨ xz ∨ yt ∨ z t .

11.Выяснить, каким из множеств T0  T1 , T1 \ T0 принадлежат перечислен-
   ные ниже функции:
         1) (( x ∨ y ) → ( x | yz )) ↓(( y ~ z ) → x );
         2) ( xy → z ) | (( x → z ) ↓(z ⊕ xy )).

12.Сколькими способами можно расставить скобки в выражении
   x1 → x 2 → x 1 → x 2 → x1 , чтобы получилась формула, реализующая
   функцию из T0.

13.Подсчитать число функций, зависящих от переменных x1 , x 2 ,..., x n , в
   каждом из следующих множеств:
  1) T1  T0 ;            4) L \ (T0  T1 );       7) S  T0  T1 ;
  2) T0  L;              5) T1  S ;              8) T0  T1 ;
  3) T1  L;              6) L  S  T1 ;          9) (S \ T0 )  T1 ;

14.Найти функцию f ( x ,..., x ), если:
        1) f ( x1 ..., x n ) ∈T1 \ T0 ;
        2) f ( x1 ,..., x n ) ∈L \ (T1  S );
        3) f ( x 1 ,..., x n ) ∈ S \ T0 ;

15.Какие из перечисленных ниже функций являются монотонными:
      1) x → ( x → y );
      2) x → ( y → x );
      3) xy( x ⊕ y );
      4) xy ⊕ yz ⊕ zx ⊕ x;
      5) f =(00110111);
      6) f =(011001111);
      7) f =(0001010101010111);
      8) f =(0000000010111111)

Страницы