Конструктивное понятие множества в информатике

Множества: антиномия Рассела, порождение, интерпретации, операции, отношения, n-парные отношения, функции. Функции алгебры логики, алгебра Буля, предикаты.

Г. Кантор - «множество - единое имя для совокупности всех объектов, обладающих данным свойством» или «множество есть многое, мыслимое как единое».

В 1903 году английский математик Бертран Рассел предложил антиномию в рамках языка классической («наивной») теории множеств Георга Кантора:

Пусть K — множество всех множеств, которые не содержат сами себя в качестве своего подмножества.Ответ на вопрос «содержит ли K само себя в качестве подмножества?» не может быть дан в принципе. Если ответом является «да», то, по определению, такое множество не должно быть элементом K. Если же «нет», то, опять же по определению, оно должно быть элементом самого себя.

Данная антиномия (более известная под названием «парадокс Рассела») поколебала основы математики и формальной логики, что вынудило ведущих математиков того времени начать поиск методов её разрешения.

Позже австрийский философ Курт Гёдель показал, что «для достаточно сложных формальных систем всегда найдутся формулы, которые невозможно вывести (доказать) в рамках данной формальной системы» —первая теорема Гёделя о неполноте.

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

Лучшее пояснение природы множества все же принадлежит основателю теории множеств Георгу Кантору:

Под множеством мы понимаем любое соединение Aв одно целое определённых вполне различаемых объектов a,которые существуют в

нашем представлении или мыслях, которые называются элементами A.

Конструктивное понятие множества в информатике

Множество - совокупность (собрание, группа) элементов, обладающих общим свойством (природой, семантикой).

Множества в информатике требуют уточнения конструктивного характера.

1. Порождающий механизм для каждого элемента множества.

2. Каждый элемент множества должен отличаться от другого элемента.

3. Интерпретация множеств суть приписывание некоторого свойства (набора свойств) именно той совокупности элементов, которые объединены в множество.

Два способа порождения множеств:

а) для конечных множеств – перечисление элементов;

б) для бесконечных множеств – алгоритм или правила порождения.

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

В современных языках программирования (особенно в объектно- ориентированных и функциональных языках) механизм кодирования объектов, составляющих множества, и операций над объектами определяет сущность языка.

Операции над множествами и их свойства

1. Объединение 𝑨 ∪ 𝑩 ={ 𝒙 | 𝒙 ∈ 𝑨 ˅ 𝒙 ∈ 𝑩}

2. Пересечение 𝑨 ∩ 𝑩 = {𝒙 | 𝒙 ∈ 𝑨 ˄ 𝒙 ∈ 𝑩}

3. Разность 𝑨\𝑩 = 𝑨 ∩ 𝑩 = {𝒙 | 𝒙 ∈ 𝑨 ˄ 𝒙 не принадлежит 𝑩}

4. Дополнение a = {𝒙 | 𝒙 не принадлежит 𝑨}

все элементы берутся из некоторого «универсального» множества, или универсума, обозначаемого U или 1.

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

Сделаем одно очень важное замечание об интерпретации (свойствах) множеств сконструированных из исходных (базовых).

! Множество, сконструированное из базовых множеств и заданное формулой, в общем случае не наследует свойства исходных базовых множеств!

Специальные множества

* Пустое множество — множество, не содержащее ни одного элемента.

* Универсальное множество — множество, содержащее все мыслимые объекты.

* Упорядоченное множество — множество, на котором задано отношение порядка.

Булевой алгеброй называется непустое множество M с двумя бинарными операциями

∩ (аналог конъюнкции), ∪ (аналог дизъюнкции), унарной операцией (аналог отрицания)

и двумя выделенными элементами: 0 (пустое множество или Ложь) 1 (универсум или Истина) такими, что для всех A, B и C из множества верны аксиомы: