Основы теории множеств и ее реализация в языке программирования Паскаль

Министерство образования и науки Российской Федерации ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО»

Кафедра информатики и программирования основы теории множеств и ее реализация в языке программирования паскаль КУРСОВАЯ РАБОТА студентки 2 курса 261 группы направления 50 100.62 Педагогическое образование (профиль Информатика) факультета компьютерных наук и информационных технологий Чечёнковой Елены Анатольевны Саратов 2015

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ГЛАВА 1. ТЕОРИЯ. МНОЖЕСТВА, ОПЕРАЦИИ НАД МНОЖЕСТВАМИ, МОЩНОСТЬ МНОЖЕСТВА

1.1 Понятие множества

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

1.3 Мощность множества ГЛАВА 2. МНОЖЕСТВА В ПАСКАЛЕ. ОПИСАНИЕ, ОПЕРАЦИИ

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

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

2.3 Операции над множествами в паскале ЗАКЛЮЧЕНИЕ СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ ПРИЛОЖЕНИЕ ВВЕДЕНИЕ Теория множеств — раздел математики, в котором изучаются общие свойства множеств. Теория множеств лежит в основе большинства математических дисциплин; она оказала глубокое влияние на понимание предмета самой математики.

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

Например, натуральное число, по Кантору, следовало рассматривать как множество, состоящее из единственного элемента другого множества, называемого «натуральным рядом» — который, в свою очередь, сам представляет собой множество, удовлетворяющее так называемым аксиомам Пеано. При этом общему понятию «множества», рассматривавшемуся им в качестве центрального для математики, Кантор давал мало что определяющие определения вроде «множество есть многое, мыслимое как единое», и т. д. Это вполне соответствовало умонастроению самого Кантора, подчёркнуто называвшего свою программу не «теорией множеств» (этот термин появился много позднее), а учением о множествах (Mengenlehre). [17]

Программа Кантора вызвала резкие протесты со стороны многих современных ему крупных математиков. Особенно выделялся своим непримиримым к ней отношением Леопольд Кронекер, полагавший, что математическими объектами могут считаться лишь натуральные числа и то, что к ним непосредственно сводится (известна его фраза о том, что «бог создал натуральные числа, а всё прочее — дело рук человеческих»). Тем не менее, некоторые другие математики — в частности, Готлоб Фреге и Давид Гильберт — поддержали Кантора в его намерении перевести всю математику на теоретико-множественный язык. [7]

Однако вскоре выяснилось, что установка Кантора на неограниченный произвол при оперировании с множествами (выраженный им самим в принципе «сущность математики состоит в её свободе») является изначально порочной. А именно, был обнаружен ряд теоретико-множественных антиномий: оказалось, что при использовании теоретико-множественных представлений некоторые утверждения могут быть доказаны вместе со своими отрицаниями (а тогда, согласно правилам классической логики высказываний, может быть «доказано» абсолютно любое утверждение!). Антиномии ознаменовали собой полный провал программы Кантора.

И всё же Кантор считается основателем теории множеств, и сделал большой вклад в современную математику. Ему принадлежит следующая характеристика понятия «множество»: Множество — это объединение определённых, различных объектов, называемых элементами множества, в единое целое.

Объект исследования: теоритические основы информатики.

Предмет исследования: множества.

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

Задачи исследования:

· Обзор литературы;

· Раскрыть, что представляет собой множество, какие операции применяются при работе с множествами;

· Рассмотреть представление, построение множеств и применение операций над множествами в паскале.

ГЛАВА 1. теория. множества, операции над множествами, мощность множества

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

Можно сказать, что множество — это любая определенная совокупность объектов. Объекты, из которых составлено множество, называются его элементами. Элементы множества различны и отличимые друг от друга. Примерами множеств могут быть: множество людей, животных, растений на нашей планете, а также множество N натуральных чисел 1, 2, 3, …, множество Р простых чисел 2, 3, 5, 7, 11, … Множество Z целых чисел: …, -2, -1, 0, 1, 2, …, множество R вещественных чисел и т. д. Множество, не содержащее элементов, называется пустым. Обозначение: Ж. Пустое множество является подмножеством любого множества. Мощность пустого множества равна нулю. Понятие пустого множества (подобно понятию «нуль») возникает из потребности, чтобы результат всякой операции над множествами был также множеством. 10]

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

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

Пусть даны два множества, А и В (Рисунок 1), тогда:

— ;

Рисунок 1. Множества и подмножества Подмножество — понятие части в теории множеств. Множество C является подмножеством множества B (Рисунок 1) в случае, если каждый элемент множества C является также и элементом множества B. Например, множество всех чётных чисел является подмножеством множества всех целых чисел. Если C является подмножеством B, то B называется надмножеством C.

Обычно множества обозначают прописными буквами латинского алфавита, а элементы множеств — строчными буквами.

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

Семейства множеств обычно обозначают прописными «рукописными» буквами латинского алфавита, чтобы отличить их от множеств, не содержащих множеств в качестве элементов. 10]

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

Сравнение множеств Множество A содержится во множестве B (множество B включает множество A), если каждый элемент A есть элемент B:

Если и, то A называется собственным подмножеством В. Заметим, что. По определению .

Два множества называются равными, если они являются подмножествами друг друга:

Теорема о сравнении множеств. Для любых множеств A и B существует одна и только одна из следующих возможностей:

|A| = |B|, |A| < |B|, |A| > |B|.

Рассмотрим основные операции над множествами:

1) объединение :

2) пересечение:

3) Разность:

4) симметрическая разность:

5) дополнение:

Операция дополнения подразумевает некоторый универсум (множество U, которое содержит A):

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

Объединением двух множеств, А и В (Рисунок 2) — называется третье множество, каждый элемент которого принадлежит хотя бы одному из множеств A и B

Рисунок 2. Объединение множеств Пересечением множеств А? В (Рисунок 3), является множество, состоящее из всех тех элементов, которые принадлежат одновременно всем данным множествам.

Рисунок 3. Пересечение множеств Разностью множеств A B = A — B (Рисунок 4) — называется такое множество, каждый элемент которого принадлежит множеству A, но не принадлежит множеству B.

Рисунок 4. Разность множеств Симметрическая разность (Рисунок 5) — теоретико-множественная операция, результатом которой является новое множество, включающее все элементы исходных множеств, не принадлежащие одновременно обоим исходным множествам. Другими словами, если есть два множества A и B, их симметрическая разность есть объединение элементов A, не входящих в B, с элементами B не входящими в A. На письме для обозначения симметрической разности множеств A и B используется обозначение

так же, реже используется обозначение: [10]

Рисунок 6. Симметрическая разность множеств Дополнение к множеству A называется множество всех элементов, не входящих в множество A (Рисунок 7)

Рисунок 7. Дополнение множества Таким образом, выяснили, что с множествами можно выполнять ряд операций: сравнение, объединение, пересечение, разность, симметрическая разность и дополнение.

1.3 Мощность множества Понятие мощности множества возникает при сравнении множеств по числу элементов. Мощность множества, кардинальное число множества (лат. cardinalis < cardo — главное обстоятельство, стержень, сердцевина) — характеристика множеств (в том числе бесконечных), обобщающая понятие количества (числа) элементов конечного множества.

В основе этого понятия лежат естественные представления о сравнении множеств:

1. Любые два множества, между элементами которых может быть установлено взаимно-однозначное соответствие (биекция), содержат одинаковое количество элементов (имеют одинаковую мощность).

2. Обратно: множества, равные по мощности, должны допускать такое взаимно-однозначное соответствие.

3. Часть множества не превосходит полного множества по мощности (то есть по количеству элементов).

До построения теории мощности множеств, множества различались по признакам: пустое/непустое и конечное/бесконечное, также конечные множества различались по количеству элементов. Бесконечные же множества нельзя было сравнить. 19]

Мощность множеств позволяет сравнивать бесконечные множества. Например, счётные множества являются самыми «маленькими» бесконечными множествами.

Мощность множества обозначается через. Сам Кантор использовал обозначение. Иногда встречаются обозначения и card (A). [2]

· Мощность множества натуральных чисел обозначается символом («алеф-нуль»). Множество называется бесконечным, если его мощность (не меньше мощности множества натуральных чисел), таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются (где индекс пробегает все порядковые числа). Среди кардинальных чисел нет наибольшего: для любого множества кардинальных чисел существует кардинальное число, большее всех элементов этого множества.

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

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

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

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

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

· Ситуация, в которой и не равномощны и ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора).

· Ситуация, в которой и, невозможна по теореме Кантора — Бернштейна.

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

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

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

ch: set of char;

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

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

type

t_ch = set of char;

var

ch1, ch2: t_ch;

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

type

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

var

work_days: set of week_days;

lett: set of 'A'.'Z';

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

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

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

type

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

var

work_days: set of week_days;

lett: set of 'A'.'Z';

begin

work_days := [Mon, Wed, Thu];

lett := ['C', 'E'.'M', 'Z']

end.

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

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

work_days := [ ];

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

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

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

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

ch1 := 'A';

ch2 := 'K';

chs := [ch1, ch2, 'M'];

В результате получится множество ['A', 'K', 'M'].

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

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

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

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

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

Type symbol= set of char;

Var small, capital, latin: symbol;

…

small:= [`a'. `z'];

capital:= [`A'. `Z'];

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

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

small:= small + [`a'] +[`b'];

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

Пример исключения множественных типов Паскаля:

letter:= [`a'. `z']; {множества букв латинского алфавита}

glasn:= [`a', `e', `o', `u', `i', `y']; {множества гласных букв}

soglasn:= letter-glasn; {образовано множества согласных букв путем исключения из множества всех букв множества гласных букв}

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

Пример пересечения множественных типов

Type chisla= set of byte;

Var z, x, y: chisla;

…

x:= [0.150];

y:= [100.255];

z:= x*y {получено множества чисел из диапазона 100.150 в результате пересечения двух множеств}

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

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

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

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

letter >= glasn; soglan <= letter;

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

И ЛИТЕРАТУРЫ

1. Болибрух А. А., Проблемы Гильберта (100 лет спустя), Глава 2 Первая проблема Гильберта: континуум-гипотеза, Библиотека «Математическое просвещение», Выпуск 2

2. Варпаховский Ф. Л., Солодовников А. С. Алгебра. Элементы теории множеств. Линейные уравнения и неравенства. Матрицы и определители. -М.: Просвещение, 1974, — 160 с.

3. Жолков С. Ю. Математика и информатика для гуманитариев: Учебник. — М.: Гардарики, 2002. — 531 с.

4. Завало С. Т., Костарчук В. Н., Хацет Б. И. Алгебра и теория чисел. Часть I — Киев: Вища школа, 1977. — 398 с.

5. Куликов Л. А. Алгебра и теория чисел. — М.: Высшая школа, 1979. — 560с.

6. Курант Р., Роббинс Г., Что такое математика? Глава II, § 4.

7. Куратовский К., Мостовский А. Теория множеств / Перевод с английского М. И. кратко под редакцией А. Д. Тайманова. — М.: Мир, 1970. — 416 с.

8. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. — М.: Наука, 1975. — 240 с.

9. Ляпин Е. С., Евсеев А. Е. Алгебра и теория чисел. Часть I. — М.: Просвещение, 1974. -383 с.

10. Новиков Ф. А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения. — СПб.: Питер, 2013. — 432 с.

11. Оре, Остин. Приглашение в теорию чисел. — М.: Наука, 1980. — 127 с.

12. Прахар К. Распределение простых чисел. — М.: Мир, 1967. — 511 с.

13. Солодовников А. С. Системы линейных неравенств. — М: Наука, 1978.

14. Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. — М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. — 280 с.

15. Фаддеев Д. К. Лекции по алгебре. — М.: Наука, 1984. -416 с.

16. Факультативный курс по математике. 7−9 / Сост. И. Л. Никольская. — М.: Просвещение, 1991. — С. 109−110. — 383 с.

17. Френкель А., Бар-Хиллел И. Основания теории множеств / Перевод с английского Гастева Ю. А. под редакцией Есенина-Вольпина А. С. — М.: Мир, 1966. — 556 с.

18. Шахмейстер А. Х. Множества. Функции. Последовательности. Прогрессии. — 2-е изд., испр. и доп. — М.: Издательство МЦНМО: СПб.: «Петроглиф»: «Виктория плюс», 2008. — 296 с.

19. Чечулин В. Л., Теория множеств с самопринадлежностью (основания и некоторые приложения), Издательство Пермского государственного университета, Пермь, 2010 — 100 с.

20. Шипачёв В. С. Высшая математика. Учеб. Для вузов. — 4-е изд., стер. — М.: Высшая школа. 1998. — 479 с.

21. Электронное ученое пособие по языку программирования Turbo Pascal. URL: http://smakcat.narod.ru/4/4−2.html (дата обращения:20.05.2015) Загл. с экрана. Яз.рус.

22. URL: http://kpolyakov.spb.ru/school/ege.htm (дата обращения: 01.06.2015) Загл. с экрана. Яз. рус

23. URL: http://olymp.ifmo.ru/shared/files/201 105/66₅₈₉.pdf (дата обращения: 01.06.2015) Загл. с экрана. Яз.рус.

ПРИЛОЖЕНИЕ Задача № 1

В олимпиаде по математике для абитуриентов приняло участие 40 учащихся, им было предложено решить одну задачу по алгебре, одну по геометрии и одну по тригонометрии. По алгебре решили задачу 20 человек, по геометрии — 18 человек, по тригонометрии — 18 человек.

По алгебре и геометрии решили 7 человек, по алгебре и тригонометрии — 9 человек. Ни одной задачи не решили 3 человека.

1. Сколько учащихся решили все задачи?

2. Сколько учащихся решили только две задачи?

3. Сколько учащихся решили только одну задачу?

Решение Запишем коротко условие и покажем решение:

· m (Е) = 40

· m (А) = 20

· m (В) = 18

· m © = 18

· m (А?В) = 7

· m (А?С) = 8

· m (В?С) = 9

m (А U В U С) = 3 => m (А U В U С) = 40 — 3 = 37

Обозначим разбиение универсального множества Е множествами А, В, С (Рисунок 8).

Рисунок.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 — число учеников решивших только одну задачу.

Ответ:

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

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

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) + m (К3) + m (К7) = 13+11=24

· 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 — все три дисциплины.

Сколько студентов выбрали по крайней мере одну дополнительную дисциплину? Сколько из них предпочли только дисциплину «Информационные технологии в рекламе»?

Решение.

Пусть A — множество студентов, выбравших дисциплину «Информационные технологии моделирования интерьера»,

B — 21 «Информационные технологии в рекламе»,

C — «Информационные технологии моделирования ландшафта».

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

Из диаграммы (Рисунок 9) видно, что на теоретикомножественном языке формулировка первого вопроса — «Чему равна мощность множества A? B? C?», а второго — «Какова мощность множества B [(A? B)? (B? C)]?».

На основании формулы включений и исключений, имеем:

A? B? C = A + B + C? A? B? B? C? A? C + A? B? C = 30 + 35 + 20? 15? 10 — 7 + 3 = 56.

Получаем:

B = [(A? B) ?(B ?C] B? (A? B)?(B ?C) = B? [ A? B + B? C? A? B? C ] = 35 — (15 + 7 — 3) = 16.

Ответ:

56 студентов выбрали по крайней мере одну дополнительную дисциплину и 16 — только дисциплину «Информационные технологии в рекламе».

Задача № 5

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

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

Решение (способ 1, круги Эйлера):

1) обозначим области «мезозой», «кроманьонец» и «неандерталец» буквами М, К и Н; пронумеруем подобласти, получившиеся в результате пересечений кругов (см. рисунок справа)

2) через N_i обозначим количество сайтов в области с номером i

3) нас интересует результат запроса кроманьонец & (мезозой | неандерталец) то есть N₂ + N₅ + N₆ (зеленая область на рисунке)

4) из первых двух запросов следует, что

N₁ + N₂ + N₄ + N₅ = 50 (мезозой)

N₂ + N₃ + N₅ + N₆ = 60 (кроманьонец)

5)

6) складывая левые и правые части уравнений, получаем

(1) N₁ + 2· N₂ + N₃ + N₄ + 2· N₅ + N₆ = 110

7) в то же время из запроса 4 получаем

(2) N₁ + N₂ + N₃ + N₄ + N₅ + N₆ = 80 (мезозой | кроманьонец)

8) вычитая из уравнения (1) уравнение (2), отдельно левые и правые части, получаем

N₂ + N₅ = 30 (мезозой & кроманьонец) вспомним, что наша цель — определить N₂ + N₅ + N₆, поэтому остается найти N₆

9) из запросов 1 и 3 следует, что

N₁ + N₂ + N₄ + N₅ = 50 (мезозой)

N₄ + N₅ + N₆ + N₇ = 70 (неандерталец)

10) складывая левые и правые части уравнений, получаем

(3) N₁ + N₂ + 2· N₄ + 2· N₅ + N₆ + N₇ = 120

11) в то же время из запроса 5 получаем

(4) N₁ + N₂ + N₄ + N₅ + N₆ + N₇ = 100 (мезозой | неандерталец)

12) вычитая из уравнения (3) уравнение (4), отдельно левые и правые части, получаем

(5) N₄ + N₅ = 20 (мезозой & неандерталец)

13) теперь проанализируем запрос 6:

неандерталец & (мезозой | кроманьонец)

(6) N₄ + N₅ + N₆ = 20

14) вычитая из уравнения (6) уравнение (5) получаем N₆ = 0, поэтому

N₂ + N₅ + N₆ = N₂ + N₅ = 30

15) таким образом, ответ — 30.

Решение (способ 2, М. С. Коротков, г. Челябинск, Лицей № 102):

1) пп. 1−3 такие же, как в первом способе;

2) из запросов 1 и 6 следует, что

(1) N₄ + N₅ + N₆ + N₇ = 70 (неандерталец)

(2) N₄ + N₅ + N₆ = 20 неандерталец & (мезозой | кроманьонец)

3) вычитая (2) из (1), сразу получаем, что N₇ = 50

4) из запросов 5 и 4 следует, что

(3) N₁ + N₂ + N₄ + N₅ + N₆ + N₇ = 100 (мезозой | неандерталец)

(4) N₁ + N₂ + N₃ + N₄ + N₅ + N₆ = 80 (мезозой | кроманьонец)

5) вычитая (4) из (3), сразу получаем, что N₇ — N₃ = 20

6) в п. 3 мы уже определили, что N₇ = 50, поэтому 50 — N₃ = 20, откуда N₃ = 30

7) из запроса 2 получаем

N₂ + N₃ + N₅ + N₆ = 60 (кроманьонец) поэтому размер интересующей нас области равен

N₂ + N₅ + N₆ = 60 — N₃ = 60 — 30 = 30

8) таким образом, ответ — 30.

Решение (способ 3, круги Эйлера, И.Б. Курбанова):

1) обозначим: М — мезозой, К — кроманьонец, Н — неандерталец.

2) нас интересует результат запроса (см. диаграмму Эйлера)

K & (M | Н)

3) т.к. по условию М = 50, К = 60, а объединение этих множеств М | К = 80, можно сделать вывод, что область пересечения

M & K = 50 + 60 — 80 = 30;

4) т.к. по условию М = 50, Н = 70, а объединение этих множеств М | Н = 100, можно сделать вывод, что область пересечения

M & Н = 50 + 70 — 100 = 20;

5) заметим, что M & Н = 20 и Н & (М | К) = 20, следовательно множества Н и К не пересекаются (К & Н = 0);

6) перерисуем диаграмму Эйлера так, чтобы множества К и Н не пересекались (см. рисунок справа); из новой схемы видно, что К & (М | Н) = (К & М) | (К & Н) = К & М = 30

7) ответ: 30 [22]

Задача № 6

В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» — &.

1) принтеры & сканеры & продажа

2) принтеры & сканеры

3) принтеры | сканеры

4) принтеры | сканеры | продажа Решение (вариант 1, рассуждение с использованием свойств операций «И» и «ИЛИ»):

1) меньше всего результатов выдаст запрос с наибольшими ограничениями — первый (нужны одновременно принтеры, сканеры и продажа)

2) на втором месте — второй запрос (одновременно принтеры и сканеры)

3) далее — третий запрос (принтеры или сканеры)

4) четвертый запрос дает наибольшее количество результатов (принтеры или сканеры или продажа)

5) таким образом, верный ответ — 1234 .

Решение (вариант 2, через таблицы истинности):

1) каждое из условий можно рассматривать как сложное высказывание

2) обозначим отдельные простые высказывания буквами:

A: принтеры (на странице есть слово «принтеры»)

B: сканеры

C: продажа

3) запишем все выражения-запросы через логические операции

, ,

4) здесь присутствуют три переменные, А, B и C (хотя второе и третье выражения от С не зависят!), поэтому для составления таблицы истинности нужно рассмотреть 8 = 2³ всевозможных комбинаций этих логических значений

5) выражение равно 1 (истинно) только при, в остальных случаях — равно 0 (ложно)

6) выражение равно 1 только при, в остальных случаях — равно 0

7) выражение равно 0 только при, в остальных случаях — равно 1

8) выражение равно 0 только при, в остальных случаях — 1

9) запишем результаты пп. 5−8 в виде таблицы истинности

10) по таблице видим, что наименьшая «область действия» у первого выражения, поисковый сервер выдаст наименьшее число запросов

11) область, где, включает в себя Каждая следующая область в полученном решении должна полностью включать предыдущую. Если это не так, тогда или вы ошиблись при построении таблицы истинности, или (не дай Бог!) в условии есть ошибка. всю область, где и еще один вариант, поэтому «поисковик» выдаст больше запросов, чем для первого случая

12) аналогично делаем вывод, что область включает всю область и расширяет ее, а область — это расширение области

13) таким образом, верный ответ — 1234 .

Решение (вариант 3, через диаграммы):

1) запишем все ответы через логические операции

, ,

2) покажем области, определяемые этими выражениями, на диаграмме с тремя областями

3) сравнивая диаграммы, находим последовательность областей в порядке увеличения: (1,2,3,4), причем каждая следующая область в этом ряду охватывает целиком предыдущую (как и предполагается в задании, это важно!)

4) таким образом, верный ответ — 1234. [22]

Задача № 7

Даны множества U={1, 2, …, 20}, A={1, 3, 8, 15}, B={8, 15, 3, 2}.

а) Найти их объединение.

Решение:

Запишем сначала все элементы множества А, а затем — те элементы множества В, которые не содержатся во множестве А:

AUB={1, 3, 8, 15, 2}.

б) Найти их пересечение.

Решение:

Берем каждый элемент множества, А и определяем, содержится ли он во множестве В, и если такой элемент есть, то записываем его:

А?В={3, 8, 15}.

в) Найти разность, А и В.

Решение:

Находим элементы, которые содержатся в обоих множествах, отсеиваем их из множества, А и записываем оставшиеся элементы:

АВ={1}

г) Найти разность В и А.

Действуем аналогично пункту в:

BA={2}

д) Найти дополнение множества, А и В.

Решение:

Записываем все элементы универсального множества, кроме тех, что содержатся во множестве, А (В):

А={2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20}

B={1, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20}

Задача № 8

В базе данных хранятся записи о возрасте (в годах) и населении (в тыс. чел.) некоторых городов. В базе нет городов с одинаковым возрастом и нет городов с одинаковым населением. Известно количество записей, получаемых в ответ на ряд запросов к этой базе:

1. Возраст <= 500 and Население <= 5000 — 300 записей

2. Возраст >= 300 and Возраст <= 500 and Население <= 5000 — 130 записей

3. Возраст <= 500 and Население >= 1500 and Население <= 5000 — 155 записей

4. Возраст >= 300 and Возраст <=500 and Население >=1500 and Население <= 5000 — 45 записей Укажите запрос к этой базе, результатом выполнения которого будет 60 записей:

1) Возраст < 300 and Население >=1500 and Население <= 5000

2) Возраст >= 300 and Возраст <=500 and Население <1500

3) Возраст < 300 and Население <1500

4) Возраст < 300 and Население <= 5000

5) Возраст <= 500 and Население < 1500

6) Такого запроса нет среди перечисленных [23]

Ответ: 3