Редактирование: Математическая Логика, 03 лекция (от 26 сентября)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

[[Математическая Логика, 02 лекция (от 25 сентября)|Предыдущая лекция]] | [[Математическая Логика, 04 лекция (от 02 октября)|Следующая лекция]]

'''Слайды:''' http://mathcyb.cs.msu.su/paper/zakh/LectLog3.pdf http://mathcyb.cs.msu.su/paper/zakh/LectLog4.pdf

418, 419 группы --- лекция 29 сентября 10:30Ю ауд. 613
420---428, 441 --- лекция 2 октября 14:35, П-5

Лекция 3. Выполнимые и общесзнач. формулы. Моедли. Логическое следование. Проблема общезначимости. Семантические таблицы.

Проблема общезн. непростая проблема, требующая разработки спец. аппарата, лектор расскаже о предпосылках созд. этого аппарата, самый простой вариант, расск. про вывод в табицах.

После введения понятия фолмуры можно классиф формуцлы:
* Ф-ла может быть итсинной всегдПА, иногда, никогда

Формула выпонлима, елси он выполн на данном наборе переменных. То есть, ф-ла выполнима, если она не совсем ложна, выполняется при нек-ром наборк параметров. Бывает, что ф-ла выполняется для оюбого набора переменных, тогда она истинна. Формула просто выполнима, которая выполнима в какой-либо интерпретации. Если же формула истинна на любой интерпретации, то она является тожд. истинна, или общезначима, то есть верна везде и свюду при любыъ значениях переменных. Если же формула никогда не выполняется, то она противоречива, неверна.

Для проверки выполнимости достаточно придумать один пример, но общезначимость надо проверять на всех интерп., как это сделать?

Выполнимые формулы --- важные вещи, так как именно они несут знания. Выполнимые формы --- формы предст. знаний. Но общезначимые формулы --- банальны, не несут никакой информации. Но вместе с тем, они для нас самые интересные. Почему? Какая роль им отводится?

Пусть у нас есть множество замк. формул. Тогда интерп., в которой выполнчются все эти формулы, называется моделью для этого множества. Мы оговорим множество утв., они образуют БЗ. И тогда возникает вопрос, есть ли мир, в которой выполняется эта БЗ? Такой мир есть модель для БЗ. Таких миров может быть много.

Почему для пустогно множества формул интерп любая? Потому что определение сокращённое, на самом деле там импликация "для любой формулы если она в Г то она должна выполняться в модели Г". Тогда импликация верна и в том случае, если левая часть ложна.

Сами по себе модели не так интересны. Гораздо более важно понятие логического следования. Пусть есть база Г, есть замкнутая формула. Эта флормула называется лог. следствием, если каждая модели Г есть модель для формулы. Логические следствия --- производные знания. Есть причинно-следст. связь, но важен факт следствия, а не механизм получения связи. Это одна из важн. задач --- получение следствий.

Обозначения

* Г |= &phi; --- &phi; --- логическо следствие Г
* следствиями пустой БЗ являютсчя общезначимые формулы, поэтому для обозн. общезн. будем исп. |= &phi;

Насколько это применимо на практике?

Пример:
* Даша любит Сашу
* Саша любит пиво
* Паша любит пиво и всех тех, кто любит то, что любит Паша

Вопрос: любима ли Даша?

Психологи изучали, с какого этапа человек способен к широкой аналитической деятельности? Ребёнок не может установить причинно-следственные связи до 10---11 лет. Можем ли мы сказать, что ребёнок 8 лет не обладает интеллектом? Нет. Следовательно, можно создать систему, которая может системно реать подобные задачи.

Решение. Сформируем алфавит:
* Даша
* Саша
* Паша
* пиво

Предикаты
* L(x, y) "x любит y"

Условия задачи на языке предикатов:
* L(Даша, Саша)
* L(Саша, пиво)
* L(Паша, пиво) & (&forall;x L(Паша, х) & (&forall;y L()))

Любима ли Даша: &exist;x L(x, Даша)

Рассмотрим аппарат для решения задачи.

Теорема о логическом следствии.

Общезн. формулы --- это кангалы причинно-следст. связи, по которым передаются знания. Важно определять эти каналы и уметь извлекать из них знания. Следовательно, будем заниматьсч робелмой общезначимости: выяснять, являетсмя ли данная формула общезначимой?

Проверка выполн./общезн. для любой формулы сводится к проверке выполн./общезн. замкнутой формулы.

Прверка перебором невозможна, так как существует формула, которая истинна для любой конечной интерп. и не общезначима.

Следовательно, перебором проверить нельзя, и нужны более извращённые способы.

Можно доказывать методом от противоположного за конечного количества шагов, правда, пока непонтно, как эти шаги систематизировать.

Пример. Проверить общезначимость формулы &phi; = &exist;xP(x) &rarr; &forall;xP(x)

Доказательство:
{|
 |
 |I |&ne; &phi;
 |-
 |I |= &exist;xP(x)
 |I |&ne; &forall;xP(x)
 |-
 |I |= P(x)[d]
 |I |&ne; P(x)[d<sub>2</sub>]
 |}
I: d1, d2, P(d1) = true, P(d2) = false

То есть, разбирая формулу, можно построить контрпример, или показать, что его нет.

Систематизируем этот способ проверки формул. Попробуем ввести способ проверки, который независит от нашей квалификации --- семант. таблицы.

Есть и другие способы (напр., секвенциальный вывод), их мы рассмотрим в 4/4 курса.

Лекция 4.

Представим, что у нас в формуле нет кванторов, то есть это ыактически нечто вроде булевой формулы. Как её проверить? Достаточно перебрать все возм. значния, и для этого хватит аппарата булевой алгебры. С кванторами это не прокатит. Важная сост. лог. вывода --- умение пользоваться подстановками. ДАлее мы рассмотрим, каковы правила табл. вывода, преобр. одни таблицы в другие, и по каким законам ведётся игра под называнием табл. вывод. И обоснуем, что если не выигрываем мы, то можем обосновать общезначимость формлы.

Подстановка --- всякое отобр. из множества перем. в множество термов.

Область подстановки --- те перем., которые изм. в результате подстановки.

Если изм. конеч. число перем., то подстановка конечна.

Формы прочтения правил табличного вывода: 
* Верхняя таблица выполнима &harr; выполнима хотя бы одна нижняя
* Верхняя таблица невыполнима &harr; ни одна нижняя невыполнима

Мнемон. обозн правил: 
* первая буква --- из левой или правой части таблицы правило
* вторая --- какая основная операция

Вопрос выполнимости таблиц сводится к вопросы выполнимости более простых таблиц.

Символ, который имеет незапятнанную репутацию, я его впервые здесь ввожу.

У меня есть константа. Дам-ка я ей свеженькое имя с.

Этот метод можно до бесконечности тянуть, поэтому нужны методы для выяснения бесконечности вывода, предохранители.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%9B%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%2C_03_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_26_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29

Редактирование: Математическая Логика, 03 лекция (от 26 сентября)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 3: / Строка 3: @@
 '''Слайды:''' http://mathcyb.cs.msu.su/paper/zakh/LectLog3.pdf http://mathcyb.cs.msu.su/paper/zakh/LectLog4.pdf
-, 419 группы — лекция 29 сентября 10:30Ю ауд. 613
+, 419 группы --- лекция 29 сентября 10:30Ю ауд. 613
-—428, 441 — лекция 2 октября 14:35, П-5
+---428, 441 --- лекция 2 октября 14:35, П-5
 Лекция 3. Выполнимые и общесзнач. формулы. Моедли. Логическое следование. Проблема общезначимости. Семантические таблицы.
@@ Строка 17: / Строка 17: @@
 Для проверки выполнимости достаточно придумать один пример, но общезначимость надо проверять на всех интерп., как это сделать?
-Выполнимые формулы — важные вещи, так как именно они несут знания. Выполнимые формы — формы предст. знаний. Но общезначимые формулы — банальны, не несут никакой информации. Но вместе с тем, они для нас самые интересные. Почему? Какая роль им отводится?
+Выполнимые формулы --- важные вещи, так как именно они несут знания. Выполнимые формы --- формы предст. знаний. Но общезначимые формулы --- банальны, не несут никакой информации. Но вместе с тем, они для нас самые интересные. Почему? Какая роль им отводится?
 Пусть у нас есть множество замк. формул. Тогда интерп., в которой выполнчются все эти формулы, называется моделью для этого множества. Мы оговорим множество утв., они образуют БЗ. И тогда возникает вопрос, есть ли мир, в которой выполняется эта БЗ? Такой мир есть модель для БЗ. Таких миров может быть много.
@@ Строка 23: / Строка 23: @@
 Почему для пустогно множества формул интерп любая? Потому что определение сокращённое, на самом деле там импликация "для любой формулы если она в Г то она должна выполняться в модели Г". Тогда импликация верна и в том случае, если левая часть ложна.
-Сами по себе модели не так интересны. Гораздо более важно понятие логического следования. Пусть есть база Г, есть замкнутая формула. Эта флормула называется лог. следствием, если каждая модели Г есть модель для формулы. Логические следствия — производные знания. Есть причинно-следст. связь, но важен факт следствия, а не механизм получения связи. Это одна из важн. задач — получение следствий.
+Сами по себе модели не так интересны. Гораздо более важно понятие логического следования. Пусть есть база Г, есть замкнутая формула. Эта флормула называется лог. следствием, если каждая модели Г есть модель для формулы. Логические следствия --- производные знания. Есть причинно-следст. связь, но важен факт следствия, а не механизм получения связи. Это одна из важн. задач --- получение следствий.
 Обозначения
-* Г |= &phi; — &phi;  — логическое следствие Г
+* Г |= &phi; --- &phi; --- логическо следствие Г
-* следствиями пустой БЗ являются общезначимые формулы, поэтому для обозн. общезн. будем исп. |= &phi;
+* следствиями пустой БЗ являютсчя общезначимые формулы, поэтому для обозн. общезн. будем исп. |= &phi;
 Насколько это применимо на практике?
@@ Строка 39: / Строка 39: @@
 Вопрос: любима ли Даша?
-Психологи изучали, с какого этапа человек способен к широкой аналитической деятельности? Ребёнок не может установить причинно-следственные связи до 10—11 лет. Можем ли мы сказать, что ребёнок 8 лет не обладает интеллектом? Нет. Следовательно, можно создать систему, которая может системно реать подобные задачи.
+Психологи изучали, с какого этапа человек способен к широкой аналитической деятельности? Ребёнок не может установить причинно-следственные связи до 10---11 лет. Можем ли мы сказать, что ребёнок 8 лет не обладает интеллектом? Нет. Следовательно, можно создать систему, которая может системно реать подобные задачи.
 Решение. Сформируем алфавит:
@@ Строка 61: / Строка 61: @@
 Теорема о логическом следствии.
-Общезн. формулы — это каналы причинно-следст. связи, по которым передаются знания. Важно определять эти каналы и уметь извлекать из них знания. Следовательно, будем заниматьсч робелмой общезначимости: выяснять, являетсмя ли данная формула общезначимой?
+Общезн. формулы --- это кангалы причинно-следст. связи, по которым передаются знания. Важно определять эти каналы и уметь извлекать из них знания. Следовательно, будем заниматьсч робелмой общезначимости: выяснять, являетсмя ли данная формула общезначимой?
 Проверка выполн./общезн. для любой формулы сводится к проверке выполн./общезн. замкнутой формулы.
@@ Строка 88: / Строка 88: @@
 То есть, разбирая формулу, можно построить контрпример, или показать, что его нет.
-Систематизируем этот способ проверки формул. Попробуем ввести способ проверки, который независит от нашей квалификации — семант. таблицы.
+Систематизируем этот способ проверки формул. Попробуем ввести способ проверки, который независит от нашей квалификации --- семант. таблицы.
 Есть и другие способы (напр., секвенциальный вывод), их мы рассмотрим в 4/4 курса.
@@ Строка 94: / Строка 94: @@
 Лекция 4.
-Представим, что у нас в формуле нет кванторов, то есть это ыактически нечто вроде булевой формулы. Как её проверить? Достаточно перебрать все возм. значния, и для этого хватит аппарата булевой алгебры. С кванторами это не прокатит. Важная сост. лог. вывода — умение пользоваться подстановками. ДАлее мы рассмотрим, каковы правила табл. вывода, преобр. одни таблицы в другие, и по каким законам ведётся игра под называнием табл. вывод. И обоснуем, что если не выигрываем мы, то можем обосновать общезначимость формлы.
+Представим, что у нас в формуле нет кванторов, то есть это ыактически нечто вроде булевой формулы. Как её проверить? Достаточно перебрать все возм. значния, и для этого хватит аппарата булевой алгебры. С кванторами это не прокатит. Важная сост. лог. вывода --- умение пользоваться подстановками. ДАлее мы рассмотрим, каковы правила табл. вывода, преобр. одни таблицы в другие, и по каким законам ведётся игра под называнием табл. вывод. И обоснуем, что если не выигрываем мы, то можем обосновать общезначимость формлы.
-Подстановка — всякое отобр. из множества перем. в множество термов.
+Подстановка --- всякое отобр. из множества перем. в множество термов.
-Область подстановки — те перем., которые изм. в результате подстановки.
+Область подстановки --- те перем., которые изм. в результате подстановки.
 Если изм. конеч. число перем., то подстановка конечна.
@@ Строка 107: / Строка 107: @@
 Мнемон. обозн правил:
-* первая буква — из левой или правой части таблицы правило
+* первая буква --- из левой или правой части таблицы правило
-* вторая — какая основная операция
+* вторая --- какая основная операция
 Вопрос выполнимости таблиц сводится к вопросы выполнимости более простых таблиц.