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

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

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

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

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

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

Приклад (аксіоми Лукасевича)[ред.ред. код]

  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\; є пустою, формула є тавтологією.

Основні проблеми числення висловлень[ред.ред. код]

Для обгрунтування будь-якої аксіоматичної теорії необхідно розглянути наступні 4 проблеми:

  1. Несуперечливості
  2. Повноти
  3. Незалежності
  4. Розв’язності

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

Означення: Нехай задано деяку формальну аксіоматичну теорію. Говорять, що побудована модель цієї теорії, якщо всім символам алфавіту надано деякого конкретного змісту, який описує певну неформальну теорію і відношення між елементами цієї теорії.

Формальна аксіоматична теорія називається категоричною, якщо будь-які її 2 моделі ізоморфні між собою, тобто між ними можна встановити взаємно-однозначну відповідність.

Формальна аксіоматична теорія називається несуперечливою відносно своєї моделі, якщо будь-яка теорема, що доводиться в формальній теорії є істинним твердженням для моделі.

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

Формальна аксіоматична теорія називається синтаксично несуперечливою якщо в ній існує хоча б якась формула, яка не являється теоремою.

Теорема: Формальна аксіоматична теорія числення висловлень є несуперечливою відносно своєї моделі алгебри висловлень.

Наслідок:  

  1. Числення висловлень – внутрішньо-несуперечлива теорія.
  2. Числення висловлень – синтаксично-несуперечлива теорія.

Теорема: Формальна аксіоматична теорія числення висловлень є категоричною.

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

Формальна аксіоматична теорія числення висловлень називається вузькою у вузькому розумінні, якщо приєднання до системи аксіом цієї теорії хоча б однієї формули, яка не є теоремою веде до того, що теорія стає внутрішньо-суперечливою.

Формальна аксіоматична теорія числення висловлень є повною у широкому розумінні або повною відносно своєї моделі, якщо будь-яка формула істинна в моделі є теоремою в цій теорії, або якщо будь-яку тотожно істинну формулу можна довести.

Теорема: Формальна аксіоматична теорія числення висловлень є повною відносно своєї моделі алгебри висловлень.

Теорема: Числення висловлень – це формальна аксіоматична теорія, повна у вузькому розумінні.

Проблема незалежності[ред.ред. код]

Означення: Нехай задано деяку формальну аксіоматичну теорію, говорять, що деяка аксіома цієї теорії є незалежною, якщо її не можна довести методами самої теорії, як теорему.

Система аксіом формальної аксіоматичної теорії називається незалежною системою аксіом, якщо всі аксіоми є незалежними.

Теорема: Система аксіом числення висловлень є незалежною.

Доведення: Для доведення незалежності деякої аксіоми числення висловлень використовують наступний підхід: будують таку модель формальної аксіоматичної теорії, в якій справджуються всі аксіоми окрім даної. Якщо доводиться, що така модель ізоморфна стандартній моделі формальної аксіоматичної теорії, то робиться висновок, що аксіома не є незалежною, якщо ж такого ізоморфізму немає – незалежна.

Приклад: В якості моделі формальної аксіоматичної теорії візьмемо

a∧b ≡ b, все інше не змінюємо, покажемо, що ІІ2 і ІІ3 справджуються, а ІІ1 ні.

ІІ a∧b → b

|- b → b

ІІ (a → b) → (( a→ c ) → ( a → b∧c ))

|-  ( a→ b ) → (( a → c ) → ( a → c))

ІІ1 a∧b → a

b → a

Доведено

Проблема розв’язності[ред.ред. код]

Полягає в тому щоб довести існування алгоритму, який для будь-якої формули числення висловлень визначає чи можна її довести чи ні.

Теорема: Проблема розв`язності числення висловлень є розв`язною.

Теорема 1: Будь-яка тотожно істинна формула алгебри висловлень є теоремою числення висловлень.

Доведення: Нехай A - довільна формула числення числення висловлень. Побудуємо для неї таблицю істинності і розглянемо її останній стовпчик. Якщо він містить лише одиниці, то A - тотожно істинна формула і за теоремою 1 є теоремою числення висловлень. В іншому випадку (останній стовпчик таблиці істинності містить хоча б один нуль), A - не тавтологія і значить, A не є теоремою.

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

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

  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.