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

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

Формальне визначення

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