Исчисление высказываний

Материал из Википедии — свободной энциклопедии

В этой статье или секции нет ссылок на источники информации.
Вы можете помочь улучшить эту статью, добавив список литературы или внешние ссылки.

Исчисле́ние выска́зываний — это формальная теория $\mathcal{L}$ , в которой осуществляется попытка формализации понятий логического закона и логического следования.

Высказывание — это повествовательное предложение, которое истинно или ложно. В исчислении высказываний значимым является лишь истинностное значение высказывания («истина» — 1, «ложь» — 0), поэтому используемые в дальнейшем высказывательные (пропозициональные) переменные могут принимать одно из этих значений.

Содержание

1 Логические связки
2 Формулы исчисления высказываний
3 Тождественно истинные формулы (тавтологии)
4 Аксиомы (одна из возможных систем аксиом)
5 Правило вывода

[править] Логические связки

Кроме высказывательных переменных, в исчислении высказываний используются так называемые логические связки. Если $p\!$ — высказывание, то через $\neg p$ будем обозначать отрицание этого высказывания. Зададим его таблицей:

$p\!$	$\neg p$
$0\!$	$1\!$
$1\!$	$0\!$

Значение двуместных логических связок $\rightarrow$ (импликация), $\vee$ (дизъюнкция) и $\wedge$ (конъюнкция) определются так:

$p\!$	$q\!$	$p\rightarrow q$	$p \wedge q$	$p \vee q$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

[править] Формулы исчисления высказываний

Атомарные формулы (состоящие из одной высказывательной переменной) являются формулами исчисления высказываний.
Если $p, q\,\!$ — формулы исчисления высказываний, то $(p\rightarrow q)$ , $(p \vee q)$ и $(p \wedge q)$ — формулы исчисления высказываний.
Если $p\!$ — формула исчисления высказываний, то $(\neg p)$ — формула исчисления высказываний.

[править] Тождественно истинные формулы (тавтологии)

Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных. Вот несколько широко известных примеров тождественно истинных формул логики высказываний:

Законы де Моргана:

1) $((p\wedge q)\vee(p\wedge r))\leftrightarrow(p\wedge(q\vee r))$ ;

2) $((p\vee q)\wedge(p\vee r))\leftrightarrow(p\vee(q\wedge r))$ ;

Закон контрапозиции:

$(p\rightarrow q)\leftrightarrow(\neg q\rightarrow \neg p)$ ;

Законы поглощения:

1) $p\vee(p\wedge q)\leftrightarrow p$ ;

2) $p\wedge(p\vee q)\leftrightarrow p$ ;

Законы дистрибутивности:

1) $p\wedge(q\vee r)\leftrightarrow(p\wedge q)\vee(p \wedge r)$ ;

1) $p\vee(q\wedge r)\leftrightarrow(p\vee q)\wedge(p \vee r)$ .

[править] Аксиомы (одна из возможных систем аксиом)

$A_1 : (A \rightarrow (B \rightarrow A))$ ;

$A_2 : ((A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)))$ ;

$A_3 : A \wedge B \rightarrow A$ ;

$A_4 : A \wedge B \rightarrow B$ ;

$A_5 : A \rightarrow (B \rightarrow (A \wedge B))$ ;

$A_6 : A \rightarrow (A \vee B)$ ;

$A_7 : B \rightarrow (A \vee B)$ ;

$A_8 : (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C))$ ;

$A_9 : \neg A \rightarrow (A \rightarrow B)$ ;

$A_{10} : (A \rightarrow B) \rightarrow ((A \rightarrow \neg B)\rightarrow \neg A)$ ;

$A_{11} : A\vee\neg A$ .

[править] Правило вывода

$\frac{A \rightarrow B, A}{B}$ (Modus ponens)

Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

Это незавершённая статья по математике.
Вы можете помочь проекту, исправив и дополнив её.

Категории: Википедия:Статьи без ссылок на источники | Незавершённые статьи по математике | Математическая логика

Исчисление высказываний

Материал из Википедии — свободной энциклопедии

Содержание

[править] Логические связки

[править] Формулы исчисления высказываний

[править] Тождественно истинные формулы (тавтологии)

[править] Аксиомы (одна из возможных систем аксиом)

[править] Правило вывода

Views

Навигация

Участие

Поиск

На других языках

$p\!$	$q\!$	$p\rightarrow q$	$p \wedge q$	$p \vee q$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

$p\!$	$q\!$	$p\rightarrow q$	$p \wedge q$	$p \vee q$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

$p\!$	$q\!$	$p\rightarrow q$	$p \wedge q$	$p \vee q$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$