Математическая Логика, 02 лекция (от 25 сентября)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(→Свободные и связанные переменные) |
||
(6 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | == | + | [[Математическая Логика, 01 лекция (от 24 сентября)|Предыдущая лекция]] | [[Математическая Логика, 03 лекция (от 26 сентября)|Следующая лекция]] |
- | + | ||
- | + | '''Слайды:''' http://mathcyb.cs.msu.su/paper/zakh/LectLog2.pdf | |
- | + | ||
+ | Отвечая на заданные себе вопросы, математики 20-го века начали разрабатывать тот аппарат, который использовали для доказательства своих утверждений, то есть, логику. В первую очередь, они разработали язык, язык предикатов. | ||
+ | |||
+ | Сегодня будет он рассмотрен, его синтаксис, семантика. Наконец, будет исследовано отношение между высказываниями и интерпретациями, отношение выполнимости, на основе которого выясняется, что такое истина, и что такое ложь. | ||
+ | |||
+ | == Логика предикатов == | ||
+ | |||
+ | === Предикат === | ||
+ | |||
+ | Логика предикатов — логика отношений. В более общем смысле это атрибут предмета, отношение предметов. | ||
+ | |||
+ | === Алфавит логики предикатов === | ||
+ | |||
+ | * Предметные переменные. Указывают на объект. Обозначаются латинскими буквами конца алфавита | ||
+ | * Предметные константы. Символы, которые играют роль имён предметов. Они просто привязаны к предмету. Имена предметов. | ||
+ | * Функциональные символы. Вместе в каждой буквой ассоциировано число больше 9, которое обозначает местность функции. Операции над предметами. | ||
+ | * Предикатные символы. Будут служить для обозначения отношения. В скобках указывается местность. Отьношения между предметами | ||
+ | |||
+ | Тройку констант, предикатов, функций обозначают сигнатурой языка. | ||
+ | |||
+ | Пример. | ||
+ | * Константы — числа | ||
+ | * Функциональные символы — арифметические операции | ||
+ | * Предикаты — операции сравнения | ||
+ | |||
+ | * Логические связки | ||
+ | ** Конъюнкция | ||
+ | ** Дизъюнкция | ||
+ | ** Импликация | ||
+ | * Квантор всеобщности - for all - ∀ | ||
+ | * Квантор существования — exists — &exists; | ||
+ | * Знаки препинания: ",", "(", ")" | ||
+ | |||
+ | === Терм === | ||
+ | |||
+ | Терм — всякая переменная, всякая константа, f<sup>(n)</sup>(t1, ..., tn). | ||
+ | |||
+ | * Term — множество всех термов | ||
+ | * Var<sub>t</sub> — множество переменных t | ||
+ | * Если Var<sub>t</sub> = ∅, то t — основной терм | ||
+ | |||
+ | === Формулы === | ||
+ | |||
+ | Другой класс генераторов правильных выражений. | ||
+ | |||
+ | Два класса формул: | ||
+ | * Атомарная формула — P<sup>(m)</sup>(t1, ..., tm) | ||
+ | * Сложная формула — (φ {&|∨|→} ψ), (¬ψ), (∀xφ), (&exists;xφ) | ||
+ | |||
+ | В импликации левая часть — посылка импликации, правая — следствие импликации. | ||
+ | |||
+ | === Приоритет операций === | ||
+ | |||
+ | Посмотрев на примеры, можно понять, что скобки затрудняют чтение, поэтому можно ввести соглашение о приоритете операций | ||
+ | |||
+ | === Свободные и связанные переменные === | ||
+ | |||
+ | Свободная пермененная может принимать любое значение, какое даёт ей автор. Значением связанной переменной руководит квантор. | ||
+ | |||
+ | * Квантор связывает ту переменную, которая идёт за ним | ||
+ | * Связанное вхождение — всякое вхождение переменной, связанной квантором. | ||
+ | * Все вхождения перменной, лежащие вне области действия квантора, связывающего эту переменную называются свободными | ||
+ | |||
+ | Var<sub>φ</sub> — множество свободных переменных формулы φ | ||
+ | |||
+ | Tckb Var<sub>φ</sub> = ∅, то формула φ называется предложением. Это законченное высказывание, которое мы можем оценивать вне зависимости от значений каких-либо параметров. | ||
+ | |||
+ | === Соглашение о приоритете операций === | ||
+ | |||
+ | Действует для формул и позволяет расставить скобки, чтобы выражение стало формулой. | ||
+ | |||
+ | * ¬, ∀, ∃ | ||
+ | * & | ||
+ | * ∨ | ||
+ | * → | ||
+ | |||
+ | === Пример === | ||
+ | |||
+ | Данный язык очень мощен и позволяет выражать утверждения из любой области языка. | ||
+ | |||
+ | * Алфавит | ||
+ | ** Константы | ||
+ | *** 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 — нет. Во всех остальных случаях выполнимость присутствует. Отсюда такая формула. | ||
+ | |||
+ | {{Математическая Логика}} | ||
+ | {{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 года | Алгоритмы решения задач