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

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


1. Формальное определение

Исчислением высказываний есть формальная система \ Mathcal {L} = \ mathcal {L} \ left (\ Alpha, \ \ Omega, \ \ Zeta, \ \ Iota \ right) , Где:

\ Omega = \ Omega_0 \ cup \ Omega_1 \ cup \ ldots \ cup \ Omega_j \ cup \ ldots \ cup \ Omega_m.
В этом разбиении \ \ Omega_j есть множество операторов арности j (Также обозначено \ Omega_0 = \ {0, 1 \}. \, \! ).
Чаще всего используются операторы:
\ Omega_1 = \ {\ lnot \}
\ Omega_2 \ subseteq \ {\ land, \ lor, \ rightarrow, \ leftrightarrow \}.
  • Множество \ \ Zeta является конечным множеством правил вывода, позволяющие получать одни формулы других.
  • Множество \ \ Iota является конечным множеством, элементы которой называются аксиомами. В отдельных примерах данная множество может быть пустым.

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

  1. все элементы множества \ \ Alpha являются формулами;
  2. если \ P_1, p_2, \ ldots, p_j являются формулами и f \ in \ Omega_j , Тогда \ Left (f (p_1, p_2, \ ldots, p_j) \ right) тоже является формулой.
  3. других формул, чем построенные по правилам 1 и 2 нет.

1.1. Вывод формул и теорем

Пусть \ Sigma \; некоторое множество формул \ Mathcal {L} , А A - Некоторая заданная формула говорится, что формула A выводится из множества формул \ Sigma \; (Обозначается \ Sigma \ vdash A ), Если существует такая конечная последовательность формул A_1, A_2 \ ldots A_n = A где для каждой формулы A_i :

  1. A_i является аксиомой, или
  2. A_i принадлежит множеству \ Sigma \; или
  3. A_i выводится из предыдущих формул последовательности с помощью одного из правил вывода.

Если при этом множество \ Sigma \; - Пустая (формула A выводится с помощью аксиом и правил вывода), то формула A называется теоремой (для этого используется обозначение \ Vdash A ).


2. Примеры аксиоматики

2.1. Пример 1

  1. Алфавит (элементы множества \ Alpha ) Исчисления высказываний состоит из элементарных высказываний (пропозициональных переменных): a, b, c, d, \ dots, x, y, z (Возможно с индексами), логическими операциями являются \ Lor, \ land, \ lnot, \ rightarrow, .
  2. Понятие формулы определяется аналогично алгебре высказываний.
    1. все пропозициональные переменные и элементарные высказывания являются формулами;
    2. если A и B - формулы, то выражения (слова) (A \ lor B), (A \ land B), (\ lnot A), (A \ rightarrow B) также являются формулами;
    3. других формул, чем построенные по правилам 2.1 и 2.2 нет.

2.1.1. Аксиомы

В многочисленные высказываний определяют такие схемы аксиом :

  1. A \ rightarrow (B \ rightarrow A)
  2. (A \ rightarrow B) \ rightarrow ((A \ rightarrow (B \ rightarrow C)) \ rightarrow (A \ rightarrow C))
  3. (A \ land B) \ rightarrow A
  4. (A \ land B) \ rightarrow B
  5. (A \ rightarrow B) \ rightarrow ((A \ rightarrow C) \ rightarrow (A \ rightarrow (B \ land C)))
  6. A \ rightarrow (A \ lor B)
  7. B \ rightarrow (A \ lor B)
  8. (A \ rightarrow C) \ rightarrow ((B \ rightarrow C) \ rightarrow ((A \ lor B) \ rightarrow C))
  9. (A \ rightarrow \ lnot B) \ rightarrow (B \ rightarrow \ lnot A)
  10. \ Lnot \ lnot A \ rightarrow A

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

\ Frac {A \ rightarrow B, A} {B} ( Modus ponens)

В данных схемах аксиом и правила вывода символы A, B, C можно замещать всеми допустимыми формулами, после чего и получаются конкретные аксиомы.


2.1.2. Пример вывода теоремы

Пользуясь представленными аксиомами и правилом вывода покажем, что ( D \ rightarrow D ) Является теоремой в данной формальной системе для любой формулы D .

Пример вывода
Номер Формула Способ получения
1 (D \ rightarrow (D \ rightarrow D)) \ rightarrow ((D \ rightarrow ((D \ rightarrow D) \ rightarrow D)) \ rightarrow (D \ rightarrow D)) Аксиома 2 из заменой A, B, C \, на D, D \ rightarrow D, D соответственно
2 (D \ rightarrow (D \ rightarrow D)) аксиома 1 (замена A, B \, на D \, )
3 ((D \ rightarrow ((D \ rightarrow D) \ rightarrow D)) \ rightarrow (D \ rightarrow D)) 1, 2 и modus ponens.
4 ((D \ rightarrow ((D \ rightarrow D) \ rightarrow D)) аксиома 1 (замена A, B \, на D, D \ rightarrow D соответственно)
5 D \ rightarrow D 3, 4 и modus ponens.

2.2. Пример 2 (аксиомы Лукасевича)

  1. Алфавит (элементы множества \ Alpha ) Исчисления высказываний состоит из элементарных высказываний (пропозициональных переменных): a, b, c, d, \ dots, x, y, z (Возможно с индексами), логическими операциями являются \ Lnot, \ rightarrow, .
  2. Понятие формулы определяется аналогично алгебре высказываний.
    1. все пропозициональные переменные и элементарные высказывания являются формулами;
    2. если A и B - формулы, то выражения (слова) (\ Lnot A), (A \ rightarrow B) также являются формулами;
    3. других формул, чем построенные по правилам 2.1 и 2.2 нет.

Следующую простую систему аксиом предложил польский логик Ян Лукасевич :

  1. (A \ to (B \ to C))
  2. ((A \ to (B \ to C)) \ to ((A \ to B) \ to (A \ to C)))
  3. ((\ Neg A \ to \ neg B) \ to (B \ to A))

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

\ Frac {A \ rightarrow B, A} {B} ( Modus ponens).

Как и в предыдущем примере данные выражения являются схемами аксиом.


2.2.1. Пример вывода теоремы

Пользуясь аксиомами Лукасевича и правилом вывода покажем, что ( D \ rightarrow D ) Является теоремой в данной формальной системе для любой формулы D .

Пример вывода
Номер Формула Способ получения
1 (D \ rightarrow ((D \ rightarrow D) \ rightarrow D)) \ rightarrow ((D \ rightarrow (D \ rightarrow D)) \ rightarrow (D \ rightarrow D)) Аксиома 2 из заменой A, B, C \, на D, D \ rightarrow D, D соответственно
2 D \ rightarrow ((D \ rightarrow D) \ rightarrow D) аксиома 1 (замена A, B \, на D \, )
3 (D \ rightarrow (D \ rightarrow D)) \ rightarrow (D \ rightarrow D) 1, 2 и modus ponens.
4 D \ rightarrow (D \ rightarrow D) аксиома 1 (замена A, B \, на D, D \ rightarrow D соответственно)
5 D \ rightarrow D 3, 4 и modus ponens.

3. Семантика

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

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

Наиболее часто операторы задаются с помощью таблиц истинности:

\ Begin {array} {| c | | c |} p & \ neg p \ \ \ hline 1 & 0 \ \ 0 & 1 \ \ \ hline \ end {array}

\ Begin {array} {| c | c | | c |} p & q & p \ and q \ \ \ hline 1 & 1 & 1 \ \ 1 & 0 & 0 \ \ 0 & 1 & 0 \ \ 0 & 0 & 0 \ \ \ hline \ end {array}

\ Begin {array} {| c | c | | c |} p & q & p \ or q \ \ \ hline 1 & 1 & 1 \ \ 1 & 0 & 1 \ \ 0 & 1 & 1 \ \ 0 & 0 & 0 \ \ \ hline \ end {array}

\ Begin {array} {| c | c | | c |} p & q & p \ to q \ \ \ hline 1 & 1 & 1 \ \ 1 & 0 & 0 \ \ 0 & 1 & 1 \ \ 0 & 0 & 1 \ \ \ hline \ end {array}

\ Begin {array} {| c | c | | c |} p & q & p \ and q \ \ \ hline 1 & 1 & 1 \ \ 1 & 0 & 0 \ \ 0 & 1 & 0 \ \ 0 & 0 & 1 \ \ \ hline \ end {array}

Учитывая способ построения формул, каждая формула при некотором заданном истинности получает определенное значение 0 или 1. Значение простейших формул для различных задач истинности можно вычислять с помощью таблиц истинности. Например:

\ Begin {array} {| c | c | c | | c | c | c | c |} p & q & r & (p \ or q) & \ neg (p \ or q) & (p \ to r ) & \ neg (p \ or q) \ to (p \ to r) \ \ \ hline 1 & 1 & 1 & 1 & 0 & 1 & 1 \ \ 1 & 1 & 0 & 1 & 0 & 0 & 1 \ \ 1 & 0 & 1 & 1 & 0 & 1 & 1 \ \ 1 & 0 & 0 & 1 & 0 & 0 & 1 \ \ 0 & 1 & 1 & 1 & 0 & 1 & 1 \ \ 0 & 1 & 0 & 1 & 0 & 1 & 1 \ \ 0 & 0 & 1 & 0 & 1 & 1 & 1 \ \ 0 & 0 & 0 & 0 & 1 & 1 & 1 \ \ \ hline \ end {array}

Если для некоторого задания истинности I \; формула A \; приобретает значение 1, то говорят, что формула A \; удовлетворяет задания I \; . Формула, удовлетворяет все возможные задания истинности (как формула \ Neg (p \ or q) \ to (p \ to r) на примере) называется тавтологией. Если \ Sigma \; - Некоторая множество формул говорится, что данная множество удовлетворяет задания истинности, если это задание удовлетворяет каждая формула этого множества. Если для некоторой формулы A \; из того, что множество \ Sigma \; удовлетворяет заданной истинности следует что A \; удовлетворяет этому заданной то формула A \; называется логическим следствием множества \ Sigma \; (Обозначается \ Sigma \ vDash A ). В случае если множество \ Sigma \; является пустой, формула является тавтологией.


4. Полнота и непротиворечивость

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

Во всех приведенных выше примерах Исчисление высказываний являются полными и непротиворечивыми.

См.. также


Источники

  1. Гильберт Д., Аккерман В. Основы теоретической логики. М., 1947
  2. Клинья С.К. Введение в метаматематику. М., 1957
  3. Мендельсон Э.. Введение в математическую логику. М., 1976
  4. Enderton, HB, A Mathematical Introduction to Logic. Harcourt / Academic Press 2002. ISBN 0-12-238452-0
  5. AG Hamilton Logic for Mathematicians, Cambridge University Press, Cambridge UK 1978 ISBN 0-521-21838-1.