Курсовая работа (т): Основы теории множеств и ее реализация в языке программирования Паскаль

·              Для мощностей, как и в случае конечных множеств, имеются понятия: «равенство», «больше», «меньше». То есть для любых множеств A и B возможно только одно из трёх:

1.         , или А и В равномощны;

2.         , или А мощнее В, т. е. А содержит подмножество, равномощное В, но А и В не равномощны;

3.        , или B мощнее A - в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.

·              Ситуация, в которой  и  не равномощны и ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора <https://ru.wikipedia.org/wiki/%D0%90%D0%BA%D1%81%D0%B8%D0%BE%D0%BC%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%B0>).

·              Ситуация, в которой  и  , невозможна по -теореме Кантора  Бернштейна <https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%B0%D0%BD%D1%82%D0%BE%D1%80%D0%B0_%E2%80%94_%D0%91%D0%B5%D1%80%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0>.

Таким образом, рассмотрели, что включает в себя мощность множества, по каким признакам различались множества до построения теории мощности множеств.

ГЛАВА 2 МНОЖЕСТВА В ПАСКАЛЕ. ОПИСАНИЕ, ОПЕРАЦИИ

.1 Множества в паскале

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

Размер множества в Turbo Pascal всегда ограничен некоторым предельно допустимым количеством элементов. Во множествах допускаются только такие элементы, порядковые значения которых не выходят за границы 0..255. Для целочисленных множеств это означает, что в них могут присутствовать только числа от 0 до 255. Отрицательные элементы множеств в Turbo Pascal не допускаются. Поэтому базовыми типами не могут быть типы shortint, integer, longint. Если же необходимо множество целочисленных объектов, то базовый тип должен объявлен как диапазон типа byte. Для множеств, содержащих символы, подобных затруднений нет, поскольку базовым типом для них является char (а в нем 256 значений с порядковыми номерами от 0 до 255).[21]

В математике для обозначения множества используют фигурные скобки (например, {4, 7, 12}), в Паскаль - квадратные (например, [1, 3, 5]). Порядок элементов во множестве не имеет значения. Так, записав [3, 6, 9] или [9, 3, 6], мы будем иметь дело с одним и тем же множеством. Более того, многократное повторение одного и того же элемента не меняет множество. Например, [4, 7, 3] и [3, 7, 4, 4] - это одно и то же множество.

По форме записи объявление переменной типа множество сходно с объявлением одномерного массива:

var

имя: set of тип;

Например, объявление переменной ch, рассматриваемой как множество с базовым типом char, имеет вид:

var: set of char;

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

Можно сначала объявить тип множества, а потом использовать его для объявления переменных:

type_ch = set of char;, ch2: t_ch;

Довольно часто в качестве базового типа множества используется тип перечисления или некоторый его диапазон:

type_days = (Mon, Tue, Wed, Thu, Fri);_days: set of week_days;: set of 'A'..'Z';

Объявление переменной-множества не дает ей определенного значения.[21]

2.2 Построение множества в паскале

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

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

type_days = (Mon, Tue, Wed, Thu, Fri);

var_days: set of week_days;: set of 'A'..'Z';_days := [Mon, Wed, Thu];:= ['C', 'E'..'M', 'Z']

end.

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

Множество, в котором нет элементов, называется пустым (или нуль-множеством). В языке программирования Паскаль обозначается квадратными скобками, между которыми нет элементов:

work_days := [ ];

Множество может быть объявлено типизированной константой, для чего в описании после знака равенства следует указать конструктор множества. Например:

const lett: set of ['а'..'я'] = ['а', 'е', 'и', 'о', 'у', 'ы', 'э', 'ю', 'я'];

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

Конструируя множества, можно использовать и переменные при условии, что их текущие значения попадают в диапазон базового типа множества. Так, если ch1 иch2 имеют тип char, то допустима следующая последовательность операторов:

ch1 := 'A';:= 'K';:= [ch1, ch2, 'M'];

Элементы множества нельзя вводить и выводить. Для организации ввода-вывода элементов множества следует использовать вспомогательные переменные. В то же время можно использовать множества как элементы типизированных файлов.

множество операция действие pascal

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

С множественными типами Паскаля можно выполнять действия объединения, исключения и пересечения.

Объединение множественных типов содержит элементы, которые принадлежат хотя бы одному множеству, при этом каждый элемент входит в объединение только один раз. Операция объединения множеств обозначается знаком ‘+’.

Пример объединения множественных типов:

Type symbol= set of char;small, capital, latin: symbol;

………………:= [‘a’ .. ‘z’];:= [‘A’ .. ‘Z’];

latin:= small + capital; {образованы множества латинских букв путем объединения множеств small и capital}

Возможно объединять множественные типы и отдельные элементы. Например, small:= [‘c’ .. ‘z’];:= small + [‘a’] +[‘b’];

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

Пример исключения множественных типов Паскаля::= [‘a’ .. ‘z’]; {множества букв латинского алфавита}:= [‘a’, ‘e’, ‘o’, ‘u’, ‘i’, ‘y’]; {множества гласных букв}:= letter-glasn; {образовано множества согласных букв путем исключения из множества всех букв множества гласных букв}

Пресечение множественных типов - множества, содержащие элементы, одновременно входящие в оба множества. Операция пересечения множеств обозначается знаком ‘*’.

Пример пересечения множественных типовchisla= set of byte;

Var z,x,y: chisla;

………..:= [0..150];:= [100..255];:= x*y {получено множества чисел из диапазона 100..150 в результате пересечения двух множеств}

Операции отношения множественных типов наряду с рассмотренными выше операциями, над значениями множественного типа определены и некоторые операции отношения. Операндами операций над множественными значениями в общем случае являются множественные выражения. Среди операций отношения над значениями множественного типа особое место занимает специальная операция проверки вхождения элемента во множества, обозначаемая служебным словом in. В отличие от остальных операций отношения, в которых значения обоих операндов относятся к одному и тому же множественному типу значений, в операции in первый операнд должен принадлежать базовому типу, а второй - множественному типу значений, построенному на основе этого базового типа. Результатом операции отношения, как обычно, является логическое значение (true или false).

Операция сравнения на равенство множественных типов. Множества считаются равными (эквивалентными), если все элементы одного множества присутствуют в другом и наоборот. Для операции сравнения на равенство или неравенство используются символы ‘=’ и ‘<>’. A:= [2,1,3]; D:= [1,3,2];

Тогда операция A=D имеет значение true, а операция A<>D имеет значение false.

Проверка включения. Одно множество считается включенным в другое (одно множество является подмножеством другого), если все его элементы содержатся во втором множестве. Обратное утверждение может быть и несправедливым. Операции проверки включения обозначаются ‘<=’ и ‘>=’.>= glasn; soglan <= letter;

Следует отметить, что применение операций < и > над операндами множественного типа недопустимо.[21]

Таким образом, подведем итог. В языке программирования Pascal существует понятие множества, имеющее смысл некоторого собрания элементов, одно и того же базового типа, с которыми можно выполнять действия объединения, исключения и пересечения.

ЗАКЛЮЧЕНИЕ

В ходе написания курсовой работы были получены следующие выводы:

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

Также, рассмотрели, что включает в себя мощность множества, ее свойства, по каким признакам различались множества до построения теории мощности множеств.

В языке программирования Pascal существует понятие множества, имеющее смысл некоторого собрания элементов, одно и того же базового типа, с которыми можно выполнять действия объединения, исключения и пересечения. Чтобы во множестве появились элементы, необходимо выполнить оператор присваивания, в левой части которого стоит имя переменной-множества, а в правой - конструктор множества или некоторое выражение над множествами. Конструктор множества - это заключенный в квадратные скобки перечень элементов, разделенных запятыми.

На основании найденной информации (учебная литература, Internet), я выделила основные пункты, которые наиболее полно и точно дают представление о теории множеств. При выполнении работы были приведены примеры множеств и примеры решения задач в паскале с применением множеств. После проделанной работы можно сделать следующий вывод:

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

1.      Болибрух А. А., Проблемы Гильберта (100 лет спустя), Глава 2 Первая проблема Гильберта: континуум-гипотеза <#"865570.files/image039.gif">

Рисунок.8

К1 - множество учеников, решивших только одну задачу по алгебре;

К2 - множество учеников, решивших только две задачи по алгебре и геометрии;

К3 - множество учеников, решивших только задачу по геометрии;

К4 - множество учеников, решивших только две задачи по алгебре и тригонометрии;

К5 - множество всех учеников, решивших все три задачи;

К6 - множество всех учеников, решивших только две задачи, по геометрии и тригонометрии;

К7 - множество всех учеников, решивших только задачу по тригонометрии;

К8 - множество всех учеников, не решивших ни одной задачи.

Используя свойство мощности множеств и рисунок можно выполнить вычисления:

·              m (К5) = m (А∩В∩С)= m (АВС) - m (А) - m (В) - m (С) + m (А∩В) + m (А∩С) + m (В∩С)

·              m (К5) = 37-20-18-18+7+8+9=5

·              m (К2) = m (А∩В) - m (К5) = 7-5=2

·              m (К4) = m (А∩С) - m (К5) = 8-5=3

·              m (К6) = m (В∩С) - m (К5) = 9-5=4

·              m (К1) = m (А) - m (К2) - m (К4) - m (К5) = 20-2-3-5=10

·              m (К3) = m (В) - m (К2) - m (К6) - m (К5) = 18-2-4-5=7

·              m (К7) = m (С) - m (К4) - m (К6) - m (К5) = 18-3-4-5 =6

·              m (К2) + m (К4) + m (К6) = 2+3+4=9 - число учеников решивших только две задачи;

·              m (К1) + m (К3) + m (К7) = 10+7+6=23 - число учеников решивших только одну задачу.

Ответ:

учеников решили три задачи;

учеников решили только по две задачи;

ученика решили только по одной задаче.

Задача № 2

Первую или вторую контрольные работы по математике успешно написали 33 студента, первую или третью - 31 студент, вторую или третью - 32 студента. Не менее двух контрольных работ выполнили 20 студентов.

Сколько студентов успешно решили только одну контрольную работу?

Решение

·              m (АВ) = 33

·              m (АС) = 31

·              m (ВС) = 32

·              m (К2) + m (К4) + m (К6) + m (К5) = 20

Найти m (К1) + m (К3) + m (К7)

·              m (АUВ) = m (К1) + m (К2) + m (К3) + m (К4) + m (К5) + m (К6) = m (К1) + m (К3) + 20 = 33 =>

·              m (К1) + m (К3) = 33 - 20 = 13

·              m (АUС) = m (К1) + m (К4) + m (К2) + m (К5) + m (К6) + m (К7) = m (К1) + m (К7) + 20 = 31 =>

·              m (К1) + m (К7) = 31 - 20 = 11

·              m (ВUС) = m (К3) + m (К2) + m (К5) + m (К6) + m (К7) + m (К4) = m (К3) + m (К7) + 20 = 32 =>

·              m (К3) + m (К7) = 32 - 20 = 12

·              2m (К1) + 12 = 24

·             

·              m (К3)= 13-6=7

·              m (К7)=12-7=5

·              m (К1) + m (К3) + m (К7) = 6+7+5=18

Ответ:

Только одну контрольную работу решили 18 учеников.

Задача № 3

В классе 35 учеников. Каждый из них пользуется хотя бы одним из видов городского транспорта: метро, автобусом и троллейбусом. Всеми тремя видами транспорта пользуются 6 учеников, метро и автобусом - 15 учеников, метро и троллейбусом - 13 учеников, троллейбусом и автобусом - 9 учеников.

Сколько учеников пользуются только одним видом транспорта?

Решение

·              m (Е) = 35

·              m (А∩В∩С)= m (К5) = 6

·              m (А∩В)= 15

·              m (А∩С)= 13

·              m (В∩С)= 9

Найти m (К1) + m (К3) + m (К7)

·              m (К2) = m (А∩В) - m (К5) = 15-6=9

·              m (К4) = m (А∩С) - m (К5) = 13-6=7

·              m (К6) = m (В∩С) - m (К5) = 9-6=3

·              m (К1) + m (К3) + m (К7) = m (Е) - m (К4) - m (К2) - m (К6) - m (К5) = 35-7-9-3-6=10

Ответ:

Только одним видом транспорта пользуется 10 учеников.

Задача №4

Студенты третьего курса, изучающие информационные технологии в университете, могут изучать и дополнительные дисциплины по выбору. В этом году 30 из них выбрали дисциплину «Информационные технологии моделирования интерьера», 35 предпочли дисциплину «Информационные технологии в рекламе», а 20 решили изучать дисциплину «Информационные технологии моделирования ландшафта». Кроме того, 15 студентов изъяви- ли желание посещать «Информационные технологии моделирования интерьера» и «Информационные технологии в рекламе», 7 - «Информационные технологии в рекламе» и «Информационные технологии моделирования ландшафта», 10 - «Информационные технологии моделирования интерьера» и «Информационные технологии моделирования ландшафта», 3 - все три дисциплины.