Поделиться Поделиться

Система аксиом исчисления высказываний

Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:

Система аксиом исчисления высказываний - Инвестирование - 1 ;

Система аксиом исчисления высказываний - Инвестирование - 2

Система аксиом исчисления высказываний - Инвестирование - 3 ;

Система аксиом исчисления высказываний - Инвестирование - 4 ;

Система аксиом исчисления высказываний - Инвестирование - 5 ;

Система аксиом исчисления высказываний - Инвестирование - 6 ;

Система аксиом исчисления высказываний - Инвестирование - 7 ;

Система аксиом исчисления высказываний - Инвестирование - 8

Система аксиом исчисления высказываний - Инвестирование - 9 ;

Система аксиом исчисления высказываний - Инвестирование - 10 ;

Система аксиом исчисления высказываний - Инвестирование - 11 .

вместе с единственным правилом:

Система аксиом исчисления высказываний - Инвестирование - 12 (Modus ponens)

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

18. Правило вывода Modus ponens. Modus ponens(правило заключения): если A и A→B — выводимые формулы, то B также выводима.

Форма записи: Система аксиом исчисления высказываний - Инвестирование - 13 , где A, B — любые формулы.

Modus ponens— правило вывода в исчислении высказываний. Является частным случаем правила резолюций. С помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

Понятие вывода.

Определение. Выводом из конечной совокупности формул H называется всякая конечная последовательность формул Система аксиом исчисления высказываний - Инвестирование - 14 , всякий член которой удовлетворяет одному из следующих трех условий: 1) является одной из формул совокупности H; 2) является доказуемой формулой; 3) получается по правилу заключения из двух любых предшествующих членов последовательности Система аксиом исчисления высказываний - Инвестирование - 15 .

Свойства вывода:

1) Всякий начальный отрезок вывода из совокупности H есть вывод из H.

2) Если между двумя соседними членами вывода из H вставить некоторый вывод из H, то полученная новая последовательность формул будет выводом из H.

3) Всякий член вывода из совокупности H, является формулой, выводимой из H.

Следствие. Всякий вывод из H является выводом его последней формулы.

4) Если Система аксиом исчисления высказываний - Инвестирование - 16 , то всякий вывод из H является из W.

5) Для того, чтобы формула B была выводима из совокупности H, необходимо и достаточно, чтобы существовал вывод этой формулы из H.

Понятие вывода

Система аксиом исчисления высказываний - Инвестирование - 17

Система аксиом исчисления высказываний - Инвестирование - 18

Система аксиом исчисления высказываний - Инвестирование - 19

Система аксиом исчисления высказываний - Инвестирование - 20

Система аксиом исчисления высказываний - Инвестирование - 21

ками вывода. Свойства:

Система аксиом исчисления высказываний - Инвестирование - 22

23. Теорема о дедукции Система аксиом исчисления высказываний - Инвестирование - 23

Лемма Кальмара

Система аксиом исчисления высказываний - Инвестирование - 24

Система аксиом исчисления высказываний - Инвестирование - 25

Система аксиом исчисления высказываний - Инвестирование - 26

29 .Теорема полноты исчисления высказывний.

Система аксиом исчисления высказываний - Инвестирование - 27

Система аксиом исчисления высказываний - Инвестирование - 28

Формулы исчисления предикатов

Система аксиом исчисления высказываний - Инвестирование - 29

Система аксиом исчисления высказываний - Инвестирование - 30

Система аксиом исчисления высказываний - Инвестирование - 31

Система аксиом исчисления высказываний - Инвестирование - 32

Система аксиом исчисления высказываний - Инвестирование - 33

Сигнатура, алгебры и модели.

Сигнатурой называется набор Σ = (R,F,C,ρ) состоящий из множеств:

R — множество символов для отношений (предикатов),

F — множество функциональных символов,

C — множество символов констант

и функции ρ — сопоставляющей элементам R и F их арность. Пример σ=<+,*,<,=,1>

Система аксиом исчисления высказываний - Инвестирование - 34

Система аксиом исчисления высказываний - Инвестирование - 35

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

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

Символы переменных (обычно Система аксиом исчисления высказываний - Инвестирование - 38 и т. д.),

Пропозициональные связки: Система аксиом исчисления высказываний - Инвестирование - 39 ,

Кванторы: всеобщности Система аксиом исчисления высказываний - Инвестирование - 40 и существования Система аксиом исчисления высказываний - Инвестирование - 41 ,

Служебные символы: скобки и запятая.

Перечисленные символы вместе с символами из Система аксиом исчисления высказываний - Инвестирование - 37 и Система аксиом исчисления высказываний - Инвестирование - 43 образуют Алфавит логики первого порядка. Более сложные конструкции определяются индуктивно:

Терм есть символ переменной, либо имеет вид Система аксиом исчисления высказываний - Инвестирование - 44 , где Система аксиом исчисления высказываний - Инвестирование - 45 — функциональный символ арности Система аксиом исчисления высказываний - Инвестирование - 46 , а Система аксиом исчисления высказываний - Инвестирование - 47 — термы.

Атом имеет вид Система аксиом исчисления высказываний - Инвестирование - 48 , где Система аксиом исчисления высказываний - Инвестирование - 49 — предикатный символ арности Система аксиом исчисления высказываний - Инвестирование - 46 , а Система аксиом исчисления высказываний - Инвестирование - 51 — термы.

Формула — это либо атом, либо одна из следующих конструкций: Система аксиом исчисления высказываний - Инвестирование - 52 , где Система аксиом исчисления высказываний - Инвестирование - 53 — формулы, а Система аксиом исчисления высказываний - Инвестирование - 54 — переменная.

Переменная Система аксиом исчисления высказываний - Инвестирование - 55 называется связанной в формуле Система аксиом исчисления высказываний - Инвестирование - 56 , если Система аксиом исчисления высказываний - Инвестирование - 57 имеет вид Система аксиом исчисления высказываний - Инвестирование - 58 либо Система аксиом исчисления высказываний - Инвестирование - 59 , или же представима в одной из форм Система аксиом исчисления высказываний - Инвестирование - 60 , причем Система аксиом исчисления высказываний - Инвестирование - 54 уже связанна в Система аксиом исчисления высказываний - Инвестирование - 62 , Система аксиом исчисления высказываний - Инвестирование - 63 и Система аксиом исчисления высказываний - Инвестирование - 64 . Если Система аксиом исчисления высказываний - Инвестирование - 65 не связанна в Система аксиом исчисления высказываний - Инвестирование - 66 , ее называют свободной в Система аксиом исчисления высказываний - Инвестирование - 57 . Формулу без свободных переменных называют замкнутой формулой, или предложением. Теорией первого порядка называют любое множество предложений

Система аксиом исчисления предикатов.

Система аксиом исчисления высказываний - Инвестирование - 68 Система аксиом исчисления высказываний - Инвестирование - 69

← Предыдущая страница | Следующая страница →