У этого термина существуют и другие значения, см.
Тавтология .
Тавтологией в логике называется тождественно истинное высказывание .
Тот факт , что формула 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.Мендельсон Э. «Введение в математическую логику». — М. Наука, 1971.Игошин В. И. «Задачник -практикум по математической логике». — Просвещение, 1986.
![{\displaystyle [(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32ce297f61ebeca9f1780fa3b8ec1458ae6c2abf)
![{\displaystyle [(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f0e8a7134d4b2312bb2eec00a0e84d58e161561)
