Русская Википедия:Тавтология (логика)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Другие значения Тавтологией в логике называется тождественно истинное высказывание.

Тот факт, что формула A — тавтология, обозначается <math>\vDash A</math>. В каждом логическом исчислении имеется своё множество тавтологий.

Тавтология также является результатом функции идентичности <math>\mathrm{id}</math>, так что <math>\mathrm{id}(x)=x</math>.

Построение тавтологий

Для выяснения того, является ли данная формула тавтологией, в алгебре высказываний есть простой способ — построение таблицы истинности. В исчислении высказываний тавтологиями являются аксиомы (точнее — схемы аксиом), а также все формулы, которые можно получать из известных тавтологий с помощью заданных правил вывода (чаще всего это Modus ponens и правило подстановки). Проверка, является ли данная формула в исчислении высказываний тавтологией, более сложна, а также зависит от системы аксиом и доступных правил вывода.
Проблема определения того, является ли произвольная формула в логике предикатов тавтологией, алгоритмически неразрешима.

Примеры тавтологий

Тавтологии исчисления высказываний (и алгебры высказываний)

  • <math> A \rightarrow A </math> («Из A следует A») — закон тождества
  • <math>(A) \lor (\lnot A)</math> («A или не-A») — закон исключённого третьего
  • <math>\neg (P \land \neg P)</math> — закон отрицания противоречия
  • <math>\neg \neg P \rightarrow P </math> — закон двойного отрицания
  • <math> (P \leftrightarrow Q) \leftrightarrow (\neg Q \leftrightarrow \neg P) </math> — закон противоположности
  • <math> (P \land Q ) \leftrightarrow (Q \land P) </math> — коммутативность конъюнкции
  • <math> (P \lor Q ) \leftrightarrow (Q \lor P) </math> — коммутативность дизъюнкции
  • <math> [(P \land Q ) \land R] \leftrightarrow [P \land (Q \land R)] </math> — ассоциативность конъюнкции
  • <math> [(P \lor Q ) \lor R] \leftrightarrow [P \lor (Q \lor R)] </math> — ассоциативность дизъюнкции
  • <math>(P \land (P \rightarrow Q)) \rightarrow Q</math>
  • <math>A \rightarrow (B \rightarrow A)</math> (истина следует из чего угодно)
  • <math>(A\rightarrow B)\wedge (B \rightarrow C) \rightarrow (A\rightarrow C)</math> — правило цепного заключения
  • <math>(A\vee B)\wedge C \leftrightarrow (A\wedge C)\vee (B\wedge C)</math> — дистрибутивность конъюнкции относительно дизъюнкции
  • <math>(A\wedge B)\vee C \leftrightarrow (A\vee C)\wedge (B\vee C)</math> — дистрибутивность дизъюнкции относительно конъюнкции
  • <math> (P \land P) \leftrightarrow P </math> — идемпотентность конъюнкции
  • <math> (P \lor P) \leftrightarrow P </math> — идемпотентность дизъюнкции
  • <math> (P \rightarrow Q) \leftrightarrow (\neg P \lor Q)</math>
  • <math> (P \leftrightarrow Q) \leftrightarrow ((P \leftrightarrow Q) \land (Q \leftrightarrow P)) </math>
  • <math> (P \land (Q \lor P) \leftrightarrow P </math> — первый закон поглощения
  • <math> (P \lor (Q \land P) \leftrightarrow P </math> — второй закон поглощения
  • <math>\neg (A\wedge B) \leftrightarrow (\neg A \vee \neg B)</math> — первый закон де Моргана
  • <math>\neg (A\vee B) \leftrightarrow (\neg A \wedge \neg B)</math> — второй закон де Моргана
  • <math>(A\rightarrow B) \leftrightarrow (\neg B \rightarrow \neg A)</math> — закон контрапозиции
  • Если <math>\vDash F(X_1,...,X_n)</math> и <math>H_1,...,H_n</math> — формулы, то <math>\vDash F(H_1,...,H_n)</math> (правило подстановки)

Тавтологии исчисления предикатов (и алгебры предикатов)

  • Если <math>F(X_1,...,X_n)</math> - тавтология в исчислении высказываний и <math>P_1,...,P_n</math> - предикаты, то <math>F(P_1,...,P_n)</math> - тавтология в исчислении предикатов
  • <math>\neg (\forall x)P(x) \leftrightarrow (\exists x)\neg P(x)</math>

<math>\neg (\exists x)P(x) \leftrightarrow (\forall x)\neg P(x)</math> (закон де Моргана)

  • <math>(\forall x)(P(x)\wedge Q(x)) \leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)</math>
  • <math>(\exists x)(P(x)\vee Q(x)) \leftrightarrow (\exists x)P(x)\vee (\exists x)Q(x)</math>
  • <math>Q \leftrightarrow (\exists x)Q</math>
  • <math>Q \leftrightarrow (\forall x)Q</math>
  • <math>(\forall x)P(x) \rightarrow P(y)</math>
  • <math>P(y) \rightarrow (\exists x)P(x)</math>
  • <math>(\forall x)(\forall y)P(x,y) \leftrightarrow (\forall y)(\forall x)P(x,y)</math>
  • <math>(\exists x)(\exists y)P(x,y) \leftrightarrow (\exists y)(\exists x)P(x,y)</math>
  • <math>(\exists x)(\forall y)P(x,y) \rightarrow (\forall y)(\exists x)P(x,y)</math>

См. также

Примечания

Шаблон:Примечания Шаблон:Викисловарь

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Тавтология_(логика)&oldid=10899483