Математическая Логика, 02 лекция (от 25 сентября)
Материал из eSyr's wiki.
( —) |
|||
Строка 11: | Строка 11: | ||
=== Предикат === | === Предикат === | ||
- | Логика | + | Логика предикатов — логика отношений. В более общем смысле это атрибут предмета, отношение предметов. |
=== Алфавит логики предикатов === | === Алфавит логики предикатов === | ||
Строка 32: | Строка 32: | ||
** Импликация | ** Импликация | ||
* Квантор всеобщности - 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φ) |
- | В импликации левая | + | В импликации левая часть — посылка импликации, правая — следствие импликации. |
=== Приоритет операций === | === Приоритет операций === | ||
Строка 62: | Строка 62: | ||
* Квантор связывает ту переменную, которая идёт за ним | * Квантор связывает ту переменную, которая идёт за ним | ||
- | * Связанное | + | * Связанное вхождение — всякое вхождение переменной, связанной квантором. |
* Все вхождения перменной, лежащие вне области действия квантора, связывающего эту переменную называются свободными | * Все вхождения перменной, лежащие вне области действия квантора, связывающего эту переменную называются свободными | ||
Строка 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}} |
Версия 21:38, 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 года | Алгоритмы решения задач