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

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

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

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

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

  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 немає.

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

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

  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. Алфавіт (елементи множини \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 A))
  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,D \rightarrow 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 )
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.

Література[ред.ред. код]

  • Прийма С.М. Математична логіка і теорія алгоритмів: Навчальний посібник – Мелітополь: ТОВ „Видавничий будинок ММД”, 2008. - 134 с.
  • Гасяк О.С. Формальна логіка : короткий словник-довідник. – Чернівці : Чернівецький нац. ун-т, 2014. – 200 с.
  • Матвієнко М.П., Шаповалов С.П. Математична логіка та теорія алгоритмів. Навчальний посібник. – К.: Видавництво Ліра-К, 2015. – 212 с.

Посилання[ред.ред. код]