Логика предикатов#
Вступление#
Основные понятия логики предикатов#
Логика предикатов оперирует следующими центральными понятиями:
универсум - совокупность объектов, о которой говорится в высказывании
предикаты - высказывания про элементы универсума
операции - действия над элементами универсума
кванторы - связки “все” и “существует”
обычные логические связки (отрицание, конъюнкция, дизъюнкция, импликация)
С уроков русского языка мы помним разбор предложения по составляющим: подлежащее, сказуемое, дополнение, определение, обстоятельство. Слово “предикат” означает сказуемое. Предикат - это то, что говорится об объекте (подлежащем).
Про каждый объект (элемент универсума) говорится высказывание, и по отношению к каждому объекту в отдельности оно истинно либо ложно. Получается много высказываний - столько же, сколько элементов в универсуме.
Это большое количество высказываний можно “свернуть” в одно высказывание при помощи квантора общности либо квантора существования. Например, “все выключатели выключены” - это конъюнкция отдельных высказываний (каждое высказывание - про каждый выключатель). Или противоположное высказывание: “некоторые выключатели включены” - это дизъюнкция отдельных высказываний.
Квантор |
Обозначение |
Смысл |
Аналог |
Нейтральный элемент |
|---|---|---|---|---|
“для всех” |
\(\forall\) |
большое И |
произведение \(\Pi\) |
1 |
“существует” |
\(\exists\) |
большое ИЛИ |
сумма \(\Sigma\) |
0 |
Цифровой пример#
Конкретная матрица / одномерный массив - турнир вычислений (кто какие задачи смог решить)
Упражнение. Реализуйте вычисление квантора общности и квантора существования по числовому массиву, пользуясь функцией reduce.
Пример из жизни#
Переведем песню про бобра на язык логики предикатов.
Сидим с бобром за столом
Вдвоём, на ужин готовим полено.
Давай поговорим, бобёр,
О том, что наболело.
Скажи, зачем же между нами плотина?
Скажи, зачем между нами обрыв?
Я обниму твоё пушистое тело.
Ну почему бобры так добры?
Универсум \(U_1\) - множество бобров, универсум \(U_2\) - множество людей, универсум \(U_3\) - множество съестных продуктов, универсум \(U_4\) - множество тем для разговора.
Одноместные предикаты:
\(K(x) = \) “\(x\) добрый” (\(x \in U_1\))
\(T(x) = \) “\(x\) сидит за столом” (\(x \in U_1\) или \(x \in U_2\))
\(P(x) = \) “\(x\) наболело” (\(x \in U_4\))
Двухместные предикаты:
\(C(x, y)\) = “\(x\) готовит на ужин \(y\)” (\(x \in U_1\) или \(x \in U_2\); \(y \in U_3\))
\(H(x, y)\) = “\(x\) обнимает \(y\)”
Трёхместные предикаты:
\(S(x, y, z) = \) “\(x\) говорит с \(y\) про \(z\)” (\(x, y \in U_1 \cup U_2\); \(z \in U_4\))
\(B(x, y, z) = \) “между \(x\) и \(y\) находится \(z\)”
Предметные константы:
\(a\) - человек
\(b\) - бобёр
\(c\) - обрыв
\(d\) - плотина
\(e\) - полено
Вариант перевода песни на язык логики предикатов:
\(T(a) \,\&\, T(b)\)
\(C(a, e) \,\&\, C(b, e)\)
\(\exists z\, \left( P(z) \,\&\, S(a, b, z) \right)\)
\(B(a, b, d) \,\&\, B(a, b, e)\)
\(H(a, b)\)
\(\forall x\, ((x \in U_1) \to K(x))\)
Пришли мы к дому бобра,
Он мне дал с собой добра четыре ведра.
Введем дополнительные универсумы: \(U_5\) - множество вёдер, \(U_6\) - множество домов. Не забудем про множество целых неотрицательных чисел \(U_7 = \mathbb N_0\).
Введем предикаты \(R(x, y) = \) “\(x\) пришел к \(y\)” (\(x \in U_1 \cup U_2\), \(y \in U_6\)), \(G(x, y, z) = \) “\(x\) дает \(y\) предмет \(z\)”.
Введем операцию \(h(x) = \text{дом бобра }x\) (\(x \in U_1\)).
Новые две строчки переводятся на язык логики предикатов так:
\(R(a, h(b)) \,\&\, R(b, h(b))\)
\(\exists z_1 \, \exists z_2 \, \exists z_3 \, \exists z_4 \, \bigl(G(b, a, z_1) \,\&\, G(b, a, z_2) \,\&\, G(b, a, z_3) \,\&\, G(b, a, z_4) \,\&\,\bigr.\)
\(\bigl.\,\&\,(z_i \in U_5) \,\&\, \forall i\, \forall j\,\left(i \in 1..4 \,\&\, j \in 1..4 \,\&\, \neg (i = j) \to \neg(z_i = z_j) \right) \bigr)\)
Благодаря точной и однозначной записи всех формул на языке логики предикатов, становится возможной процедура логического вывода.
Упражнение. Обратитесь к любой большой языковой модели с просьбой перевести и другие куплеты песни про бобра на язык логики предикатов.
Зачем программисту логика предикатов?#
Логика предикатов нужна, чтобы выражать высказывания про наборы объектов. Например, “в массиве найдутся два одинаковых числа” или “все числа положительны”. Как и логика высказываний, логика предикатов необходима для того, чтобы комментировать и анализировать программный код.
Строгие определения#
Литература#
Зюзьков - Введение в математическую логику