Geum.ru

Основы логического программирования Исчисление высказываний

Вид материалаДокументы

Содержание


Тождественно истинные формулы (тавтологии)
Законы де Моргана
Закон контрапозиции
Modus ponens
Логика первого порядка
0,1} (или «ложь
Алфавит логики первого порядка
Подобный материал:
Основы логического программирования

Исчисление высказываний (пропозициональная логика) — это формальная теория, основным объектом которой служит понятие логического высказывания. С точки зрения выразительности, её можно охарактеризовать как классическую логику нулевого порядка.

Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, — и (пропозициональная) формула, определяемая индуктивно следующим образом:
  • Если P — пропозициональная переменная, то — формула.
  • Если A — формула, то — формула.
  • Если A и B — формулы, то , и — формулы.
  • Других соглашений нет.

Знаки и (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками.

Приняты следующие соглашения о скобках:
  • Если опущены внешние скобки, то они восстанавливаются.
  • Если рядом стоят две конъюнкции или дизъюнкции (например, ), то в скобки заключается сначала самая левая часть.
  • Если рядом стоят разные связки, то скобки расставляются согласно приоритету: и .

Оценкой пропозициональных переменных называется функция из множества всех пропозициональных переменных в множество {0,1} (множество истинностных значений). Основной задачей логики высказываний является установление истинностного значения формулы, определяемое индуктивно с использованием таблиц истинности.

Оценка отрицания задаётся таблицей:










Значение двуместных логических связок , и :








0
0
1
0
0

0
1
1
0
1

1
0
0
0
1

1
1
1
1
1

Тождественно истинные формулы (тавтологии)


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

Законы де Моргана:

1) ;

2) ;

Закон контрапозиции:

;

Законы поглощения:

1) ;

2) ;

Законы дистрибутивности:

1) ;

2) .


Вариантом аксиоматизации логики высказываний является следующая система аксиом:

;

;

;

;

;

;

;

;

;

;

.

Единственное правило вывода ( Modus ponens):




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


Все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

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

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


Предикат (n-местный, или n-арный) — это функция с множеством значений { 0,1} (или «ложь» и «истина»)


С каждым функциональным и предикатным символом связана арность, то есть число возможных аргументов. Допускаются как функциональные так и предикатные символы арности 0. Первые выделяют в отдельное множество констант.


Кроме того используются следующие дополнительные символы
  • Символы переменных (обычно x,y,z,x1,y1,z1,x2,y2,z2, и т. д.),
  • Пропозициональные связки: ,
  • Кванторы: всеобщности и существования ,
  • Служебные символы: скобки и запятая.

Перечисленные символы вместе с символами из и образуют Алфавит логики первого порядка.


Более сложные конструкции определяются индуктивно:
  • Терм есть символ переменной, либо имеет вид , где f — функциональный символ арности n, а — термы.
  • Атом имеет вид , где p — предикатный символ арности n, а — термы.
  • Формула — это либо атом, либо одна из следующих конструкций: , где F,F1,F2 — формулы, а x — переменная.

Переменная x называется связанной в формуле F, если F имеет вид либо , или же представима в одной из форм , причем x уже связанна в H, F1 и F2.

Если x не связанна в F, ее называют свободной в F.

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

Теорией первого порядка называют любое множество предложений.

Система логических аксиом логики первого порядка состоит из аксиом исчисления высказываний дополненной двумя новыми аксиомами:
  • ,
  • ,

где A[t / x] — формула, полученная в результате подстановки терма t вместо переменной x в формуле A.

Правил вывода:


  • Правило обобщения (GEN):



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

Полнота - означает, что для любой формулы выводима либо она сама, либо ее отрицание (теорема Гёделя о полноте - устанавливает эквивалентность понятий доказуемости и общезначимости).

Непротиворечивость - означает, что ни одна формула не может быть выведена одновременно со своим отрицанием.

Пример формализации утверждений ЕЯ в логике первого порядка. Возьмем рассуждение «Каждый студент молод. Иванов — студент. Следовательно, Иванов молод». Обозначим «x есть студент» через СТУДЕНТ(x) и «x молод» через МОЛОД(x). Тогда утверждение «каждый студент молод» может быть представлено формулой: x(СТУДЕНТ(x) → МОЛОД(x)) утверждение «Иванов — студент» формулой СТУДЕНТ(Иванов), и «Иванов молод» формулой МОЛОД(Иванов). Утверждение может быть записано формулой:

(x(СТУДЕНТ(x) → МОЛОД(x)) СТУДЕНТ(Иванов)) → МОЛОД(Иванов)