Математическая Логика, 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 года | Алгоритмы решения задач


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

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