NEWsbornik

2. x = y = 1. 13. à)

x

(y z), á)

x

yz , â) x(y

z

x

t

).

14. à)

x

y

, á)

x

y

, â)

x

y.

15. à)

x = 1, y = 0,

z = 1; á)

x = 1,

yНапример,= 0, z = 0. 16. a b =

a

·

17. ab =

a

. 21. à)

b

.

b

a = 0, b = 1; á) a = 0, b è c любые; в) a = b = c = 0.

24.

a = 0, b è c любые.

29. ab = (a → (b → 0)) → 0.

произвольную30. a b = (a →формулуb) → b.

32. Указание. Рассмотрите ab è

A(a, b, →) на строчках (0; 0), (0; 1) è

(1; 0).

33. y 1. 34. xy x y 1. 35. xy x z 1.

36.

xyz x y z .

37.

xyzt yzt xzt xyt xyz xy xz yt 1.

38.

xyz xy xz yz y z 1. 39. xyz xy yz y 1.

40.

abcd abc abd acd bcd ab ac ad bc cd bd a b c d.

41.

xy x 1. 42. xyz xy xz x z .

43. abcde abcd 1.

44.

a b c d 1.

45. xyz xz yz z 1. 46. 1.

47. 2n .

48.

22n . 50. 2n+1 , 2.

52.

x

y

z

. 53. x

z

xy

yz èëè

xz

yx

zy. 54.

x

z

y.

55.

a

d

b

c

cd.

56.

c

a

b

ab

d

.

57.

ac

e

bde ac

d

.

60.

x

y

zt. 61. x

yz

yt xy

z

.

62.

Упрощенныеx z . 63. x

y

схемыxy

отвечаютz . 64. xyÏÔ xz yz .

65. a

b

b

c

c

d

.

66.

Схема соответстует ПФ

x

yz è

x

y

z

.

схемы67.

отвечают ПФ

xy z(x y).

68. Упрощенные

x

y

z è

y(

x

z

).

69.

x

y

y

z

.

70.

yt y

t

. 71. (

x

z

)(

x

y).

72. (a b)(

c

d)(

b

c).

73.

(a b

c

)(

b

d

)(

a

c). 74. (a b)(

b

c

).

75.

(a c)(

a

b

c

).

76. (a

b

c

)(b c d)(a c d) èëè

(отвечаетa b

c

формуле)(b c d)(a

b

d). 77. Функциональная схема

xy

·

xz

·

yz

.

78. Функциональная схема

·

·

a

b

c

.

отвечает формуле

b

cd

d

79. Функциональная схема

ac

·

·

80.

x

= x ↓ x,

отвечает формуле

a

c

bc.

xy = (x ↓ x) ↓ (y ↓ y),

x y = (x ↓ y) ↓ (x ↓ y).

81.

x

= x → 0,

61

153.

Докажите следующие равенства

S

=

T

α ,

á) A ∩ ( S Bα) =

S (A ∩ Bα),

Aα

à)

A

α I

α I

α I

α I

T

=

S

α ,

ã)o A ( T Bα) =

T (A Bα).

Aα

â)o

A

α I

α I

α I

α I

154.

Выразите операции \ и через {4, ∩}.

1

a+1

1

a

[0;Åñëè), òî x [0;

) [1 − a; 1]; åñëè a [

; ∞), òî x [0; 1].

2

3

3

108åñëè.

|a| > 3, òî x ; åñëè a [2; 3], òî x [2a − 5; 1];

a [−2; 2], òî x [−1; 1]; åñëè a [−3; −2], òî

−остальных2 < a 6 −случаях1, 5, òî x (1 −

p

p

1 + a/2; 1 +

1 + a/2); â

x .

112. à) A = 1, B = 1; á) A = 0,

B = 0à); â) A = 1, B = 0. 113. à) A = 1, B = 0; á)

A = 0, B = 0.

114.

y [−1; 1]; á) y R; â) y (−∞; −1] [1; ∞); ã) .

115.

y (−∞; −1]. 116. y [−2; 0] (1; 2].

√

117.

y (−∞; 4) [5; ∞). 118. y (−∞; −1) [0;

2].

предыдущей119. A = 0, Bзадаче= 1. случай120. A = 1, B = 0.

125. Рассмотрите в

M1 = . 126. n кратно m.

127. à)k(n = 12k) → l(n = 4l) m(n = 6m).

131.

x y(P (x, y) Q(x)), P (a, b) Q(a).

x y(

Q(x)), x(

Q(x)).

132.

P (x, y)

P (x, f(x))

133.

x x0(P (x) Q(x0)), x0(P (c) Q(x0)).

x0 x00(P (x) ·

Q(x0)

· Q(x00)),

134.

P (x)

x00(P (x) ·

· Q(x00)).

Q(c)

P (x)

x x0 x00(P (x0) · Q(x)

·

Q(x00)),

135.

P (x)

0

00

0

00

)).

x xà)(P (x ) · Q(c) P (c) · Q(x

xã) M , x1 M .

137. à) p q,

p

·

q

; á) pq,

p

q

; â) p

q

,

p

q;

p q, p q.

150. X = A4B . 151. X = B (C \ A).

à)

t M является истинным предикат

P (t) → x P (x);

á) x P (x) → P (t).

x P (x) = x (x M1 → P (x)),

x M1

x M

á) x P (x) = x (x M1 P (x)).

x M1

x M

125.o Почему естественно доопределить следующим образом кван-

òîðû: x P (x) = true, à x P (x) = false?

x

x

à) lim f(x) = A,

á) x0 = inf M , â) A = sup f(x).

x→x0

x M

214.

0

0

0

0

0

).

а)Например,Нет, б) нет,(x, â)y) äà6 .(x , y

),а)еслиНе xинъективна< x (x =èxíå y 6 y

220.

221.

сюръективна, б) сюръективна, но не инъективна, в) инъективна,

но не сюръективна, г) биективна. 222. а) Инъективна, но не

сюръективна, б) сюръективна, но не инъективна, в) не

инъективна и не сюръективна, г) биективна.

223.

а) Например,

f(n) = [

n

]; б) например, f(n) = 2n.

224. б) Например,

2

f : Rá)→Например,R, f(x) = x2 , A = (−1; 0), B = (0; 2).

225.

f : R → R, f(x) = x2 , A = (−1; 0),

B = (0; 2).

226. à)

p(x) = x2 + 1, q(x) = (x + 1)2 ; á) p(n) = n,

q(n) =Например,|n − 1| + 1; â) p(m, n) = (m + n, m + n), q(n) = 2n.

229.

A = {a}, B = {a, b}, F (a) = a, G(a) = a,

Gинъективно,(b) = a. 230á). à) F −1 не функционально, т.к. F íå

â)

F −1

не функционально, т.к. F не сюръективно,

F −1

функционально, F −1(x) = −√

, ã) F −1

функционально,

x

F −1(n5040) = Fспособов(n). 232. . 144.120233. . 40; 256168030.

.

234. −363.

235.

kAnk−−11 .

236.

237.

238. 2(n − 1)!.

239. 648.

240.

241. 27216.

242. 13776.

243. 64, 17760.

244. kn

способов.биективных,245åñëè. 2n .

246. nm ; Anm инъективных, если m 6 n; n!

2n−1 .

m = n.

247. 3n − 1.

248. 2n+1 .

249. 22n−1 .

250.

251. 151200.

252. 720.

253. 2520. 254. 1260.

255.

(m+n)!

257. −126. 258. −1904.

259. 252.

m!n!

.

256. 60.

k

k

P xixjxl .

260.

P xi2 + 2 P xixj .

261.

P xi3 + 3 P xi2xj + 6

i=1

i<j

i=1

i=6j

i<j<l

263.

265.

266.

126.

267.

60.

268.

1199.

271.

Указание.

n

91.n

3. n−1

C2n = C2n−1 + C2n−1 .

273. 100, 5050, 220.

274. 293930.

275.

Ck

(p+1)!

Ck−n

способов(n.)

способов56. .

276.457q!(.p−q+1)! .734277. . 36.

729278. .

(n) 218.

150.

279.

280.

281.

282.

283.

284.

285. 4. 286. 12.

287.

в) Указание. Используйте, что

k · Pn(k) = nPn−1(k − 1).

288. (1 − tn+1)/(1 − t). 289. à)

1

1−t ,

á)

n

1

nt

n .

(1 + t)

290. A(t) =

, E(t) = e

291. 2

.

1−nt

.

292.

à)

t/(1 − t)2 , á) t(1 + t)/(1 − t)3 .

293. 2t2/(1 − t)3 .

294.

à)

tet , á) t(1 + t)et .

295. (2n+1 − 1)/(n + 1).

296. 0.

n2n−1

. 298. (2n−3)t+3

299. (e2 − 1)/4.

300. −t3 ln |1 − t|.

297.

(1−t)n+1

.

304.

K(27, 6, 10) = 55252.

305. un = n + 1.

65

o

M , то в ее сокращенной ДНФ нет

отрицаний94. Докажите,. что, если f

95.o Докажите незамкнутость относительно суперпозиции следу-

ющих классов:

ã) S L.

à) K0 K1 ; á) L M ; â) K0 M ;

постоянная363.

функция.

à)C(I12(x1, x2)), ãäå C(x) ≡ c

á)

365.

f(t, x) = t(x + 1),

f(t, x) = t + (x −. 1), â) f(t, x) = 2 −. tx, ã) f(t, x) = 2t(x+1) .

366.

à) 2x + 1, á) x2 , â) 2x , ã)

t +

x(x−1)

367. à) tt

x ,

2

.

á) (t1à)+ t2)x . 369. Например, x = y = 2, z = 3.

â)371.

JP =

sg(|f(x, y) − g(x, y)|), á) JP = sg(|f(x, y) − g(x, z)|),

ä) JP =

sg(f(x, y) −. g(x, x)), ã)

JP = sg(g(z, t) −. f(x, y)),

á)

sg

f(x, y), å) sg f(x, y) ·

sg(f(x, y) −. z).

372. à) x −. (x −. y),

á)

x + (y −. x), â)x + ((y + (z −. y)) −. x). 373. à) 1 +

sg(y −. x),

x sg(|x − 2|). 374. x + sg(5 −. y) + x sg(y −. 9).

375.

sg(x) + (t −. (x −. 1)) sg(x).

376.

2t ·

sg(x) + (x −.

1)

sg((x −.

1) −.

t). 377. f(0) = 0,

f(x +à)1) = 1 −. f(x).

378. f(0) = 0,

f(x + 1) = x −. f(x).

á)379. (2x −. 9) sg(10 −. x) + (x + 1) sg(x −. 9),

â) (x2 −. 7)

sg(x −. 3) + (2x + 1) sg(x −. 3),

(x2 + 2) sg(3 −. x) + (x + 5) sg(x −. 2).

380.

d(x, y) = µt (x < y(t + 1)).

381. x −.

y[x/y].

P

t6x

P i

382.

sg(r(x, i)) −.

sg

x. 383.

sg(r(x, i)). 384. τ(x) = 2.

i6x

i6x

385.

sg(xy) · µt (t . x t . y t > 0).

t6xy

386.

f(x) = µt (2x2 < (t + 1)2).

t62x

387.

µt (4xy < ((t + 1)2 −.

(x + y))2).

t6x+y

â)388. à) f(x) = (2x + 1) sg(x), á) 2

sg(x),

(4x + 26)

sg(x −. 4) + (3x + 30) sg(x −. 4).

389. à) g(x) = 0, åñëè

xíå=определена,3 и не определена,если

åñëè x =6 3; á) g(x) = x −. 2, åñëè x > 2 è

ã)

x < 2; â) g(x) нигде не определена;

66.

Для схем, изображенных на рис. 1 и 2, найдите функцию

проводимости, преобразуйте ее к минимальной ДНФ и постройте

упрощенную схемуyпо минимальной ДНФ.

r

x

r

r

r z HH y

r

z

r

−

x

x

H

H

+

r

x

r

+ r

HH

z

HHHr−

H

H

H

H

y

H

H r y

z

x HH r z

H

Ðèñ. 1

Ðèñ. 2

68.o Для схем, изображенных на рис. 3 и 4, найдите функцию

проводимости, преобразуйте ее к минимальной ДНФ и постройте

упрощенную схему по минимальной ДНФ.

+

r

r

r r

r

r

y

r

z

r

y

r

z

A

y

x

+ xr

x

y

AA r−

r

z

x

t

z

z

A

A

r

r

r x

r

r

yAA

r

r

r

−

y

y

z

x

z

A

Ðèñ. 3

Ðèñ. 4

В задачах 69 70 требуется найти минимальную ДНФ и по-

строить контактную схему по этой ДНФ для недоопределенной

булевой функции f .

1 на наборах 0, 1, 3, 4, 13;

69. f(x, y, z, t) =

0 на наборах 7 − 10, 14.

1 на наборах 1, 4, 11, 14;

70.o f(x, y, z, t) =

следующей,программе состояние,

0L

,

q61 → q00E

. 414. Â

q50 → q01L q30 → q60L q6

0 → q6

значению предиката, а

q20

соответствует истинному

q30

ложному: q10 → q20R, q20 → q30R,

программе для,

1

→ q300L

,

q30

0

→ q00L

. 415. Аналогично

q200

→ q0

1L q30

x −. y.

416. y = 1 − x.

417. y = 2.

3

422. ПрограммаC ◦ HR ◦ Zмашины◦ HL ◦ G ◦ T R ◦ HL ◦ T R ◦ H ◦ HL ◦ F .

2

423.

T может быть следующей:

q10 → q20R, q20 → q00L(q0q0T1), q21 → q30L(q3q4T2),

q40 → q51L, q51 → q60E(q6q1HL), ãäå

T1 = HR2 ◦ T R ◦ Z ◦ HL ◦ T R ◦ Z ◦ HL,

ýòîì ì-ò

2

◦ T R

◦ C ◦ T R ◦ HR ◦ C ◦ P L ◦ HL ◦ P L ◦ N ◦ HL

, ïðè

T2 = HR

машины P L вычисляет сумму двух чисел.

424. Программа

T может быть следующей: q10 → q20R,

q20 → q00L(q0q0T1), q21 → q31L(q3q4T2), q40 → q51L,

q51 → q60E(q6q1HL), ãäå

T1 = HR3 ◦ (T R ◦ Z ◦ HL)3 ,

3

Например:

◦ HL

2

, à ì-ò

P L

вычисляет сумму

двух чисел.

T2 = HR

◦ T R

◦ C ◦ T R ◦ P L

425.

q10 → q20E(q2q3C ◦ HR ◦ F ),

69

39.

x

y

z.

40. a b c d.

41.

x → y.

42. (x → y) → z.

43.o a → (b → (c → (d → e))).

44. a b c d.

45.

x y

(z → x).

46.o (xy → zx)

xyz

.

47.

Какое максимальное количество слагаемых может быть в

многочлене Жегалкина от n переменных?

48.

Найдите количество всех многочленов Жегалкина от данных

n переменных.

49.

Докажите, что любая булева функция может быть реализо-

вана только одним многочленом Жегалкина.

50.o

Булева функция называется линейной, если ее многочлен

линейных БФ от

,

ci

{0; 1}

. Íàé-

дитеЖегалкинаколичествоимеетвсехвид c0 c1x1

c2x2 . . . cnxn

них имеют

n переменных. Сколько из

n существенных переменных?

6

481. à)H = {a, b, f(a), f(b), f(f(a)), f(f(b)), . . .}.

482. H = {a, b}.

484.ã)

x = 0, 5, y = 1; á)

x = 0, 5,

y = 0; â) x = 0, 5, y = z = 1;

ðèñx. =20;0,ã)5,åñëèy = z = 0.

486. à) ñì. ðèñ. 18; á) ñì. ðèñ. 19; â) ñì.

ñì. ðèñ. 22; ä) ñì0.6ðèñC.6230., 5, òî ñì. ðèñ. 21, åñëè 0, 5 6 C 6 1, òî

y

q

y

q

y

q

6

6

6

1

q

1

q

1

q

C

q q -