- •1. Предикаты и кванторы
- •Определение
- •Примеры
- •Операции над предикатами
- •Логические операции
- •Кванторные операции
- •Примеры
- •Введение в понятие
- •Кванторы в математической логике
- •Свободные и связанные переменные
- •Операции над кванторами
- •2. Комбинаторные правила. Правило птичьих гнёзд. Правило сложения
- •Тема 2. Элементы теории множеств и комбинаторика
- •3. Общие правила комбинаторики
- •Пример 1
- •Пример 2
- •3. Правило умножения
- •4. Размещение с повторениями и без повторений
- •Количество размещений
- •Размещение с повторениями
- •Размещения без повторений
- •Где все это применяется, уже очевидно. Осталось только привести несколько хитрых примеров:
- •5. Сочетания без повторений
- •6. Сочетания с повторениями. Разбитие множеств на части
- •Определение
- •Разбиения конечных множеств
- •Примеры
- •7. Отношения. Представления и свойства отношений
- •8. Отношения эквивалентности. Связь отношений эквивалентности и разбиений множеств
- •Связанные определения
- •Примеры отношений эквивалентности
- •Факторизация отображений
- •9. Отношение эквивалентности. Связь отношений эквивалентности и разбиений множеств Отношение частичного порядка
- •10. Отношения линейного порядка Отношение линейного порядка
- •Упорядоченные множества
- •11. Логические функции. Задание и элементарные функции
- •Основные сведения
- •Нульарные функции
- •Унарные функции
- •Бинарные функции
- •Тернарные функции
- •[Править]Полные системы булевых функций Суперпозиция и замкнутые классы функций
- •Тождественность и двойственность
- •Полнота системы, критерий Поста
- •Представление булевых функций
- •Дизъюнктивная нормальная форма (днф)
- •Конъюнктивная нормальная форма (кнф)
- •Элементарные функции по Лиувиллю
- •Дифференцирование элементарных функций
- •Интегрирование элементарных функций
- •12. Дизъюнктивные нормальные формы
- •Примеры и контрпримеры
- •Построение днф Алгоритм построения днф
- •Пример построения днф
- •Переход от днф к сднф
- •13. Минимизация днф
- •14. Монотонные функции
- •Определения
- •Другая терминология
- •Свойства монотонных функций
- •Условия монотонности функции
- •15. Графы. Представления графов. Пути в графах
- •Путь и цикл в графе. Эйлеровые линии
Кванторные операции
Квантор (все-)общности
Квантор существования
Квантор существования по переменной x1
Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего упоминают:
Квантор всеобщности (обозначение: , читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).
Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).
В математической логике приписывание квантора к формуле называется связыванием или квантификацией.
В многозначных логиках также вводятся и другие кванторы, например, квантор плюральности (квантор Решера) (обозначается перевёрнутой M, читается означает «для большинства …»).
Примеры
Обозначим P(x) предикат «x делится на 5». Используя квантор общности, можно формально записать следующие высказывания (конечно, ложные):
любое натуральное число кратно 5;
каждое натуральное число кратно 5;
все натуральные числа кратны 5;
следующим образом:
.
Следующие (уже истинные) высказывания используют квантор существования:
существуют натуральные числа, кратные 5;
найдётся натуральное число, кратное 5;
хотя бы одно натуральное число кратно 5.
Их формальная запись:
.
Введение в понятие
Пусть на множестве Х простых чисел задан предикат Р(х): «Простое число х — нечётно». Подставим перед этим предикатом слово «любое». Получим ложное высказывание «любое простое число х нечётно» (это высказывание ложно, так как 2 — простое чётное число).
Подставив перед данным предикатом Р(х) слово «существует», получим истинное выказывание «Существует простое число х, являющееся нечётным» (например, х=3).
Таким образом, превратить предикат в высказывание можно, поставив перед предикатом слова: «все», «существует», и др., называемые в логике кванторами.
Кванторы в математической логике
Высказывание означает, что область значений переменной x включена в область истинности предиката P(x).
(«При всех значениях (x) утверждение верно»).
Высказывание означает, что область истинности предиката P(x) непуста.
(«Существует (x) при котором утверждение верно»).
Свободные и связанные переменные
Множество свободных переменных* формулы F определяется рекурсивно, следующим образом:
Свободные переменные.
Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,
свободные переменные формулы F являются свободными переменными формулы ¬F,
переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),
все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.
Замкнутая формула.
Формула без свободных переменных называется замкнутой формулой, или предложением.
Связанная переменная.
Переменная v связана в формуле F, если F содержит вхождение Kv, где K — квантор.
Связанное переименование, свободное переименование
Операции над кванторами
Правило отрицания кванторов — применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид: