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

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

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

Система аксиом исчисления высказываний - Инвестирование -  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

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