[mathematical logic] propositional logic (equivalent calculus | idempotent law | exchange law | combination law | distribution law | De Morgan law | absorption rate | zero law | identity | exclusion l

Based on the previous blog 【 Mathematical logic 】 Propositional logic ( Review of propositions and connectives | Propositional formula | Connective priority | Truth table Satisfiability Paradoxical Tautology ) ;

One 、 Equivalent calculus

---

Equivalent calculus :

• Equivalent formula
• Basic equivalence
• Equivalence calculus replacement rule

Two 、 Equivalent formula

---

Equivalent concept :

A

,

B

A , B

A,B It's two propositional formulas , If

A

B

A \leftrightarrow B

AB It's Yongzhen style , that

A

,

B

A,B

A,B The two propositional formulas are equivalent , Remember to do

A

⇔

B

A \Leftrightarrow B

A⇔B ;

Equivalent characteristics :

A

A

A and

B

B

B Two propositional formulas , Sure Replace each other , Whenever there is

A

A

A All places can be replaced with

B

B

B , Whenever there is

B

B

B All places can be replaced with

A

A

A ;

prove

p

→

q

p \to q

p→q And

¬

p

∨

q

\lnot p \lor q

¬p∨q Is equivalent ;

$p$	$q$	$p\to q$	$\neg p\vee q$	$(p\to q)(\neg p\vee q)$
$0$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

Write the truth table of two propositional formulas , thus Calculation

(

p

→

q

)

(

¬

p

∨

q

)

(p \to q) \leftrightarrow (\lnot p \lor q)

(p→q)(¬p∨q) Truth table of , After the calculation, it is found that Yongzhen style , According to the definition , These two propositional formulas are equivalent ,

(

p

→

q

)

⇔

(

¬

p

∨

q

)

(p \to q) \Leftrightarrow (\lnot p \lor q)

(p→q)⇔(¬p∨q) ;

3、 ... and 、 Basic equivalence

---

Basic operation rules :

• 1. Idempotent law : $A\iff A\vee A$

  A⇔A∧A

• 2. Commutative law : $A\vee B\iff B\vee A$

  A∧B⇔B∧A

• 3. Associative law : $(A\vee B)\vee C\iff A\vee (B\vee C)$

  (A∧B)∧C⇔A∧(B∧C)

• 4. Distributive law : $A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$

  A∧(B∨C)⇔(A∧B)∨(A∧C)

New operation rules :

• 5. De Morgan law : $\neg (A\vee B)\iff \neg A\wedge \neg B$

  ¬(A∧B)⇔¬A∨¬B

• 6. absorptivity :
  • The former absorbs the latter :

    A

    ∨

    (

    A

    ∧

    B

    )

    ⇔

    A

    A \lor ( A \land B ) \Leftrightarrow A

    A∨(A∧B)⇔A

  • The latter absorbs the former :

    A

    ∧

    (

    A

    ∨

    B

    )

    ⇔

    A

    A \land ( A \lor B ) \Leftrightarrow A

    A∧(A∨B)⇔A ;

0

,

1

0 , 1

0,1 Related operation laws :

• 7. Law of zero : $A\vee 1\iff 1$

  A∧0⇔0

• 8. The same thing :$A\vee 0\iff A$

  A∧1⇔A

• 9. The law of excluded middle :

  A

  ∨

  ¬

  A

  ⇔

  1

  A \lor \lnot A \Leftrightarrow 1

  A∨¬A⇔1

• 10. Law of contradiction :

  A

  ∧

  ¬

  A

  ⇔

  0

  A \land \lnot A \Leftrightarrow 0

  A∧¬A⇔0

The duality principle is applicable to the above operation law , Put both sides

∧

,

∨

\land , \lor

∧,∨ swap , meanwhile

0

,

1

0 ,1

0,1 swap , Equivalence still holds ;

Equivalent implication operation law :

• 11. Double negative rate :

  ¬

  ¬

  A

  ⇔

  A

  \lnot \lnot A \Leftrightarrow A

  ¬¬A⇔A

• 12. Implication equivalence : $\to$

  A→B⇔¬A∨B

• 13. Equivalent equation : $A\to B$

  AB⇔(A→B)∨(B→A)

• 14. Equivalent negative equivalent :

  A

  B

  ⇔

  ¬

  A

  ¬

  B

  A \leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot B

  AB⇔¬A¬B

• 15. Hypothetical translocation ( Converse no proposition ) : $A$

  A→B⇔¬B→¬A

• 16. To fallacy ( Reduction to absurdity ) : $A$

  (A→B)∧(A→¬B)⇔¬A

Four 、 Basic operation

---

Basic operation :

Equivalent equation : Equivalent connectives

\leftrightarrow

It's not necessary , Use

→

,

∨

\to , \lor

→,∨ Two connectives can be substituted Equivalent connectives ;

Implication equivalence : Contains connectives

→

\to

→ It's not necessary , Use

¬

,

∨

\lnot , \lor

¬,∨ Two connectives can be substituted Contains connectives ;

De Morgan law :

• With And ( $\wedge$

  ¬ ) , I can represent or (

• With or ( $\vee$

  ¬ ) , I can represent And (

So come to the conclusion , And non perhaps Or not ( A choice ) , It can express all propositions ;

5、 ... and 、 Equivalent calculus

---

prove

p

→

(

q

→

r

)

p \to ( q \to r )

p→(q→r) And

(

p

∧

q

)

→

r

(p \land q) \to r

(p∧q)→r It is equivalent. ;

Prove that the above two propositions are equivalent , There are two ways :

• One is to list Truth table
• The other is to Equivalent calculus

p

→

(

q

→

r

)

p \to ( q \to r )

p→(q→r)

Use Implication equivalence , Replace : take

q

→

r

q \to r

q→r Replacement for

¬

q

∨

r

\lnot q \lor r

¬q∨r

⇔

p

→

(

¬

q

∨

r

)

\Leftrightarrow p \to ( \lnot q \lor r )

⇔p→(¬q∨r)

Continue to use Implication equivalence , Replace the implication symbol of the outer layer :

⇔

¬

p

∨

(

¬

q

∨

r

)

\Leftrightarrow \lnot p \lor ( \lnot q \lor r )

⇔¬p∨(¬q∨r)

Use Associative law , take

p

,

q

p, q

p,q Bind together :

⇔

(

¬

p

∨

¬

q

)

∨

r

\Leftrightarrow ( \lnot p \lor \lnot q ) \lor r

⇔(¬p∨¬q)∨r

Use De Morgan law , take

¬

\lnot

¬ Take it outside :

⇔

¬

(

p

∧

q

)

∨

r

\Leftrightarrow \lnot ( p \land q ) \lor r

⇔¬(p∧q)∨r

Use Implication equivalence , Replace ;

⇔

(

p

∧

q

)

→

r

\Leftrightarrow (p \land q) \to r

⇔(p∧q)→r