IV. Пример решения контрольной работы

Задача I.1. Даны множества:

А = {–1; 0; 1},

В = [–2; 0) – полуинтервал на числовой оси,

С = [–0.5; 2] - отрезок на числовой оси.

IV. Пример решения контрольной работы - student2.ru Найти:

Изобразить на плоскости: А ´ В, А ´ С, В ´ С. Найти IV. Пример решения контрольной работы - student2.ru , считая универсальным множеством множество всех вещественных чисел.

Решение:

IV. Пример решения контрольной работы - student2.ru = {[–2; 0]; 1}

IV. Пример решения контрольной работы - student2.ru = {–1; [–0.5; 2]}

IV. Пример решения контрольной работы - student2.ru = [–2; 2]

IV. Пример решения контрольной работы - student2.ru = [–2; 2]

IV. Пример решения контрольной работы - student2.ru = {–1}

IV. Пример решения контрольной работы - student2.ru = {0; 1}

IV. Пример решения контрольной работы - student2.ru = [–0.5; 0)

IV. Пример решения контрольной работы - student2.ru = Æ – пустое множество

А \ В = {0; 1}

В \ А = {[–2; –1); (–1; 0)}

А \ С = {–1}

С \ А = {[–0.5; 0); (0; 1); (1; 2]}

B \ C = [–2; –0.5)

C \ B = [0; 2]

IV. Пример решения контрольной работы - student2.ru
(A \ B) \ C = Æ

IV. Пример решения контрольной работы - student2.ru
A \ (B \ C) = {0; 1}

Задача I.2. Доказать тождество, используя диаграммы Эйлера-Венна.

IV. Пример решения контрольной работы - student2.ru

IV. Пример решения контрольной работы - student2.ru
Решение: Изобразим диаграмму для левой части тождества по шагам:

IV. Пример решения контрольной работы - student2.ru
Теперь диаграмму правой части по шагам:

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

Задача II. 1. Даны множества А={a,b,c} и B={1,2,3,4} и два бинарных отношения: P1={(a,1); (a,3); (b,2); (c,1); (c,4)} и P2={(1,1); (1,3); (2,2); (2,1); (2,4); (3,3); (4,1); (4,4)}

Изобразить Р1, Р2 графически. Найти: Р1-1, Р2-1, IV. Пример решения контрольной работы - student2.ru . Определить, является ли отношение Р2 рефлексивным, транзитивным, симметричным, антисимметричным.

Решение: рассмотрим два способа графического представления бинарных отношений:

IV. Пример решения контрольной работы - student2.ru

По определению обратное отношение IV. Пример решения контрольной работы - student2.ru . Таким образом, Р1-1={(1,a); (3,a); (2,b); (1,c); (4,c)} и P2-1={(1,1); (3,1); (2,2); (1,2); (4,2); (3,3); (4,4); (1,4)}.

По определению композиции бинарных отношений

IV. Пример решения контрольной работы - student2.ru

Таким образом, IV. Пример решения контрольной работы - student2.ru ={(a,1); (a,3); (b,2); (b,1); (b,4); (c,1); (c,3); (c,4)}.

Тогда IV. Пример решения контрольной работы - student2.ru -1={(1,a); (3,a); (2,b); (1,b); (4,b); (1,c); (3,c); (4,c)}.

IV. Пример решения контрольной работы - student2.ru ={(1,a); (1,c); (3,a); (3,c); (2,b); (1,b); (4,b); (4,c)}

Последние два множества совпадают, что и должно быть по свойствам композиции.

Отношение Р2 рефлексивно, т. к. в соответствии с определением рефлексивности IV. Пример решения контрольной работы - student2.ru .

a) Отношение Р2 не является транзитивным, поскольку по определению транзитивности требуется, чтобы для любых пар (x, y) и (y, z), таких что (x, y) IV. Пример решения контрольной работы - student2.ru следовало бы, чтобы пара IV. Пример решения контрольной работы - student2.ru . Однако это не так. Например, пары (2,1) и (1,3) Î Р2, но пара (2,3) Ï Р2.

b) Отношение Р2 не является симметричным, т. к. по определению симметричности для любой пары (x, y) Î Р2 должно быть и (y, x) Î Р2 . Однако это не так. Например, пара (1,3)Î Р2 , но пара (3,1) Ï Р2.

c) Отношение Р2 антисимметрично, поскольку для любой пары (x, y) Î Р2 такой, что (y, x) Î Р2 обязательно следует, что x=y.

Задача II. 2

Даны две функции IV. Пример решения контрольной работы - student2.ru и IV. Пример решения контрольной работы - student2.ru и два отрезка A = [0; 3] и B = [ ‑1; 0]. Найти :f∘g, g∘f, f ‑1, g ‑1, (f∘g) ‑1,(g∘f) ‑1 ,f(A), g(A), f ‑1(B), g‑1(B). Найти неподвижные точки f и g.

Решение: по свойствам композиции находим

(f∘g)(x) = f(g(x)) = (g(x)–2)2–1 = (1–x–2)2 –1 = (–x–1)2 – 1=(x+1)2–1;

(g∘f)(x) = g(f(x)) =1– f(x) = 1 – (x–2)2 +1 = 2 – (x–2)2 ;

Т.к. IV. Пример решения контрольной работы - student2.ru , где y³ –1. То из выражения IV. Пример решения контрольной работы - student2.ru найдем x. Тогда IV. Пример решения контрольной работы - student2.ru , где y³ –1 и f ‑1(у) – не является всюду определенным и однозначным соответствием.

Заметим, что исходное отображение f обратимо справа, а именно: :f∘f ‑1 = f(f ‑1(y))= IV. Пример решения контрольной работы - student2.ru – тождественное отображение при y³ ‑1.

Аналогично, IV. Пример решения контрольной работы - student2.ru , где y любое. И из IV. Пример решения контрольной работы - student2.ru следует: IV. Пример решения контрольной работы - student2.ru , при этом исходное отображение g обратимо как справа, так и слева, а именно: g∘g‑1 = g(g‑1(y)) = 1– (1– y)= y и g‑1∘g = IV. Пример решения контрольной работы - student2.ru – тождественные отображения.

По свойствам композиции IV. Пример решения контрольной работы - student2.ru

IV. Пример решения контрольной работы - student2.ru f(A) = { y = f(x), где xÎA }, поэтому f(A)=[–1; 3].

Аналогично, g(A) = { y = g(x), где xÎA } = [–2; 1].

IV. Пример решения контрольной работы - student2.ru

IV. Пример решения контрольной работы - student2.ru

Найдем неподвижные точки. По определению это такие х, что: f(x)=x и g(x)=x. Таким образом, x = (x–2)2–1. Отсюда x2–5x+3=0 и т. к. дискриминант D=25–12=13>0, то IV. Пример решения контрольной работы - student2.ru – две неподвижные точки f(x).

Из g(x)=x следует, что x=1–x и IV. Пример решения контрольной работы - student2.ru – неподвижная точка g(x).

Задача III. 1.

Составить полную и сокращенную таблицы истинности для формул: IV. Пример решения контрольной работы - student2.ru

x y f1 f2 f3 f4

Решение:
для построения полной таблицы истинности первой формулы выделим подформулы: IV. Пример решения контрольной работы - student2.ru Таким образом, таблица будет содержать 4 строки и 6 столбцов.

Значения формулы совпадают со значениями последнего столбца таблицы.

Сокращенная таблица истинности строится непосредственно под формулой. Столбец результата выделяем. Стрелками показываем столбцы, участвующие в операции. Номером – столбец, полученный в результате операции.

IV. Пример решения контрольной работы - student2.ru x IV. Пример решения контрольной работы - student2.ru y) IV. Пример решения контрольной работы - student2.ru (y IV. Пример решения контрольной работы - student2.ru x)

Выделим подформулы второй заданной формулы:

IV. Пример решения контрольной работы - student2.ru Построим полную таблицу истинности.

x y z f1 f2 f3 f4 f5 f6 f7

Сокращенная таблица истинности для 2-ой формулы:

IV. Пример решения контрольной работы - student2.ru ((x IV. Пример решения контрольной работы - student2.ru y) | z) IV. Пример решения контрольной работы - student2.ru (y & IV. Пример решения контрольной работы - student2.ru IV. Пример решения контрольной работы - student2.ru IV. Пример решения контрольной работы - student2.ru )

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

Задача III. 2.

Проверить двумя способами, будут ли эквивалентны следующие формулы: IV. Пример решения контрольной работы - student2.ru . а) составлением таблиц истинности; б) эквивалентными преобразованиями.

Решение: а) составим сокращенные таблицы истинности обеих формул:

IV. Пример решения контрольной работы - student2.ru x IV. Пример решения контрольной работы - student2.ru (y IV. Пример решения контрольной работы - student2.ru z) (x IV. Пример решения контрольной работы - student2.ru y) IV. Пример решения контрольной работы - student2.ru (x IV. Пример решения контрольной работы - student2.ru z)

Поскольку полученные столбцы не совпадают, формулы не эквивалентны.

б) Выполним преобразования формул, перейдя к системе связок {Ø, &, Ú}. Для этого воспользуемся тождествами: IV. Пример решения контрольной работы - student2.ru и IV. Пример решения контрольной работы - student2.ru , где a и b – произвольные формулы. Тогда IV. Пример решения контрольной работы - student2.ru IV. Пример решения контрольной работы - student2.ru IV. Пример решения контрольной работы - student2.ru (по закону де Моргана) IV. Пример решения контрольной работы - student2.ru IV. Пример решения контрольной работы - student2.ru (по закону дистрибутивности)= IV. Пример решения контрольной работы - student2.ru

IV. Пример решения контрольной работы - student2.ru IV. Пример решения контрольной работы - student2.ru

IV. Пример решения контрольной работы - student2.ru

IV. Пример решения контрольной работы - student2.ru

Формулы (*) и (**) не эквивалентны.

V. Список литературы

1. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики». М., МАИ, 1992.

2. О.Е. Акимов «Дискретная математика: логика, группы, графы». М., Лаборатория Базовых Знаний, 2001.

3. Я.М. Ерусалимский «Дискретная математика». М., Вузовская книга, 2001.

4. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики». Москва, ИНФРА-М, 2002.

5. О.П. Кузнецов, Г.М. Адельсон-Вельский «Дискретная математика для инженера». М., «Энергия», 1980.

6. Ф.А. Новиков «Дискретная математика для программистов». СПб: Питер, 2001.

7. С.В. Яблонский «Введение в дискретную математику». М., Высшая школа, 2001.

8. И.А. Лавров, Л.Л. Максимова «Задачи по теории множеств, математической логике и теории алгоритмов». М., Физматлит, 2002.

9. Е.С. Ляпин, А.Я. Айзенштат, М.М. Лесохин «Упражнения по теории групп». М., Наука, 1967.

10. Е.С. Ляпин, А.Е. Евсеев «Алгебра и теория чисел». М., «Просвещение», 1974.

11. Дж.Л. Келли «Общая топология». М., «Наука», 1968.

12. Н. Бурбаки «Теория множеств». М., «Мир», 1965.

13. П.С. Александров «Введение в общую теорию множеств и функций». М., ОГИЗ Гостехиздат, 1948.

Наши рекомендации