当前位置：网站首页>[mathematical logic] equivalent calculus and reasoning calculus of propositional logic (propositional logic | equivalent calculus | principal conjunctive (disjunctive) paradigm | reasoning calculus)**

[mathematical logic] equivalent calculus and reasoning calculus of propositional logic (propositional logic | equivalent calculus | principal conjunctive (disjunctive) paradigm | reasoning calculus)**

2022-07-03 16:41:00 【Programmer community】

List of articles

One 、 Basic concepts of propositional logic
Two 、 Equivalent calculus
3、 ... and 、 The LORD takes ( Disjunction ) normal form
Four 、 Reasoning and calculation
- 1、 Additional law
- 2、 The law of simplification
- 3、 Hypothetical reasoning
- 4、 Reject
- 5、 Disjunctive syllogism
- 6、 Hypothetical syllogism
- 7、 Equivalent syllogism
- 8、 constructive dilemma

Reference blog :

【 Mathematical logic 】 Propositions and conjunctions ( proposition | Proposition symbolization | Truth connectives | no | Syntaxis | Disjunction | Non truth connectives | implication | Equivalent )
【 Mathematical logic 】 Propositional logic ( Review of propositions and connectives | Propositional formula | Connective priority | Truth table Satisfiability Paradoxical Tautology )
【 Mathematical logic 】 Propositional logic ( Equivalent calculus | Idempotent law | Commutative law | Associative law | Distributive law | De Morgan law | absorptivity | Law of zero | The same thing | The law of excluded middle | Law of contradiction | Double negative rate | Implication equivalence … )
【 Mathematical logic 】 normal form ( Conjunctive paradigm | Disjunctive normal form | Major item | Small term | The maximal term | minterm | The main conjunctive paradigm | Principal disjunctive normal form | Equivalent calculus method for principal analysis / Conjunctive paradigm | Truth table method for principal analysis / Conjunctive paradigm )
【 Mathematical logic 】 Propositional logic ( Propositional logic inference | The formal structure of reasoning | The law of reasoning | Additional law | The law of simplification | Hypothetical reasoning | Reject | Disjunctive syllogism | Hypothetical syllogism | Equivalent syllogism | constructive dilemma )
【 Mathematical logic 】 Propositional logic ( Judgment of the correctness of propositional logic reasoning | The formal structure is forever true - Equivalent calculus | Deduce the conclusion from the premise - logical reasoning )

One 、 Basic concepts of propositional logic

Basic concepts of propositional logic

Propositional logic connectives
Truth table
Propositional logic type : Satisfiability , Yongzhen style , Permanent falsehood ;

1 . Propositional formula form :

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

② If

$A$ Is a proposition formula , be

(

)

(\lnot A)

$(\neg A)$ It is also a propositional formula ;

③ If

A,B

$A, B$ Is a proposition formula , be

(

∧

)

(

∨

)

(

→

)

(

)

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

$(A \land B), (A \lor B), (A \to B), (A B)$ It is also a propositional formula ;

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

2 . Conjunctions :

Atomic proposition :

p , q , r

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

really :
false :

Negative connectives : $\lnot$
$\neg$
Conjunctions : $\land$
$\land$ ,
Disjunctive connectives : $\lor$
$\lor$ ,
Implicative connectives : $\to$
$\to$ ,
Equivalent connectives : $\leftrightarrow$
,

Connective priority :

“

\lnot

$\neg$ ” Greater than “

∧

∨

\land , \lor

$\land, \lor$ ” Greater than “

→

\to, \leftrightarrow

$\to,$ ”

∧

∨

\land , \lor

$\land, \lor$ Same priority ;

→

\to, \leftrightarrow

$\to,$ Same priority ;

3 . Propositional logic type :

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 ;

4 . Simple proposition formalization :

Reference resources : Compound proposition And Proposition symbolization

Define propositions : Use

p,q

$p, q$ A declarative sentence that stands for truth and falsehood ;

Use connectives : Then use connectives to connect these

p,q

$p, q$ proposition ;

Reference blog :

【 Mathematical logic 】 Propositions and conjunctions ( proposition | Proposition symbolization | Truth connectives | no | Syntaxis | Disjunction | Non truth connectives | implication | Equivalent )
【 Mathematical logic 】 Propositional logic ( Review of propositions and connectives | Propositional formula | Connective priority | Truth table Satisfiability Paradoxical Tautology )

Two 、 Equivalent calculus

Equivalent concept :

A , B

$A, B$ It's two propositional formulas , If

A \leftrightarrow B

$A B$ It's Yongzhen style , that

A,B

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

⇔

A \Leftrightarrow B

$A \Leftrightarrow B$ ;

Equivalence calculus replacement rule :

$A$ and

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

$A$ All places can be replaced with

$B$ , Whenever there is

$B$ All places can be replaced with

$A$ ;

Basic operation rules :

1. Idempotent law : $\Leftrightarrow A \lor AA⇔A∨A , A ⇔ A ∧ A A \Leftrightarrow A \land A$
$A \Leftrightarrow A \land A$
2. Commutative law : $\lor B \Leftrightarrow B \lor AA∨B⇔B∨A , A ∧ B ⇔ B ∧ A A \land B \Leftrightarrow B \land A$
$A \land B \Leftrightarrow B \land A$
3. Associative law : $\lor B ) \lor C \Leftrightarrow A \lor (B \lor C)(A∨B)∨C⇔A∨(B∨C) , ( A ∧ B ) ∧ C ⇔ A ∧ ( B ∧ C ) (A \land B ) \land C \Leftrightarrow A \land (B \land C)$
$(A \land B) \land C \Leftrightarrow A \land (B \land C)$
4. Distributive law : $\lor (B \land C) \Leftrightarrow ( A \lor B ) \land ( A \lor C )A∨(B∧C)⇔(A∨B)∧(A∨C) , A ∧ ( B ∨ C ) ⇔ ( A ∧ B ) ∨ ( A ∧ C ) A \land (B \lor C) \Leftrightarrow ( A \land B ) \lor ( A \land C )$
$A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C)$

New operation rules :

5. De Morgan law :
¬
(
A
∨
B
)
⇔
¬
A
∧
¬
B
\lnot ( A \lor B ) \Leftrightarrow \lnot A \land \lnot B
$\neg (A \lor B) \Leftrightarrow \neg A \land \neg B$ ,
¬
(
A
∧
B
)
⇔
¬
A
∨
¬
B
\lnot ( A \land B ) \Leftrightarrow \lnot A \lor \lnot B
- With And ( $\land∧ ) Not ( ¬ \lnot¬ ) , I can represent or ( ∨ \lor∨ )$
- With or ( $\lor∨ ) Not ( ¬ \lnot¬ ) , I can represent And ( ∧ \land∧ )$
$\neg (A \land B) \Leftrightarrow \neg A \lor \neg B$
6. absorptivity :
- The former absorbs the latter : $\lor ( A \land B ) \Leftrightarrow A$
  $A \lor (A \land B) \Leftrightarrow A$
- The latter absorbs the former : $\land ( A \lor B ) \Leftrightarrow A$
  $A \land (A \lor B) \Leftrightarrow A$ ;

0 , 1

$0, 1$ Related operation laws :

7. Law of zero :
A
∨
1
⇔
1
A \lor 1 \Leftrightarrow 1
$A \lor 1 \Leftrightarrow 1$ ,
A
∧
0
⇔
0
A \land 0 \Leftrightarrow 0
- And zero yuan The result of the operation is zero yuan ;
$A \land 0 \Leftrightarrow 0$
8. The same thing :
A
∨
0
⇔
A
A \lor 0 \Leftrightarrow A
$A \lor 0 \Leftrightarrow A$ ,
A
∧
1
⇔
A
A \land 1 \Leftrightarrow A
- And Unit element The result of the operation is In itself
$A \land 1 \Leftrightarrow A$
9. The law of excluded middle : $\lor \lnot A \Leftrightarrow 1$
$A \lor \neg A \Leftrightarrow 1$
10. Law of contradiction : $\land \lnot A \Leftrightarrow 0$
$A \land \neg A \Leftrightarrow 0$

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

∧

∨

\land , \lor

$\land, \lor$ swap , meanwhile

0 ,1

$0, 1$ swap , Equivalence still holds ;

Equivalent implication operation law :

11. Double negative rate : $\lnot \lnot A \Leftrightarrow A$
$\neg \neg A \Leftrightarrow A$
12. Implication equivalence :
A
→
B
⇔
¬
A
∨
B
A \to B \Leftrightarrow \lnot A \lor B
- Replace implied connectives : Contains connectives $\to→ It's not necessary , Use ¬ , ∨ \lnot , \lor¬,∨ Two connectives can be substituted Contains connectives ;$
$A \to B \Leftrightarrow \neg A \lor B$
13. Equivalent equation :
A
B
⇔
(
A
→
B
)
∨
(
B
→
A
)
A \leftrightarrow B \Leftrightarrow ( A \to B ) \lor ( B \to A )
- Double arrow ( Equivalent connectives ) It can be understood as a necessary condition for re division
- $\to BA→B ( Contains connectives ) Comprehend A AA yes B BB Sufficient conditions of , B BB yes A AA Necessary conditions$
- $\to AB→A ( Contains connectives ) Comprehend B BB yes A AA Sufficient conditions of , A AA yes B BB Necessary conditions$
- Replace equivalent connectives : Equivalent connectives $\leftrightarrow It's not necessary , Use → , ∨ \to , \lor→,∨ Two connectives can be substituted Equivalent connectives ;$
$A B \Leftrightarrow (A \to B) \lor (B \to A)$
14. Equivalent negative equivalent : $\leftrightarrow B \Leftrightarrow \lnot A \leftrightarrow \lnot B$
$A B \Leftrightarrow \neg A \neg B$
15. Hypothetical translocation ( Converse no proposition ) :
A
→
B
⇔
¬
B
→
¬
A
A \to B \Leftrightarrow \lnot B \to \lnot A
$A \to B \Leftrightarrow \neg B \to \neg A$
16. To fallacy ( Reduction to absurdity ) :
(
A
→
B
)
∧
(
A
→
¬
B
)
⇔
¬
A
( A \to B ) \land ( A \to \lnot B ) \Leftrightarrow \lnot A
- This is the principle of disproof , from $\lnot B¬B , B BB and ¬ B \lnot B¬B Is contradictory , be A AA It's wrong. , ¬ A \lnot A¬A Yes. ;$
$(A \to B) \land (A \to \neg B) \Leftrightarrow \neg A$

3、 ... and 、 The LORD takes ( Disjunction ) normal form

1 . minterm

minterm : minterm yes A kind of Simple conjunction ;

1. Premise ( Simple conjunction ) : contain
$n$ individual Propositional variables Of Simple conjunction ;
2. The number of occurrence of propositional variables : Each propositional variable all With written words Of form In which , And Only appears once ;
3. Where the propositional variable appears :
The first
i
i
$i$ (
1
≤
i
≤
n
1 \leq i \leq n
$1 \leq i \leq n$ ) Words appear in From the left The first
i
i
- $n$ It refers to the number of propositional variables ;
$i$ A place ;
4. Summary of minor items : Meeting the above three conditions Simple conjunction , be called minterm ;
5. $m_imi And M i M_i$
$M_{i}$ The relationship between :①

Each proposition In the order specified , And Only once Of Simple conjunction , It is called the minimal term ;

Minima list the true assignment , Because only one case of conjunctive form comes true , That is Quanzhen ;

2 . The maximal term

About The maximal term Of explain :

1. The number of maximal terms : $2^n$
$2^{n}$ individual The maximal term ;
2. Not equal to each other : $2^n$
$2^{n}$ A very large item all Not equal to each other ;
3. The maximal term : $m_imi Express The first i ii A very large item , among i i$
$i$ Is the largest item False assignment Of Decimal means ;
4. Maximum item name : The first $M_i$
$M_{i}$ ;
5. $m_imi And M i M_i$
$M_{i}$ The relationship between :①

Each proposition In the order specified , And Only once Of Simple disjunctive , It is called the minimal term ;

The maximal term lists the false assignment , Because only one case of disjunction is false , That's all vacation ;

3 . The LORD takes ( Disjunction ) normal form

① List requirements The LORD takes ( Disjunction ) normal form Truth table of ;

p , q , r

$p, q, r$ The truth value of three propositions starts from

0,0,0

$0, 0, 0$ To

1,1,1

$1, 1, 1$ , Yes

2^3 = 8

$2^{3} = 8$ Column , Each column corresponds to

∼

m_0 \sim m_8

$m_{0} \sim m_{8}$ minterm ,

∼

M_0 \sim M_8

$M_{0} \sim M_{8}$ The maximal term ;

② Principal disjunctive normal form ( Take the minimum ) : The truth value in the truth table is

$1$ The column of take minterm ; minterm True assignment ; According to the subscript and true assignment of the minimum term, the propositional formula of the minimum term can be listed ;

③ The main conjunctive paradigm ( Take the maximum ) : The truth value in the truth table is

$0$ The column of take The maximal term ; The maximal term False assignment ; According to the subscript of the maximum term and the false assignment, the propositional formula of the maximum term can be listed

4 . summary :

minterm : Combined type , True assignment , Take the truth table when calculating really Column ;

The maximal term : disjunction , False assignment , Take the truth table when calculating false Column ;

Four 、 Reasoning and calculation

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$

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$ ;

1、 Additional law

Additional law :

⇒

(

∨

)

A \Rightarrow (A \lor B)

$A \Rightarrow (A \lor B)$

according to The law of reasoning ,

→

(

∨

)

A \to (A \lor B)

$A \to (A \lor B)$ Implicative form yes Yongzhen style ;

Premise :

$A$

Conclusion :

∨

A \lor B

$A \lor B$

$A$ Yes. , that

∨

A \lor B

$A \lor B$ That's right. , The latter is an addition to the former

$B$ ;

2、 The law of simplification

The law of simplification :

(

∧

)

⇒

( A \land B ) \Rightarrow A

$(A \land B) \Rightarrow A$ ,

(

∧

)

⇒

( A \land B ) \Rightarrow B

$(A \land B) \Rightarrow B$

according to The law of reasoning ,

(

∧

)

→

( A \land B ) \to A

$(A \land B) \to A$ ,

(

∧

)

→

( A \land B ) \to B

$(A \land B) \to B$ Implicative form yes Yongzhen style ;

Premise :

∧

A \land B

$A \land B$

Conclusion :

$A$ or

$B$

∧

A \land B

$A \land B$ Yes. , that

$A$ or

$B$ That's right. , The latter is simplified on the basis of the former ;

3、 Hypothetical reasoning

Hypothetical reasoning :

(

→

)

∧

⇒

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

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

according to The law of reasoning ,

(

→

)

∧

→

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

$(A \to B) \land A \to B$ Implicative form yes Yongzhen style ;

Premise :

→

A \to B

$A \to B$ ,

$A$

Conclusion :

$B$

This is a typical small three paragraph theory ;

4、 Reject

Reject :

(

→

)

∧

⇒

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

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

according to The law of reasoning ,

(

→

)

∧

→

( A \to B ) \land \lnot B \to \lnot A

$(A \to B) \land \neg B \to \neg A$ Implicative form yes Yongzhen style ;

Premise :

→

A \to B

$A \to B$ ,

\lnot B

$\neg B$

Conclusion :

\lnot A

$\neg A$

It can be understood as a counter evidence ;

5、 Disjunctive syllogism

Disjunctive syllogism :

(

∨

)

∧

⇒

( A \lor B ) \land \lnot A \Rightarrow B

$(A \lor B) \land \neg A \Rightarrow B$ ,

(

∨

)

∧

⇒

( A \lor B ) \land \lnot B \Rightarrow A

$(A \lor B) \land \neg B \Rightarrow A$

according to The law of reasoning ,

(

∨

)

∧

→

( A \lor B ) \land \lnot A \to B

$(A \lor B) \land \neg A \to B$ ,

(

∨

)

∧

→

( A \lor B ) \land \lnot B \to A

$(A \lor B) \land \neg B \to A$ Implicative form yes Yongzhen style ;

Premise :

∨

A \lor B

$A \lor B$ ,

\lnot A

$\neg A$

Conclusion :

$B$

(

∨

)

(A \lor B)

$(A \lor B)$ That's right. , among

$A$ It's wrong. , that

$B$ It must be right ;

(

∨

)

(A \lor B)

$(A \lor B)$ That's right. , among

$B$ It's wrong. , that

$A$ It must be right ;

Police often use reasoning methods to solve cases , Exclude suspects one by one ;

6、 Hypothetical syllogism

Hypothetical syllogism :

(

→

)

∧

(

→

)

⇒

(

→

)

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

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

according to The law of reasoning ,

(

→

)

∧

(

→

)

→

(

→

)

( A \to B ) \land ( B \to C ) \to ( A \to C )

$(A \to B) \land (B \to C) \to (A \to C)$ Implicative form yes Yongzhen style ;

Premise :

→

A \to B

$A \to B$ ,

→

B \to C

$B \to C$

Conclusion :

→

A \to C

$A \to C$

7、 Equivalent syllogism

Equivalent syllogism :

(

)

∧

(

)

⇒

(

)

( A \leftrightarrow B ) \land ( B \leftrightarrow C ) \Rightarrow ( A \leftrightarrow C )

$(A B) \land (B C) \Rightarrow (A C)$

according to The law of reasoning ,

(

)

∧

(

)

→

(

)

( ( A \leftrightarrow B ) \land ( B \leftrightarrow C ) ) \to ( A \leftrightarrow C )

$((A B) \land (B C)) \to (A C)$ Implicative form yes Yongzhen style ;

Premise :

A \leftrightarrow B

$A B$ ,

B \leftrightarrow C

$B C$

Conclusion :

A \leftrightarrow C

$A C$

8、 constructive dilemma

Equivalent syllogism :

(

→

)

∧

(

→

)

∧

(

∨

)

⇒

(

∨

)

( A \to B ) \land ( C \to D ) \land ( A \lor C ) \Rightarrow ( B \lor D )

$(A \to B) \land (C \to D) \land (A \lor C) \Rightarrow (B \lor D)$

according to The law of reasoning ,

(

→

)

∧

(

→

)

∧

(

∨

)

→

(

∨

)

( ( A \to B ) \land ( C \to D ) \land ( A \lor C ) ) \to ( ( B \lor D ) )

$((A \to B) \land (C \to D) \land (A \lor C)) \to ((B \lor D))$ Implicative form yes Yongzhen style ;

Premise :

→

A \to B

$A \to B$ ,

→

C \to D

$C \to D$ ,

∨

A \lor C

$A \lor C$

Conclusion :

∨

B \lor D

$B \lor D$

Way of understanding :

$A$ Is to develop the economy ,

$B$ It's pollution

$C$ Is not to develop the economy ,

$D$ It's poverty

∨

A \lor B

$A \lor B$ Or develop the economy , Or do not develop the economy
The result is

∨

B \lor D

$B \lor D$ , Or produce pollution , Or endure poverty

原网站

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

当前位置：网站首页>[mathematical logic] equivalent calculus and reasoning calculus of propositional logic (propositional logic | equivalent calculus | principal conjunctive (disjunctive) paradigm | reasoning calculus)**

[mathematical logic] equivalent calculus and reasoning calculus of propositional logic (propositional logic | equivalent calculus | principal conjunctive (disjunctive) paradigm | reasoning calculus)**

List of articles

One 、 Basic concepts of propositional logic

Two 、 Equivalent calculus

3、 ... and 、 The LORD takes ( Disjunction ) normal form

Four 、 Reasoning and calculation

1、 Additional law

2、 The law of simplification

3、 Hypothetical reasoning

4、 Reject

5、 Disjunctive syllogism

6、 Hypothetical syllogism

7、 Equivalent syllogism

8、 constructive dilemma

边栏推荐

猜你喜欢

随机推荐