информатика. Глава 1, часть 2_р. 1 Кодирование текстовых и символьных данных

• Название: 1 Кодирование текстовых и символьных данных
• Анкор: информатика
• Дата: 21.05.2023
• Размер: 5.84 Mb.
• Имя файла: Глава 1, часть 2_р.doc
• Тип: Документы; #1148633
• страница: 7 из 8

1.13.2. Элементы теории множеств

Первичным понятием теории множеств является понятие самого множества. Множество — это совокупность некоторых (произвольных) объектов, объединенных по какому-либо признаку. Элементы множества при этом должны быть различными. Множество обозначается парой скобок , внутри которых либо просто перечисляются элементы, либо описываются их свойства. Например,  — множество натуральных чисел, удовлетворяющих условию , очевидно, пусто. сложение, умножение  — множество основных арифметических операций. Пустое множество обозначается знаком . Если необходимо указать, что объект является элементом множества , то пишут ( принадлежит ), наоборот запись говорит о том, что не принадлежит .

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

Объединение (или сумма). Эта операция над множествами обозначается , определяется как . Все операции над множествами можно иллюстрировать с помощью диаграмм Эйлера⁵- Венна^6. Если за некоторое универсальное множество, содержащее как подмножества все другие множества, обозначить (или ) и изобразить его в виде всей плоскости, то любое множество можно изобразить в виде части плоскости, то есть в виде некоторой фигуры, лежащей на плоскости. Множество объединение множеств и , на рис.  1.7 заштриховано. .

Р
ис. 1.7. Объединение множеств

Рис. 1.8. Пересечение множеств

Пересечением (или произведением) двух множеств называется такое множество , которое состоит из элементов, принадлежащим одновременно обоим множествам, то есть . Пересечение множеств и заштриховано и изображено на рис.  1.8.

Разностью двух множеств и называется множество , состоящее из тех и только тех элементов, которые входят в и одновременно не входят в , то есть (рис. 1.9). Если, в частности, подмножество , то разность обозначается и называется дополнением множества (рис. 1.10).

Рис. 1.9. Разность множеств

Рис. 1.10. Дополнение множества

С
имметрической разностью или кольцевой суммой множеств и называется множество (рис. 1.11). Очевидно, что . Если и , то пару элементов называют упорядоченной парой, причем пары и равны тогда и только тогда, когда и .

Р
ис. 1.11. Симметрическая разность

Множество, элементами которого являются все упорядоченные пары , , называется прямым или декартовым произведением множеств и и обозначается . Например, , , а . Таким образом, декартово произведение не подчиняется коммутативному закону, и справедливо, если . Произведение называется декартовым квадратом.

Свойства операций объединения, пересечения и дополнения иногда называются законами алгебры множеств. Эти законы аналогичны правилам для равносильностей в булевой алгебре (1.13.1)—(1.13.3).

Часто элементы разных множеств связаны различными соотношениями, например, соотношениями порядка. -местным отношением или -местным предикатом на множествах называется любое подмножество декартова произведения . Обозначение -местного отношения . При отношение называется унарным и является подмножеством множества . Бинарным (или двуместным при ) отношением называется множество упорядоченных пар. Элементы называются координатами или компонентами отношения .

В теории множеств важную роль играют два вида специальных бинарных отношений: отношения эквивалентности и отношения порядка. Прообразами этих отношений служат интуитивные понятия равенства, предшествования и предпочтения.

Рассмотрим два конечных множества , и бинарное отношение . Введем матрицу бинарного отношения следующим образом:

.

Эта матрица содержит полную информацию о связях между элементами множеств и и позволяет представить эту информацию в графическом виде.

Матрица любого бинарного отношения обладает следующими свойствами:

• 
  если и , то ; , причем сложение элементов матрицы осуществляется по правилам 0 + 0 = 0, 1 + 1 = 1, 1 + 0 = 0 + 1 = 1, а умножение осуществляется почленно обычным образом, т. е. по правилам , ;
  
• 
  , где  — матрица обратного отношения ;
  
• 
  если , то и .
  

Пример 1. Бинарное отношение , изображено на рис. 1.12. Его матрица имеет вид:

.

Пусть

,

тогда

, .

Р
ис. 1.12. Бинарное отношение ,

Пусть  — бинарное отношение на множестве , . Отношение на множестве называется рефлексивным, если , , т. е.

,

где звездочкой обозначены нули или единицы. Отношение называется иррефлексивным, если , . Отношение на множестве называется симметричным, если и из условия следует, что . Это значит, что . Отношение называется антисимметричным, если из условий и следует, что , или . Это свойство приводит к тому, что у матрицы все элементы вне главной диагонали будут нулевыми (на главной диагонали тоже могут быть нули). Отношение называется транзитивным, если из и следует, что .

Рефлексивное, транзитивное и симметричное отношение на множестве называется эквивалентностью на . Эквивалентность обозначается символами или , например, , .

Пример 2. Докажем, что на множестве отношение является отношением эквивалентности, если .

Если отношение рефлексивно на , то . В нашем случае роль играет множество , а роль элемента играет пара . Тогда отношение рефлексивно на , если . По определению , но , следовательно, рефлексивно.

Аналогично, если , то и , так как из следует, что . Таким образом, симметрично.

Наконец, если , , то , так как и . Тогда , т. е. транзитивно.

Рефлексивное, транзитивное и антисимметричное отношение на множестве называется частичным порядком на . Частичный порядок обозначается символом , а обратное ему отношение символом . Отношение называется строгим порядком и определяется таким образом: и . Это отношение не является частичным порядком, так как не удовлетворяет условию рефлексивности .

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

Непустое множество , на котором зафиксирован некоторый частичный (линейный) порядок, называется частично (линейно) упорядоченным множеством. Элемент частично упорядоченного множества называется максимальным (минимальным), если для из того, что , следует . Элемент называется наибольшим (наименьшим), если для всех . Наибольший элемент обозначается , наименьший — . Этих элементов у множества может и не быть, например, линейно упорядоченное множество рациональных чисел не имеет наименьшего элемента, наибольший элемент равен единице.

Верхней (нижней) гранью подмножества частично упорядоченного множества называется всякий элемент и такой, что для всех . Точной верхней (нижней) гранью подмножества называется наименьшая верхняя (наибольшая нижняя) грань для . Точная верхняя и точная нижняя грани множества обозначаются через (супремум) и (инфимум) соответственно.

Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным.