Числення висловлень

Матеріал з Вікіпедії — вільної енциклопедії.

Перейти до: навігація, пошук

Числення висловлень (логіка висловлень) — це формальна система в математичній логіці, в якій формули, що відповідають висловленням можуть утворюватись шляхом з'єднання простих висловлень із допомогою логічних операцій, та система формальних правил виводу, які дозволяють визначати певні формули в якості «теорем» формальної системи.

Зміст

[ред.] Формальне визначення

У загальному випадку численням висловлень є формальна система \mathcal{L} = \mathcal{L} \left( \Alpha,\ \Omega,\ \Zeta,\ \Iota \right), де:

  • Множина \ \Alpha є скінченною чи зліченною множиною символів висловлень (чи пропозиційних змінних, елементарних висловлювань, атомарних формул). Для зображення атомарних формул нижче використовуються малі латинські літери.
  • Множина \ \Omega — скінченна множина операторів або логічних зв'язок. Дану множину можна розбити на підмножини:
\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 немає.

[ред.] Виведення формул і теорем

Нехай \Sigma\; деяка множина формул \mathcal{L}, а A — деяка задана формула то кажуть, що формула A виводиться з множини формул \Sigma\; (позначається \Sigma \vdash A), якщо існує така скінченна послідовність формул A_1, A_2 \ldots A_n = A де для кожної формули Ai:

  1. Ai є аксіомою, або
  2. Ai належить множині \Sigma\; або
  3. Ai виводиться з попередніх формул послідовності за допомогою котрогось із правил виводу.

Якщо при цьому множина \Sigma\; — пуста (формула A виводиться лише за допомогою аксіом і правил виводу) то формула A називається теоремою (для цього використовується позначення \vdash A).

[ред.] Приклади аксіоматики

[ред.] Приклад 1

  1. Алфавіт (елементи множини Α) числення висловлень складається з елементарних висловлень (пропозиційних змінних): 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 немає.

[ред.] Аксіоми

В численні висловлень визначають наступні схеми аксіом:

  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 можна заміщувати усіма допустимими формулами, після чого і отримуються конкретні аксіоми.

[ред.] Приклад виведення теореми

Користуючись поданими аксіомами і правилом виведення покажемо, що (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 (аксіоми Лукасевича)

  1. Алфавіт (елементи множини Α) числення висловлень складається з елементарних висловлень (пропозиційних змінних): 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))
  1. ((A \to (B \to C)) \to ((A \to B) \to (A \to C)))
  1. ((\neg A \to \neg B) \to (B \to A))

Єдиним правилом виводу є:

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

Як і у попередньому прикладі дані вирази є схемами аксіом.

[ред.] Приклад виведення теореми

Користуючись аксіомами Лукасевича і правилом виведення покажемо, що (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.

[ред.] Семантика

У поданих вище формальних системах атомарні формули і оператори можуть фактично мати довільну природу. Для логіки важливе значення має інтерпретація цих символів. Інтерпретація визначається заданням істинності тобто наданням кожній атомарній формулі одного із значень 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\; є пустою, формула є тавтологією.

[ред.] Повнота і несуперечливість

Числення висловлень називається повним якщо будь-яка тавтологія є теоремою даного числення. Якщо зворотно будь-яка теорема числення висловлень є тавтологією то числення називається несуперечливим.

В усіх наведених вище прикладах Числення висловлень є повними і несуперечливими.

[ред.] Див. також

[ред.] Джерела

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