Викия

Математика

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

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

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


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

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

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

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

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

  1. Если P — пропозициональная переменная, то P — формула.
  2. Если A — формула, то \neg A — формула.
  3. Если A и B — формулы, то (A \wedge B), (A \vee B) и (A \to B) — формулы.
  4. Каждая формула может быть получена за конечное число шагов при помощи предыдущих трёх правил.

Знаки \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 — противоречием.

См. также Править

Ссылки Править


Викия-сеть

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