[mathematical logic] propositional logic (propositional and connective review | propositional formula | connective priority | truth table satisfiable contradiction tautology)

Based on the previous blog 【 Mathematical logic 】 Predicate logic ( Individual words | Individual domain | The predicate | Full name quantifier | There are quantifiers | Predicate formula | exercises ) ;

One 、 Propositions and connectives

---

Atomic proposition :

p

,

q

,

r

p , q , r

p,q,r Express Atomic proposition , Also known as Simple proposition ;

• really :$1$
• false :$0$

Conjunctions : Last blog 【 Mathematical logic 】 Predicate logic ( Individual words | Individual domain | The predicate | Full name quantifier | There are quantifiers | Predicate formula | exercises ) 3、 ... and . Conjunctions The chapter explains the connectives ;

• Negative connectives :

  ¬

  \lnot

  ¬

• Conjunctions : $p\wedge q$

  ∧ ,

• Disjunctive connectives : $p\vee q$

  ∨ ,

• Implicative connectives : $p\to q$

  → ,

• Equivalent connectives : $pq$

  ,

Two 、 Propositional formula

---

Propositional formula form :

① Single Propositional argument / Propositional constant Is a proposition formula ;

② If

A

A

A Is a proposition formula , be

(

¬

A

)

(\lnot A)

(¬A) It is also a propositional formula ;

③ If

A

,

B

A,B

A,B Is a proposition formula , be

(

A

∧

B

)

,

(

A

∨

B

)

,

(

A

→

B

)

,

(

A

B

)

(A \land B) , (A \lor B), (A \to B), (A \leftrightarrow B)

(A∧B),(A∨B),(A→B),(AB) It is also a propositional formula ;

④ A limited number of times application ① ② ③ Formed symbol string Is a proposition formula ; ( Infinite times cannot )

3、 ... and 、 Examples of propositional formulas

---

Examples of propositional formulas :

Simple proposition :

p

p

p

Compound proposition : Use Conjunctions The proposition of is called Compound proposition ;

¬

p

\lnot p

¬p

(

p

→

q

)

(p \to q)

(p→q) , The outermost parentheses can be omitted ,

p

→

q

p \to q

p→q

(

p

→

(

q

→

r

)

)

(p \to (q \to r))

(p→(q→r)) , The outermost bracket can be omitted , Inner brackets cannot ,

p

→

(

q

→

r

)

p \to (q \to r)

p→(q→r) ;

Four 、 Connective priority

---

Connective priority :

“

¬

\lnot

¬” Greater than “

∧

,

∨

\land , \lor

∧,∨” Greater than “

→

,

\to, \leftrightarrow

→,”

∧

,

∨

\land , \lor

∧,∨ Same priority ;

→

,

\to, \leftrightarrow

→, Same priority ;

5、 ... and 、 Truth table

---

Truth table :

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

p

→

q

p \to q

p→q yes Satisfiability ;

p

∧

¬

q

p \land \lnot q

p∧¬q yes Paradoxical , Also known as Permanent falsehood ;

p

∧

(

p

∨

q

)

p

p \land ( p \lor q ) \leftrightarrow p

p∧(p∨q)p yes Tautology , Also known as Yongzhen style ;

Satisfiability : Truth table , At least one result is true , It can be true ;

Paradoxical ( Permanent falsehood ) : All truth values are false ;

Satisfiability And Paradoxical , yes A choice Of , Compound proposition Or Satisfiability , Or Paradoxical ;

Tautology ( Yongzhen style ) Is a kind of satisfiable ;