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

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

Перейти к: навигация, поиск

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

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

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

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

Содержание

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

Предикат

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

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

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

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

Пример.

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

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

Терм

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

  • Term — множество всех термов
  • Vart — множество переменных t
  • Если Vart = ∅, то 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 — нет. Во всех остальных случаях выполнимость присутствует. Отсюда такая формула.


Математическая Логика


Лекции

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

Сентябрь
24 25 26
Октябрь
02 03 10 17 24 31
Ноябрь
07 14 21 28
Декабрь
05 12 19
Семинары

01 02 03 04 05 06 07


Календарь

Сентябрь
26
Октябрь
10 24
Ноябрь
07 21
Декабрь
05 19

Ссылки
Официальная страница курса | Задачи
Проведение экзамена | Решение задач: Решение задач методички | Решение задач варианта экзамена 2004 года | Алгоритмы решения задач


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы