1. Что такое предикат

Предикат — это выражение, которое становится высказыванием, если подставить конкретные значения переменных.
Он как функция: принимает аргументы и возвращает истину (1) или ложь (0).

Пример:

• \(P(x)\): «x — чётное число».
  Тогда \(P(2) = \text{истина}\), \(P(3) = \text{ложь}\).

2. Переменные и область определения

Переменная \(x\) — это элемент множества, по которому идёт рассуждение.
Множество, из которого берутся \(x\), называется областью определения (или универсумом).

Пример:
Если \(x\) — натуральные числа, то область определения \(D = \{1,2,3,\dots\}\).

3. Кванторы

Кванторы вводят обобщение или существование, обозначают о скольких объектах идёт речь.
Они говорят: высказывание относится не к одному элементу, а ко многим.

Квантор всеобщности — для всех элементов множества;
квантор существования — что есть хотя бы один элемент, для которого верно утверждение.

Вместе они позволяют описывать любое утверждение с переменными.

Квантор	Обозначение	Чтение	Пример	Перевод
Всеобщности	\(\forall x\)	“для всех x”	\(\forall x \, (x > 0)\)	“все x положительные”
Существования	\(\exists x\)	“существует хотя бы один x”	\(\exists x \, (x < 0)\)	“есть хотя бы одно отрицательное x”

4. Отрицание кванторов

Отрицание кванторов — частый источник ошибок.
Главное правило: при отрицании тип квантора меняется на противоположный, а предикат отрицается.

То есть: «не для всех» превращается в «существует хотя бы один, для кого неверно».

Формула	Эквивалент	Смысл
\(\neg (\forall x \, P(x))\)	\(\exists x \, \neg P(x)\)	Не для всех верно → есть хотя бы один, где неверно
\(\neg (\exists x \, P(x))\)	\(\forall x \, \neg P(x)\)	Не существует → для всех неверно

5. Вложенные кванторы

Порядок кванторов играет ключевую роль:
переставишь — поменяется смысл формулы.

Например,

• “каждый любит кого-то” ≠ “существует один, кого любят все”.

Такие различия — суть логики предикатов: она описывает отношения между множествами и объектами.

Формула	Смысл	Пример
\(\forall x \exists y \, P(x, y)\)	Для каждого x найдётся свой y	Каждый человек любит кого-то
\(\exists y \forall x \, P(x, y)\)	Есть одно y, которое подходит всем	Есть человек, которого любят все

6. Свободные и связанные переменные

• Свободная переменная — переменная вне квантора.
• Связанная переменная — переменная под квантором.

Пример:

Здесь \(x\) — связанная, \(y\) — свободная.

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

Только формулы, где нет свободных переменных, можно считать полноценными высказываниями.
Если в формуле осталась свободная переменная — это просто открытое утверждение, его нельзя оценить как «истину» или «ложь», пока не подставим значения.

7. Интерпретация и истинность формулы

Формула сама по себе — это шаблон.
Она становится высказыванием только при интерпретации, когда мы задаём контекст:

1. Область определения (например, числа);
2. Смысл предикатов (например, “\(x\) > \(y\)”);
3. Значения переменных.

Только тогда можно сказать, истинна ли формула.
Без интерпретации логика предикатов — просто набор символов.

Пример:

Если \(x, y\) — натуральные числа, то формула истинна (всегда можно взять \(y = x+1\)).

8. Формализация предложений

Здесь идёт перевод естественного языка в язык логики.

Это важно, чтобы учиться строго формулировать утверждения и понимать их структуру:
кто “все”, кто “существует”, где “если”, где “тогда”.

Одна и та же фраза по-разному формализуется в зависимости от смысла.

Фраза	Формула
Все люди смертны	\(\forall x (Человек(x) \to Смертен(x))\)
Существует человек, который любит всех	\(\exists x \forall y (Любит(x, y))\)
Каждый любит кого-то	\(\forall x \exists y (Любит(x, y))\)
Никто никого не любит	\(\forall x \forall y \, \neg Любит(x, y)\)

9. Правила отрицания (логические эквиваленты)

Эти законы позволяют переписывать формулы, сохраняя смысл, но меняя структуру.

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

Формула	Эквивалент
\(\neg (P \wedge Q)\)	\(\neg P \vee \neg Q\)
\(\neg (P \vee Q)\)	\(\neg P \wedge \neg Q\)
\(\neg (P \to Q)\)	\(P \wedge \neg Q\)
\(\neg (\forall x \, P(x))\)	\(\exists x \, \neg P(x)\)
\(\neg (\exists x \, P(x))\)	\(\forall x \, \neg P(x)\)

10. Логические связи и операции

Все сложные высказывания строятся из простых с помощью этих пяти операций.

По сути, это “алгебра логики” — те же правила, что и с числами, но с истиной и ложью вместо 1 и 0.

Символ	Операция	Пример	Значение
\(\neg P\)	отрицание	“не P”	инверсия
\(P \wedge Q\)	конъюнкция	“P и Q”	оба истинны
\(P \vee Q\)	дизъюнкция	“P или Q”	хотя бы одно истинно
\(P \to Q\)	импликация	“если P, то Q”	ложь, если P истина, Q ложь
\(P \leftrightarrow Q\)	эквиваленция	“P тогда и только тогда, когда Q”	оба совпадают

11. Семантика (смысл логики предикатов)

Семантика — это “смысловая начинка” формулы.
Она отвечает за то, что на самом деле означает логическое выражение при заданных интерпретациях.

Например, одно и то же выражение может быть истинным в одних множествах и ложным в других.

Истинность формулы зависит от:

• множества (области определения);
• значений предикатов;
• конкретных подставленных элементов.

То есть предикаты — это как “функции истины” от элементов множества.

12. Разница между логикой высказываний и предикатов

Логика высказываний — это “плоская” логика: только истина и ложь, без переменных.
Логика предикатов — “объёмная”: в ней есть объекты, свойства, отношения и кванторы.
Первая — частный случай второй.

Характеристика	Логика высказываний	Логика предикатов
Минимальная единица	Высказывание (“идёт дождь”)	Утверждение о свойствах объектов
Переменные	Нет	Есть
Кванторы	Нет	Есть
Таблицы истинности	Работают	Не работают напрямую
Пример	“A → B”	“∀x (P(x) → Q(x))”

13. Термины

Термин	Определение
Высказывание	Утверждение, которому можно приписать истину или ложь
Предикат	Функция, возвращающая истину/ложь в зависимости от аргументов
Квантор	Символ, определяющий, для скольких элементов утверждение верно
Импликация	“Если P, то Q”
Эквиваленция	“P тогда и только тогда, когда Q”
Свободная переменная	Не под квантором
Связанная переменная	Под квантором
Интерпретация	Задание смысла предикатам и области определения
Модель	Интерпретация, в которой формула истинна

14. Для запоминания

• \(\forall\) — все, без исключений.
• \(\exists\) — хотя бы один.
• Отрицание квантора → меняем тип и ставим отрицание внутрь.
• Порядок кванторов менять нельзя — смысл меняется!
• Формулы с кванторами — не высказывания, пока не задана область.
• Таблицы истинности работают только для чистых высказываний.