Задачник по теории множеств

Задачи по теории множеств, математической логике и теории алгоритмов, Лавров И.А., Максимова Л.Л., 2004.

В книге в форме задан систематически изложены основы теории множеств. Математической логики и теории алгоритмов. Книга предназначена для активного изучения математической логики и смежных с ней наук.
Состоит из трех частей: «Теория множеств». «Математическая логика» и «Теория алгоритмов». Задачи снабжены указаниями и ответами. Вce необходимые определения сформулированы в кратких теоретических введениях к каждому параграфу.
Сборник может быть использовал как учебное пособие для математических факультетов университетов, педагогических институтов, а также в технических вузах при изучении кибернетики и информатики. Для математиков — алгебраистов. логиков и кибернетиков.

Задачи.

Доказать, что всякое множество есть:
(а) объединение всех своих подмножеств;
(б) объединение всех своих конечных подмножеств;
(а) объединение всех своих одноэлементных подмножеств.

Пусть А и В — конечные множества, состоящие из т и n элементов соответственно.
(а) Сколько существует бинарных отношений между элементами множеств А и В?
(б) Сколько имеется функций из А в 5?
(в) Сколько имеется l — l-функций из А в В?
(г) При каких т и n существует взаимно однозначное соответствие между А и В?

СОДЕРЖАНИЕ.

Предисловие к четвертому изданию
Предисловие к первому изданию
Часть I. Теория множеств
§ 1. Операции над множествами
§ 2. Отношения и функции
§ 3. Специальные бинарные отношения
§ 4. Кардинальные числа
§ 5. Ординальные числа
§ 6. Действия над кардинальными числами
Часть II. Математическая логика
§ 1. Алгебра высказываний
§ 2. Функции алгебры логики
§ 3. Исчисления высказываний
§ 4. Язык логики предикатов
§ 5. Выполнимость формул логики предикатов
§ 6. Исчисления предикатов
§ 7. Аксиоматические теории
§ 8 Фильтрованные произведения
§ 9. Аксиоматизируемые классы
Часть III. Теория алгоритмов
§ 1. Частично рекурсивные функции
§ 2. Машины Тьюринга
§ 3. Рекурсивные и рекурсивно перечислимые множества
§ 4. Нумерации Клини и Поста
Ответы, решения, указания
Список литературы
Предметный указатель

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Задачи по теории множеств, математической логике и теории алгоритмов, Лавров И.А., Максимова Л.Л., 2004 — fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России. Купить эту книгу

Разделы: Математика

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

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

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

Множества обозначим А, В, С…, а элементы множеств а, b, с…, используя латинский алфавит.

Можно сделать такую запись определения множества:

, где

“” – принадлежит;
“=>“ – следовательно;
“ø” – пустое множество, т.е. не содержащее ни одного элемента.

Два множества будем называть равными, если они состоят из одних и тех же элементов

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

Графически это выглядит так (рис.1):

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

Рассмотрим операции над множествами и их графическую иллюстрацию (рис.2).

Объединением множеств А и В называется множество С, образованное всеми элементами, которые принадлежат хотя бы одному из множеств А или В. Слова “или ” ключевое в понимании элементов входящих в объединение множеств.

Это определение можно записать с помощью обозначений:

А υ В, где

где “ υ ” – знак объединения,

“ / ” – заменяет слова ”таких что“

Пресечение двух множеств А и В называется множество С, образованное всеми элементами, которые принадлежат и множеству А, и множеству В. Здесь уже ключевое слово “и”. Запишем коротко:

А ∩ В = С, где

“∩“ – знак пересечения. (рис.3)

Обозначим буквой Е основное или универсальное множество, где A С Е (“”- любо число), т.е. А Е = Е; АЕ =А

Множество всех элементов универсального множества Е, не принадлежащих множеству А называется дополнением множества А до Е и обозначается Ā Е или Ā (рис.4)

Примерами для понимания этих понятий являются свойства:

А Ā=Е Ø = Е Е Ā=Ā

Свойства дополнения имеют свойства двойственности:

АВ = А∩В

АВ = АUВ

Введем еще одно понятие – это мощность множества.

Для конечного множества А через m (A) обозначим число элементов в множестве А.

Из определение следуют свойства:

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

m (AB) =m (A) + m (В) – m (А∩В)

m (A∩B) = m (A) + m (В) – m (АВ)

m (ABC) = m (A) + m (В) + m (С)– m (А∩В) — m (А∩С) – m (В∩С) – m (А∩В∩С).

А теперь рассмотрим ряд задач, которые удобно решать, используя графическую иллюстрацию.

Задача №1

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

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

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

Задача № 2

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

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

Задача № 3

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

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

Решение задачи № 1

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

m (Е) = 40
m (А) = 20
m (В) = 18
m (С) = 18
m (А∩В) = 7
m (А∩С) = 8
m (В∩С) = 9

m (АВС) = 3 => m (АВС) = 40 – 3 = 37

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

К 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

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

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 учеников.

Литература: А.Х. Шахмейстер «Множества. Функции. Последовательности»

Лавров И.А., Максимова Л.Л.

В книге систематически изложены основы теории множеств, математической логики и теории алгоритмов в форме задач. Книга предназначена для активного изучения математической логики и смежных с ней наук. Состоит из трех частей: "Теория множеств", "Математическая логика" и "Теория алгоритмов". Задачи снабжены указаниями и ответами. Все необходимые определения сформулированы в кратких теоретических введениях к каждому параграфу. Сборник может быть использован как учебное пособие для математических факультетов университетов, педагогических институтов, а также в технических ВУЗах при изучении кибернетики и информатики. Для математиков-алгебраистов, логиков и кибернетиков.

Использование материалов ЭБ РФФИ

Воспроизведение материалов из ЭБ в любой форме требует письменного разрешения РФФИ. Пользователи вправе в индивидуальном порядке использовать материалы, находящиеся на сайте РФФИ, для некоммерческого использования.

Пользователь обязуется не осуществлять (и не пытаться получить) доступ к каким-либо материалам ЭБ иным способом, кроме как через интерфейс Сайта.

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

Другие произведения в разделе:

№	Название	Автор	Рубрика	Номер гранта
1	2-регулярные решения нелинейных задач. Теория и численные методы.	Измаилов А.Ф., Третьяков А.А.	математика, механика, информатика	99-01-14129
2	АМS-Tex. Краткий курс математического набора	Клименко С.В. и др.	математика, механика, информатика	00-01-14095
3	Абелевы многообразия, тэта-функции и преобразование Фурье	Полищук А.Е.	математика, механика, информатика	04-01-14115
4	Автоволновые процессы в нелинейных средах с диффузией	Мищенко Е.Ф. и др.	математика, механика, информатика	09-01-07125
5	Автоэлектронные катоды и пушки: Монография	Бугаев А.С. и др.	математика, механика, информатика	17-11-00063

Книги, изданные при поддержке РФФИ
Вестник РФФИ, издание на русском языке
Вестник РФФИ, издание на английском языке
Вестник РФФИ. Гуманитарные и общественные науки
Научно-популярные статьи и фотоматериалы
Аннотированные отчеты по проектам РФФИ

Россия, 119334, Москва, Ленинский проспект, 32а, 20-21 этаж
Телефон для справок: +7 (499) 941-01-15