Дискретная математика: Учебное пособие. Часть I - Основания дискретной математики, страница 2

Если AÍB и BÍA, то A=B.

Например, если А={1, 2, 3} и B={3, 2, 1}, то A=B.

Если AÍB и A¹B, то A называют собственным подмножеством B.

Например, если А={1, 2, 3} и B={1, 2, 3, 4, 5}, то A есть собственное подмножество B.

Для обозначения этого в тексте используют символ “Ì“- знак строгого включения: AÌB.

Если, не все элементы множество A принадлежат множеству B, то множество A не включено в множество B.

Например, если А={1, 2, 3, 6 , 7} и B={1, 2, 3, 4, 5}, то множество A не включено в множество B.

Для обозначения этого в тексте используют символ “Ë“ - знак невключения: AËB.

На языке pascal факт невключения множества A в множество B записывают так: not(A£B).

Множество, не содержащее ни одного элемента, называют пустым множеством и обозначают знаком Æ, т.е. Æ ={ } Пустое множество является подмножеством любого множества. Множество, содержащее все элементы всех подмножеств, принимающих участие в решении каких-либо задач, называют универсальным множеством и обозначают символом U.

 Например, если в решении каких-либо задач принимают участие два множества  А={a, b} и B={b, c, d}, то универсальное множество U ={a, b, c, d}.

Множество, элементами которого являются подмножества, называют семейством подмножеств.

Например, AÎ{{a, b}, {b, c, d}}, BÎ{{a, b}, {b, c, d}}.

Пусть даны множества {1; 2} и {{1; 2; 3}, {1; 3}, 1; 2}.

Тогда выражение {1; 2}Î{{1; 2; 3}, {1; 3}, 1; 2} неверно, т.к. среди элементов множества {{1; 2; 3}, {1; 3}, 1; 2} нет элемента {1; 2}, а {1; 2}Í{{1, 2, 3}; {1; 3}; 1; 2} верно, т.к. элементы 1, 2 множества {{1; 2; 3}, {1; 3}, 1; 2} формируют подмножество {1; 2}.

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

Булеан универсального множества обозначают символом Â(U).

Например, если U={a,b,c},

то Â(U)={Æ, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}}.

На языке pascal булеан описывают как объект множественного типа на основе элементов базового типа.

 Например, Â(U)=set of (‘a’, ‘b’, ‘c’) = [[], [a], [b], [c], [a,b], [b,c], [a,c], [a,b,c]], где Â(U):=<идентификатор_булеана>.

Число элементов булеана Â(U) зависит от числа элементов универсального множества U по формуле:

 |Â(U)|=2|U|, где |U| - мощность или число элементов универсального множества, а |Â(U)| - мощность или число элементов булеана.

Например, если |U|=3, то |Â(U)|=23=8, если |U|=5, то |Â(U)|=25=32.

В компьютере для кодирования букв, цифр и символов используют 8 разрядов двоичного кода. Это позволяет сформировать 256 кодовых комбинаций.

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

 Перечисление элементов множества или указание диапазона допустимо только для конечных и счетных множеств.

Например, множество ПРОДУКТЫ ПИТАНИЯ={‘хлебобулочные_изделия’, ‘кондитерские_изделия’, ‘молочные_продукты’, ‘напитки’, ‘фрукты’, ...} или множество целых чисел А={1, 2, 3, 4} или В={1, 2,..9}.

При описании множества указанием характерных свойств между фигурными скобками после указания текущего элемента множества ‘x’ ставят знак “½“, вслед за которым эти свойства описывают логической функцей - Р(х):=”..”. Если при подстановке х=а логическая функция Р(а) принимает значение “истина”, то элемент ‘a’ включается в перечень элементов множества.

 Например, множество СТУДЕНТЫ ГРУППЫ 00-ИЭ={x| P(x):=”x - студент учебной группы 00-ИЭ ”}, где P(x) –логическая функция, определяющий условие принадлежности студента учебной группе 00-ИЭ. Просматривая список всех студентов факультета или университета можно сформировать список СТУДЕНТЫ ГРУППЫ 00-ИЭ={Бровань О. Д., Виниченко С.В., Данилков А. В., Драгулов М.И.,..}.