На главную   ::   Содержание



Полнота и непротиворечивость исчисления высказываний

Определение 1.   Абстрактной буквой называется класс символов (конкретных букв), которые мы считаем одинаковыми. Множество абстрактных букв называется алфавитом. Конечный ряд букв алфавита называется словом в алфавите.

Замечание 1.   Алфавит исчисления высказываний состоит из трех групп символов: пропозициональные переменные (обозначаются большими буквами); логические символы $ \to,\cup,\cap,\neg$ и символ следствия $ \vdash$; вспомогательные символы: запятая и скобки.

Определение 2.   Будем говорить, что задано исчисление высказываний $ I$, если задан алфавит $ A(I)$, множество слов алфавита $ E(I)$ -- множество выражений исчисления, множество аксиом исчисления $ Ax(I)$ и множество операций на множестве $ E(I)$ -- правил вывода исчисления $ I$.

Определение 3.   Любое утверждение, имеющее логическую значимость, называется высказыванием.

Определение 4.   Формулой ИВ назовем слово в алфавите, построенное по индукции: пропозициональная переменная является формулой, и для двух формул $ \phi,\psi$ верно $ \phi\to\psi$ и аналогичные логические конструкции -- тоже формулы.

Определение 5.   Секвенция ИВ -- последовательность формул $ \phi_0,\dots,\phi_n,\psi$ следующих четырех типов:
  1. $ \phi_0,\dots,\phi_n\vdash\psi$ (из истинности $ \phi_0,\dots,\phi_n$ следует истинность $ \psi$)
  2. $ \phi_0,\dots,\phi_n\vdash$ ( $ \phi_0,\dots,\phi_n$ противоречивы)
  3. $ \vdash\psi$
  4. $ \vdash$

Определение 6.   Секвенция $ S$ называется доказуемой, если существует последовательность секвенций ИВ $ S_0,\dots,S_n$ такая что $ S_n=S$.

Определение 7.   ИВ называется непротиворечивым, если не все формулы в нем доказуемы.

Теорема 1.   ИВ непротиворечиво.

Доказательство. Дадим неформальное доказательство: если множество формул ИВ непусто, то там найдется формула $ \psi$. Построим формулу следующего вида $ \psi\cap\neg\psi$. Эта формула будет недоказуемой. $ \blacksquare$

Замечание 2.   Пусть пропозициональные переменные принимают булевские значения $ \{0,1\}$. Тогда каждой формуле можно поставить в соответствие функцию, которая для каждого набора значений переменных дает 0 или $ 1$, т.е. указывает истинность или ложность формулы на данном наборе. Тогда формулу можно называть тождественно истинной, если соответствующая ей функция принимает значение $ 1$ на всех наборах входящих в формулу переменных.

Определение 8.   Множество формул $ \Phi$ называется полным, если можно доказать либо $ \Phi\vdash B$, либо $ \Phi\vdash\neg B$.



На главную   ::   Содержание