Discrete mathematics: Main Normal Form (main disjunctive normal form, main conjunctive normal form)

Solve the main disjunctive normal form 、 Principal conjunctive normal form method

1、 Truth table method
① List all possible values of arguments in the table
② Look up the table to judge the proposition
Propositional result really , The argument value corresponds to Principal disjunctive normal form
Propositional result false , The argument value corresponds to The main conjunctive paradigm

2、 Equivalent algorithm
① Propositional simplification
Implication equivalence ：A→B ¬A∨B（ effect ： Go to →）
Law of contradiction ：A ∧¬A（ effect ： Complement argument ）
Distributive law ：(A∧B)∨C (A∨C)∧(B∨C)、(A∨B)∧C (A∧C)∨(B∧C)
② Judgement proposition
Propositional result really , The argument value corresponds to Principal disjunctive normal form
Propositional result false , The argument value corresponds to The main conjunctive paradigm

Example

Find the formula (p→q)∧(q→r) Principal disjunctive normal form and principal conjunctive normal form of 、 True assignment .
Explain ：
1、 Truth table method

p	q	r	p→q	q→r	(p→q)∧(q→r)
0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

Look up the table
True assignment ：000、001、011、111
Principal disjunctive normal form ：∑(0,1,3,7)

False assignment ：010、100、101、110
The main conjunctive paradigm ：∏(2,4,5,6)

2、 Equivalent algorithm
(p→q)∧(q→r)
= (¬p∨q)∧(¬q∨r) -----------------------------（ Implication equivalence ： Simplification →）
= ((¬p∨q)∨(¬r∧r)))∧((¬q∨r)∨(¬p∧p))----（ Law of contradiction ： Complement argument ）
= (¬p∨q∨¬r)∧(¬p∨q∨r)∧(¬p∨¬q∨r)∧(p∨¬q∨r)—（ Distributive law ： Simplification ）
M₅M₄M₆M₂

According to the calculation results The main conjunctive paradigm ：∏(2,4,5,6)
False assignment ：010、100、101、110
be Principal disjunctive normal form ：∑(0,1,3,7)
True assignment ：000、001、011、111