Государственное образовательное учреждение высшего профессионального образования

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
Московский государственный институт электроники и математики
(Технический университет)Кафедра «Вычислительные
УДК 519.1 Предназначены для решения задач по дискретной математике как при самостоятельном изучении теории множеств, отношений, функций, специальных бинарных отношений, алгебраических структур, кодирования, комбинаторики и, в частности, формулы включений и исключений, так и при решении задач на семинарах по дискретной математике в курсе дискретной математики студентами I (дневного) и II (вечернего) курсов специальности 22.0101. Дискретная математика: Метод. указания к самостоятельным и семинарским занятиям/ Моск. гос. ин-т электроники и математики; Сост. Л.Е. Захарова. М., 2010. 32 с.Ил. 3. Библиогр.: 3 назв.
ISBN 978-5-94506-251-1
Пустое множество ( ) является подмножеством любого множества: . . Универсальное множество ( ) содержит любое множество: . Множество степень P(A) – это множество всех подмножеств A. Если = n, то .
1. А В=B A (комму- 1’. А В=B A (комму-
тативность ); тативность );
2. А (В C)=(A B) C (ассоциа- 2’. А (В C)=(A B) C (ассоциа-
тивность ); тивность );
3. А (В C)=(A B) (A C) 3’. А (В C)=(A B) (A C)
(дистрибутивность (дистрибутивность
относительно ); относительно )
4. A =A 4’. A U=A
5. A A= U 5’. A A =
6. A A= A 6’. A A =A
7. A U=U 7’. A =
8. (A B)= A B (закон 8’. (A B)= A B (закон
Моргана) Моргана)
9. А (В A)=A (закон поглощения) 9’. А (В A)=A (закон
поглощения)
где А В={x ¦ x A или x B} – объединение множеств A и B; А В={x ¦ x A и x B} – пересечение множеств A и B. Выполняются соотношения: А В A А В и А В B А В. Кроме того: BA=B A={x ¦ x A и x B} — относительное дополнение множества A до множества B (разность между B и A, B минус A); A=UA={x ¦ x A} — абсолютное дополнение множества A (инверсия A); A+B=(AB) (BA) – симметрическая разность множеств A и B. A=B тогда и только тогда, когда A B и B A, поэтому при доказательстве тождеств надо сначала брать любой элемент из правой части тождества и доказать, что он принадлежит и левой его части, а затем брать любой элемент x из левой части тождества и доказать, что он принадлежит и правой его части. Это первый способ доказательства тождеств. Например, докажем тождество 8: пусть x (A B) x A B x A и x B x A B.
По опред.
Под двойной двусторонней стрелкой указано, определение какой операции использовано. Поскольку стрелка двусторонняя, то любой элемент x из левой части тождества 8 принадлежит и правой его части и наоборот, но не всегда стрелка бывает двусторонней. Во втором способе доказательства тождеств используются основные тождества, половина тождеств доказывается первым способом, а половина – вторым. Если тождество в примере одно, то надо доказать его двумя способами. При втором способе надо или правую часть тождества свети к левой его части, или наоборот, левую к правой, или свести обе части тождества к одному и тому же выражению. Например: докажем, что если А В=A, то А В=B. А В=(А В) В=B.
По услов. 9Под знаками равенства указывается, какое основное тождество использовано, или использовано условие задачи, как в примере.

Оцените статью
Добавить комментарий