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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Численням висловлень є формальна система \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 немає.

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

Нехай \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 (аксіоми Лукасевича)[ред.ред. код]

  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).

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

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

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