2Дискретка / Задачники / 3.ИВ ИП

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)аксиому Евклида о параллельных прямых (через точку, не лежащую на данной прямой, всегда можно провести прямую, па- раллельную данной прямой, причем только одну).

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 − женщина".

Записать в модели 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	),Ch(	),C(		),M ( ),W ( )				,	12		),Dc(	),C(		)	,M ( )	,W ( )	,
M = L; E(				2						M = L; E(				2
	2	2					1	1			2	2				1	1
	4	),Ch(	),H (			),M	( ),W	( )	,	13		), Dc(	),H (			),M ( ),W ( )		,
M = L; E(										M = L; E(
	2	2		2			1	1			2	2		2		1	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

M9 = L; E(2),S(2),D(2),Wf (2) ,

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) – бесконечно малая функция.

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))?

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).

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))

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)Для сходимости монотонной последовательности … чтобы она была ограниченна снизу.

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)Если функция дифференцируема в точке, то она непрерывна в

ней.

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)Некоторые кашалоты дышат жабрами.