книги / Основы дискретной математики

{/.3. 5,7}

, наибольшего

в наименьшего

элементов нет; J u p £ s

i n f 8

не

существует; в)

максимальные

элементы

0 . 2 } , минималь­

ные

{

Z 8,

9, / о }

;

наименьшего и наибольшего элементов нет; 5ар 5

не

существует,

i n

f 0 : 0 ;

д) максимальный элемент {/}» минималь­

ные {5.6. 7.6, 12, f5. f*t}% наименьшего элемента,

наибольший О],

2. Математическая логика

3.

Таблица 6.1

Таблица 6.2

0

0

1

0

0

0

I

о

I

I

0

0

1

I

1

0

0

0

1

0

I

X

I

I

0

I

I

I

1

0

0

I

1

О

I

I

I

I

о

I

I

I

I

I

6. 16 операций; кавдая операция задается своей таблицей

истинности,

так что задача

заключается в том. чтобы найти об­

щее число различных таблиц.

™ V

D/ £ “^ , (Sa^

рвшаетс" аналогично ирелиуще

Ь)

( X * у ) 4 Z B ( х у у ) & Z * (К, (у, y j ) 4 z - (Щ

~

-

s ((x i(y t y j)iz )i((x i(y /y j) l z )

<у

y})

Z

е

25,

x v z

. н )

x s z v U

z v i & u

t i

£VCAZ>

*) xA y A z v ia у А г v х Л % у

г / Л

9

и) A 4 6 V A Z C V S 4 C V 0 4 с ,

Л f t ? * г 9 4 *

т)

x A y v y A l ,

I )

X . Z x . V X Z X

V I Ax'

w

s

в) у v х A z .

' *

t * * t v S * b

ш) * v y v z

А у. у2 У, У/ yt y2 A

Ух A

y, У/

У, У/

Af

У,

A

У/

У2

So &01f a 4зь

Bn *a f a

§22 £23 4у £32 £& fat % £уз

£si 8s?

о£г

f a £п

ht ht

В Bsf B2f

f a

f a

B2f £31

8*ff

Sst

801

**t

£з(

8

//

S¥1 31

£ f a

£/2$22f a

&a£$2£st £22 f a

£02B,22в*г By? £52 £02 822 й г

e,i

к

*os

** h , f a £33£33 fa

3

3

803

£23

£vs

£33

803

£23

8j3 £/3

Bf

&&Э

i—

Таблица 6.4

i

A

A

Ух

Уз

Ум Ух A

/

У/

A

Ух

У/ Уt Уз

Уз

У/

У

832 833 fat 8*2

fax

f a

£01

В02 So, £// 8/2 8/3

** '«

£23 Bxt

*1

f a

80/ *21 £ 31

fat fa/ f a

£xt 83/ fa t

fa t

fa t 8xt fa t

8ot

f a t

*02

£02

£22

£32

Y

£22

£J I

Y

£$2 822 832

802 8*2

x/

£ 2832 802

8 2 fax

fas 823 £3318c3

ь

f a

to*

£33

£43 £33 80s £23

£33

tv*

Q

8*3

8 3

8.

а) рис. 6.18.

а

б

Рис.

6.22.

9. а) ядра нет;

б) {3 ,5 } ; в)

ядра нет; г) { 1 , 3 ) ; д) { 2 , 5 }

в) f 1.53; ж).{2 ,4 }

; { 3 , 5 } - два

ядра; в) { 1 , 4 } ; ж) £ 1 ,4 };

i t

Л

А П Ь A P f ,

/

К П Ь

в) будем представлять любое

натуральное число, а такие

h

f3

fs

Л

щ ,

-

Aflt„

A C f B

/

Щ я

/Lftfs

+

-

—

-

—

е) табл. 6.7.

It

Таблица 6.7

9j

9з

Л

on Я2

ЛП 9л

{СЯо

0

OH 9i

7C£A-

/

tn<t2

L

fO9s

2CAsu

2

2ГЫ,

2 n L

A C 9о

3

5 П ъ 2

_ J/7«*

ttcis-

4

f/7 h

__5СЯя-

5

_5Я Я2

8/?9I

CCl£-

6

on%2 n

6П9,

iC JLsu

7

-7Я9»

70*2

JCXs-

8

_6/7y2

8П 92

9C1s-

9

90<f*

Mil..

2* а)

входной алфавит { Л . 1 } , схема подстановок /Л

б)

входной алфавит {Л,1, Ч . Н Ч } , схема подстановок

11 ~ Л .

1-*.Ч ;

Л - . Н Ч ;

в)

входной алфавит { x . y . z }

, схема подстановок д — -</>

y - z .

zz-*z,

Z~*. ZZX .

3.

а)

//>; =

s f x ) ,..)}=

х + п .

п р а г

в)

f f r . O J s f ( % ) ж А * (х) = X ,

У - / /Л.

Я

О, f ( X . O ) ) * h

(х, о. х )= s ( J * ( x . v ) J ‘ X о /;

Я ‘ г

{ (* . 2 )* k (x ,

f. / ( x , f ) } * h

( x j , x i-f)= s(ct* (x,/,x* fj= X+2;

y - 0 - t ( x , o ) * y ( x ) - Z ( x ) = 0 ,

у - i ;

t) - k ( x . о, { (x ,o ))= J* (> г,а //у.<з“

А.о, / л . o;j= *.

r t:{(*.ЦфЬ (*-y.{(*.</))= **(х.у.Ы*4(*'1-

s

t 3

J