[discrete mathematics review series] i. propositional logic

1、 What is a proposition
The only statement to judge the result
(1) True proposition : A proposition whose result is true
(2) False proposition : The judgment result is a false proposition
(3) paradox : Contradictory statements
for example : What I am saying is a lie
So how to judge a proposition ？
(1) First look at whether it is a declarative sentence . An imperative sentence , Rhetorical questions , Exclamation sentence … It's not a proposition
(2) See if the truth value is unique
example :x>1 It's not a proposition
Tomorrow is a sunny day ： Declarative sentence , Result only ： It's either sunny or rainy

2、 What is a simple proposition （ Atomic proposition ）
The sentence can't be broken down
Proposition symbolization : Symbolize a proposition ,p,q,r etc.
Propositional constant ( Propositional constant ): A statement with a definite truth value
Propositional variables ( Propositional argument ): A statement whose truth value can vary example :x>2 x Different assignment results in different results , It is not a proposition
Compound proposition : A proposition that is connected by connectives

3、 What is a conjunction
(1)¬: Negative connectives translate : No , Not
(2)∧: Conjunctions translate : Both … also …, Not only … and …, although … however …
(3)∨: Disjunctive connectives translate : or
1) Compatibility or ： You can send it at the same time
2) Repulsion or : Can't send at the same time
example : I either eat or sleep pVq Exclusion or both cannot occur at the same time
Choose Xiao Wang and Xiao Ming as monitor (¬p∧q)∨(p∧¬q)
(4) Contains connectives : Here are p->q

(5)<–>: Equivalent connectives : translate : If and only if

4.(1) Propositional formula ( The resultant formula ):
A correct representation of a finite number of propositions and connectives example ：pVq correct pq Incorrect
(2)n Layer proposition formula :

5. assignment ( explain )
Assign a value to the propositional variable of the propositional formula , If the result is true, assign a value to it , Otherwise, assign false values example pVq 11 It's true 00 For false .
The number of assignments :n There are three propositional variables in common 2^n Assignments

6.(1) Tautology ( Yongzhen style ): Any assignment result is true
(2) Paradoxical ( Permanent falsehood ): Any assignment result is false
(3) Satisfiability : There is at least one set of true assignments
Truth table ：

7.(1)n Meta truth function （ Truth table ）: One n(n≥1) Cartesian product of order {0,1}” To {0,1} The function of is called a n Meta truth function F Write it down as
F: {0,1}"→{0,1 }
(2)n There are three propositional variables 2^{n Assignments , Yes 2}2^n A truth function （ Truth table ）
example p q There are four kinds of assignment , You can write 16 A truth function with different results

8. proposition A And proposition B equivalence :
Equivalency AB It's tautology , That is, both assignment results are the same ,A<=>B
Judge whether it is equivalent :
(1) Compare and judge with the truth table
(2) Equivalent calculus
The formula of equivalent calculus ：

purpose : Equivalent calculus
1） Verify that the equivalents are equal

(2) Determine the type of formula

10.(1) Disjunctive normal form : A disjunctive form consisting only of a finite number of simple conjunctions
(2) Conjunctive paradigm : A conjunctive form consisting only of a finite number of simple disjunctions
(3) The existence theorem of normal form : Any propositional formula has its equivalent disjunctive normal form and conjunctive normal form . And not unique

11.(1) minterm : In the simple conjunctive, each propositional variable and its negation only appear once ,n Propositional variables produce 2^n minterm （ Syntaxis , True assignment ）
(2) The maximal term : In simple disjunctions, each propositional variable and its negation only appear once ,n Propositional variables produce 2^n The maximal term （ Disjunction , False assignment ）
The opposite of the minimal term is the maximal term
n The propositional formula of propositional variables contains 2 Of n The minimal or maximal term of the power
12.(1) Principal disjunctive normal form : The formula A The simple conjunctives in the disjunctive normal form of are all minimal terms and unique
(2) The main conjunctive paradigm : The formula A The simple disjunctions in the conjunctive normal form of are all maximal terms and unique
（3） How to find the principal disjunctive normal form
a. First find the disjunctive normal form
b. Then find the principal disjunctive normal form
c. Truth table Find the real assignment

(4) Main disjunctive normal form uses :
(1) Judge whether the two propositional formulas are equivalent
If two propositions are equivalent, their principal disjunctions must be the same

(2) Judge the type of propositional formula
if A It's tautology , If and only if its main disjunction contains all minimal terms （ Because the minimal term is a real assignment ）
if A It is contradictory , If and only if its main disjunction does not contain any minimal term
if A To satisfy the formula , If and only if its main disjunction contains at least one minimal term

(3) Find the true assignment and false assignment of propositions
A minimal term is a real assignment
Negating the minimal term is the maximal term
13. Full feature set : set up S Is a set of connectives , If any truth value function can be used, it only contains S The propositional formula of the connectives in
Basic full feature set :{¬,∧,∨}、{¬,∧}、{¬,∨}、{¬,→}、

14.(1)p↑q: And non form Equivalent to ¬(p∧q) Referred to as "p And q The negation of "
(2)p↓q: Or not : Equivalent to ¬(p∨q) Referred to as "p or q The negation of "
(3){↑},{↓} Is a full feature set

15. Combinational circuit ： The logic operation is physically realized by electronic components , Form a propositional formula

16. Reasoning theory
What is reasoning ?
Reasoning is the thinking process of withdrawing the conclusion from the premise .
A premise is a known propositional formula
The conclusion is that the propositional formula proposed before to use some inference rules to exit
if (A1,A2…Ak)→B It's tautology , said A1,A2 ,…,Ak Draw conclusions B My reasoning is correct ,B yes A1 ,A2 ,…,Ak A logical or valid conclusion ． call (A1,A2…Ak)→B For the premise A1,A2,…,Ak Draw conclusions B The formal structure of reasoning .
example : If the weather is cool , Xiao Wang won't go swimming . It's cool . So Xiao Wang didn't go swimming .
Using truth table method

Use the equivalent algorithm

To judge whether a reasoning is correct or not, it mainly depends on whether its implication is tautological
It can be used ：
1） Truth table method
2） Equivalent algorithm
3） The main disjunctive normal form sends
To judge

16.(1) The law of reasoning
The following reasoning theorems are established under the premise that the premise and conclusion are true

(2) Reasoning problem solving method :
1) Ask directly : Through known premises , Judge whether the conclusion is tenable

2) Additional premises : If the conclusion is implicative , The left side of the arrow can be used as the premise , To the right of the judgment arrow is the conclusion
You can put the antecedent of the conclusion into the premise , It is sufficient to prove that this formula is tautological

3) Reduction to absurdity : Suppose the conclusion is false , As a precondition , Judge whether the result is contradictory

other : When it is tautological , The results of the principal disjunctive normal form and the principal conjunctive normal form are 1
Chapter one common question types
1. Judge whether it is a proposition , Simple proposition , Compound proposition , True false proposition
2. Judge whether the proposition is tautological or contradictory : Truth table method , Equivalent calculus
3. Change principal conjunctive normal form and principal disjunctive normal form
4. Reasoning , Known premises , Draw a conclusion : Reasoning formula
5. Full feature set conversion
6. Know the truth value of propositional variable , Find the truth value of the constructed proposition