сборник задач по дискретке другой вариант

13)A – множество людей, Q(x, y) "x любит y";

14)A – множество людей, Q(x, y) "x родитель y";

15)A – множество людей,

Q(x, y) "x живет в одном городе с y".

6. Пусть A = {a,b,c} , а предикат Q(x, y) задан таблицей. Определить истинность следующих формул в модели M = A; Q(2) .

1)xQ(x,a), xQ(x,a), xQ(a, x), xQ(a, x);

2)xQ(x,b), xQ(x,b), xQ(b, x), xQ(b, x);

3)x yQ(x, y), y xQ(x, y),

x yQ(x, y), y xQ(x, y); 4) x yQ(x, y), y xQ(x, y),x yQ(x, y), y xQ(x, y)

x	y	Q(x, y)
a	a	0
a	b	1
a	с	1
b	a	0
b	b	1
b	с	1
с	a	0
с	b	1
с	с	1

7. Пусть A – множество точек, прямых и плоскостей трехмерного евклидова пространства. Рассмотрим модель M = A; f , где f –

соответствие, которое для предикатных символов P1 (x), P2 (x),

P3 (x), Q(x, y), E (x, y) определяет следующие предикаты: P1 (x) "x − точка", P2 (x) "x − прямая",

P3 (x) "x − плоскость",

Q(x, y) "x лежит на y", E (x, y) "x совпадает с y". Записать в этой модели следующие утверждения:

1)через каждые две точки можно провести прямую и притом единственную, если эти две точки различны;

2)через каждые три точки, не лежащие на одной прямой, можно провести единственную плоскость;

3)определение параллельных прямых;

4)определение параллельных плоскостей;

5)аксиому Евклида о параллельных прямых (через точку, не лежащую на данной прямой, всегда можно провести прямую, параллельную данной прямой, причем только одну).

41

8.Пусть P A2 – бинарное отношение. Подобрать необходимую модель и записать следующие утверждения и их отрицания:

1)P – рефлексивное отношение;

2)P – иррефлексивное отношение;

3)P – симметричное отношение;

4)P – антисимметричное отношение;

5)P – транзитивное отношение;

6)P – отношение эквивалентности.

9.В модели M = P (A); S(2) , где

A – некоторое множество, S (x, y) "x y",

записать следующие утверждения:

1)x – пересечение y и z ;

2)x – объединение y и z ;

3)x = ;

4)x = A;

5)x – дополнение y .

10.Пусть L – множество людей, а где f – соответствие, которое

для предикатных символов E (x, y), P(x, y), Ch(x, y), S (x, y),

D(x, y), F (x, y), Dc(x, y), C (x, y), H (x, y), Wf (x), M (x), W (x)

определяет предикаты:

E	(x, y) "x è y − î äèí è òî ò æå ÷åëî âåê";
P(x, y)	"x ро дитель y";	Ch(x, y) "x ребен о к y";
S (x, y) "x ñû í y"; D(x, y) "x − äî ÷ü";
F (x, y)	"x ï ðåäî ê y";	Dc(x, y) "x ï î òî ì î ê y";
	C (x, y) "x è y − ñóï ðóãè ";
H (x, y) "x ì óæ y";		Wf (x, y) "x æåí à y";
M (x) "x − м ужчин а";		W (x) "x − æåí ù èí à".

42

Записать в модели M = L; f			формулы, выражающие следую-
щие утверждения:
1) некоторые супруги бездетны;			17)	x – деверь (брат мужа);
2) некоторые супруги имеют детей;			18)	x – шурин (брат жены);
3) некоторые супруги имеют детей			19)	x – золовка (сестра мужа);
только женского пола;
4) некоторые супруги имеют детей			20)	x – свояченица (сестра жены);
только мужского пола;
5) x внебрачный сын y ;			21)	x – дядя (брат отца или матери);
6) x внебрачная дочь y ;			22)	x – тетя (сестра отца или матери);
7) x – тесть (отец жены);			23)	x – сноха (жена брата мужа);
8) x – теща (мать жены);			24)	x – свояк (муж сестры жены);
9) x – свекор (отец мужа);			25)	x – племянник (сын сестры или
			брата);
10) x – свекровь (мать мужа);			26)	x – племянница (дочь сестры или
11) x – зять (муж дочери);			брата);
			27)	x – кузен (двоюродный брат);
12) x – невестка (жена сына);			28)	x – кузина (двоюродная сестра);
13) у каждого есть бабушка;			29)	x – двоюродный дядя;
14) у каждого есть дедушка;			30)	x – двоюродная тетя;
15) у каждого есть отец и мать;			31)	x – двоюродный племянник;
16) x – незаконнорожденный			32)	x – двоюродная племянница;
M = L; E(2),P(2),C(2),M (1),W (1) ,			M = L; E(2),F(2),C(2),M (1),W (1)		,
1			10
M = L; E(2),P(2), H (2),M (1),W (1)		,	M = L; E(2), F(2),H (2),M (1),W (1)		,
2			11
M = L; E(2),P(2),Wf (2),M (1),W (1)		,	M = L; E(2),F(2),Wf (2),M (1),W (1)		,
3			12
M = L; E(2),Ch(2),C(2),M (1),W (1)		,	M = L; E(2), Dc(2),C(2),M (1),W (1)		,
4			13
M = L; E(2),Ch(2),H (2),M (1),W (1)		,	M = L; E(2),Dc(2),H (2),M (1),W (1)		,
5			14
M = L; E(2),Ch(2),Wf (2),M (1),W (1)			, M = L; E(2), Dc(2),Wf (2),M (1),W (1) .
6			15
M = L; E(2),S(2),D(2),C(2)	,
7
M = L; E(2),S(2),D(2),H (2)	,
8
M = L; E(2),S(2),D(2),Wf (2)	,
9

43

11. Пусть f (x) – всюду определенная фиксированная функция. Рассмотрим модель M = ¡; g , где g – соответствие, которое для предикатных символов T (x, y, z), Q(x, y, z) и S (x) определяет предикаты:

S (x) "x > 0"; P(x,a,b) "x [a,b]";

A(x, y, z) " x − y < z"; B(x, y, z) " f (x)− y < z"; F (x, y, z) " f (x) − f ( y) < z".

Сформулировать следующие утверждения:

1)число A есть предел функции f (x) при x → x0 ;

2)неверно, что число A есть предел функции f (x) при x → x0 ;

3)не существует предела функции f (x) при x → x0 ;

4)f (x) непрерывна в точке x0 ;

5)f (x) разрывна в точке x0 ;

6)f (x) непрерывна на [a,b];

7)f (x) разрывна на [a,b];

8)f (x) равномерно-непрерывна на [a,b];

9)f (x) не является равномерно-непрерывной на [a,b].

10)функция f (x) непрерывна на отрезке [a,b], но равномернонепрерывной на этом отрезке не является.

12.Подобрать необходимую модель и записать следующие утверждения и их отрицания:

1)f (x) – возрастающая функция;

2)f (x) – монотонная функция;

3)f (x) – ограниченная функция;

4)f (x) – бесконечно большая функция;

5)f (x) – бесконечно малая функция.

44

13.Подобрать необходимую модель и записать следующие утверждения и их отрицания:

1)xn – возрастающая последовательность;

2)xn – монотонная последовательность;

3)xn – ограниченная последовательность;

4)xn – бесконечно большая последовательность;

5)xn – бесконечно малая последовательность.

14.Определить являются ли следующие формулы истинными, ложными или выполнимыми в модели M = ¢+ ; S(3) , P(3) , E(2) , где

S (x, y, z) Û "x + y = z", P(x, y, z) Û "xy = z", E (x, y) Û "x = y".

1)"x"y "z "u ((S (x, y, z)Ù S (x, y,u)) É E (z,u));

2)"x"y"z "u ((P(x, y, z)Ù P(x, y,u)) É E (z,u));

3)(S (x, y, z) Ù S (x, y,u)) É E (z,u);

4)$y (P(x, x, y) É S (x, x, y));

5)$x S (x, y, y) É "x S (x, y, y);

6)$x S ( y, x, y) É "y P( y, x, y);

7)$x S (x, x, y);

8)$y S (x, x, y).

15.Выполнимы ли следующие формулы:

1)

$xP(x);

6) P(x) É "yP( y);

2) "xP(x);

7) $xP(x) É P( y);

3)

$x$y (P(x)Ù ¬ P( y));

8) "x$y (P(x) É ¬ P( y));

4)

$x"y (P(x, x)Ù ¬ P(x, y));

))

9) "x$y ( ¬ P(x) É P( y));

5)

$x"y

(

Q

(

x, y

)

É "zR

(

x, y, z

;

10)

y x(P(x)

É ¬

P( y));

$ "

11)

$y"x( ¬ P(x) É P( y))?

45

16. Будут ли общезначимы следующие формулы:

1) "xP(x) É P( y);	4)	¬($xP(x) É "xP(x));
2) P( y) É "xP(x);	5)	$x"yQ(x, y) É "y$xQ(x, y);
3) $xP(x) É "xP(x);	6) "x$yQ(x, y) É $y"xQ(x, y)?

17. Докажите, что следующие формулы общезначимы:

1)	¬$xP(x) É ¬"xP(x);	2) "xP(x) É $xP(x);
3) "xP(x) É P( y) ;		4) P( y) É $xP(x) ;
5) "x"yP(x, y) : "y"xP(x, y) ;		6) $x$yP(x, y) : $y$xP(x, y);

7)("xA(x) Ù C ) : "x( A(x) Ù C );

8)(C Ù "xA(x)) : "x(C Ù A(x));

9)(C Ù $xA(x)) : $x(C Ù A(x));

10)($xA(x) Ù C ) : $x(A(x) Ù C );

11)(C Ú "xA(x)) : "x(C Ú A(x));

12)("xA(x) Ú C ) : "x( A(x) Ú C );

13)(C Ú $xA(x)) : $x(C Ú A(x));

14)($xA(x) Ú C ) : $x(A(x) Ú C );

15)(C É "xA(x)) : "x(C É A(x)) ;

16)("xA(x) É C ) : $x(A(x) É C );

17)($xA(x) É C ) : "x(A(x) É C );

18)(C É $xA(x)) : $x(C É A(x));

19)("xA(x) Ù "xB(x)) : "x( A(x) Ù B(x));

20)($xB (x) Ú $xA(x)) : $x(B(x) Ú A(x));

21)"x(A(x) É ¬ B(x)) É ¬($xA(x) Ù "xB(x)) ;

22)"x(A(x) É ¬ B(x)) É ¬("xA(x) Ù $xB(x)) ;

23)$x(P (x) É Q(x)) : ("xP(x) É $xQ(x));

24)$x(P(x) Ù (B É R(x))) É ("x(P(x) É ¬R(x)) É ¬B).

46

18.Найти нормальную форму для следующих предикатов:

1)¬$x"y$z"uA;

2)$x"yA(x, y) Ù $x"yB(x, y) ;

3)$x"yA(x, y) Ú $x"yB(x, y) ;

4)$x"yA(x, y) É $x"yB(x, y) ;

5)$x"yA(x, y) É "x$yB(x, y) ;

6)($x"yA(x, y) Ú $xB(x)) É $y"xC (x, y);

7)¬ ($x"yA(x, y) É $y$zB( y, z)) Ù¬$y$zC ( y, z);

8)($x"yA(x, y) Ú ¬"x"yB(x, y)) É ¬"zC (z) ;

9)("x$y"zA(x, y, z) Ú ¬"yB( y)) É ¬"x"zC (x, z) ;

10)¬("x"y"zA(x, y, z) É $y$zB( y, z)) Ù "x"zC (x, z);

11)("x"yA(x, y) É $x$y"zB(x, y, z)) É $zC (z) ;

12)¬ "x$yA(x, y) É ("y"zB( y, z) ɬ "zC (z));

13)¬ $yA( y) É ("y"zB( y, z) ɬ "zC (z));

14)¬ ("x"yA(x, y) Ú "x$yB(x, y)).

19.Докажите теорему о дедукции для предикатов.

Указание. Доказательство аналогично доказательству теоремы о дедукции для высказываний, только добавляются ещё два случая:

1) Вспомогательный вывод содержит формулы: i. CÉP(x),

ii. CÉ"xP(x) "-правило, i.

тогда в результирующем выводе должна появиться последовательность формул:

k. AÉ(CÉP(x))

× × ×

m. AÙCÉP(x)

m+1. AÙCÉ"xP(x) "-правило, m

× × ×

n. AÉ(CÉ"xP(x))

47

2) Вспомогательный вывод содержит формулы: i. P(x)ÉC

ii. $yP(y)ÉC $-правило, i

тогда в результирующем выводе должна появиться последовательность формул:

k. AÉ(P(x)ÉC)

× × ×

m. P(x)É(AÉC)

m+1. $yP(y)É(AÉC) $-правило, m

× × ×

n. AÉ($yP(y)ÉC)

Здесь A является переносимой посылкой. Для доказательства теоремы необходимо восстановить для обоих случаев пропущенные формулы результирующего вывода (т.е. формулы между k-й и m-й, m+1-й и n-й.

20.Дано неравенство kx + l2 ≤ 0. При каких значения k истинны следующие утверждения:

1)При любом l неравенство имеет хотя бы одно решение.

2)Существует l , при котором неравенство имеет хотя бы одно решение?

21.Рассмотрим два определения легкой контрольной:

1)Контрольная называется легкой, если каждую задачу решил хотя бы один ученик.

2)Контрольная называется легкой, если хотя бы один ученик решил все задачи.

Может ли контрольная быть легкой в смысле первого определения и трудной (не легкой) в смысле второго? Может ли работа быть легкой в смысле второго определения и трудной в смысле первого?

22.Замените многоточия словами «необходимо и достаточно», «необходимо, но не достаточно», «достаточно, но не необходимо» так, чтобы получились верные утверждения:

1)Для того чтобы определитель матрицы был равен нулю … чтобы ее строки (столбцы) были линейно зависимы.

2)Для сходимости монотонной последовательности … чтобы она была ограниченна снизу.

48

3)Для того чтобы последовательность расходилась … чтобы она была неограничена.

4)Для того чтобы из три числа a, b, c были равны между собой, …

чтобы выполнялось уравнение (a − b)2 + (b − c)2 = 0.

5)Для того чтобы сумма двух действительных чисел была числом рациональным, … чтобы каждое слагаемое было рациональным числом.

23.Какие из следующих шести теорем являются по отношению друг к другу обратными, противоположными, противоположными обратным? Какие из этих теорем верны?

1)Если каждое из двух натуральных чисел делится нацело на 7, то их сумма делится на 7.

2)Если ни одно из двух чисел не делится на 7, то их сумма делится на 7.

3)Если хотя бы одно из двух чисел делится на 7, то их сумма делится на 7.

4)Если сумма двух чисел делится на 7, то каждое слагаемое делится на 7.

5)Если сумма двух чисел не делится на 7, то ни одно из слагаемых не делится на 7.

6)Если сумма двух чисел не делится на 7, то хотя бы одно из слагаемых не делится на 7.

24.Для каждой из нижеследующих теорем сформулировать обратную, противоположную и противоположную обратной теоремы. Указать, какие из этих теорем верны.

1)Если квадратное уравнение не имеет двух различных действительных корней, то дискриминант этого квадратного уравнения неположителен.

2)Если в четырехугольник можно вписать окружность, то этот четырехугольник представляет собой ромб.

3)Если параллелограмм является прямоугольником, то вокруг него можно описать окружность.

4)Если многоугольник является четырехугольником, то сумма его внутренних углов равна 360о.

5)Если функция дифференцируема в точке, то она непрерывна в

ней.

49

25.Какие из приведенных имен являются противоречащими, а какие противоположными?

1)высокий – низкий;

2)молодой – старый;

3)близкий – неблизкий;

4)близкий – далекий;

5)совершеннолетний – несовершеннолетний;

6)равнодушный – неравнодушный;

7)молотый кофе – растворимый кофе,

8)страна Северного полушария – страна Южного полушария.

26.Укажите, какие из приведенных высказываний являются общеутвердительными, общеотрицательными, частноутвердительными, частноотрицательными.

1)Всякий моряк умеет плавать.

2)У каждой лошади есть хвост.

3)Ни одна кошка не дружит с мышами.

4)Есть кошки, которые дружат с собаками.

5)Не все книги содержат полезную информацию.

6)Некоторые люди не умеют читать.

7)Ряд водоплавающих не дышит жабрами.

8)Несколько человек не пошли в музей.

9)Многие люди все еще верят в злых духов.

10)Люди в подавляющем своем большинстве хотят добра

27.Какие из следующих высказываний могут быть одновременно истинными, но не могут быть одновременно ложными.

1)Все врачи окулисты.

2)Некоторые из врачей окулисты.

3)Некоторые врачи не окулисты.

4)Среди врачей нет окулистов.

28.Какие из следующих высказываний противоречат друг другу:

1)Каждый кашалот является водоплавающим.

2)Ни один кашалот не является водоплавающим.

3)Отдельные кашалоты не являются водоплавающими.

4)Некоторые кашалоты – водоплавающие.

5)Не все кашалоты дышат жабрами.

6)Нет кашалота, который дышал бы жабрами.

7)Кашалот дышит жабрами.

8)Некоторые кашалоты дышат жабрами.

50