Главная страница
Навигация по странице:

  • Р ис. 1.7.

  • Рис. 1.9.

  • Р ис. 1.11.

  • Р ис. 1.12.

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


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

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


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

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

    Объединение (или сумма). Эта операция над множествами обозначается , определяется как . Все операции над множествами можно иллюстрировать с помощью диаграмм Эйлера5- Венна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. Докажем, что на множестве отношение является отношением эквивалентности, если .

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

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

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

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

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

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

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

    Линейный порядок на множестве называется полным, если каждое непустое подмножество множества имеет наименьший элемент. В этом случае множество называется вполне упорядоченным.
    1   2   3   4   5   6   7   8


    написать администратору сайта