当前位置：网站首页>[mathematical logic] propositional logic (judgment of the correctness of propositional logic reasoning | formal structure is eternal truth - equivalent calculus | deduction from premise - logical reas

[mathematical logic] propositional logic (judgment of the correctness of propositional logic reasoning | formal structure is eternal truth - equivalent calculus | deduction from premise - logical reas

2022-07-03 03:40:00 【Programmer community】

List of articles

One 、 Judgment of the correctness of propositional logic reasoning
Two 、 The formal structure is forever true ( Equivalent calculus )
3、 ... and 、 Deduce the conclusion from the premise ( logical reasoning )

One 、 Judgment of the correctness of propositional logic reasoning

Propositional reasoning , according to Premise , Reasoning out Conclusion ;

Such as :
Premise : yes

→

(

→

)

p \to (q \to r)

$p \to (q \to r)$ ,

$p$ ,

$q$ ;
Conclusion : yes

$r$

How to judge according to the above premise , The reasoning conclusion is correct ?

The law of reasoning :

A,B

$A, B$ There are two propositions , If

→

A \to B

$A \to B$ It's Yongzhen style , that

⇒

A \Rightarrow B

$A \Rightarrow B$ ;

The formal structure of reasoning

Premise :

⋯

A_1 , A_2 , \cdots , A_k

$A_{1}, A_{2}, \dots, A_{k}$

Conclusion :

$B$

The formal structure of reasoning is :

(

∧

⋯

∧

)

→

(A_1 \land A_2 \land \cdots \land A_k) \to B

$(A_{1} \land A_{2} \land \dots \land A_{k}) \to B$

Propositional logic The correctness of reasoning determine , There are two ways ;

Method 1 : Write inferential Formal structure , Check whether the formal structure of the reasoning is Yongzhen style ; If it is Yongzhen , Then the reasoning is correct ;

Method 2 : from Premise Deduce Conclusion , according to Equivalence calculus rules , Rules of reasoning , Make a deduction ;

Two 、 The formal structure is forever true ( Equivalent calculus )

Premise :

→

(

→

)

p \to (q \to r)

$p \to (q \to r)$ ,

$p$ ,

$q$ ;
Conclusion :

$r$

The formal structure of reasoning is :

(

→

(

→

)

∧

→

(p \to (q \to r)) \land p \land q \to r

$(p \to (q \to r)) \land p \land q \to r$

Use Equivalent calculus Methods , Verify whether the above formal structure is Yongzhen style ;

Connective The priority for :“

\lnot

$\neg$ ” Greater than “

∧

∨

\land , \lor

$\land, \lor$ ” Greater than “

→

\to, \leftrightarrow

$\to,$ ” ; Start with the higher priority ;

(

→

(

→

)

∧

→

(p \to (q \to r)) \land p \land q \to r

$(p \to (q \to r)) \land p \land q \to r$

Implication equivalence : Use Implication equivalence The rules , Put the above

(

→

(

→

)

(p \to (q \to r))

$(p \to (q \to r))$ Perform equivalent calculus :

⇔

(

∨

(

∨

)

∧

→

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

$\Leftrightarrow (\neg p \lor (\neg q \lor r)) \land p \land q \to r$

Distribution rate : according to Distribution rate , Calculation

(

∨

(

∨

)

∧

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

$(\neg p \lor (\neg q \lor r)) \land p$ part :

⇔

(

∧

)

∨

(

∨

)

∧

)

∧

→

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

$\Leftrightarrow ((\neg p \land p) \lor ((\neg q \lor r) \land p)) \land q \to r$

Law of contradiction : among according to Law of contradiction You know ,

∧

⇔

\lnot p \land p \Leftrightarrow 0

$\neg p \land p \Leftrightarrow 0$ :

⇔

(

∨

(

∨

)

∧

)

∧

→

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

$\Leftrightarrow (0 \lor ((\neg q \lor r) \land p)) \land q \to r$

The same thing : according to The same thing ,

∨

(

∨

)

∧

)

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

$0 \lor ((\neg q \lor r) \land p)$ And

(

∨

)

∧

(\lnot q \lor r) \land p

$(\neg q \lor r) \land p$ It is equivalent. :

⇔

(

∨

)

∧

)

∧

→

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

$\Leftrightarrow ((\neg q \lor r) \land p) \land q \to r$

Associative law : according to Associative law , To recombine

(

∨

)

∧

)

∧

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

$((\neg q \lor r) \land p) \land q$ by

(

∨

)

∧

)

∧

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

$((\neg q \lor r) \land q) \land p$ :

⇔

(

∨

)

∧

)

∧

→

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

$\Leftrightarrow ((\neg q \lor r) \land q) \land p \to r$

Distribution rate : according to Distribution rate , Calculation

(

∨

)

∧

(\lnot q \lor r) \land q

$(\neg q \lor r) \land q$ , The result is

(

∧

)

∨

(

∧

)

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

$(\neg q \land q) \lor (r \land q)$

⇔

(

∧

)

∨

(

∧

)

∧

→

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

$\Leftrightarrow ((\neg q \land q) \lor (r \land q)) \land p \to r$

Law of contradiction : according to Law of contradiction Calculation

∧

\lnot q \land q

$\neg q \land q$ , As a result,

$0$ :

⇔

(

∨

(

∧

)

∧

→

\Leftrightarrow ( 0 \lor (r \land q) ) \land p \to r

$\Leftrightarrow (0 \lor (r \land q)) \land p \to r$

The same thing : According to the same ,

∨

(

∧

)

0 \lor (r \land q)

$0 \lor (r \land q)$ Equivalent to

(

∧

)

(r \land q)

$(r \land q)$ :

⇔

(

∧

)

∧

→

\Leftrightarrow (r \land q) \land p \to r

$\Leftrightarrow (r \land q) \land p \to r$

Connective priority :

(

∧

)

∧

(r \land q) \land p

$(r \land q) \land p$ in , The conjunctions have the same priority , Brackets can be deleted , Put three propositions in a bracket ;

⇔

(

∧

)

→

\Leftrightarrow (r \land q \land p ) \to r

$\Leftrightarrow (r \land q \land p) \to r$

Implication equivalence : according to Implication equivalence , elimination Implicative connectives

→

\to

$\to$ :

⇔

(

∧

)

∨

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

$\Leftrightarrow \neg (r \land q \land p) \lor r$

De Morgan law : according to De Morgan law , Assign a negative sign in parentheses ;

⇔

(

∨

)

∨

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

$\Leftrightarrow (\neg r \lor \neg q \lor \neg p) \lor r$

Connective priority :

(

∨

)

∨

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

$(\neg r \lor \neg q \lor \neg p) \lor r$ in , The conjunctions have the same priority , Brackets can be deleted , Put three propositions in a bracket ;

⇔

∨

\Leftrightarrow \lnot r \lor \lnot q \lor \lnot p \lor r

$\Leftrightarrow \neg r \lor \neg q \lor \neg p \lor r$

The law of excluded middle : According to the law of exclusion ,

∨

\lnot r \lor r

$\neg r \lor r$ And

$1$ Equivalent ;

⇔

∨

\Leftrightarrow 1 \lor \lnot q \lor \lnot p

$\Leftrightarrow 1 \lor \neg q \lor \neg p$

Law of zero : According to the zero law ,

$1$ Extract any value , Are equivalent to

$1$ :

⇔

\Leftrightarrow 1

$\Leftrightarrow 1$

3、 ... and 、 Deduce the conclusion from the premise ( logical reasoning )

Premise :

→

(

→

)

p \to (q \to r)

$p \to (q \to r)$ ,

$p$ ,

$q$ ;
Conclusion :

$r$

Connect the prerequisites with conjunctive connectives ,

(

→

(

→

)

∧

(p \to (q \to r)) \land p \land q

$(p \to (q \to r)) \land p \land q$ , Perform equivalent calculus , To calculate the

$r$ ;

(

→

(

→

)

∧

(p \to (q \to r)) \land p \land q

$(p \to (q \to r)) \land p \land q$

Equivalent calculus Associative law :

⇔

(

→

(

→

)

∧

)

∧

\Leftrightarrow ((p \to (q \to r)) \land p) \land q

$\Leftrightarrow ((p \to (q \to r)) \land p) \land q$

logical reasoning Hypothetical reasoning :

(

→

)

∧

⇒

( A \to B ) \land A \Rightarrow B

$(A \to B) \land A \Rightarrow B$ , So from

(

→

(

→

)

∧

(p \to (q \to r)) \land p

$(p \to (q \to r)) \land p$ It can be inferred that

→

q \to r

$q \to r$ ;

⇒

(

→

)

∨

\Rightarrow (q \to r) \lor q

$\Rightarrow (q \to r) \lor q$

logical reasoning Hypothetical reasoning :

(

→

)

∧

⇒

( A \to B ) \land A \Rightarrow B

$(A \to B) \land A \Rightarrow B$ , So from

(

→

)

∨

(q \to r) \lor q

$(q \to r) \lor q$ It can be inferred that

$r$ ;

⇒

\Rightarrow r

$\Rightarrow r$

logical reasoning Than Equivalent calculus fast , Equivalent calculus is more intuitive , Logical reasoning needs to choose the appropriate reasoning law ;

原网站

版权声明
本文为[Programmer community]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202150734464710.html