当前位置:网站首页>[discrete mathematics review series] i. propositional logic
[discrete mathematics review series] i. propositional logic
2022-06-10 14:05:00 【Ape, it's you】
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 2n Assignments , Yes 22^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
边栏推荐
猜你喜欢

Qualcomm has finally begun to develop its own core architecture after learning from the difficulties of assembling chips to maintain its competitive advantage

Microsoft Word tutorial, how to change margins and create a newsletter column in word?

【离散数学期复习系列】四、图

How to solve the problem that vmware tools are grayed out when VMware Workstation is installed

40 necessary methodologies for large factories

新功能|Mail GPU Counter模块新增GPU图元处理和GPU Shader Cycles

Solve the problem that win10 virtual machine and host cannot paste and copy each other

NC|王军/宋默识结合三代测序解析肠道菌群结构变异和功能

anaconda安装opencv(cv2),在jupyter notebook中使用

Still saying that university rankings are a joke? The latest regulation: Top50 universities in the world can be directly settled in Shanghai!
随机推荐
软件智能:aaas系统 度量衡及文法的形式规则
Kotlin practises. Take login as an example. Anko simply uses it
【离散数学期复习系列】三、集合的概念及运算
苹果生产线迁离,说明5G工业互联、智能制造对中国制造帮助有限
NC|王军/宋默识结合三代测序解析肠道菌群结构变异和功能
MarkDown 标题居中
Mmdetection adds precision to the evaluation index
What is CAS and ABA in CAS
Allan方差与随机误差辨识
北京/上海内推 | 微软亚洲研究院系统与网络组招聘全职实习生
Gree mobile phone challenge Apple mobile phone? I'm afraid there's nothing else but hard talk
C multithreading learning note 2
CentOS Linux 已死!Oracle Linux 可能是它的更好替代品
Ue5 how to convert screen coordinates to world coordinates and World Directions
About native SQL and database methods in PHP framework
《软件体系结构原理、方法与实践》第二版期末考试复习总结
Flutter 页面跳转 传参,TabBar学习总结5
短文本重复率快速检测
C#多线程学习笔记三
【笔记】74HC573的一些记录