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

Исчисление высказываний

Правила вывода новых высказываний, основанные на известных высказываниях, имеющих значение «истина», представляют исчисление высказываний (ИВ). В этом случае высказывания, из которых делают вывод новых высказываний, называют посылками, а получаемое новое высказывание – заключением.

Исчисление высказываний – это формальная система вида:

<Q, X, W, P>,

где QÍТÈS – терминальный алфавит системы – множество базовых символов, из которых строятся произвольные выражения системы - ППФ;

Т ={A, B, C, …} - множество пропозициональных переменных,

S = {Ø, &, Ú, ®, «, º, } - множество логических операторов и отношений, включая символ выводимости,

X – множество синтаксических правил, позволяющих формировать ППФ формальной системы:

ППФ::=(F)|(ØF)|(F₁&F₂)|(F₁ÚF₂)|(F₁®F₂)|(F₁«F₂)|(F₁ºF₂)|(F₁,...,F_n) F|, где Ф – это ППФ, причем ПП – это ППФ,

W – аксиомы формальной системы - подмножество ППФ, истинность которых принимается без доказательств, для ИВ это высказывания, имеющие значение истины при любых значениях входящих в состав ПП. К аксиомам относятся также и исходные высказывания, которые всегда истинны,

Р – правила вывода формальной системы. Для ИВ каждое из этих правил описывает, как формировать новое высказывание из исходных и уже построенных высказываний, т.е. это такое отношение между высказываниями, которое позволяет из множества посылок и аксиом делать выводы об истинности заключения.

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

Задание необходимого числа аксиом определяет полноту исчисления, а задание правил вывода – метод исчисления.

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

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

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

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

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

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

1) Логические связки ® и Ø:

(A®(B®A)),

(A®(B®C))®((A®B)®(A®C)),

(ØA®ØB)®((ØA®B)®A).

2) Логические связки Ø, &, Ú, ®:

А1. A®(B®A),

А2. (A®B)®((B®C)®(A®C)),

А3. (A&B)®A,

А4. (A&B)®B,

А5. A®(B®(A&B)),

А6. A®(AÚB),

А7. B®(AÚB),

А8. (A®C)®((B®C)®((AÚB)®C)),

А9. (A®B)®(ØB®ØA),

А10. (A®B)®((A&C)®(B&C)),

А11. (A®B)®((AÚC)®(BÚC)),

А12. ØØA®A

Существует два способа доказательства того, что приведенные ППФ являются аксиомами:

· через таблицы истинности – каждая сложная формула, соответствующая аксиоме, будет принимать только значение «истина»,

· через эквивалентные преобразования – всегда будет получаться значение истины.

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

· П1. Правило введения логической связки &: если формулы A и В истинны, то истинной является их конъюнкция (аксиома А5):

A, В

A&B

· П2. Правило удаления логической связки &: если формула (A&B) истинна, то истинными являются формулы A, B, т.е. (аксиомы А3 и А4):

A&B A&B

A B

· П3. Правило введения логической связки Ú: если хотя бы одна из формул A или B истинна, то истинной является их дизъюнкция, т.е. (аксиомы А6 и А7):

A B

AÚB AÚB

· П4. Правило удаления логической связки Ú: если формула AÚB истинна, то истинными могут быть формулы A (при ложности В) или B (при ложности А), т.е.:

AÚB, ØB AÚB, ØA

A B

· П5. Правило введения логической связки ®: если формула B истинна, то истинной является формула (A ®B) при любом значении A, т.е. (аксиома А1 – «истина из чего угодно»):

B

A®B

· П6. Правило контрапозиции: если формула (A®B) истинна, то истинной является формула (ØB®ØA), т.е. (аксиома А9):

A®B

ØB®ØA

· П7. Правило введения в формулу (A®B) логической связки Ú: если формула (A®B) истинна, то истинной является формула (AÚC)®(BÚC) при любом значении C, т.е. (аксиома А11):

(A®B)

(AÚC)®(BÚC)

· П8. Правило введения в формулу (A®B) логической связки &: если формула (A®B) истинна, то истинной является формула (A&C)®(B&C) при любом значении C, т.е. (аксиома А10):

(A®B)

(A&C)®(B&C)

· П9. Правило силлогизма: если формулы (A®B) и (B®C) истинны, то истинной является формула (A®C), т.е. (аксиома А2):

(A®B), (B®C)

(A®C)

· П10. Правило введения логической связки «: если формулы (A®B) и (B®A) истинны, то истинной является формула (A«B), т.е.:

(A®B), (B®A)

(A«B)

· П11. Правило удаления логической связки «: если формула (A«B) истинна, то истинными являются формулы (A®B) и (B®A), т.е.:

(A«B) (A«B)

(A®B) (B®A)

· П12. Правило объединения формул (A®C) и (B®C): если формулы (A®C) и (B®C) истинны, то истинной является формула ((AÚB)®C), т.е. (аксиома А8):

(A®C), (B®C)

((AÚB)®C)

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

Дата добавления: 2014-01-04