Логика высказываний

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

Логика высказываний — раздел логики, занимающийся изучением логических высказываний, операций над ними и их свойств.

Содержание

1 Основные понятия
2 Соглашения о скобках
3 Истинностное значение
4 См. также

[править] Основные понятия

Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, — и (пропозициональная) формула, определяемая индуктивно следующим образом:

Если P — пропозициональная переменная, то P — формула.
Если A — формула, то $\neg A$ — формула.
Если A и B — формулы, то $(A \wedge B)$ , $(A \vee B)$ и $(A \to B)$ — формулы.
Других формул нет.

Знаки $\neg, \wedge, \vee$ и $\to$ (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.

[править] Соглашения о скобках

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

Если опущены внешние скобки, то они восстанавливаются.
Если рядом стоят две конъюнкции или дизъюнкции (например, $A \wedge B \wedge C$ ), то в скобки заключается сначала самая левая часть (т.е. две подформулы со связкой между ними). (Говорят также, что эти связки левоассоциативны.)
Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: $\neg, \wedge, \vee$ и $\to$ (от высшего к низшему).

Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.

Например: запись $A \vee B \wedge \neg C$ означает формулу $(A \vee (B \wedge \neg C))$ , а её длина равна 10.

[править] Истинностное значение

Оценкой пропозициональных переменных называется функция из множества всех пропозициональных переменных в множество {0, 1} (т.е. множество истинностных значений). Основной задачей логики высказываний является установление истинностного значения формулы, если дана оценка (т.е. определены истинностные значения входящих в неё переменных). Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок.

Формула, которая при всех оценках переменной принимает значение 1, называется тавтологией, значение 0 — противоречием.

Например: формула $A \vee \neg A$ в классическом исчислении высказываний является тавтологией, а $A \wedge \neg A$ — противоречием.