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

Доказать тождество .

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

Задача 4. Упростить выражение

.

Решение.

1) Применив дистрибутивный закон, получим

2) Используя коммутативный закон, закон де Моргана и Закон двойного дополнения, получим

.

3) Применив дистрибутивный закон и закон де Моргана, получим

4) Применим закон получим

.

Варианты заданий

1. Докажите тождество .

2. Докажите, что .

3. Упростите .

4. Докажите тождество

.

5. Упростите .

6. Докажите тождество .

7. Докажите тождество

.

8. Докажите тождество .

9. Докажите тождество .

10. Докажите тождество

11. Докажите тождество .

12. Упростите .

13. Докажите тождество .

14. Докажите закон поглощения .

15. Докажите тождество .

16. Докажите закон поглощения .

17. Докажите тождество .

18. Докажите тождество .

19. Докажите тождество .

20. Докажите, тождество

2. БИНАРНЫЕ ОТНОШЕНИЯ

Теоретические сведения

В множестве Xn-местным или n-арным отношением называется подмножество R n-й декартовой степени = заданного множества, , называется носителем отношения [2, 6, 7]. Будем говорить, что упорядоченные элементы находятся в отношении R, если R. Одноместное отношение называется унарным, или свойством, и соответствует подмножеству множества X. Особую роль в приложениях играют бинарные отношения R Х Х. Каждому бинарному отношению можно поставить в соответствие матрицу бинарного отношения, которую также будем обозначать через R= и элементы которой определяются по следующему правилу:

1, если R

=

0, если R

Рассмотрим свойства бинарных отношений.

Отношение R называется

рефлексивным, если для х Х (х, х) R;

антирефлексивным, если х Х (х, х) R;

симметричным, если х, y Х из условия (х, у) R следует (у, х) R;

антисимметричным, если х, y Х из условия (х, у) R следует условие (у, х) R;

транзитивным, если х, y,z Х из условий (х, у) R и (у, z) R следует (x, z) R.

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

Так как отношение является прежде всего множеством упорядоченных пар, то для отношений можно ввести те же операции, что и для множеств, то есть операции объединения, пересечения, дополнения и разности. Кроме того, для отношений существуют специальные операции [1, 6]:

инверсией отношения R называется отношение .

Пусть - отношения, заданные на множестве X, тогда композицией отношений R и R называется отношение, определяемое следующим образом

.

Замечание. .

Рефлексивное, симметричное, транзитивное отношение называется отношением эквивалентности или эквивалентностью (обозначение I) [1, 2].

Пример. Отношение равенства на множестве целых чисел, отношения подо­бия на множестве треугольников являются отношениями эквивалентности.

Классом эквивалентности K(x) элемента х называется множество всех элементов у Х, каждый из которых находится с этим элементом в отношении эквивалентности. Иными словами, класс эквивалентности - это множество эквивалентных элементов.

Два различных класса эквивалентности не пересекаются, поэтому если все элементы множества Х распределены по классам эквивалентности, то эти классы эквивалентности образуют разбиение множества X.

Для определения, является ли заданное отношение R отношением эквивалентности, используют следующий критерий:

Пусть R - матрица бинарного отношения. Если путем перестановки строк и столбцов ее можно привести к блочно-диагональному виду (на главной диагонали расположены подматрицы, состоящие из 1, а остальные элементы равны 0), то R является отношением эквивалентности, иначе - R не является отношением эквивалентности.

Поиск по сайту: