Логическая эквивалентность

В логике и математике утверждения $p$ и $q$ Говорят, что они логически эквивалентны , если они имеют одинаковое истинностное значение в каждой модели . ^[1] Логическая эквивалентность $p$ и $q$ иногда выражается как $p\equiv q$ , $p::q$ , ${\textsf {E}}pq$ , или $p\iff q$ , в зависимости от используемых обозначений.Однако эти символы также используются для материальной эквивалентности , поэтому правильная интерпретация будет зависеть от контекста. Логическая эквивалентность отличается от материальной эквивалентности, хотя эти два понятия неразрывно связаны.

Логические эквиваленты [ править ]

В логике существует множество общих логических эквивалентностей, которые часто обозначаются как законы или свойства. Следующие таблицы иллюстрируют некоторые из них.

логические эквивалентности Общие

Эквивалентность	Имя
$p\wedge \top \equiv p$ $p\vee \bot \equiv p$	Законы об идентичности
$p\vee \top \equiv \top$ $p\wedge \bot \equiv \bot$	Законы доминирования
$p\vee p\equiv p$ $p\wedge p\equiv p$	Законы идемпотентности или тавтологии.
$\neg (\neg p)\equiv p$	двойного отрицания Закон
$p\vee q\equiv q\vee p$ $p\wedge q\equiv q\wedge p$	Коммутативные законы
$(p\vee q)\vee r\equiv p\vee (q\vee r)$ $(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$	Ассоциативные законы
$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$ $p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$	Распределительные законы
$\neg (p\wedge q)\equiv \neg p\vee \neg q$ $\neg (p\vee q)\equiv \neg p\wedge \neg q$	Законы де Моргана
$p\vee (p\wedge q)\equiv p$ $p\wedge (p\vee q)\equiv p$	Законы поглощения
$p\vee \neg p\equiv \top$ $p\wedge \neg p\equiv \bot$	Законы отрицания

Логическая эквивалентность, условные включающая операторы

$p\implies q\equiv \neg p\vee q$
$p\implies q\equiv \neg q\implies \neg p$
$p\vee q\equiv \neg p\implies q$
$p\wedge q\equiv \neg (p\implies \neg q)$
$\neg (p\implies q)\equiv p\wedge \neg q$
$(p\implies q)\wedge (p\implies r)\equiv p\implies (q\wedge r)$
$(p\implies q)\vee (p\implies r)\equiv p\implies (q\vee r)$
$(p\implies r)\wedge (q\implies r)\equiv (p\vee q)\implies r$
$(p\implies r)\vee (q\implies r)\equiv (p\wedge q)\implies r$

Логические эквивалентности, включающие двуусловия [ править ]

$p\iff q\equiv (p\implies q)\wedge (q\implies p)$
$p\iff q\equiv \neg p\iff \neg q$
$p\iff q\equiv (p\wedge q)\vee (\neg p\wedge \neg q)$
$\neg (p\iff q)\equiv p\iff \neg q\equiv p\oplus q$

Где $\oplus$ представляет собой XOR .

Примеры [ править ]

В логике [ править ]

Следующие утверждения логически эквивалентны:

Если Лиза находится в Дании , то она находится в Европе (заявление вида $d\implies e$ ).
Если Лизы нет в Европе, то ее нет в Дании (заявление вида $\neg e\implies \neg d$ ).

Синтаксически (1) и (2) выводятся друг из друга с помощью правил противопоставления и двойного отрицания . Семантически (1) и (2) верны в абсолютно одних и тех же моделях (интерпретациях, оценках); а именно те, в которых либо Лиза находится в Дании, являются ложными, либо Лиза находится в Европе, являются истинными.

(Обратите внимание, что в этом примере классическая логика предполагается . Некоторые неклассические логики не считают (1) и (2) логически эквивалентными.)

к эквиваленту материальному Отношение

Логическая эквивалентность отличается от материальной эквивалентности. Формулы $p$ и $q$ логически эквивалентны тогда и только тогда, когда утверждение об их материальной эквивалентности ( $p\leftrightarrow q$ ) является тавтологией. ^[2]

Материальный эквивалент $p$ и $q$ (часто пишется как $p\leftrightarrow q$ ) само по себе является еще одним оператором на том же объектном языке, что и $p$ и $q$ . В этом высказывании выражается идея «' $p$ тогда и только тогда, когда $q$ '». В частности, истинностное значение $p\leftrightarrow q$ может меняться от одной модели к другой.

С другой стороны, утверждение о том, что две формулы логически эквивалентны, является высказыванием на метаязыке , которое выражает связь между двумя высказываниями. $p$ и $q$ . Утверждения логически эквивалентны, если в каждой модели они имеют одинаковое истинностное значение.

См. также [ править ]

Логическое следствие
Равновыполнимость
Если и только если
Логическое двуусловие
Логическое равенство
≡ символ iff (U+2261 ИДЕНТИЧЕН )
∷ a как относится к b, c к символу d (U+2237 ПРОПОРЦИЯ )
⇔ двустороннее условие с двойным ударом (U + 21D4 ДВОЙНАЯ СТРЕЛКА ВЛЕВО ВПРАВО )
↔ двунаправленная стрелка (U + 2194 СТРЕЛКА ВЛЕВО ВПРАВО )

Ссылки [ править ]

^ Мендельсон, Эллиотт (1979). Введение в математическую логику (2-е изд.). стр. 56 . ISBN 9780442253073 .
^ Копи, Ирвинг ; Коэн, Карл ; МакМахон, Кеннет (2014). Введение в логику (Новое международное изд.). Пирсон. п. 348.

[1] Мендельсон, Эллиотт (1979). Введение в математическую логику (2-е изд.). стр. 56 . ISBN 9780442253073 .

[2] Копи, Ирвинг ; Коэн, Карл ; МакМахон, Кеннет (2014). Введение в логику (Новое международное изд.). Пирсон. п. 348.

[1]

[2]