Математическая Логика, 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 --- нет. Во всех остальных случаях выполнимость присутствует. Отсюда такая формула.