У этого термина существуют и другие значения, см.
Тавтология .
Тавтологией в логике называется тождественно истинное высказывание .
Тот факт , что формула A — тавтология, обозначается ⊨ A {\displaystyle \vDash A} . В каждом логическом исчислении имеется своё множество тавтологий.
Тавтология также является результатом функции идентичности i d {\displaystyle \mathrm {id} } , так что i d ( x ) = x {\displaystyle \mathrm {id} (x)=x} .
Для выяснения того, является ли данная формула тавтологией, в алгебре высказываний есть простой способ — построение таблицы истинности . В исчислении высказываний тавтологиями являются аксиомы (точнее — схемы аксиом), а также все формулы, которые можно получать из известных тавтологий с помощью заданных правил вывода (чаще всего это Modus ponens и правило подстановки ). Проверка, является ли данная формула в исчислении высказываний тавтологией, более сложна, а также зависит от системы аксиом и доступных правил вывода. Проблема определения того, является ли произвольная формула в логике предикатов тавтологией, алгоритмически неразрешима.
Тавтологии исчисления высказываний (и алгебры высказываний) [ править | править код ] A → A {\displaystyle A\rightarrow A} («Из A следует A ») — закон тождества ( A ) ∨ ( ¬ A ) {\displaystyle (A)\lor (\lnot A)} («A или не-A ») — закон исключённого третьего ¬ ( P ∧ ¬ P ) {\displaystyle \neg (P\land \neg P)} — закон отрицания противоречия ¬ ¬ P → P {\displaystyle \neg \neg P\rightarrow P} — закон двойного отрицания ( P ↔ Q ) ↔ ( ¬ Q ↔ ¬ P ) {\displaystyle (P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)} — закон противоположности ( P ∧ Q ) ↔ ( Q ∧ P ) {\displaystyle (P\land Q)\leftrightarrow (Q\land P)} — коммутативность конъюнкции ( P ∨ Q ) ↔ ( Q ∨ P ) {\displaystyle (P\lor Q)\leftrightarrow (Q\lor P)} — коммутативность дизъюнкции [ ( P ∧ Q ) ∧ R ] ↔ [ P ∧ ( Q ∧ R ) ] {\displaystyle [(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]} — ассоциативность конъюнкции [ ( P ∨ Q ) ∨ R ] ↔ [ P ∨ ( Q ∨ R ) ] {\displaystyle [(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]} — ассоциативность дизъюнкции ( P ∧ ( P → Q ) ) → Q {\displaystyle (P\land (P\rightarrow Q))\rightarrow Q} A → ( B → A ) {\displaystyle A\rightarrow (B\rightarrow A)} (истина следует из чего угодно) ( A → B ) ∧ ( B → C ) → ( A → C ) {\displaystyle (A\rightarrow B)\wedge (B\rightarrow C)\rightarrow (A\rightarrow C)} — правило цепного заключения ( A ∨ B ) ∧ C ↔ ( A ∧ C ) ∨ ( B ∧ C ) {\displaystyle (A\vee B)\wedge C\leftrightarrow (A\wedge C)\vee (B\wedge C)} — дистрибутивность конъюнкции относительно дизъюнкции ( A ∧ B ) ∨ C ↔ ( A ∨ C ) ∧ ( B ∨ C ) {\displaystyle (A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)} — дистрибутивность дизъюнкции относительно конъюнкции ( P ∧ P ) ↔ P {\displaystyle (P\land P)\leftrightarrow P} — идемпотентность конъюнкции ( P ∨ P ) ↔ P {\displaystyle (P\lor P)\leftrightarrow P} — идемпотентность дизъюнкции ( P → Q ) ↔ ( ¬ P ∨ Q ) {\displaystyle (P\rightarrow Q)\leftrightarrow (\neg P\lor Q)} ( P ↔ Q ) ↔ ( ( P ↔ Q ) ∧ ( Q ↔ P ) ) {\displaystyle (P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))} ( P ∧ ( Q ∨ P ) ↔ P {\displaystyle (P\land (Q\lor P)\leftrightarrow P} — первый закон поглощения ( P ∨ ( Q ∧ P ) ↔ P {\displaystyle (P\lor (Q\land P)\leftrightarrow P} — второй закон поглощения ¬ ( A ∧ B ) ↔ ( ¬ A ∨ ¬ B ) {\displaystyle \neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)} — первый закон де Моргана ¬ ( A ∨ B ) ↔ ( ¬ A ∧ ¬ B ) {\displaystyle \neg (A\vee B)\leftrightarrow (\neg A\wedge \neg B)} — второй закон де Моргана ( A → B ) ↔ ( ¬ B → ¬ A ) {\displaystyle (A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg 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 \neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)} ¬ ( ∃ x ) P ( x ) ↔ ( ∀ x ) ¬ P ( x ) {\displaystyle \neg (\exists x)P(x)\leftrightarrow (\forall x)\neg 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 Q\leftrightarrow (\exists x)Q} Q ↔ ( ∀ x ) Q {\displaystyle Q\leftrightarrow (\forall x)Q} ( ∀ x ) P ( x ) → P ( y ) {\displaystyle (\forall x)P(x)\rightarrow P(y)} P ( y ) → ( ∃ x ) P ( x ) {\displaystyle P(y)\rightarrow (\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)\rightarrow (\forall y)(\exists x)P(x,y)}
Игошин В. И. «Математическая логика и теория алгоритмов». — Academia, 2008. Карпов Ю. Г. «Теория автоматов». — П., 2003. — С. 49, 60. Мендельсон Э. «Введение в математическую логику». — М. Наука, 1971. Игошин В. И. «Задачник -практикум по математической логике». — Просвещение, 1986.