Математическая Логика, 02 лекция (от 25 сентября)
Материал из eSyr's wiki.
( —) |
|||
Строка 5: | Строка 5: | ||
Отвечая на заданные себе вопросы, математики 20-го века начали разрабатывать тот аппарат, который использовали для доказательства своих утверждений, то есть, логику. В первую очередь, они разработали язык, язык предикатов. | Отвечая на заданные себе вопросы, математики 20-го века начали разрабатывать тот аппарат, который использовали для доказательства своих утверждений, то есть, логику. В первую очередь, они разработали язык, язык предикатов. | ||
- | Сегодня будет он рассмотрен, его синтаксис, семантика. Наконец, будет | + | Сегодня будет он рассмотрен, его синтаксис, семантика. Наконец, будет исследовано отношение между высказываниями и интерпретациями, отношение выполнимости, на основе которого выясняется, что такое истина, и что такое ложь. |
== Логика предикатов == | == Логика предикатов == | ||
Строка 15: | Строка 15: | ||
=== Алфавит логики предикатов === | === Алфавит логики предикатов === | ||
- | * Предметные переменные. Указывают на объект. Обозначаются | + | * Предметные переменные. Указывают на объект. Обозначаются латинскими буквами конца алфавита |
- | * Предметные константы | + | * Предметные константы. Символы, которые играют роль имён предметов. Они просто привязаны к предмету. Имена предметов. |
- | * | + | * Функциональные символы. Вместе в каждой буквой ассоциировано число больше 9, которое обозначает местность функции. Операции над предметами. |
- | * Предикатные символы. Будут служить для | + | * Предикатные символы. Будут служить для обозначения отношения. В скобках указывается местность. Отьношения между предметами |
Тройку констант, предикатов, функций обозначают сигнатурой языка. | Тройку констант, предикатов, функций обозначают сигнатурой языка. | ||
Строка 24: | Строка 24: | ||
Пример. | Пример. | ||
* Константы — числа | * Константы — числа | ||
- | * | + | * Функциональные символы — арифметические операции |
* Предикаты — операции сравнения | * Предикаты — операции сравнения | ||
- | * | + | * Логические связки |
** Конъюнкция | ** Конъюнкция | ||
** Дизъюнкция | ** Дизъюнкция | ||
Строка 98: | Строка 98: | ||
=== Семантика === | === Семантика === | ||
- | Семантика — свод правил, наделяющих значением, смыслом | + | Семантика — свод правил, наделяющих значением, смыслом синтаксические констр языка. |
- | Интерпретация — воображаемый математический мир, в котором все | + | Интерпретация — воображаемый математический мир, в котором все базовые математические объекты наделяются смыслом в соответствии с их предназначением и названием. Интерпретация константы — предмет, и т.д. |
Здесь будет использоваться алгебраическая интерпретация это строгая форма интерпретации. | Здесь будет использоваться алгебраическая интерпретация это строгая форма интерпретации. | ||
Строка 109: | Строка 109: | ||
* Pred — два разных обозначения. Если предикат выполняется, то true, иначе false. | * Pred — два разных обозначения. Если предикат выполняется, то true, иначе false. | ||
- | Миров можно придумать много. Потенциал для | + | Миров можно придумать много. Потенциал для определения разных интерпретаций неограничен. |
==== Как на основе интерпретации вычислить значение терма и формул ==== | ==== Как на основе интерпретации вычислить значение терма и формул ==== | ||
- | Пусть задана интерпретация, терм и набор элементов из | + | Пусть задана интерпретация, терм и набор элементов из области интерпретации. |
* Если терм — переменная, то значение терма — значение переменной. | * Если терм — переменная, то значение терма — значение переменной. | ||
Строка 119: | Строка 119: | ||
* Если терм составной, то его значение будет образом … | * Если терм составной, то его значение будет образом … | ||
- | Для интерпретации формулы можно вывести | + | Для интерпретации формулы можно вывести свойство выполнимости между интерпретацией и формулой. Оно выражает суждение о том, что заданная интерпретация, соответствующая формуле, является верной. |
Обычная конъюнкция такова, что A & B и B & A равносильны. Но в лингвистике для A = "начался пожар" и B = "приехали пожарные" это не так. | Обычная конъюнкция такова, что A & B и B & A равносильны. Но в лингвистике для A = "начался пожар" и B = "приехали пожарные" это не так. |
Версия 21:45, 2 октября 2010
Предыдущая лекция | Следующая лекция
Слайды: 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 — нет. Во всех остальных случаях выполнимость присутствует. Отсюда такая формула.
|
|
Ссылки
Официальная страница курса | Задачи
Проведение экзамена | Решение задач: Решение задач методички | Решение задач варианта экзамена 2004 года | Алгоритмы решения задач