. . 92 9.3 Свободные и связанные вхождения и подстановки . <...> Отметим, что для основных числовых множеств приня8 ты такие стандартные имена: N - множество натуральных чисел, Z - множество целых чисел, Q - множество рациональных чисел, R - множество действительных чисел, C - множество комплексных чисел. <...> Конечно, это можно сказать более естественно: B - множество целых четных чисел. <...> Все знаки, кроме трех последних, связывают какие-то утверждения, обозначенные через A и B, и называются логическими связками. <...> Три последних знака обращаются к элементам множества и указывают «количество» элементов, имеющих некоторое свойство: все или хотя бы один – и называются кванторами (quantum - количество, сумма). <...> Для множеств это отношение включения напоминает отношение неравенства для чисел; во всяком случае, если конечное множество A является подмножеством конечного множества B, то количество элементов в A не больше числа элементов в B. <...> Симметрическая разность: A△B = (A∪B)\(A∩B) = ∈ B}; Например, объединением множествAиB называется множество всех элементов, принадлежащих A или B (возможно, обоим) и аналогично для оставшихся определений. <...> Отметим, что симметрическая разность выражается через ранее определённые операции и потому может считаться неосновной. <...> Для графической иллюстрации операций с множествами используются диаграммы Эйлера, в которых множества условно изображаются кругами или частями кругов, а результат операции выделяется штриховкой или цветом: На рисунке более темным цветом выделены результаты применения операций объединения - A∪B, пересечения - A∩B, разности A\B и симметрической разности A△B к множествам A и B. <...> Если A - конечное множество и |A| = k, - множество соответствующих векторов. <...> На его основе можно дать точные определения понятиям функции, частичного порядка, эквивалентности и другим. <...> Бинарным отношением (соответствием) G из A в B называется подмножество множества AЧB: G ⊆ AЧB. <...> Если F - биекция A на B , то F−1 - биекция B на A Простейшим <...>
Элементы_теории_множеств_и_математической_логики._Теория_и_задачи_учебное_пособие.pdf
Министерство образования и науки Российской Федерации
Ярославский государственный университет
им. П. Г. Демидова
Л. Ю. Белова, Ю. А. Белов
Элементы теории множеств
и математической логики
Теория и задачи
Учебное пособие
Рекомендовано
Научно-методическим советом университета для студентов,
обучающихся по направлениню Прикладная математика и информатика
Ярославль 2012
Стр.1
УДК 510.23:510.6(075.8)
ББК В12я73
Б43
Рекомендовано
Редакционно-издательским советом университета в качестве учебного
издания. План 2012 года
Рецензенты:
кандидат физико-математических наук, доцент Корнилов П. А.;
кафедра теории и методики преподавания информатики Ярославского
государственного педагогического университета им. К. Д. Ушинского,
Белова, Л. Ю. Элементы теории множеств и математической
логики. Теория и задачи: учебное пособие /Л.Ю. Белова,
Б43 Ю. А. Белов; Яросл. гос. ун-т им. П. Г. Демидова. – Ярославль: ЯрГУ,
2012. – 204 с.
ISBN 978-5-8397-0878-5
Пособие содержит материал по элементам теории множеств, исчислению высказываний,
исчислению предикатов, булевым функциям. Приведён ряд задач,
дополняющих основное содержание пособия.
Предназначено для студентов, обучающихся по направлению 010400.62 Прикладная
математика и информатика (дисциплина «Дискретная математика»,
цикл Б3), очной формы обучения.
ISBN 978-5-8397-0878-5
УДК 510.23:510.6(075.8)
ББК В12я73
- Ярославский государственный университет
им. П. Г. Демидова, 2012
c
Стр.2
Содержание
Введение
1 Понятие множества
6
8
1.1 Примеры множеств . . . . . . . . . . . . . . . 8
1.2 Обозначение и задание множеств . . . . . . . . . 8
1.3 Отношения между множествами и
операции над множествами . . . . . . . . . . . . 10
1.4 Свойства операций над множествами . . . . . . . 13
2 Отношения и функции
15
2.1 Декартово произведение множеств . . . . . . . . 15
2.2 Отношения . . . . . . . . . . . . . . . . . . . 17
2.3 Произведение отношений . . . . . . . . . . 18
2.4 Функции . . . . . . . . . . . . . . . . . . . . 20
2.5 Специальные свойства отношений на множестве . . 22
3 Эквивалентность множеств
29
3.1 Конечные множества . . . . . . . . . . . . . . . 29
3.2 Счетные множества . . . . . . . . . . . . . . . 33
4 Сравнение мощностей
5 Шкала мощностей
36
4.1 Несчетные множества . . . . . . . . . . . . . . 36
4.2 Неравенство мощностей . . . . . . . . . . . . . 41
44
5.1 Теорема о шкале мощностей . . . . . . . . . . . 44
5.2 Замечания . . . . . . . . . . . . . . . . . . . 47
Задачи и упражнения . . . . . . . . . . . . 51
6 Элементы математической логики
3
59
Стр.3
6.1 Высказывания . . . . . . . . . . . . . . . . . 59
6.2 Формальные теории . . . . . . . . . . . . . . . 61
6.3 Исчисление высказываний . . . . . . . . . . . . 66
6.4 Примеры формальных выводов . . . . . . . . . 69
7 Выводимость
8 Доказуемость, истинность, полнота
72
7.1 Теорема о дедукции . . . . . . . . . . . . . . . 72
7.2 Теорема о десяти выводимых правилах . . . . . . 75
78
8.1 Булевы функции . . . . . . . . . . . . . . . . 78
8.2 Непротиворечивость исчисления высказываний . . 80
8.3 Выводимость и истинность . . . . . . . . . 82
8.4 Полнота исчисления высказываний . . . . . . . 86
8.5 Замечания . . . . . . . . . . . . . . . . . . . 88
9 Логика предикатов
90
9.1 Предикаты . . . . . . . . . . . . . . . . . . . 90
9.2 Алфавит и формулы исчисления предикатов . . . 92
9.3 Свободные и связанные вхождения и подстановки . 94
9.4 Аксиомы и правила вывода . . . . . . . . . . . . 95
9.5 Примеры простейших доказательств . . . . . . . 97
10 Интерпретация формул логики предикатов 99
10.1 Определения . . . . . . . . . . . . . . . . . . . 99
10.2 Примеры задания интерпретации . . . . . . . . . 103
10.3 Логическое следование и равносильность . . . . . 110
11 Непротиворечивость, неразрешимость, полнота
4
117
11.1
Непротиворечивость исчисления предикатов . . . 117
11.2 Неразрешимость и полнота ИП . . . . . . . . . 122
Стр.4
11.3 Пример необщезначимой
k-общезначимой формулы . . . . . . . . . . . . 124
Задачи и упражнения . . . . . . . . . . . . 128
12 Булевы функции
135
12.1 Элементарные булевы функции,
равенство функций . . . . . . . . . . . . . . . . 135
12.2 Свойства основных операций
для булевых функций . . . . . . . . . . . . . . 140
12.3 Формулы. Принцип двойственности . . . . . . . 142
13 Полные системы функций
146
13.1 Теорема об СДНФ . . . . . . . . . . . . . . . . 146
13.2 Теоремы о полноте . . . . . . . . . . . . . . . 150
14 Критерий функциональной полноты 155
14.1 Замкнутость . . . . . . . . . . . . . . . . . . 155
14.2 Основные леммы . . . . . . . . . . . . . . . . 159
14.3 Теорема о функциональной полноте . . . . . . . 161
Задачи и упражнения . . . . . . . . . . . . 165
Решения, указания, ответы
169
Множества . . . . . . . . . . . . . . . . . . 169
Логика . . . . . . . . . . . . . . . . . . . . 183
Булевы функции . . . . . . . . . . . . . . . 192
Литература
202
5
Стр.5