Дискретная математика

9 4) множество чисел Фибоначчи: ai, 02, oj, где + акч, к >\, fly=fl7=l; 5) множество самолетов и авиапассажиров. Элементы множества могут быть разнородными, как в последнем примере. Если объект (элемент) х принадлежит множеству М, то записываем хеМ, если же х не является элементом из М, то хеМ. Отношение е называется отношением пршадпеоюности. То, что множество М состоит из элементов aj, 02,..., а„, записываем с помощью фигурных скобок: M={ai, а^, о„}. Введём понятие предиката и порождающей процедуры. Предикат - это некоторое условие, выраженное в форме логического утверждения, которое истинно тогда и только тогда, когда указанные переменные (указанная переменная) удовлетворяют заданному условию. Порождающая процедура - это процедура, которая, будучи запущенной, поролсдает некоторые объекты по заданным правилам. Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Задать множество можно различными способами: перечислением элементов: M={ai, ог,..., а„)\ предикатом: М={х\ Р(х))\ порождающей процедурой; М={х-. x-f). Например, пусть на множестве всех целых чисел предикат Р(х) означает х - четное число, тогда М={х: х - четное число} состоит из четных и только четных чисел. В тех случаях, когда при определении множества уточняется, что предикат Р введён на заранее заданном множестве S, записывается: M={xeS-. Р(х)) или M={x\xeS и Р(х)}. Порождающей процедурой можно задать числа Фибоначчи: М={щ: <^к +fl/i+y,<^1~а2=1, к>\ }. при записи множеств перед предикатом или порождающей процедурой, т. е. перед любым определяющим условием, поставлено двоеточие. В литературе, кроме двоеточия, может применяться вертикальная черта, т. е. вместо записи М={х: Р(х)} может использоваться следующая форма записи: М={х1 Р(х)}. Иногда множество М={х: Р(х)} записывают в виде: M={x}p(^j. Выявление принадлежности элемента данному множеству может оказаться сложной задачей. Например, будет ли принадлежать число 93878763456789567 множеству простых чисел? Интуитивное определение множества, приведённое в начале этого параграфа, может приводить к противоречиям (парадоксам). Бертраном Расселом в 1902 г. был построен следующий парадокс. Рассмотрим множество всех окон в данной комнате. Элементами этого множества являются окна, т.е. множество окон не является элементом этого множества. Есть множества, которые являются элементами самого себя,