text: 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)} — коммутативность дизъюнкции ↔ {\displaystyle \leftrightarrow } — ассоциативность конъюнкции ↔ {\displaystyle \leftrightarrow } — ассоциативность дизъюнкции ( P ∧ ( P → Q ) ) → Q {\displaystyle (P\land (P\rightarrow Q))\rightarrow Q} A → ( B → A ) {\displaystyle A\rightarrow (B\rightarrow A)} (истина следует из чего угодно) A ↔ ¬ ¬ A {\displaystyle A\leftrightarrow \neg \neg 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)} Рассмотрим известное из песни высказывание: «В хоккей играют настоящие мужчины, (следовательно)Трус не играет в хоккей».