复习(数理逻辑部分)

《复习(数理逻辑部分)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章命题逻辑的基本概念一：基本概念：1.称能判断真假而不是可真可假的陈述句为命题。2.真值为真的命题称为真命题。3.真值为假的命题称为假命题。4.简单命题(原子命题)。5.由简单命题通过联结词而成的陈述句，称这样的命题为复合命题。例1判断下列句子是否为命题。(1)4是素数。(2)x大于y。(3)充分大的偶数等于两个素数之和。(4)北京是中国的首都。(5)请不要吸烟！(6)我正在说假话。6.合式公式:命题符号与联结词组成不是合式公式的例子：pq→r；(p→(r→q)7.公式的类型：重言式、永真式、可满足式重言式

2、(永真式)：都是1矛盾式(永假式)：都是0可满足式：有1，也有0二.联结词：否定：┐p非p合取：p∧qp并且q(或“p与q”)析取：p∨qp或q蕴涵：p→q如果p，则q等价：p«qp当且仅当q本书规定的联结词优先顺序为：()，┐，∧，∨，→，«，对于同一优先级的联结词，先出现者先运算。例2令p：北京比天津人口多。q：2+2＝4.     r：乌鸦是白色的。求下列复合命题的真值： (1)(q∨r)→(p→┐r) (2)(┐p∨r)«(p∧┐r)解：p、q、r的真值分别：1、1、0 (1)1(2)0例3求下列公式的

3、真值表，并求成真赋值和成假赋值。判断公式类型(1)(p∧┐p)«(q∧┐q)(2)(┐p∧q)→┐r(3)┐(p→q)∧q∧r解：先做真值表（1）是永真式，00，01，10，11是成真赋值，没有成假赋值。（2）是可满足式，011是成假赋值，其余是成真赋值。（3）是永假式，都是成假赋值，没有成真赋值。第2章命题逻辑等值演算一：验证两个公式是否等值：方法一：真值表方法二：等值演算1.双重否定律AÛ┐┐A2.幂等律AÛA∨A,AÛA∧A3.交换律A∨BÛB∨A，A∧BÛB∧A4.结合律(A∨B)∨CÛA∨(B∨C)(

4、A∧B)∧CÛA∧(B∧C)5.分配律        A∨(B∧C)Û(A∨B)∧(A∨C)（∨对∧的分配律）A∧(B∨C)Û(A∧B)∨(A∧C)（∧对∨的分配律）6.德·摩根律     ┐(A∨B)Û┐A∧┐B┐(A∧B)Û┐A∨┐B7.吸收律        A∨(A∧B)ÛA，A∧(A∨B)ÛA8.零律     A∨1Û1,A∧0Û09.同一律        A∨0ÛA，A∧1ÛA10.排中律       A∨┐AÛ111.矛盾律  A∧┐AÛ012.蕴涵等值式   A→BÛ┐A∨B13.等价等值式   

5、A«BÛ(A→B)∧(B→A)例1.用等值演算法验证等值式(p∨q)→rÛ(p→r)∧(q→r)解：方法一：真值表方法二：等值演算：(p→r)∧(q→r)Û(┐p∨r)∧(┐q∨r)(蕴含等值式)Û(┐p∧┐q)∨r(分配律)Û┐(p∨q)∨r(德摩根律)Û(p∨q)→r(蕴含等值式)二：基本概念（理解）：1.在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，称这样的简单合取式（简单析取式）为极小项（极大项）。2.定理2.4设mi与Mi是命题变项

6、p1,p2,…,pn形成的极小项和极大项，则┐miÛMi，┐MiÛmi3.极小项构成的析取范式称为主析取范式。极大项构成的合取范式称为主合取范式。4.定理2.5任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。表p,q,r形成的极小项与极大项三.范式的求法（计算）方法一、等值演算法(1)消去联结词→、«(若存在)。A→BÛ┐A∨BA«BÛ(┐A∨B)∧(A∨┐B)(2)否定号的消去(利用德摩根律)。(3)利用分配律：A∧(B∨C)Û(A∧B)∨(A∧C)求析取范式，A∨(B∧C)Û(A∨B)∧

7、(A∨C)求合取范式。并化成极小（大）项.(4)表示成主析取（合取）范式.方法二、真值表法(1)写出A的真值表，(2)找出成真（假）赋值，得到极小（大）项，(3)表示成主析取（合取）范式.例2求命题公式p→q的主析取范式和主合取范式。解：方法一：等值演算(1)求主合取范式p→qÛ┐p∨qÛM2(2)求析取范式p→qÛ┐p∨qÛ（┐p∧（┐q∨q））∨（(┐p∨p)∧q）Û(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)Û(┐p∧┐q)∨(┐p∧q)∨(p∧q)Ûm0∨m1∨m3方法二：真值表2.主析取范式

8、：成真赋值有：00，01，11所以：p→qÛm0∨m1∨m3pqp→qq0010111001113.主合取范式：成假赋值：10所以：p→qÛ┐p∨qÛM2第3章命题逻辑的推理理论一.判断推理是否正确的方法：q真值表法q等值演算法q主析取范式法例1判断下列推理是否正确。（方法一：等值演算法）下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。解：设p:马芳下午去看电影，q:马芳下