Математическая Логика, 02 лекция (от 25 сентября)

Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Слайды: http://mathcyb.cs.msu.su/paper/zakh/LectLog2.pdf

Отвечая на заданные себе вопросы, математики 20-го века начали разрабатывать тот аппарат, который использовали для доказательства своих утверждений, то есть, логику. В первую очередь, они разработали язык, язык предикатов.

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

Логика предикатов

Предикат

Логика предикатов — логика отношений. В более общем смысле это атрибут предмета, отношение предметов.

Алфавит логики предикатов

• Предметные переменные. Указывают на объект. Обозначаются латинскими буквами конца алфавита
• Предметные константы. Символы, которые играют роль имён предметов. Они просто привязаны к предмету. Имена предметов.
• Функциональные символы. Вместе в каждой буквой ассоциировано число больше 9, которое обозначает местность функции. Операции над предметами.
• Предикатные символы. Будут служить для обозначения отношения. В скобках указывается местность. Отьношения между предметами

Тройку констант, предикатов, функций обозначают сигнатурой языка.

Пример.

* Константы — числа
* Функциональные символы — арифметические операции
* Предикаты — операции сравнения

• Логические связки
  • Конъюнкция
  • Дизъюнкция
  • Импликация
• Квантор всеобщности - for all - ∀
• Квантор существования — exists — &exists;
• Знаки препинания: ",", "(", ")"

Терм

Терм — всякая переменная, всякая константа, f⁽ⁿ⁾(t1, ..., tn).

• Term — множество всех термов
• Var_t — множество переменных t
• Если Var_t = ∅, то t — основной терм

Формулы

Другой класс генераторов правильных выражений.

Два класса формул:

• Атомарная формула — P^(m)(t1, ..., tm)
• Сложная формула — (φ {&|∨|→} ψ), (¬ψ), (∀xφ), (&exists;xφ)

В импликации левая часть — посылка импликации, правая — следствие импликации.

Приоритет операций

Посмотрев на примеры, можно понять, что скобки затрудняют чтение, поэтому можно ввести соглашение о приоритете операций

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

Свободная пермененная моет принимать любое значение, какое даёт ей автор. Значением связанной переменной руководит квантор.

• Квантор связывает ту переменную, которая идёт за ним
• Связанное вхождение — всякое вхождение переменной, связанной квантором.
• Все вхождения перменной, лежащие вне области действия квантора, связывающего эту переменную называются свободными

Var_φ — множество свободных переменных формулы φ

Tckb Var_φ = ∅, то формула φ называется предложением. Это законченное высказывание, которое мы можем оценивать вне зависимости от значений каких-либо параметров.

Соглашение о приоритете операций

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

• ¬, ∀, ∃
• &
• ∨
• →

Пример

Данный язык очень мощен и позволяет выражать утверждения из любой области языка.

• Алфавит
  • Константы
    • 0 константа, действительное число ноль;
  • Функциональные символы
    • h(2) (x,y) — абсолютная разность чисел x и y;
  • Предикатные символы
    • R(1) (x)x действительное число;
    • N(1) (x)x натуральное число;
    • S(1) (x)x последовательность действительных чисел;
    • E(3) (x,y,z)x это y-ый член последовательности z;
    • <(2) (x,y) число x меньше числа y.

Формула

Семантика

Семантика — свод правил, наделяющих значением, смыслом синтаксические констр языка.

Интерпретация — воображаемый математический мир, в котором все базовые математические объекты наделяются смыслом в соответствии с их предназначением и названием. Интерпретация константы — предмет, и т.д.

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

• D1
• Const — имя становится становится тем предметом, который носит это имя
• Func — функциональные символы обозначают отображение, функции, многоместные операции
• Pred — два разных обозначения. Если предикат выполняется, то true, иначе false.

Миров можно придумать много. Потенциал для определения разных интерпретаций неограничен.

Как на основе интерпретации вычислить значение терма и формул

Пусть задана интерпретация, терм и набор элементов из области интерпретации.

• Если терм — переменная, то значение терма — значение переменной.
• Если терм — константа, то значение терма — значение константы.
• Если терм составной, то его значение будет образом …

Для интерпретации формулы можно вывести свойство выполнимости между интерпретацией и формулой. Оно выражает суждение о том, что заданная интерпретация, соответствующая формуле, является верной.

Обычная конъюнкция такова, что A & B и B & A равносильны. Но в лингвистике для A = "начался пожар" и B = "приехали пожарные" это не так.

Импликация — самая отчаянная связка. Выполнимости не будет, если ψ1 выполнилось, а ψ2 — нет. Во всех остальных случаях выполнимость присутствует. Отсюда такая формула.