Математическая Логика, 02 лекция (от 25 сентября)
Материал из eSyr's wiki.
(Отмена правки № 1411 участника 66.230.230.230 (обсуждение)) |
(→Свободные и связанные переменные) |
||
(5 промежуточных версий не показаны.) | |||
Строка 3: | Строка 3: | ||
'''Слайды:''' http://mathcyb.cs.msu.su/paper/zakh/LectLog2.pdf | '''Слайды:''' http://mathcyb.cs.msu.su/paper/zakh/LectLog2.pdf | ||
- | Отвечая на заданные себе вопросы, математики 20-го века начали разрабатывать тот аппарат, который использовали для доказательства своих утверждений, | + | Отвечая на заданные себе вопросы, математики 20-го века начали разрабатывать тот аппарат, который использовали для доказательства своих утверждений, то есть, логику. В первую очередь, они разработали язык, язык предикатов. |
- | Сегодня будет он рассмотрен, его синтаксис, семантика. Наконец, будет | + | Сегодня будет он рассмотрен, его синтаксис, семантика. Наконец, будет исследовано отношение между высказываниями и интерпретациями, отношение выполнимости, на основе которого выясняется, что такое истина, и что такое ложь. |
== Логика предикатов == | == Логика предикатов == | ||
Строка 11: | Строка 11: | ||
=== Предикат === | === Предикат === | ||
- | Логика | + | Логика предикатов — логика отношений. В более общем смысле это атрибут предмета, отношение предметов. |
=== Алфавит логики предикатов === | === Алфавит логики предикатов === | ||
- | * | + | * Предметные переменные. Указывают на объект. Обозначаются латинскими буквами конца алфавита |
- | * Предметные константы | + | * Предметные константы. Символы, которые играют роль имён предметов. Они просто привязаны к предмету. Имена предметов. |
- | * | + | * Функциональные символы. Вместе в каждой буквой ассоциировано число больше 9, которое обозначает местность функции. Операции над предметами. |
- | * Предикатные символы. Будут служить для | + | * Предикатные символы. Будут служить для обозначения отношения. В скобках указывается местность. Отьношения между предметами |
Тройку констант, предикатов, функций обозначают сигнатурой языка. | Тройку констант, предикатов, функций обозначают сигнатурой языка. | ||
Строка 24: | Строка 24: | ||
Пример. | Пример. | ||
* Константы — числа | * Константы — числа | ||
- | * | + | * Функциональные символы — арифметические операции |
* Предикаты — операции сравнения | * Предикаты — операции сравнения | ||
- | * | + | * Логические связки |
** Конъюнкция | ** Конъюнкция | ||
** Дизъюнкция | ** Дизъюнкция | ||
** Импликация | ** Импликация | ||
* Квантор всеобщности - for all - ∀ | * Квантор всеобщности - for all - ∀ | ||
- | * Квантор | + | * Квантор существования — exists — &exists; |
* Знаки препинания: ",", "(", ")" | * Знаки препинания: ",", "(", ")" | ||
=== Терм === | === Терм === | ||
- | + | Терм — всякая переменная, всякая константа, f<sup>(n)</sup>(t1, ..., tn). | |
- | * | + | * Term — множество всех термов |
- | * Var<sub>t</sub> | + | * Var<sub>t</sub> — множество переменных t |
- | * Если Var<sub>t</sub> = ∅, то | + | * Если Var<sub>t</sub> = ∅, то t — основной терм |
=== Формулы === | === Формулы === | ||
Строка 48: | Строка 48: | ||
Два класса формул: | Два класса формул: | ||
- | * Атомарная | + | * Атомарная формула — P<sup>(m)</sup>(t1, ..., tm) |
- | * Сложная | + | * Сложная формула — (φ {&|∨|→} ψ), (¬ψ), (∀xφ), (&exists;xφ) |
- | В импликации левая | + | В импликации левая часть — посылка импликации, правая — следствие импликации. |
=== Приоритет операций === | === Приоритет операций === | ||
Строка 59: | Строка 59: | ||
=== Свободные и связанные переменные === | === Свободные и связанные переменные === | ||
- | Свободная пермененная | + | Свободная пермененная может принимать любое значение, какое даёт ей автор. Значением связанной переменной руководит квантор. |
* Квантор связывает ту переменную, которая идёт за ним | * Квантор связывает ту переменную, которая идёт за ним | ||
- | * Связанное | + | * Связанное вхождение — всякое вхождение переменной, связанной квантором. |
* Все вхождения перменной, лежащие вне области действия квантора, связывающего эту переменную называются свободными | * Все вхождения перменной, лежащие вне области действия квантора, связывающего эту переменную называются свободными | ||
Строка 95: | Строка 95: | ||
Формула | Формула | ||
- | |||
- | <!-- педедыв --> | ||
=== Семантика === | === Семантика === | ||
- | + | Семантика — свод правил, наделяющих значением, смыслом синтаксические констр языка. | |
- | + | Интерпретация — воображаемый математический мир, в котором все базовые математические объекты наделяются смыслом в соответствии с их предназначением и названием. Интерпретация константы — предмет, и т.д. | |
- | Здесь будет | + | Здесь будет использоваться алгебраическая интерпретация это строгая форма интерпретации. |
* D1 | * D1 | ||
- | * | + | * Const — имя становится становится тем предметом, который носит это имя |
- | * | + | * Func — функциональные символы обозначают отображение, функции, многоместные операции |
- | * | + | * Pred — два разных обозначения. Если предикат выполняется, то true, иначе false. |
- | Миров можно придумать много. Потенциал для | + | Миров можно придумать много. Потенциал для определения разных интерпретаций неограничен. |
- | ==== Как на | + | ==== Как на основе интерпретации вычислить значение терма и формул ==== |
- | Пусть задана интерпретация, терм и набор элементов из | + | Пусть задана интерпретация, терм и набор элементов из области интерпретации. |
- | * Если | + | * Если терм — переменная, то значение терма — значение переменной. |
- | * Если | + | * Если терм — константа, то значение терма — значение константы. |
- | * Если терм составной, то его значение будет образом | + | * Если терм составной, то его значение будет образом … |
- | Для | + | Для интерпретации формулы можно вывести свойство выполнимости между интерпретацией и формулой. Оно выражает суждение о том, что заданная интерпретация, соответствующая формуле, является верной. |
Обычная конъюнкция такова, что A & B и B & A равносильны. Но в лингвистике для A = "начался пожар" и B = "приехали пожарные" это не так. | Обычная конъюнкция такова, что A & B и B & A равносильны. Но в лингвистике для A = "начался пожар" и B = "приехали пожарные" это не так. | ||
- | + | Импликация — самая отчаянная связка. Выполнимости не будет, если ψ1 выполнилось, а ψ2 — нет. Во всех остальных случаях выполнимость присутствует. Отсюда такая формула. | |
{{Математическая Логика}} | {{Математическая Логика}} | ||
{{Lection-stub}} | {{Lection-stub}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Слайды: 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 года | Алгоритмы решения задач