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

UptoLike

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

49
2)
(
)
;zyxtzyxf
Ú
Ú
Ú
=
3)
(
)
(
)
;zxyxf Å®¯=
4)
f=xyxzytzt.

11. Выяснить, каким из множеств
0110
TTTT \,
принадлежат перечислен-
ные ниже функции:
1)
(
)
(
)
(
)
(
)
(
)
;~| xzyyzxyx ®¯®Ú
2)
(
)
(
)
(
)
(
)
.| xyzzxzxy ů®®
12. Сколькими способами можно расставить скобки в выражении
12121
xxxxx
®
®
®
®
, чтобы получилась формула, реализующая
функцию из
0
T
.
13. Подсчитать число функций, зависящих от переменных
n
xxx ,...,,
21
, в
каждом из следующих множеств:
1) ;
01
TT
2) ;LT
0
3) ;LT
1
4)
(
)
;\
10
TTL
5) ;ST
1
6) ;
1
TSL
7) ;
10
TTS
8) ;
10
TT
9)
01
\.
STT
I
14. Найти функцию
(
)
,,..., xxf если:
1)
(
)
;\...,
011
TTxxf
n
Î
2)
(
)
(
)
;\,..., STLxxf
n
11
Î
3)
.
\
1n
fST
0
x,...,x
15. Какие из перечисленных ниже функций являются монотонными:
1)
(
)
;yxx
®
®
2)
(
)
;xyx
®
®
3)
(
)
;yxxy
Å
4)
;
x
zx
yz
xy
Å
Å
Å
5)
(
)
;00110111
=
f
6)
(
)
;011001111
=
f
7)
(
)
;0101110001010101
=
f
8)
f=0000000010111111.
            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. Сколькими способами можно расставить скобки в выражении
    x 1 � x 2 � x 1 � x 2 � x 1 , чтобы получилась формула, реализующая
   функцию из T0 .

13. Подсчитать число функций, зависящих от переменных x 1 , 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 � x 1 ..., x n � � T1 \ T0 ;
         2) f � x 1 ,..., x n � � L \ �T1 � S �;
            3) f  x1 ,...,xn  S \ T .
                                      0

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




                                               49