Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

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

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

Логические связки Править

Кроме высказывательных переменных, в исчислении высказываний используются так называемые логические связки. Если 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

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

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


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

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

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

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

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

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

(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} : \neg\neg A \rightarrow A.

Правило вывода Править

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

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


ar:منطق القضايا

be-x-old:Злічэнне выказванняўet:Lauseloogika fa:حساب گزاره‌هاhe:תחשיב פסוקים hu:Ítéletlogikalt:Teiginių logika nl:Propositielogica no:Setningslogikk pl:Rachunek zdańsv:Satslogik th:แคลคูลัสเชิงประพจน์

Викия-сеть

Случайная вики