Задача I.1. Даны множества:
А = {–1; 0; 1},
В = [–2; 0) – полуинтервал на числовой оси,
С = [–0.5; 2] - отрезок на числовой оси.
Найти:
Изобразить на плоскости: А ´ В, А ´ С, В ´ С. Найти , считая универсальным множеством множество всех вещественных чисел.
Решение:
= {[–2; 0]; 1}
= {–1; [–0.5; 2]}
= [–2; 2]
= [–2; 2]
= {–1}
= {0; 1}
= [–0.5; 0)
= Æ – пустое множество
А \ В = {0; 1}
В \ А = {[–2; –1); (–1; 0)}
А \ С = {–1}
С \ А = {[–0.5; 0); (0; 1); (1; 2]}
B \ C = [–2; –0.5)
C \ B = [0; 2]
(A \ B) \ C = Æ
A \ (B \ C) = {0; 1}
Задача I.2. Дано семейство множеств { A γ}γÎℝ, где для всякого вещественного индекса γ множество А γ={ (x, y): | x |+| y | ≤ |γ| и x, y Îℝ }. Найти объединение и пересечение А γ по всем вещественным индексам γ.
Решение: рассмотрим множества А γ для некоторых фиксированных индексов γ: при γ=0 множество А 0={ (x, y): | x |+| y | ≤ 0}={(0;0)} – центр вещественной плоскости. При γ=0.5 и γ= –0.5 А 0.5= А ‑0.5={ (x, y): | x |+| y | ≤ 0.5} – ромб в центре вещественной плоскости с диагоналями, равными 1 и направленными по осям координат. При γ=2 и γ= –2 А 2= А ‑2={ (x, y): | x |+| y | ≤ 2} – ромб с диагоналями, равными 4 и т. д.… При увеличении абсолютной величины индекса γ диагонали ромба, расположенного в центре вещественной плоскости, увеличиваются и при |γ|→+ ромб А занимает всю вещественную плоскость. Таким образом, объединение по всем вещественным индексам γ равно – вся вещественная плоскость, а пересечение по всем вещественным индексам γ равно – центр вещественной плоскости.
Задача I.3. Доказать тождество, используя только определения операций над множествами:
Решение: по определению два множества А и В равны тогда и только тогда, когда они состоят из одних и тех же элементов, т. е.
а) (1) Пусть , тогда . Отсюда следует, что 1) и или 2) и . В первом случае из того, что следует, что х принадлежит также объединению множества А с любым другим множеством, в том числе и множеством В, т.е. . Но в то же время и, следовательно, х принадлежит также объединению с любым другим множеством, в том числе и множеством , т.е. . Таким образом, , т.е. . Аналогично во втором случае: из того, что следует, что х принадлежит также и . И в то же время, поскольку , то х принадлежит также объединению , с любым другим множеством, в том числе и множеством , т.е. . И также как в первом случае имеем: , тем самым .
(2) Пусть теперь . Тогда , отсюда . Следовательно, если , то , т.е. . Если же , то и значит . Таким образом, , что равносильно тому, что . Из (1) и (2) следует справедливость тождества.
б) (1) Пусть пара . Тогда , отсюда . Поэтому пара и . Таким образом, .
(2) Пусть теперь . Тогда и . Следовательно, , и . Поэтому, т. е. Из (1) и (2) – тождество верно.
Задача I.4. Доказать тождество, используя диаграммы Эйлера-Венна.
Решение: Изобразим диаграмму для левой части тождества по шагам:
Теперь диаграмму правой части по шагам:
Ввиду того, что заштрихованные области, полученные на последнем шаге для левой и правой части тождества, одинаковы, можно заключить, что исходное выражение верно.
Задача II. 1. Даны множества А ={ a, b, c } и B ={1,2,3,4} и два бинарных отношения: P 1={(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, . Определить, является ли отношение Р 2 рефлексивным, транзитивным, симметричным, антисимметричным.
Решение: рассмотрим два способа графического представления бинарных отношений:
По определению обратное отношение . Таким образом, Р 1-1={(1, a); (3, a); (2, b); (1, c); (4, c)} и P 2-1={(1,1); (3,1); (2,2); (1,2); (4,2); (3,3); (4,4); (1,4)}.
По определению композиции бинарных отношений
Таким образом, ={(a,1); (a,3); (b,2); (b,1); (b,4); (c,1); (c,3); (c,4)}.
Тогда -1={(1, a); (3, a); (2, b); (1, b); (4, b); (1, c); (3, c); (4, c)}.
={(1, a); (1, c); (3, a); (3, c); (2, b); (1, b); (4, b); (4, c)}
Последние два множества совпадают, что и должно быть по свойствам композиции.
Отношение Р 2 рефлексивно, т. к. в соответствии с определением рефлексивности .
a) Отношение Р 2 не является транзитивным, поскольку по определению транзитивности требуется, чтобы для любых пар (x, y) и (y, z), таких что (x, y) следовало бы, чтобы пара . Однако это не так. Например, пары (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
Дано бинарное отношение P Í ℕ2 и P = { (x, y): x mod y = 2 }, где «mod» – операция нахождения остатка от деления x на y.
Найти область определения и область значений отношения Р. Определить, является ли отношение Р рефлексивным, транзитивным, симметричным, антисимметричным.
Решение: областью значений отношения Р является множество таких натуральных чисел y, что в остатке от деления на y может быть получено значение 2. В качестве такого делителя y можно взять любое натуральное число >2. Таким образом, пр2 Р = { y Î ℕ: y ³ 3 } – область значений.
Область определения отношения Р – это множество тех значений x, для которых может быть получен остаток, равный 2, при делении на y ³ 3. Выразим x через y: x = k . y +2, где k =0,1,2,… и y ³ 3. Отсюда возможными значениями x являются числа: 2,5,6,7,8,… Таким образом, пр1 Р ={2,5,6,7,8,9,…}=ℕ \ {1,3,4}
Отношение Р не является рефлексивным, т. к. для всех x Î ℕ (x, x) Ï P. Действительно, " x Î ℕ Þ x mod x = 0.
Отношение Р не является транзитивным, т. к. существуют такие пары (x, y)Î P и (y, z)Î P, но (x, z)Ï P. Например, пары (7,5) и (5,3) обе Р, но пара (7,3)Ï Р, т. к. 7 mod 3 = 1.
Отношение Р не является симметричным, поскольку существуют такие пары, что (x, y)Î P, но (х, у)Ï Р. Например, пара (7,5)Î Р, но (5,7)Ï Р, т.к. 5 mod 7=5.
По определению антисимметричности для всех таких пар (х, у), что (у, х)Î Р и (х, у)Î Р обязательно следует, что х = у. Но для заданного отношения Р не существует таких пар (х, у), что (х, у)Î P и (у, х)Î Р, поскольку равенство (х mod y = y mod x) не выполняется ни при каких х, у Îℕ. Поэтому данное отношение Р является антисимметричным.
Задача II. 3
Даны две функции и и два отрезка 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 ;
Т.к. , где y ³ –1. То из выражения найдем x. Тогда , где y ³ –1 и f ‑1(у) – не является всюду определенным и однозначным соответствием.
Заметим, что исходное отображение f обратимо справа, а именно: :f ∘ f ‑1 = f (f ‑1(y)) = – тождественное отображение при y ³ ‑1.
Аналогично, , где y любое. И из следует: , при этом исходное отображение g обратимо как справа, так и слева, а именно: g ∘ g ‑1 = g (g ‑1(y)) = 1– (1– y)= y и g ‑1∘ g = – тождественные отображения.
По свойствам композиции
f (A) = { y = f (x), где x Î A }, поэтому f (A)=[–1; 3].
Аналогично, g (A) = { y = g (x), где x ÎA } = [–2; 1].
Найдем неподвижные точки. По определению это такие х, что: f (x)= x и g (x)= x. Таким образом, x = (x –2)2–1. Отсюда x 2–5 x +3=0 и т. к. дискриминант D =25–12=13>0, то – две неподвижные точки f (x).
Из g (x)= x следует, что x =1– x и – неподвижная точка g (x).
Задача III. 1.
Составить полную и сокращенную таблицы истинности для формул:
x | y | f 1 | f 2 | f 3 | f 4 |
Решение:
для построения полной таблицы истинности первой формулы выделим подформулы: Таким образом, таблица будет содержать 4 строки и 6 столбцов.
Значения формулы совпадают со значениями последнего столбца таблицы.
Сокращенная таблица истинности строится непосредственно под формулой. Столбец результата выделяем. Стрелками показываем столбцы, участвующие в операции. Номером – столбец, полученный в результате операции.
(Ø | x | y) | (y | x) | |||
Выделим подформулы второй заданной формулы:
Построим полную таблицу истинности.
x | y | z | f 1 | f 2 | f 3 | f 4 | f 5 | f 6 | f 7 |
Сокращенная таблица истинности для 2-ой формулы:
((x | y) | | | z) | (y | & | ) | ||||
Заметим, что для обеих формул результаты, полученные в полной и сокращенной таблице истинности, совпали. Это подтверждает правильность вычислений.
Задача III. 2.
Проверить двумя способами, будут ли эквивалентны следующие формулы: . а) составлением таблиц истинности; б) эквивалентными преобразованиями.
Решение: а) составим сокращенные таблицы истинности обеих формул:
x | (y | z) | (x | y) | (x | z) | |||||
Поскольку полученные столбцы не совпадают, формулы не эквивалентны.
б) Выполним преобразования формул, перейдя к системе связок {Ø, &, Ú}. Для этого воспользуемся тождествами: и , где a и b – произвольные формулы. Тогда (по закону де Моргана) (по закону дистрибутивности)=
Формулы (*) и (**) не эквивалентны.
Задача III.3.
Доказать или опровергнуть тождественную истинность формулы двумя способами: .
Решение:
1 способ (таблица истинности): выделим подформулы: ; ; ; ; ; ; ; ; ; .
x | y | z | f 1 | f 2 | f 3 | f 4 | f 5 | f 6 | f 7 | f 8 | f 9 | f 10 |
2-ой способ (эквивалентные преобразования): используем тождества:
.
Задача IV.1.
Для функций из задачи III.1 записать: двойственные функции, СКНФ, СДНФ и СПНФ.
Решение: по определению f *(x 1,…, xn)= . СКНФ строится по нулевым кортежам, СДНФ – по единичным кортежам, а СПНФ может быть получена из СДНФ путем замены «Ú» на «Å» и «» на «x Å1».
x | y | f (x, y) | ||
СКНФ (f (x, y))=
СДНФ(f (x, y))=
СПНФ(f (x, y))=
x | y | z | f (x, y, z) | ||
СКНФ(f (x, y, z))= .
СДНФ(f (x, y, z))= .
Тождество: a Å a =0.
СПНФ(f (x, y, z))=(x Å1)(y Å1)(z Å1) Å (x Å1)(y Å1) z Å (x Å1) y (z Å1) Å x (y Å1) z Å xy (z Å1)=(xyz Å xy Å xz Å x Å yz Å y Å z Å1) Å (xyz Å xz Å yz Å z) Å (xyz Å xy Å yz Å y) Å(xyz Å xz) Å (xyz Å xy) = xyz Å xy Å xz Å yz Å x Å1.
Задача IV.2.
C помощью принципа двойственности записать формулы, двойственные заданным: а) ; б) . В полученных формулах расставить скобки, указывающие порядок действий.
Решение: по принципу двойственности для записи двойственной формулы необходимо заменить «&» на «Ú», «Ú» на «&», оставив при этом неизменной структуру исходной формулы.
а) u * =
б) u * =
Задача IV.3.
Дана формула . С помощью эквивалентных преобразований привести ее к виду: ДНФ, КНФ, СДНФ, СКНФ, СПНФ.
Решение: используем тождества:
Для компактности записи вместо «a & b», будем писать «ab».
ДНФ=
КНФ=
СДНФ=
СКНФ=
СПНФ= xyz Å xy (z Å1) Å (x Å1) yz Å (x Å1)(y Å1) z Å x (y Å1) z = xyz Å xyz Å xy Å xyz Å yz Å xyz Å xz Å yz Å z Å xyz Å xz = xyz Å xy Å z
Задача V. 1
Каким из замкнутых классов Поста принадлежит функция f (x, y,z), если f (0,1,0)= f (1,0,0)= f (1,0,1)=1?
Решение: рассмотрим таблицу истинности функции
x | y | z | f (x,y, z) |
Т.к. f (0,0,0)=0, то f Î T 0 (класс функций, сохраняющих ноль).
Т.к. f (1,1,1)=0, то f Ï T 1 (класс функций, сохраняющих единицу).
Т.к. f *(x, y, z)=(1,1,0,0,1,0,1,1) ¹ f (x, y, z), то f Ï S (класс самодвойственных функций).
Рассмотрим кортежи: a =(0,1,0) и b =(0,1,1), f (a) =1, f (b) =0.
Т.к. a £ b, но f (a)> f (b), то f Ï M (класс монотонных функций).
Найдем полином Жегалкина:
f (x, y, z)= (x Å1) y (z Å1) Å x (y Å1)(zÅ1) Å x (y Å1) z = xyz Å xy Å yz Å y Å xyz Å xy Å xz Å x Å xyz Å xz = xyz Å yz Å x Å y.
Т.к. в СПНФ имеются нелинейные слагаемые, то f Ï L (класс линейных функций).
Задача V. 2
Дана система функций F ={ }. Определить, является ли F полной и образует ли она базис?
Решение: построим таблицы истинности для функций системы F.
x | y | ||
СПНФ () = (x Å1)(y Å1)Å(x Å1) y Å x (y Å1)= xy Å1
СПНФ () = x Å y
Оформим в виде таблицы принадлежность функций из F классам Поста:
T0 | T1 | S | M | L | |
– | – | – | – | – | |
+ | – | – | – | + |
Т.к. в системе F имеются функции: не сохраняющая ноль, не сохраняющая единицу, не самодвойственная, немонотонная и нелинейная, то по теореме о полноте (Поста) система F является полной. В то же время базиса она не образует, т.к. из неё может быть удалена функция () и при этом оставшаяся система будет полной.
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.