А Ì В ® (( х Î А)(х Î B ) & A ¹ В)).

Приведем основные свойства строгого включения:

· А Ë А                                         - антирефлексивность;

·     - транзитивность;

· А Ì В ® А ¹ В                          - неравенство.

Любое непустое множество М включает, по крайней мере, два подмножества - пустое и само себя, т.е. М Í М и Æ Í М. Доказательство этого утверждения следует из определения подмножества. Множества М и Æ называют несобственными подмножествами множества М, все остальные подмножества множества М называются собственными подмножествами.

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

Множество всех подмножеств множества М называется семейством подмножеств множества Ми обозначается Â(M)(читается "Пэ от Эм"). Из определения семейства следует, что ÆÎÂ(М), М ÎÂ(М) и если В Í М, то ® ВÎÂ(М).

Если множество М содержит m элементов, то мощность семейства подмножеств множества М равна 2 ^m.

Например, подсчитаем, сколько подмножеств имеет конечное множество А = {a, b}. Так как n = 2, то семейство подмножеств содержит 2 ^m = 4 подмножества:

{a, b}; {a}, {b}, {Æ}.

Для B = {a, b, c} семейство подмножеств равно 2 ^m = 8.

Если множество содержит n элементов, а его подмножество состоит из k элементов, то число k элементных подмножеств, называемых сочетанием из n по k, равно

,

где n! = 1×2×3×…×(n - 1)× n.

ПРИМЕЧАНИЯ

1. Пустое множество является единственным подмножеством самого себя Æ Í Æ.

2. Пустое множество не имеет собственных и истинных подмножеств.

3. Одноэлементное множество имеет два подмножества - с a м o себя и Æ, т.е. не имеет собственных подмножеств.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

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

Пример 1.1. Задано множество А = { a, b, c, d }. Какие из следующих высказываний являются истинными?

а) a ÎA;          в) d ÎA;

б) { a, b }ÎA;  г) { a, b, c, d }ÎA.

Ответ: Высказывания a ÎA и d ÎA являются истинными, т.к. среди элементов множества А есть элементы a и d, высказывания { a, b }ÎA и { a, b, c, d }ÎA являются ложными, т.к. такие элементы не входят в множество А.

 

Пример 1.2. Перечислите элементы множеств:

а) A = { x | ($ y)(y Î{0, 1, 2} & x = y ³)};

б) B = { x | x ÎN & ($ y)(y ÎN & x < y)};

в) C = { x | x ÎN & (" y)(y ÎN ® x £ y)}.

Ответ: a) элементы множества А могут быть найдены вычислением третьей степени всех возможных значений y. Таким образом, A = {0, 1, 8}.

б) x и y - элементы множества натуральных чисел N и, каково бы ни было значение х, всегда можно в множестве N найти значение у, при котором будет выполняться условие x < y.

в) если х и у - элементы множества натуральных чисел N, то условие x £ любого элемента множества N - будет выполняться только для одного значения х, равного 0. Следовательно, С = {0}.

 

Пример 1.3. Задать множества высказывательным способом:

а) A = {3};

б) P = {6, 7, 8, 9, 10};

в) В - множество четных целых чисел.

Ответ: а) один из возможных вариантов ответа A = { x ÎN | (x + 2 = 5)};

б) Один из возможных вариантов ответа P = { x | x ÎN & (x > 5 & x < 11)};

в) В = { x | x ÎZ & (" y)(y ÎZ ® x = 2 y)}.

 

Пример 1.4. Определите, равны ли множества А и В, С и D, если A = {1, 2, 3, 4}; B = {4, 3, 2, 1}; C = {2, 3, 4, 5}; D = {3, 4, 5}.

Ответ: А = В, т.к. они содержат одни и те же элементы; С ¹ D, т.к. множество С содержит элемент 2, не принадлежащий множеству D.

 

Пример 1.5. Пусть: A = {1, 7, 9, 15}; B = {7, 9}; C = {7, 9, 15, 20}.

Все ли следующие утверждения истинны?

 

а) B Í C,	д) 15 Î C,
б) B Í A,	е){7, 9} Î B,
в) B Ì A,	ж) {7} Ì A,
г) A Ë C,	з) Æ Í C.

Ответ: Все утверждения, кроме е), истинны.

 

Пример 1.6. Доказать, чтоА Í В, если A = { x ÎN | x кратно 8}; B = { x ÎN | x кратно 4};

Доказательство: Пусть х - произвольный элемент множества А. Мы должны показать, что х так же является элементом множества В, т.е. обладает свойством, характерным множеству В. Это означает, что х должно быть кратным 4. Поскольку х является элементом множества А, он обладает характерным свойством этого множества, следовательно, х кратно 8 и можно записать х = 8× m для любого целого m. Это же выражение может быть записано в виде x = 2×4× m или x = 4× k, где k - четное целое число. Следовательно, х всегда кратен 4 и поэтому х ÎВ, что и требовалось доказать.

 

Пример 1.7. Доказать, что А = В, если A = { x ÎN | x ² < 15}; B = { x ÎN | 2 x < 7};

Доказательство: Чтобы доказать, что А = В, необходимо доказать, что А Í В, а затем, что В Í А. Пусть х ÎА, следовательно, х должно обладать характерным свойством множества А, т.е. должен выполняться условия: х ² < 15 и х ÎN. Этим двум условиям удовлетворяют следующие четыре значения х: 0, 1, 2, 3. Следовательно, только эти числа являются элементами множества А. Причем удвоенные значения любого элемента множества А меньше 7, т.е. каждый из них обладает характерным свойством множества В. Следовательно, А Í В. Теперь докажем, что В Í А. Любой элемент множества В должен быть положительным, а его удвоенное значение меньше 7. Множество В cоставляют следующие элементы: 0, 1, 2, 3. Квадрат любого из них меньше 15, следовательно, В Í А. Таким образом, доказано, что А = В.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что такое “множество”, “элемент множества”?

2. Какие существуют способы задания множеств? Привести примеры.

3. Приведите определение понятий простого и составного логического высказывания.

4. Перечислите основные операции над логическими высказываниями. Приведите примеры.

5. Что представляет собой квантор существования и квантор общности?

6. Какие множества называются равными?

7. Какие подмножества называются несобственными?

8. В чем отличие между “принадлежностью к множеству” и “включением в множество”?

9. Приведите способы задания множеств.

10. Отличаются ли множества А = Æ и А = { Æ } и если “да”, то в чем состоит отличие.

11. Что такое строгое и нестрогое включение?

12. Как построить семейство подмножеств?

13. Сколько элементов содержит семейство подмножеств?

14. Приведите формулу подсчета числа подмножеств множества.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Задано множество S = {0, 4, 12, 31}. Какие из следующих высказываний являются истинными?

а) 12ÎS;	б) 0+31ÎS;	в) 4+12ÎS;
г) ÆÎS;	д) {4}ÎS;	е){0,4,12,31}ÎS.

2. Записать произвольное одноэлементное множество, элементом которого является множество.

3. Привести примеры таких множеств A, B, C и D, что A Î B, B Ï D, D Î C, A Ï D, B Ï C.

4. Задать каждое из множеств с помощью перечисления:

а) A = { x | x Î R & x ² < 0};

б) B = { x ÎN | 3 < x £ 7};

в) D = { x | x - месяц года, содержащий 30 дней};

г) C = { y | y - факультеты ТРТУ};

д) E = { x ÎN | (" y)(y Î{2, 3, 4, 5} ® x > y)};

e) F = { x | ($ y)($ z)(y Î{1, 2} & z Î{2, 3} & x = y + z)}.

5. Задать множества высказывательным способом:

a) A = {1, 4, 9, 16};

б) B = {2, 3, 5, 7, 11, 17};

в) C = {3, 5, 7, 9, 11, 13, 15};

г) D = {февраль};

д) F = {понедельник, вторник, среда, четверг, пятница}.

6. Запишите таблицы истинности основных операций над высказываниями и поясните их смысл.

7. Определить, равны ли множества А и В:

а) A = { a, b, c };	B = { b, c, a };
б) A = { a, b, { c }};	B = { b, c, a };
в) A = {{ a, b, c }};	B = { a, b, c };
г) A = {{ a, b, c }};	B = {{ a }, { b }, { c }};
д) A = { a, b, c };	B = {{ a }, { b }, { c }}.

8. Пусть A = { x Î N | x > 5}; B = {10, 12, 16, 20}; C = { x | ($ y)(y ÎN & x = 2 y)}. Какое из следующих высказываний истинно?

а) B Í C,	ж) B Ì A,
б) A Í C,	з) 26ÎC,
в) {11, 12, 13} Í A,	и) {11, 12, 13} Ì C,
г) {12}ÎB,	к) {12} Í B,
д) { x ÎN | x < 20} Ë B,	л) 5 Í A,
е) {Æ} Í B,	м) ÆÏA.

9. Пусть A = { x ÎR | x ² - 4 x + 3 = 0}; B = { x ÎN | 1 £ x £ 4}. Доказать, чтоA Ì B.

10. Доказать или опровергнуть, что A = B, если A={ x ÎR | 2 x = 5}; B={ x ÎR | x > 3}.

11. Привести пример множества, имеющего только несобственные подмножества.

12. Выбрать из элементов множества A = { a, x, { b, c }, Æ, 5} несобственные элементы.

13. Записать семейство подмножеств пустого множества.

14. Записать семейство всех подмножеств множества  A = { x, y, z, k } и B = {Æ, {Æ}}.

15. Задать множества A, B, C, удовлетворяющие следующим условиям:

а) AÎB, A Í B;                            б) AÎB, A Í C;

в) AÎB, A Í B, A Í C;                г) AÎB, B Í C;

д) AÎB, A Ì B;                            е) A Í B, B Í A.