Сделай Сам Свою Работу на 5

Исчисление высказываний (ИВ). Проблемы разрешимости формул. Таблицы истинности.





Всё множество правильно построенных формул можно разбить на 3 класса: тождественно истинные, тождественно ложные и выполнимые.

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

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

Выполнимые формулы – это сложные высказывания, которые принимают значения true или false для различных наборов пропозициональных переменных.

Отнесение формулы к тому или иному классу не имеет единого алгоритма, поэтому эта проблема получила название проблемы разрешимости ИВ.

Это можно определить по таблице истинности.

Исчисление высказываний. Метод дедуктивного вывода. Modus ponens.

Выводимость формулы B из множества формул F1; F2; … Fn со всей очевидностью равносильна доказательству теоремы ├─ (F1 & F2 & … Fn ® B), т. е. доказательству того, что B логически следует (имплицирует) из конъюнкции всех посылок (F1 & F2 & … Fn).



Т. о., если каждая Fi имеет значение true, то (F1 & F2 & … Fn) также имеет значение true, а если (F1 & F2 & … Fn) имеет значение true, то B также имеет значение true, что и требовалось доказать.

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

1) ├─ (F1 & F2 & … & Fn ® B)

2) ├─ (ù(F1 & F2 & … & Fn) Ú B)

3) ├─ (ùF1 Ú ùF2 Ú … Ú ùFn Ú B)

4) ├─ (ùF1 Ú ùF2 Ú … Ú (Fn ® B))


5) ├─ (F1 ® (F2 ® … ® (Fn ® B)…)

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

Удаление импликации. Modus ponens:

F1; (F1 ® F2)

F2

Остальные аксиомы см. вопрос 8.

Исчисление высказываний. Метод дедуктивного вывода. Modus tollens.

см. вопрос 7.

Удаление импликации. Modus tollens:

ùF2; (F1 ® F2)

ùF1

Остальные аксиомы см. вопрос 8.

Исчисление высказываний. Основные аксиомы вывода.

1) введение конъюнкции _F1; F2_ (F1 & F2)
2) удаление конъюнкции (F1& F2)(F1& F2) F1 ; F2
3) введение дизъюнкции ___F1___ ___F2___ (F1 Ú F2) ; (F1 Ú F2)
4) введение дизъюнкции ùF1; (F1 Ú F2)ùF2; (F1 Ú F2) F2 ; F1
5) введение импликации:  
а) “истина из чего угодно” ___F1___ F2 ® F1
б) “из ложного что угодно” ___ùF1___ F1 ® F2
в) закон силлогизма (F1 ® F2); (F2 ® F3) (F1 ® F3)
г) закон контрапозиции _(F1 ® F2)_ (ùF2 ® ùF1)
6) удаление импликации:  
а) modus ponens F1; (F1 ® F2) F2
б) modus tollens ùF2; (F1 ® F2) ùF1
7) введение эквиваленции (F1 ® F2); (F2 ® F1) (F1 « F2)
8) удаление эквиваленции (F1 « F2)(F1 « F2) (F1 ® F2) ; (F2 ® F1)

Исчисление высказываний. Принцип резолюции.



Выводимость формулы B из множества посылок F1; F2; … Fn равносильна доказательству теоремы ├─ (F1 & F2 & … & Fn ® B). Используя правила эквивалентных преобразований алгебры высказываний, формулу теоремы можно преобразовать так: ├─ (F1 & F2 & … & Fn ® B) = (ù(F1 & F2 & … & Fn) Ú B) = ù(F1 & F2 & … & Fn & ùB). Т. е. заключение B является логическим следствием посылок F1; F2; … Fn т. и только т., когда формула теоремы (F1 & F2 & … & Fn & ùB) противоречива, т. е. имеет значение false. Сведения доказательства теоремы к противоречию на формуле, представленной в КНФ, составляет основу принципа резолюции.

Для вывода по принципу резолюции необходимо:

1) допустить отрицание заключения, т. е. ùB (известный способ доказательства от противного);

2) привести все формулы (посылки и заключение) к КНФ;

3) выписать множество дизъюнктов S = {D1; D2; … Dk};

4) выполнить анализ всех пар множества S по правилу: “если существуют контрарные пары, один элемент которой Di содержит литеру A, а другой элемент Dj – ùA, то соединить эту пару логической связкой дизъюнкции (Di Ú Dj), исключив контрарные литеры A и ùA: в результате этой операции получен новый дизъюнкт – резольвента, которую нужно включить в множество исходных дизъюнктов (п. 3); продолжая процедуру соединения дизъюнкт, устранить все контрарные пары; если в результате соединения всех дизъюнктов и резольвент будет получена пустая резольвента - , то вывод окончен и доказательство подтвердило противоречие.



Исчисление высказываний. Расширение принципа резолюции (линейность и упорядоченность литер в дизъюнкте).

см. вопрос 9.

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

Следует обратить внимание, что использование закона дистрибутивности ведёт к “разбуханию” формул, что разрушает их структуру и может привести к неверным заключениям в принципе резолюции. Более того учёт невостребованных посылок также не обеспечивает пустой резольвенты.

Для усиления принципа резолюции вводят упорядоченные дизъюнкты по их вхождению в резольвенты и учёт информации об удаляемых контрарных литерах для возможного их восстановления в последующих склеиваниях.

рис. 10.1. Линейная резолюция.

Исчисление предикатов. Основные понятия.

В то время, как исчисление высказываний проявляет интерес только к внешним связям простых повествовательных предложений, исчисление предикатов проникает внутрь предложения, исследуя связи между его составными частями.

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

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

Множество предметов, фактов, явлений, событий или процессов, описываемых одним понятием, называют объёмом понятия.

Содержание понятия обратно пропорционально объёму понятия.

Логическую функцию, которая позволяет раскрыть признаки предмета, факта, явления, события или процесса или признаки отношений между ними называют предикатом (лат. predicatum – логическое сказуемое). Для обозначения предиката используют символ P.

Если логическая функция содержит один аргумент, то говорят, что область определения предиката задана объёмом одного понятия. Если логическая функция содержит n аргументов, то говорят, что область предиката задана объёмами n понятий. Область определения принято обозначать символом M.

Аргументы логической функции называют предметными переменными и обозначают латинскими буквами x, y, … . Если предметной переменной придать значение конкретного предмета, факт, явления, события или процесса, то её называют предметной постоянной. Предметные постоянные обозначают строчными буквами латинского алфавита a, b, c, … .

Предикат с n аргументами называют n-местными. Одноместный предикат, как правило, определяет атрибутивное суждение о наличии или отсутствии отношений между предметами. Область определения предиката чаще всего обозначают так Pn или Pn(x), подчёркивая число аргументов n.

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

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

Если в области определения предиката задана n-местная функция, то ей соответствует (n + 1)-местный предикат, сравнивающий запись и значение функции (“быть равным”, “быть эквивалентным”, “быть больше” и т. п.). Имена элементов области определения предиката (предметные переменные, предметные постоянные и элементы, заданные функциональными отношениями) получили название терм – t. Для указанных функциональных отношений используют функциональные символы f, а для обозначения числа аргументов этих отношений используют верхние индексы, т. е. fn(x). Предикат, аргументами которого являются термы получил название формулы F = Pn(t1; t2;… tn).

Суждение, в котором утверждается или отрицается наличие каких-либо признаков у части предметных переменных предиката, называют частным суждением. Как правило, эти суждения на естественном языке отражают словами “некоторые”, “часть” и т. п. Для формализации этих суждений используют логическую операцию, ограничивающую область определения предиката. Оператор этой логической функции получил названия квантора существования. Этот оператор имеет обозначение $x. Использование квантора существования связывает предметную переменную ограниченной областью определения предиката. Выражение предиката записывают после квантора существования в круглых скобках $x(Pn(x)). На естественном языке эта формальная запись означает: “существуют такие элементы x, что Pn(x) истинно (или ложно).

Суждение, в котором утверждается или отрицается наличие каких-либо признаков или отношений для всех предметов области определения предиката, называют общими суждениями. Как правило, эти суждения в естественном языке отмечают словами “все”, “каждый”, “любой” и т. п. Для формализации этих суждений используют логическую операцию, оценивающую всю область определения предиката. Оператор этой логической операции получил название квантора общности. Этот оператор обозначают так: "x. Использование квантора общности связывает предметную переменную предиката и формирует сложное высказывание, принимающее значение true или false для конкретного значения xi = ai только в области действия квантора "x. Выражение предиката записывают после квантора общности в круглых скобках "x(Pn(x)). На естественном языке эта формальная запись означает: “для всех x истинно (или ложно) значение P(x)”.

Квантор общности или существования с предикатом, аргументами которого являются термы, называют также формулой F, т. е. F = "t(Pn(t)) или F = $t(Pn(t)). Если предметная переменная x предиката P(x) находится в области действия квантора, то её называют связной переменной формулы, в противном случае – свободной переменной.

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

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.