1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование icon

1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование


Название1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование
Размер21 Kb.
ТипДокументы

1. МЛ Формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование. Р – пропозициональная переменная.

х, у – предметные переменные.

, &,, - связки. ,  - кванторы.

Фомулой является выражение вида:

1. Р(х1,…х2) – атомарная формула

2. Если А и В формулы, то (А&В), (АВ), (АВ), А, хА(х), хА(х) –формулы

3.Ничто, кроме определенного в 1. и 2. не является формулой.

Интерпретация формулы – придание переменным конкретных значений и задание правил вычисления значений для связок

Интерпретация - это пара (М, ), где М – произвольное множество, а  - некоторое отображение, которое каждому предикатному символу ставит в соответствие отношение, заданное на множестве М, а каждой предметной ставит в соотношение элемент из множества М.

хА(х) истинно тогда и только тогда когда А(х) истинно для всех значений х из всей области интерпритации.

хА(х) истинно, если А(х) истинно при некотором значении х.

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

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

Формула называется выполнимой, если она истина хотя бы в одной интерпритации.

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

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

Основные эквивалентности:

1)(АВ)С)А(ВС)

2)А&BB&A

3)A&)(ВС)(A&B)(A&C)

4)ABAB

5)AA

6)(A&B)AB

7)xyA(x,y) )yxA(x,y)

8) xyA(x,y) ) yxA(x,y)

9)xA(x)xA(x)

10) xA(x)  xA(x)

11)x(A(x)&B(x))xA(x)&xB(x)

12) x(A(x) B(x)) xA(x)  xB(x)

13) x(AB(x))A xB(x)

14) x(A &B(x)) A & xB(x)

15)xA(x)yA(y)

Для всякой формулы существует эквивалентная ей предваренная н.ф. – такая, где ни один квантор не находится в области действия ни одной пропозициональной связки(все кванторы снаружи).

КНФ – конъюнкция нескольких дизъюнкиций

ДНФ – дизъюнкция нескольких конъюнкций

Из формул А1,…Аn логически следует B (А1,…Аn |= B), если во всякой интерпритации, в которой А1,…Аn истинны, формула В токже истина. А1,…Аn – допущения.

Свойства |=:

1) Если АГ, то Г|=А(Г – список формул)

2) Если Г|=А, то В,Г|=А

3) Если Г|=А, то Г’|=А, где Г’ получено из Г сокращением повторяющихся формул

4) Если Г|=А, то Г’|=А, где Г’ получено из Г перестановкой формул

5) Если Г|=А и АД|=В, то Г,Д|=В

^ 2. МЛ Система аксиом исчисления предикатов. Формальные доказательства, формальный вывод. Свойства выводимости. Правила введения и удаления логических связок.

Аксиомы: 1) А(ВА)

2)(А(ВС)) ((АВ) (АС))

3)А(ВА&В)

4)а)А&ВА б)А&ВВ

5)а)ААВ б)ВАВ

6)(АС) (ВС) (АВС)

7)(АВ) ((АВ) А)

8)АА

9)хА(х) А(у)

10)А(у) хА(х)

Правила вывода:1) МР: ^ А АВ

В

2)-правило: С  А(х)

СхА(х)

3)-правило: А(х)  С

хА(х)С

Формальное доказательство – конечная последовательность формул, каждая из которых является либо аксиомой, либо получена из предшествующих формул с использованием одного из правил вывода.

Формальным выводом из допущений А1,…Аn называется конечная последовательность формул, каждая из которых либо является аксиомой, либо допущением из списка А1,…Аn, либо получена из предшествующих формул по одному из правил вывода.

Формальное доказательство – вывод, в котором нет допущений.

Свойства |-:

1) Если АГ, то Г|-А(Г – список формул)

2) Если Г|-А, то В,Г|-А

3) Если Г|-А, то Г’|-А, где Г’ получено из Г сокращением повторяющихся формул

4) Если Г|-А, то Г’|-А, где Г’ получено из Г перестановкой формул

5) Если Г|-А и АД|-В, то Г,Д|-В

Введение : Если Г,А|-В, то Г|-АВ

Удаление: А,АВ|-В

Введение &: А,В|-А&В

Удаление &: А&В|-А, А&В|-В

Введение : А|-АВ, В|-АВ

Удаление : Г, АС и Г,ВС, то Г,АВ|-С

Введение : Г,АВ и Г,АВ, то Г|-А

Удаление : А|-А

^ 3. МЛ Полнота и непротиворечивость исчисления предикатов.

Формальная теория Т называется синтаксически непротиворечивой, если не существует такой формулы F, что F и F являются теоремами теории Т, т.е. в Т невыводимыми являются одновременно формула и ее отрицание.

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

Идея док-ва непротиворечивости ИП: Все аксиомы общезначимы. Покажем, что применение правил вывода ИП(modes ponens, -правило, -правило) сохраняют общезначимость.

Правило MP. Допустим, что ╞ F→G и ╞ F. Докажем, что тогда ╞ G Возьмем любую подстановку а констант.
Тогда, по условию, каждое из высказываний F(a) →G(a) и F(a), получаемых соответственно из формул F → G и F в результате подстановки предметных констант а, будет истинным. Тогда истинным будет и высказывание G(a), т.е. это и означает, что ╞ G.

-правило. Допустим, что╞ G(y) → F(x, у), где х не входит свободно в формулу G, а у обозначает все свободные предметные переменные в формулах F и G (в F — кроме х). Тогда сделанное допущение означает, что для любых элементов a,

b высказывание G(b) → F (а, b) истинно. Рассмотрим теперь высказывание G(b) →(x) F(x, b), и покажем, что оно истинно при любом b. В самом деле, если G(b) ложно, то рассматриваемое высказывание истинно. Если же G(b) истинно, то, по отмеченному выше, истинным будет и высказывание F(a, b). Поскольку оно будет истинным при любом а, то отсюда вытекает истинность для таких b высказывания (x) F(x, b). Это, в свою очередь, влечет истинность высказывания G(b) →(x) F(x, b) для тех b, для которых G(b) истинно. Итак, высказывание G(b) →(x) F(x, b) истинно для любых b. Это и означает, что ╞G(b) →(x) F(x, b).

-правило. Докажем, что если ╞F(x) →G , то ╞xF(x) →G. Если G истино, то высказывание xF(x) →G истинно. Пусть G ложно, тогда если предположим, что xF(x) истина, т.е. F(x0)=t, но в таком случае получаем противоречие с общезначимостью высказывания F(x) →G. Значит, в таком случае xF(x) ложно. Итак, xF(x) →G истинно при любом значении истинности высказывания G. Это и означает, ╞xF(x) →G.

Т.о., получаем что если формула ИП доказуемая, то она общезначима (├F, то╞ F). Предположим, что ФИП противоречиво. Значит, найдется такая формула F, что F и F будут теоремами ФИП. Тогда формулы F и F будут общезначимыми, что невозможно на основании определения

общезначимости. Значит, предположение было верно и ФИП непротиворечиво, чтд.

Формальная теория называется полной, если в ней доказуемы все общезначимые формулы (т.е. ╞ F, то ├F)

ФИП полна. В основе доказательства лежит теорема Геделя, которая не рассматривалась в рамках нашего курса.

^ 4. МЛ Понятие алгоритма. Тезис Тьюринга. Понятие об алгоритмически неразрешимых проблемах. Неразрешимость проблемы самоприменимости для машин Тьюринга.

Алгоритм – точное предписание о выполнении определенной последовательности действий, ведущих от вирируемых исходных данных к окончательным результатам.

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

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

Машина Тьюринга – это математическая (воображаемая) машина. Представляется виде автоматического устройства. В каждый момент времени управляющее устройство обозревает содержимое одной ячейки протягиваемой через устройство бесконечной ленты, изменяя или нет содержимое в этой ячейке, и переходит в новое состояние и к обозревание ячейки справа или слева. Машина Тьюринга располагает конечным числом символов – внешний алфавит А={a0, a1,…, am} и конечным числом внутренних состояний

Q={q0,…,qn}. Работа машины Тьюринга определяется программой состоящей из команд следующего вида: qiaj→qkalR(L,N)

Существует функция, не вычислимая по Тьюрингу, т. е. не вычислимая ни на одной машине Тьюринга.

Доказательство. Функции, о которых идет речь, представляют собой функции, заданные и принимающие значения в множестве слов в алфавите А1 = {1}. Ясно, что множество слов в алфавите А1 = {1} счетно. Следовательно, рассматривается множество всех функций, заданных на счетном множестве и принимающих значения в счетном же множестве. Как известно, это множество имеет мощность континуума. С другой стороны, поскольку множество всевозможных машин Тьюринга, перенумеровав их, счетно, это и множество функций, вычислимых по Тьюрингу, также счетно. Континуальная мощность строго больше счетной. Следовательно, существуют функции, не вычислимые по Тьюрингу.

Проблема распознавания самоприменимых машин Тьюринга алгоритмически не разрешима.

Доказательство. Допустим противное, т.е. алгоритм для такого распознавания существует. Значит, на основании тезиса Тьюринга, существует машина Тьюринга, реализующая

данный алгоритм. Пусть  — такая машина. На ее ленту заносится соответствующим образом закодированная программа той или иной машины Тьюринга. При этом, если машина самоприменима, то занесенное слово перерабатывается машиной  в какой-то символ  (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости). Если же машина несамоприменима, то занесенное на ленту слово, кодирующее ее программу, перерабатывается машиной  в какой-то символ  (имеющий смысл отрицательного ответа). Рассмотрим теперь такую машину Тьюринга 1 которая попрежнему перерабатывает несамоприменимые коды в , а к самоприменимым кодам машина 1 уже не применима. Такая машина получается из машины , если следующим образом слегка изменить ее программу: после появления символа  вместо остановки машина должна неограниченно его повторять. Итак, 1 применима ко всякому несамоприменимому коду
(вырабатывая символ ) и не применима к самоприменимым кодам. Это приводит к противоречию, потому что такая машина не может быть ни самоприменимой, ни несамоприменимой. В самом деле, если машина

1 самоприменима, то она не применима к своему коду. Значит, машина несамоприменима. Противоречие. С другой стороны, если машина 1 несамоприменима, то ее код должен перерабатываться самой машиной 1 в символ . Значит, 1 применима к собственному коду, т.е. самоприменима - противоречие, чтд.























































Похожие:

1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование icon1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование
Мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое...
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование icon1. дм функции алгебры логики. Реализация функций формулами. Канонические нормальные формы представления функций
Ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн ия ф-ии f на любом наборе переменных принадлежат E2
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование iconЭлементы алгебры логики
Для описания логики функционирования аппаратных и программных средств компьютера используется алгебра логики или булева алгебра
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование iconТема : Основные понятия математической логики
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование iconТема : Основные понятия математической логики
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование iconНаука о правильности мышления. Предметом логики являются
Этап начало 20 века. Значение логики: Логика развивает логическое мышление человека. Она позволяет глубже отражать окружающий мир,...
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование iconУчебник логики Глава I определение и задачи логики определение логики
То мышление, при помощи которого достигается истина, должно быть названо правильным мышлением. Таким образом, логика может быть определена...
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование iconСистемы обеспечения безопасности на Калининской аэс
Пример использования формулы (формулы должны выполняться в ms equation/Mathtype)
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование iconПредмет и основные термины логики Понятие, суждение и умозаключение как формы мышления
Простой категорический силлогизм. Правила посылок, правила терминов и правила фигур
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование iconА. О. Маковельский история логики книга
Во второй части исследуются логические теории эпохи феодального общества, в третьей части—логические концепции Нового времени (Декарт,...
1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование icon10. кл. Тема: Решение задач на определение формулы вещества
Цель урока: Научится решать задачи на определение формулы вещества по продуктам сгорания
Вы можете разместить ссылку на наш сайт:
Документы


При копировании материала укажите ссылку ©ignorik.ru 2015

контакты
Документы