Тавтология (логика)

19.01.2021

Тавтологией в логике называется тождественно истинное высказывание, инвариантное относительно значений своих компонентов.

Тот факт, что формула A — тавтология, обозначается ⊨ A {displaystyle vDash A} . В каждом логическом исчислении имеется своё множество тавтологий.

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

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

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

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

  • A → A {displaystyle A ightarrow A} («Из A следует A») — закон тождества
  • ( A ) ∨ ( ¬ A ) {displaystyle (A)lor (lnot A)} («A или не-A») — закон исключённого третьего
  • ¬ ( P ∧ ¬ P ) {displaystyle eg (Pland eg P)} — закон отрицания противоречия
  • ¬ ¬ P → P {displaystyle eg eg P ightarrow P} — закон двойного отрицания
  • ( P ↔ Q ) ↔ ( ¬ Q ↔ ¬ P ) {displaystyle (Pleftrightarrow Q)leftrightarrow ( eg Qleftrightarrow eg P)} — закон противоположности
  • ( P ∧ Q ) ↔ ( Q ∧ P ) {displaystyle (Pland Q)leftrightarrow (Qland P)} — коммутативность конъюнкции
  • ( P ∨ Q ) ↔ ( Q ∨ P ) {displaystyle (Plor Q)leftrightarrow (Qlor P)} — коммутативность дизъюнкции
  • [ ( P ∧ Q ) ∧ R ] ↔ [ P ∧ ( Q ∧ R ) ] {displaystyle [(Pland Q)land R]leftrightarrow [Pland (Qland R)]} — ассоциативность конъюнкции
  • [ ( P ∨ Q ) ∨ R ] ↔ [ P ∨ ( Q ∨ R ) ] {displaystyle [(Plor Q)lor R]leftrightarrow [Plor (Qlor R)]} — ассоциативность дизъюнкции
  • ( P ∧ ( P → Q ) ) → Q {displaystyle (Pland (P ightarrow Q)) ightarrow Q}
  • A → ( B → A ) {displaystyle A ightarrow (B ightarrow A)} (истина следует из чего угодно)
  • ( A → B ) ∧ ( B → C ) → ( A → C ) {displaystyle (A ightarrow B)wedge (B ightarrow C) ightarrow (A ightarrow C)} — правило цепного заключения
  • ( A ∨ B ) ∧ C ↔ ( A ∧ C ) ∨ ( B ∧ C ) {displaystyle (Avee B)wedge Cleftrightarrow (Awedge C)vee (Bwedge C)} — дистрибутивность конъюнкции относительно дизъюнкции
  • ( A ∧ B ) ∨ C ↔ ( A ∨ C ) ∧ ( B ∨ C ) {displaystyle (Awedge B)vee Cleftrightarrow (Avee C)wedge (Bvee C)} — дистрибутивность дизъюнкции относительно конъюнкции
  • ( P ∧ P ) ↔ P {displaystyle (Pland P)leftrightarrow P} — идемпотентность конъюнкции
  • ( P ∨ P ) ↔ P {displaystyle (Plor P)leftrightarrow P} — идемпотентность дизъюнкции
  • ( P → Q ) ↔ ( ¬ P ∨ Q ) {displaystyle (P ightarrow Q)leftrightarrow ( eg Plor Q)}
  • ( P ↔ Q ) ↔ ( ( P ↔ Q ) ∧ ( Q ↔ P ) ) {displaystyle (Pleftrightarrow Q)leftrightarrow ((Pleftrightarrow Q)land (Qleftrightarrow P))}
  • ( P ∧ ( Q ∨ P ) ↔ P {displaystyle (Pland (Qlor P)leftrightarrow P} — первый закон поглощения
  • ( P ∨ ( Q ∧ P ) ↔ P {displaystyle (Plor (Qland P)leftrightarrow P} — второй закон поглощения
  • ¬ ( A ∧ B ) ↔ ( ¬ A ∨ ¬ B ) {displaystyle eg (Awedge B)leftrightarrow ( eg Avee eg B)} — первый закон де Моргана
  • ¬ ( A ∨ B ) ↔ ( ¬ A ∧ ¬ B ) {displaystyle eg (Avee B)leftrightarrow ( eg Awedge eg B)} — второй закон де Моргана
  • ( A → B ) ↔ ( ¬ B → ¬ A ) {displaystyle (A ightarrow B)leftrightarrow ( eg B ightarrow eg A)} — закон контрапозиции
  • Если ⊨ F ( X 1 , . . . , X n ) {displaystyle vDash F(X_{1},...,X_{n})} и H 1 , . . . , H n {displaystyle H_{1},...,H_{n}} — формулы, то ⊨ F ( H 1 , . . . , H n ) {displaystyle vDash F(H_{1},...,H_{n})} (правило подстановки)

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

  • Если F ( X 1 , . . . , X n ) {displaystyle F(X_{1},...,X_{n})} - тавтология в исчислении высказываний и P 1 , . . . , P n {displaystyle P_{1},...,P_{n}} - предикаты, то F ( P 1 , . . . , P n ) {displaystyle F(P_{1},...,P_{n})} - тавтология в исчислении предикатов
  • ¬ ( ∀ x ) P ( x ) ↔ ( ∃ x ) ¬ P ( x ) {displaystyle eg (forall x)P(x)leftrightarrow (exists x) eg P(x)}

¬ ( ∃ x ) P ( x ) ↔ ( ∀ x ) ¬ P ( x ) {displaystyle eg (exists x)P(x)leftrightarrow (forall x) eg P(x)} (закон де Моргана)

  • ( ∀ x ) ( P ( x ) ∧ Q ( x ) ) ↔ ( ∀ x ) P ( x ) ∧ ( ∀ x ) Q ( x ) {displaystyle (forall x)(P(x)wedge Q(x))leftrightarrow (forall x)P(x)wedge (forall x)Q(x)}
  • ( ∃ x ) ( P ( x ) ∨ Q ( x ) ) ↔ ( ∃ x ) P ( x ) ∨ ( ∃ x ) Q ( x ) {displaystyle (exists x)(P(x)vee Q(x))leftrightarrow (exists x)P(x)vee (exists x)Q(x)}
  • Q ↔ ( ∃ x ) Q {displaystyle Qleftrightarrow (exists x)Q}
  • Q ↔ ( ∀ x ) Q {displaystyle Qleftrightarrow (forall x)Q}
  • ( ∀ x ) P ( x ) → P ( y ) {displaystyle (forall x)P(x) ightarrow P(y)}
  • P ( y ) → ( ∃ x ) P ( x ) {displaystyle P(y) ightarrow (exists x)P(x)}
  • ( ∀ x ) ( ∀ y ) P ( x , y ) ↔ ( ∀ y ) ( ∀ x ) P ( x , y ) {displaystyle (forall x)(forall y)P(x,y)leftrightarrow (forall y)(forall x)P(x,y)}
  • ( ∃ x ) ( ∃ y ) P ( x , y ) ↔ ( ∃ y ) ( ∃ x ) P ( x , y ) {displaystyle (exists x)(exists y)P(x,y)leftrightarrow (exists y)(exists x)P(x,y)}
  • ( ∃ x ) ( ∀ y ) P ( x , y ) → ( ∀ y ) ( ∃ x ) P ( x , y ) {displaystyle (exists x)(forall y)P(x,y) ightarrow (forall y)(exists x)P(x,y)}


Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru © 2020
При цитировании и использовании любых материалов ссылка на сайт обязательна