- •1. Элементы теории множеств
- •1.1 Множества. Основные понятия
- •1.2. Способы задания множеств
- •1.3. Операции над множествами. Диаграммы Венна
- •1.4. Свойства операций над множествами
- •1.5. Прямое (декартово) произведение множеств
- •1.6 Разбиения и покрытия
- •1.7. Замечание о мощности некоторых множеств
- •1.8 Представление множеств в эвм
- •1.9. Отношения
- •1.9.1.Определения
- •1.9.2 Бинарные отношения
- •1.9.3. Способы задания бинарных отношений
- •1.9.4 Свойства бинарных отношений
- •1.9.5. Отношение эквивалентности
- •1.9.5. Отношение порядка
- •1.9.6.1. Минимальные и максимальные элементы множества
- •1.9.6.2. Диаграммы Хассе
- •1.9.6.3. Принцип двойственности
- •1.9.7. Представление отношений в эвм
- •1.10. Соответствия. Функции. Операции. Отображения
- •1.10.1. Соответствия и их свойства
- •1.10.2 Функции и отображения
- •1.10.3. Инъекция, сюръекция и биекция
- •1.10.4. Композиция и суперпозиция функций. Способы задания функций
- •1.10.5. Представление функций в эвм
- •1.10.6. Операции
- •1.10.6.1. Способы задания операций
- •1.11. Алгебраические структуры
- •1.11.2. Замыкание и подалгебры
- •1.11.3. Гомоморфизм и изоморфизм
- •1.11.4. Алгебры с одной бинарной операцией
- •1.11.5. Алгебры с двумя бинарными операциями
- •1.11.6.Решетки
- •1.11.7. Булевы алгебры
- •2. Элементы математической логики и булевы функции
- •2.1. Операции над высказываниями
- •2.2. Логические операции (логические связки)
- •2.3. Элементарные булевы функции
- •2.3.1. Функции алгебры логики
- •2.3.2. Равносильность функций. Существенные и несущественные переменные
- •2.3.3. Реализация функций формулами. Суперпозиция функций
- •2.3.4. Подстановки и замены
- •2.3.5. Принцип двойственности
- •2.3.6. Нормальные формы в логике высказываний
- •2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)
- •2.3.6.2. Совершенная дизъюнктивная нормальная форма
- •2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
- •2.3.8. Монотонные функции алгебры логики
- •2.3.9. Функционально замкнутые классы
- •2.4. Полнота системы булевых функций. Теорема
- •2.5. Элементы логике предикатов
- •2.5.1. Определение предиката
- •2.5.2. Кванторы. Формулы логики предикатов
- •2.5.3. Равносильность формул
- •2.5.4. Предикаты на конечных областях. Логика одноместных предикатов
- •2.6. Операции над предикатами и кванторами
- •2.7. Построение доказательств в логике предикатов
- •1.6.2. Разбор решений задач по логике предикатов
- •1. Элементы теории множеств 3
- •1.1 Множества. Основные понятия 3
- •2.6. Операции над предикатами и кванторами 137
- •394026 Воронеж, Московский просп., 14
2. Элементы математической логики и булевы функции
В данном разделе демонстрируется эффективность и действенность алгебраических методов, рассмотренных ранее. Помимо основных фактов из теории булевых функций здесь затрагиваются весьма общие понятия, такие как реализация функции формулами, нормальные формы, двойственность, полнота. Эти понятия трудно описать исчерпывающим образом при выбранном элементарном уровне изложения, но знакомство с ними необходимо. Поэтому рассматриваются частные случаи этих понятий на простейшем примере булевых функций. Этот материал является подготовительным для изучения довольно абстрактного и формального материала в дальнейшем. Сначала вспомним операции над высказываниями.
2.1. Операции над высказываниями
Математическая логика изучает логические операции над высказываниями. Она изучает языки, основная цель которых – обеспечить систему формальных обозначений для рассуждений, встречающихся не только в математике, но и в повседневной жизни.
Простейшая математическая логика – логика высказываний. Здесь нас интересуют утвердительные предложения, которые могут оказаться истинными или ложными, но не тем и другим вместе.
Каждое такое утвердительное предложение называется высказыванием.
Таким образом, высказывание есть утвердительное предложение, которое истинно, либо ложно, но не то и другое вместе. Обозначается буквами А, В, С… Истинность высказываний обозначается 1, ложность – 0.
А,В,С – атомарные формулы, или атомы. Сложное высказывание – некоторая конструкция, построенная по определенным правилам из простых высказываний с помощью логических связок.
Примеры:
1. «На улице светит солнце, и в классе идут занятия».
2. «На улице не светит солнце».
3. «На улице светит солнце, однако в классе идут занятия».
4. «В классе идут занятия, а на улице светит солнце».
5. «На улице светит солнце, или в классе идут занятия».
6. «Или на улице светит солнце, или в классе идут занятия»
7. «Если на улице светит солнце, то в классе идут занятия».
8. «Если в классе идут занятия, то на улице светит солнце.»
9. «На улице светит солнце, или в классе идут занятия».
10. «На улице светит солнце тогда и только тогда, когда в классе идут занятия».
Существуют высказывания истинные (или, соответственно, логичные) во всех возможных ситуациях – абсолютно истинные (или абсолютно логичные). Такие высказывания называются логическими константами.
Истинность или ложность сложного высказывания зависит от двух факторов:
1. от истинности или ложности простых высказываний, входящих в сложное;
2. от логической операции, которая используется в данном высказывании.
2.2. Логические операции (логические связки)
Любая логическая операция определяется с помощью таблицы истинности. Таблица истинности связывает значение истинности результирующих сложных высказываний со значениями истинности предыдущих высказываний.
1.Инверсия, (отрицание не).
Обозначается: ¯, ¬: А – высказывание, Ā, ¬А – инверсия.
А |
Ā |
0 |
1 |
1 |
0 |
Эта операция одноместная, так как применяется к одному выражению.
Отрицание абсолютно истинного высказывания абсолютно ложно.
2. Конъюнкция (логическое умножение)
Обозначается: &,^,и, and.
А |
В |
АvВ |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
тогда, когда истинны оба высказывания А и В.
Высказывание А^В абсолютно истинно <=>, когда абсолютно истинны оба выражения А и В.
3. Дизъюнкция (логическое сложение)
Обозначается: v, +, or, или.
Здесь «или» используется в неальтернативном смысле: утверждается истинность по крайней мере одного из участвующих в нем простых высказываний.
Абсолютная истинность АvВ означает, что в каждой ситуации хотя бы одно из высказываний А и В истинно.
А |
В |
АΔВ |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Обозначение: w, , xor, АΔВ.
Здесь союз «или» имеет исключающее (альтернативное) значение.
5. Несовместность (штрих Шеффера) (и-не).
А |
В |
А\В |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
6. Эквивалентность (тогда и только тогда)
Обозначается:↔, ~.
А |
В |
А~В |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
7.Импликация (если…,то…)
Обозначается: →.
Сложное высказывание «если А, то В» записывается в виде A→В,
А |
В |
А→В |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
С точки зрения алгебры высказываний истинность импликации, в некоторой ситуации означает лишь, что если истинна посылка, то истинно заключение. В результате истинными могут оказаться импликации типа «Если в Воронеже идет дождь, то книга серого цвета». В силу интуитивного представления высказывание А→В абсолютно истинно тогда и только тогда, когда в каждой ситуации, в которой высказывание А истинно, истинно и В, т.е. не существует ситуации, когда А истинно, а В – ложно.