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

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

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

Зміст

1 Формальне визначення
- 1.1 Виведення формул і теорем
2 Приклади аксіоматики
- 2.1 Приклад 1
  - 2.1.1 Аксіоми
  - 2.1.2 Приклад виведення теореми
- 2.2 Приклад 2 (аксіоми Лукасевича)
  - 2.2.1 Приклад виведення теореми
3 Семантика
4 Повнота і несуперечливість
5 Див. також
6 Джерела

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

У загальному випадку численням висловлень є формальна система $\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$ є скінченною множиною елементи якої називаються аксіомами. В окремих прикладах дана множина може бути пустою.

Мовою числення висловлень є множина формул, що визначаються рекурсивно за допомогою наступних правил:

всі елементи множини $\ \Alpha$ є формулами;
якщо $\ p_1, p_2, \ldots, p_j$ є формулами та $f \in \Omega_j$ , тоді $\left( f(p_1, p_2, \ldots, p_j) \right)$ теж є формулою.
інших формул, ніж побудовані за правилами 1 і 2 немає.

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

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

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

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

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

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

Алфавіт (елементи множини $Α$ ) числення висловлень складається з елементарних висловлень (пропозиційних змінних): $a,b,c,d,\dots,x,y,z$ (можливо з індексами), логічними операціями є $\lor , \land , \lnot , \rightarrow,$ .
Поняття формули визначається аналогічно алгебрі висловлень.
1. всі пропозиційні змінні та елементарні висловлення є формулами;
2. якщо A і B — формули, то вирази (слова) $(A\lor B), (A\land B), (\lnot A), (A\rightarrow B)$ також є формулами;
3. інших формул, ніж побудовані за правилами 2.1 і 2.2 немає.

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

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

$A \rightarrow(B\rightarrow A)$
$(A \rightarrow B)\rightarrow ((A\rightarrow(B\rightarrow C))\rightarrow (A\rightarrow C))$
$(A\land B)\rightarrow A$
$(A\land B)\rightarrow B$
$(A\rightarrow B)\rightarrow ((A\rightarrow C)\rightarrow (A\rightarrow (B\land C)))$
$A\rightarrow (A\lor B)$
$B\rightarrow (A\lor B)$
$(A\rightarrow C)\rightarrow ((B\rightarrow C)\rightarrow((A\lor B)\rightarrow C))$
$(A\rightarrow \lnot B)\rightarrow (B\rightarrow \lnot A)$
$\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 (аксіоми Лукасевича)

Алфавіт (елементи множини $Α$ ) числення висловлень складається з елементарних висловлень (пропозиційних змінних): $a,b,c,d,\dots,x,y,z$ (можливо з індексами), логічними операціями є $\lnot , \rightarrow,$ .
Поняття формули визначається аналогічно алгебрі висловлень.
1. всі пропозиційні змінні та елементарні висловлення є формулами;
2. якщо A і B — формули, то вирази (слова) $(\lnot A), (A\rightarrow B)$ також є формулами;
3. інших формул, ніж побудовані за правилами 2.1 і 2.2 немає.

Наступну просту систему аксіом запропонував польський логік Ян Лукасевич:

$(A \to (B \to C))$

$((A \to (B \to C)) \to ((A \to B) \to (A \to C)))$

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

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

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

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

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

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

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

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

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

Зміст

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

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

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

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

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

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

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

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

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

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

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

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

Перегляди

Особисті інструменти

Навігація

Участь

Пошук

Панель інструментів

Іншими мовами