Темы практических занятий

Таблицы истинности формул алгебры высказываний. (2 часа)

Нормальные формы формул. (4 часа)

Булевы функции. (4 часа)

Правила вывода в исчислении высказываний. (2 часа)

Правила вывода в исчислении предикатов. (2 часа)

Построение машин Тьюринга. (2 часа)

Алгоритмы Маркова. (2 часа)

Частично рекурсивные функции. (2 часа)

Функции сложности. (2 часа)

Построение машин произвольного доступа. (2 часа)

Контрольная работа. (2 часа)

Самостоятельная работа

№	Наименование работы	Количество час.	Форма контроля
1.	Проработка лекционного материала.		Зачет.
2.	Подготовка к практическим занятиям. Выполнение до- машних заданий.		Опрос на прак. занятиях.
3.	Подготовка к контрольным работам.		Проверка контрольной работы
4.	Изучение тем для самосто- ятельной проработки		Зачет. Конспекты.

Всего часов самостоятельной работы - 45 часов.

КОНТРОЛЬНЫЕ ЗАДАНИЯ ПО КУРСУ

"МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ"

(Упражнение, друзья, дает больше, чем хорошее (природное) дарование.

Эпихарм

КОНТРОЛЬНАЯ № 1

Вариант 1

1. Найдите множество X, удовлетворяющее следующему условию:

A\(A\X) = Æ.

2. Равны ли два множества:

{{1,2}, {2,3}} и {1,2,3}?

3. Докажите следующее утверждение: AÌB и BÍC Þ AÌC.

4. Пусть A={0, 1}. Перечислите элементы множеств A², A³.

5. Пусть r и j - бинарные отношения, определенные на некотором множестве. Тогда (j \ r)^-1 = j^-1 \ r^-1.

6. Укажите все сюръективные отображения множества A={1,2,3} на множество B={a, b}.

7. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

c_AÇB(x) = c_A(x)+c_B(x)- c_A(x) c_B(x);

8. Пусть отношение r определено на множестве N² (N - множество натуральных чисел {1,2,3,…}): <x,y> r <u,v> ó x+v = y +u. Доказать, что r - отношение эквивалентности.

9. Построить линейный порядок: а) на множестве N²; б) на множестве NÇN²Ç…ÇNⁿÇ… = {все конечные последовательности из натуральных чисел}.

10. Если r и j - отношения эквивалентности на X, то rÈj также отношение эквивалентности на X.

Вариант 2

1. Докажите следующее утверждение: AÌB и BÍC Þ AÌC.

2. Равны ли два множества:

{2,3}, {3.4} и {2,3,4}?

3. Найдите AÇB, AÈB, A\B, B\A, для

A={1,2,3}, B={2,3,4,5}, U = {0,1,…,9};

4. Определим упорядоченную пару <a,b> как множество {{a}, {a,b}}. Убедимся, что такое формальное теоретико-множественное определение вполне соответствует нашему неформальному определению упорядоченной пары. Для этого достаточно доказать, что для любых элементов <a,b> = <c,d> ó a=c, b=d.

5. Пусть x r y ó x² = y². Определите r^-1, r ë r, r^-1ë r^-1.

6. Найдите все отображения множества A={1,2} в себя, укажите, какие из них инъективные, сюръективные.

7. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

(x) = 1- c_A(x);

8. Если r и j - отношения эквивалентности на X, то rÈj также отношение эквивалентности на X.

9. Докажите, что отношение делимости на множестве натуральных чисел N является отношением частичного порядка. Является ли это отношение линейным порядком? Является ли отношением частичного порядка отношение делимости на множестве целых чисел Z?

10. Если r и j - отношения эквивалентности на X, то rÇj - отношение эквивалентности на X ó rÇj = r ë j.

Вариант 3

1. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание:

{1,2}? {1,2, {1}, {2}};

2. Равны ли два множества:

{4,5}, {5,6} и {4,5,6}?

3. Найдите AÇB, AÈB, A\B, B\A, для

A={x | x делится на 2}, B = {x| x делится на 3}, U = N - множество натуральных чисел.

4. Пусть AÍC, BÍC. Докажите, что A´B = (A´C)È(C´B).

5. Пусть r - бинарное отношение на R и e_R = {<x,x>|xÎR}. Доказать, что r = e_R ó r ë j = j ë r = j для любого отношения j на R.

6. Пусть X - конечное множество и отображение f: X à X инъективно. Доказать, что тогда f биективно.

7. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать: c_A\B(x) = c_A(x) -c_A(x) c_B(x).

8. Если r и j - отношения эквивалентности на X, то rÇj - отношение эквивалентности на X ó rÇj = r ë j.

9. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A = {1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.

10. Если r - частичный порядок на X, то r^-1 также частичный порядок на X.

Вариант 4

1. Докажите следующее утверждение: AÌB и BÍC Þ AÌC.

2. Доказать, что если конечное множество A содержит n элементов, то множество-степень P(A) содержит 2ⁿ элементов.

3. Докажите, что = Ç B.

4. Докажите, что подмножество C множества A´B является прямым произведением некоторого подмножества A1 множества A и подмножества B1 множества B тогда и только тогда, когда для любых <a,b>ÎC, <c,d>ÎC следует, что <a,d>, <c,b> ÎC.

5. Пусть A={0, 1}. Перечислите элементы множеств A², A³.

6. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

c_AÈB(x) = c_A(x) c_B(x);

7. Пусть f: X à Y и AÍX. Образом множества A при отображении f называется множество f(A)= {y | y= f(x), xÎA}.

Пусть BÍY. Прообразом множества B при отображении f называется множество f^-1(B)={xÎX| f(x)ÎB}.

Доказать, что f^-1(AÇB) = f^-1(A)Çf^-1(B).

8. Если r - частичный порядок на X, то r^-1 также частичный порядок на X.

9. Пусть A={1,2,3}. На множестве P(A) задано бинарное отношение X r Y ó "множества X и Y имеют равное количество элементов". Доказать, что это отношение эквивалентности и найдите классы эквивалентности.

10. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A = {1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.

Вариант 5

1. Перечислить все элементы каждого из следующих множеств:

{x| xÍ {1}};

2. Доказать, что для любых множеств A и B имеем AÇ(AÈB) = A.

3. Найдите множество X, удовлетворяющее следующему условию:

A\(A\X) = Æ.

4. Пусть A, B, C, D - непустые множества. Докажите, что

AÍB и CÍD ó A´C Í B´D,

5. Определим упорядоченную пару <a,b> как множество {{a}, {a,b}}. Убедимся, что такое формальное теоретико-множественное определение вполне соответствует нашему неформальному определению упорядоченной пары. Для этого достаточно доказать, что для любых элементов <a,b> = <c,d> ó a=c, b=d.

6. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

c_AÇB(x) = c_A(x)+c_B(x)- c_A(x) c_B(x);

7. Пусть A={a₁, a₂,…, a_n} - конечное множество. Определим отображение

f: P(A) à {0,1}ⁿ следующим образом

f(B) = <a₁, a₂,…, a_n>, где a_i=0, если a_iÏB, и a_i=1, если a_iÎB.

Докажите, что f - биекция.

8. Пусть A={1,2,3}. На множестве P(A) задано бинарное отношение X r Y ó "множества X и Y имеют равное количество элементов". Доказать, что это отношение эквивалентности и найдите классы эквивалентности.

9. Если r - частичный порядок на X, то r^-1 также частичный порядок на X.

10. Докажите, что отношение делимости на множестве натуральных чисел N является отношением частичного порядка. Является ли это отношение линейным порядком? Является ли отношением частичного порядка отношение делимости на множестве целых чисел Z?

Вариант 6

1. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: Æ? {Æ}.

2. Перечислить все элементы каждого из следующих множеств:

{x| xÍ {1}};

3. Найдите соответствующую форму P(x) для каждого множества:

{2,3,5,7,11,13,17,19};

4. Пусть A, B, C, D - непустые множества. Докажите, что

A´C = B´D ó A=B и С=В.

5. Пусть AÍC, BÍC. Докажите, что A´B = (A´C)È(C´B).

6. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

(x) = 1- c_A(x);

7. Найдите прообраз множества {0} при следующих отображениях R à R:

x à sin(x);

x à lg(x²+1);

x à x²+2x+1.

8. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A={1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.

9. Если r и j - отношения эквивалентности на X, то rÇj - отношение эквивалентности на X ó rÇj = r ë j.

10. Построить линейный порядок: а) на множестве N²; б) на множестве NÇN²Ç…ÇNⁿÇ… = {все конечные последовательности из натуральных чисел}.

Вариант 7

1. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: Æ? {{Æ}};

2. Перечислить все элементы каждого из следующих множеств:

{x | xÍ {1,2}};

3. Найдите соответствующую форму P(x) для каждого множества:

{м, о, н, е, ж, т, с, в};

4. Докажите тождество (A\B)´C = (A´C)\(B´C).

5. Докажите, что подмножество C множества A´B является прямым произведением некоторого подмножества A1 множества A и подмножества B1 множества B тогда и только тогда, когда для любых <a,b>ÎC, <c,d>ÎC следует, что <a,d>, <c,b> ÎC.

6. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

c_A\B(x) = c_A(x) -c_A(x) c_B(x).

7. Какие отображения инъективны, сюръективны?

f: RàR, xà x²+3x+5;

8. Докажите, что отношение делимости на множестве натуральных чисел N является отношением частичного порядка. Является ли это отношение линейным порядком? Является ли отношением частичного порядка отношение делимости на множестве целых чисел Z?

9. Если r и j - отношения эквивалентности на X, то rÈj также отношение эквивалентности на X.

10. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A={1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.

Вариант 8

1. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: Æ? {1,2,{1},{Æ}};

2. Перечислить все элементы каждого из следующих множеств:

{x | x Í {1,2,3}};

3. Найдите соответствующую форму P(x) для каждого множества:

[-2,3].

4. Докажите, что (A´B)Ç(C´D) Í (AÇC)´(BÇD).

5. Пусть A, B, C, D - непустые множества. Докажите, что

AÍB и CÍD ó A´C Í B´D,

6. Пусть f: X à Y и AÍX. Образом множества A при отображении f называется множество f(A)= {y | y= f(x), xÎA}.

Пусть BÍY. Прообразом множества B при отображении f называется множество f^-1(B)={xÎX| f(x)ÎB}.

Доказать, что f^-1(AÇB) = f^-1(A)Çf^-1(B).

7. Какие отображения инъективны, сюръективны?

f: RàR, xà x¹⁵(x²-1);

8. Построить линейный порядок: а) на множестве N²; б) на множестве NÇN²Ç…ÇNⁿÇ… = {все конечные последовательности из натуральных чисел}.

9. Пусть отношение r определено на множестве N² (N - множество натуральных чисел {1,2,3,…}): <x,y> r <u,v> ó x+v = y +u. Доказать, что r - отношение эквивалентности.

10. Пусть A={1,2,3}. На множестве P(A) задано бинарное отношение X r Y ó "множества X и Y имеют равное количество элементов". Доказать, что это отношение эквивалентности и найдите классы эквивалентности.

Вариант 9

1. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: {1,2}? {1, 2, {1,2}};

2. Перечислить все элементы каждого из следующих множеств:

{x | x Í Æ}.

3. Приведите пример множеств A, B и C таких, чтобы выполнялись условия AÎB, BÏC, AÍC.

4. Для бинарного отношения r = {<x,y> | x² + y² < 1} найдите D_r и R_r .

5. Докажите тождество (A\B)´C = (A´C)\(B´C).

6. Пусть A={a₁, a₂,…, a_n} - конечное множество. Определим отображение

f: P(A) à {0,1}ⁿ следующим образом

f(B) = <a₁, a₂,…, a_n>, где a_i=0, если a_iÏB, и a_i=1, если a_iÎB.

Докажите, что f - биекция.

7. Какие отображения инъективны, сюръективны?

f: RàR, xà 2^3x+1;

8. Пусть отношение r определено на множестве N² (N - множество натуральных чисел {1,2,3,…}): <x,y> r <u,v> ó x+v = y +u. Доказать, что r - отношение эквивалентности.

9. Построить линейный порядок: а) на множестве N²; б) на множестве NÇN²Ç…ÇNⁿÇ… = {все конечные последовательности из натуральных чисел}.

10. Если r - частичный порядок на X, то r^-1 также частичный порядок на X.

Вариант 10

1. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: {1}? {1, {1,2}};

2. Перечислите все подмножества множества A:

A = {{1,2}, {3}, 1};

3. Доказать тождество A\(B\C) = (A\B)Ç(AÈC).

4. Пусть A = {1,2,3,4,5}, B = {{1},{1,2},{2,5},{3}}. Для бинарного отношения r = {<a, X> Î A´B| aÎX} найдите D_r и R_r .

5. Докажите, что (A´B)Ç(C´D) Í (AÇC)´(BÇD).

6. Найдите прообраз множества {0} при следующих отображениях R à R:

x à sin(x);

x à lg(x²+1);

x à x²+2x+1.

7. Какие отображения инъективны, сюръективны?

f: Z´Z à Z, <a,b> à a+b, Z - множество целых чисел;

8. Если r и j - отношения эквивалентности на X, то rÈj также отношение эквивалентности на X.

9. Докажите, что отношение делимости на множестве натуральных чисел N является отношением частичного порядка. Является ли это отношение линейным порядком? Является ли отношением частичного порядка отношение делимости на множестве целых чисел Z?

10. Если r и j - отношения эквивалентности на X, то rÇj - отношение эквивалентности на X ó rÇj = r ë j.

Вариант 11

1. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: {1,2}? {1,2, {1}, {2}};

2. Перечислите все подмножества множества A:

A={{1}, {2}, 1};

3. Равны ли два множества:

{{1,2}, {2,3}} и {1,2,3}?

4. Какими свойствами обладает отношение x r y ó x² + x = y² +y, определенное на множестве действительных чисел?

5. Для бинарного отношения r = {<x,y> | x² + y² < 1} найдите D_r и R_r .

6. Какие отображения инъективны, сюръективны?

f: RàR, xà x²+3x+5;

7. Какие отображения инъективны, сюръективны?

f: Zà Z´Z, aà<a,a>;

8. Если r и j - отношения эквивалентности на X, то rÇj - отношение эквивалентности на X ó rÇj = r ë j.

9. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A={1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.

10. Построить линейный порядок: а) на множестве N²; б) на множестве NÇN²Ç…ÇNⁿÇ… = {все конечные последовательности из натуральных чисел}.

Вариант 12

1. Перечислить все элементы каждого из следующих множеств:

{x | x Í Æ}.

2. Перечислите все подмножества множества A:

A = {Æ, {Æ}, {Æ, {Æ}}}.

3. Равны ли два множества:

{2,3},{3.4} и {2,3,4}?

4. Какими свойствами обладает отношение r, определенное на множестве

всех прямых плоскости: x r y ó x пересекается с y?

5. Пусть A={0, 1}. Перечислите элементы множеств A², A³.

6. Какие отображения инъективны, сюръективны?

f: RàR, xà x¹⁵(x²-1);

7.Укажите все сюръективные отображения множества A={1,2,3} на множество B={a,b}.

8. Если r - частичный порядок на X, то r^-1 также частичный порядок на X.

9. Пусть A={1,2,3}. На множестве P(A) задано бинарное отношение X r Y ó "множества X и Y имеют равное количество элементов". Доказать, что это отношение эквивалентности и найдите классы эквивалентности.

10. Если r и j - отношения эквивалентности на X, то rÈj также отношение эквивалентности на X.

Вариант 13

1. Перечислить все элементы каждого из следующих множеств:

{x | x Í {1,2,3}};

2. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: {1,2}? {1,2, {1}, {2}};

3. Равны ли два множества:

{4,5}, {5,6} и {4,5,6}?

4. Какими свойствами обладает отношение r, определенное на множестве

всех прямых плоскости: x r y ó x не пересекается с y?

5. Определим упорядоченную пару <a,b> как множество {{a}, {a,b}}. Убедимся, что такое формальное теоретико-множественное определение вполне соответствует нашему неформальному определению упорядоченной пары. Для этого достаточно доказать, что для любых элементов <a,b> = <c,d> ó a=c, b=d.

6. Какие отображения инъективны, сюръективны?

f: RàR, xà 2^3x+1;

7. Найдите все отображения множества A={1,2} в себя, укажите, какие из них инъективные, сюръективные.

8. Пусть A={1,2,3}. На множестве P(A) задано бинарное отношение X r Y ó "множества X и Y имеют равное количество элементов". Доказать, что это отношение эквивалентности и найдите классы эквивалентности.

9. Построить линейный порядок: а) на множестве N²; б) на множестве NÇN²Ç…ÇNⁿÇ… = {все конечные последовательности из натуральных чисел}.

10. Пусть отношение r определено на множестве N² (N - множество натуральных чисел {1,2,3,…}): <x,y> r <u,v> ó x+v = y +u. Доказать, что r - отношение эквивалентности.

Вариант 14

1. Перечислить все элементы каждого из следующих множеств:

{x | xÍ {1,2}};

2. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: {1}? {1, {1,2}};

3. Доказать, что если конечное множество A содержит n элементов, то множество-степень P(A) содержит 2ⁿ элементов.

4. Пусть r - отношение на множестве X. Докажите:

r симметрично ó r^-1 = r;

5. Пусть AÍC, BÍC. Докажите, что A´B = (A´C)È(C´B).

6. Какие отображения инъективны, сюръективны?

f: Z´Z à Z, <a,b> à a+b, Z - множество целых чисел;

7. Пусть X - конечное множество и отображение f: X à X инъективно. Доказать, что тогда f биективно.

8. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A={1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.

9. Докажите, что отношение делимости на множестве натуральных чисел N является отношением частичного порядка. Является ли это отношение линейным порядком? Является ли отношением частичного порядка отношение делимости на множестве целых чисел Z?

10. Если r и j - отношения эквивалентности на X, то rÇj - отношение эквивалентности на X ó rÇj = r ë j.

Вариант 15

1. Перечислить все элементы каждого из следующих множеств:

{x| xÍ {1}};

2. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: {1,2}? {1, 2, {1,2}};

3. Доказать, что для любых множеств A и B имеем AÇ(AÈB) = A.

4. Пусть r - отношение на множестве X. Докажите:

r транзитивно ó r ë r Í r;

5. Докажите, что подмножество C множества A´B является прямым произведением некоторого подмножества A1 множества A и подмножества B1 множества B тогда и только тогда, когда для любых <a,b>ÎC, <c,d>ÎC следует, что <a,d>, <c,b> ÎC.

6. Какие отображения инъективны, сюръективны?

f: Zà Z´Z, aà<a,a>;

7. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

c_AÈB(x) = c_A(x) c_B(x);

8. Докажите, что отношение делимости на множестве натуральных чисел N является отношением частичного порядка. Является ли это отношение линейным порядком? Является ли отношением частичного порядка отношение делимости на множестве целых чисел Z?

9. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A={1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.

10. Если r - частичный порядок на X, то r^-1 также частичный порядок на X.

Вариант 16

1. Доказать, что для любых множеств A и B имеем AÇ(AÈB) = A.

2. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: Æ? {1,2,{1},{Æ}};

3. Перечислить все элементы каждого из следующих множеств:

{x| xÍ {1}};

4. Пусть r - отношение на множестве X. Докажите:

r рефлексивно Þ r Í r ë r;

5. Пусть A, B, C, D - непустые множества. Докажите, что

AÍB и CÍD ó A´C Í B´D,

6. Какие отображения инъективны, сюръективны?

f: P(A) à N, f(X)= количество элементов в X, N - множество

неотрицательных целых чисел, A - конечное множество.

7. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

c_AÇB(x) = c_A(x)+c_B(x)- c_A(x) c_B(x);

8. Построить линейный порядок: а) на множестве N²; б) на множестве NÇN²Ç…ÇNⁿÇ… = {все конечные последовательности из натуральных чисел}.

9. Пусть A={1,2,3}. На множестве P(A) задано бинарное отношение X r Y ó "множества X и Y имеют равное количество элементов". Доказать, что это отношение эквивалентности и найдите классы эквивалентности.

10. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A={1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.

Вариант 17

1. Доказать, что если конечное множество A содержит n элементов, то множество-степень P(A) содержит 2ⁿ элементов.

2. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: Æ? {{Æ}};

3. Перечислите все подмножества множества A:

A = {{1,2}, {3}, 1};

4. Пусть r - отношение на множестве X. Докажите:

r рефлексивно и транзитивно Þ r = r ë r.

5. Пусть A, B, C, D - непустые множества. Докажите, что

A´C = B´D ó A=B и С=В.

6.Укажите все сюръективные отображения множества A={1,2,3} на множество B={a,b}.

7. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

(x) = 1- c_A(x);

8. Пусть отношение r определено на множестве N² (N - множество натуральных чисел {1,2,3,…}): <x,y> r <u,v> ó x+v = y +u. Доказать, что r - отношение эквивалентности.

9. Если r - частичный порядок на X, то r^-1 также частичный порядок на X.

10. Построить линейный порядок: а) на множестве N²; б) на множестве NÇN²Ç…ÇNⁿÇ… = {все конечные последовательности из натуральных чисел}.

Вариант 18

1. Равны ли два множества:

{4,5}, {5,6} и {4,5,6}?

2. Вставьте между множествами символ Î или Í так, чтобы получилось истинное высказывание: Æ? {Æ}.

3. Перечислить все элементы каждого из следующих множеств:

{x | x Í Æ}.

4. Какова характеристическая особенность декартовой диаграммы рефлексивного (симметричного, антисимметричного) отношения, определенного на множестве вещественных чисел R.

5. Докажите тождество (A\B)´C = (A´C)\(B´C).

6. Найдите все отображения множества A={1,2} в себя, укажите, какие из них инъективные, сюръективные.

7. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

c_A\B(x) = c_A(x) -c_A(x) c_B(x).

8. Если r и j - отношения эквивалентности на X, то rÈj также отношение эквивалентности на X.

9. Если r и j - отношения эквивалентности на X, то rÇj - отношение эквивалентности на X ó rÇj = r ë j.

10. Докажите, что отношение делимости на множестве натуральных чисел N является отношением частичного порядка. Является ли это отношение линейным порядком? Является ли отношением частичного порядка отношение делимости на множестве целых чисел Z?

Вариант 19

1. Равны ли два множества:

{2,3},{3.4} и {2,3,4}?

2. Докажите следующее утверждение: AÌB и BÍC Þ AÌC.

3.Найдите множество X, удовлетворяющее следующему условию:

A\(A\X) = Æ.

4. Пусть r₁ = {<x,y>ÎR´R | x‰y >0}, r₂ = {<x,y>ÎR´R | x+y -целое число}. Найти r₁ë r₂.

5. Докажите, что (A´B)Ç(C´D) Í (AÇC)´(BÇD).

6. Пусть X - конечное множество и отображение f: X à X инъективно. Доказать, что тогда f биективно.

7. Пусть f: X à Y и AÍX. Образом множества A при отображении f называется множество f(A)= {y | y= f(x), xÎA}.

Пусть BÍY. Прообразом множества B при отображении f называется множество f^-1(B)={xÎX| f(x)ÎB}.

Доказать, что f^-1(AÇB) = f^-1(A)Çf^-1(B).

8. Если r и j - отношения эквивалентности на X, то rÇj - отношение эквивалентности на X ó rÇj = r ë j.

9. Если r и j - отношения эквивалентности на X, то rÈj также отношение эквивалентности на X.

10. Пусть A={1,2,3}. На множестве P(A) задано бинарное отношение X r Y ó "множества X и Y имеют равное количество элементов". Доказать, что это отношение эквивалентности и найдите классы эквивалентности.

Вариант 20

1. Равны ли два множества:

{{1,2}, {2,3}} и {1,2,3}?

2. Найдите AÇB, AÈB, A\B, B\A, для

A={1,2,3}, B={2,3,4,5}, U = {0,1,…,9};

3. Приведите пример множеств A, B и C таких, чтобы выполнялись условия AÎB, BÏC, AÍC.

4. Пусть r₁ = {<x,y>ÎR´R | x‰y >0}, r₂ = {<x,y>ÎR´R | x=y² }. Найти r₁ë r₂.

5. Для бинарного отношения r = {<x,y> | x² + y² < 1} найдите D_r и R_r .

6. Характеристическая функция множества A определяется следующим образом

c_A(x) =

Доказать:

c_AÈB(x) = c_A(x) c_B(x);

7. Какие отображения инъективны, сюръективны?

f: RàR, xà x²+3x+5;

8. Если r - частичный порядок на X, то r^-1 также частичный порядок на X.

9. Пусть отношение r определено на множестве N² (N - множество натуральных чисел {1,2,3,…}): <x,y> r <u,v> ó x+v = y +u. Доказать, что r - отношение эквивалентности.

10. Докажите, что M = {{1}, {2,5}, {3}, {4,6,7}} - разбиение множества A={1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности r, соответствующего разбиению M.