Краткие ответы на экзаменационные вопросы по дисциплине "Дискретная математика" (Предмет дискретной математики. Метод Блейка-Порецкого), страница 2

2. указание св-ва, к-м должны обладать все эл-ты множ-ва: A={ x: x… }

Множества называются равными, если любой эл-т одного мн-ва явл-ся эл-м другого и наоборот разность А\В={ x: xÎA и x Ï B}

Универсальным множеством наз-ся мн-во, содержащее все эл-ты, находящиеся в рассмотрении.

7. Основные понятия ТМ. Симметр-я разность

«Множество» - неопределяемое базовое понятие.

Кантор: «Под множеством я понимаю вообще все многое, к-е возможно мыслить как единое, т.е. такую совокупность определенных элементов, которые посредством одного закона м.б. соединена в одно целое.»

Способы задания множеств:

1. перечисление эл-в: { a₁, …,a_k } k элементное множество

2. указание св-ва, к-м должны обладать все эл-ты множ-ва: A={ x: x… }

Множества называются равными, если любой эл-т одного мн-ва явл-ся эл-м другого и наоборот

СР = AêB =(A\B) È(B\A)

Универсальным множеством наз-ся мн-во, содержащее все эл-ты, находящиеся в рассмотрении.

8. Свойства множеств

1. свойства коммутативности:

AUB=BUA; A∩B=B∩A

2 ассоциативность

AU(B∩C)=(A∩B) U (A∩C) ; A∩(BUC)=(AUB) ∩ (AUC)

3. дистрибутивность

AU(BUC)=(AUB)UC; A∩(B∩C)=(A∩B)∩C

4. нуля и единицы

A∩Ø=Ø; AUØ=A; A∩U=A; AU=U; A∩=Ø

AUA=A ; A∩A=A ; AUU=U

5.двойного отрицания

=А

6. законы Де-Моргана

A\B=A∩

AB=(AUB)\(A∩B)

A (BC)=(AB) C

AB=BC

A∩(BC)=(A∩B)  (A∩C)

9. Док-во теоретико-множ-х тождеств:

AB=(AUB)\(A∩B)

Пусть xÎAB, по опр-ю получаем

xÎ(А\В) U(В\А), т.е. xÎ(А\В) или xÎ(В\А)

Если xÎ(А\В), то xÎА и хÏВ

хÎ(AUB) и хÏ(A∩B)

Если xÎ(В\А), то или xÎВ и хÏА, тогда хÎ(АUВ) и хÏ(A∩B)

Получили, что хÎ(AUB)\(A∩B)

Обратный ход

Пусть xÎ( AUB)\(A∩B), тогда

xÎ( AUB) и хÏ( A∩B), т.е. xÎА или xÎВ

Если xÎА и  хÏ A∩B, то xÎА и хÏВ, т.е. xÎА\В

Если xÎВ и хÏА, т.е. xÎ В\А

Получаем xÎ А\В или xÎ В\А, т.е. xÎ (А\В) U(В\А)

10. Диаграммы Эйлера-Венна     

Если зафиксированное U, то можно опр-ть дополнение множ-ва А до U: =U\A Подмножеством мн-ва А наз-ся такое мн-во В, все эл-ты к-го явл-ся эл-ми мн-ва А. BÍА

Замечания:

1.Пустое мн-во явл-ся подмножеством любого мн-ва.

2. 2 мн-ва А и В явл-ся равными тогда и только тогда, когда BÍА АÍВ

Чтобы док-ть равенство 2 мн-в: X и У исп-т различные методы, но наиболее часто метод 2 включений (зам.2), т.е. из предположения, что xÎ X док-т, что х Î У, и наоборот.

У каждого мн-ва м.б. образовано несколько подмножеств.

Мн-во всех подмножеств мн-ва А называют Булеаном и обозначают 2^A – такое мн-во, состоящее из мн-ва х, состоящих из множества А.

11. Конъюнкция, ее табл.истинности, мн-ва Любое высказывание м.б. истинным и ложным

Конъюнкция

Высказывание P^Q ититтк истинны оба выск-я

		^
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

12. Дизъюнкция

Любое высказывание м.б. истинным и ложным

Высказывание P v Q ититтк истинно хотя бы одно из выск-й

13. Отрицание.

Любое высказывание м.б. истинным и ложным

Высказывание ¬P ититтк P ложно

14. Импликация.

Любое высказывание м.б. истинным и ложным

Высказывание P=>Q ититтк истинно выск-е Q, или оба выск-я ложны

15. Эквиваленция

Любое высказывание м.б. истинным и ложным

Высказывание P<=>Q ититтк оба высказывания или одновременно истинны, или ложны