复习(数理逻辑部分).doc

第1章 命题逻辑的基本概念一：基本概念：1.称能判断真假而不是可真可假的陈述句为命题。2.真值为真的命题称为真命题。3.真值为假的命题称为假命题。4.简单命题(原子命题)。5.由简单命题通过联结词而成的陈述句，称这样的命题为复合命题。 例1 判断下列句子是否为命题。 (1)4是素数。 (2)x大于y。(3)充分大的偶数等于两个素数之和。(4)北京是中国的首都。(5)请不要吸烟！(6)我正在说假话。6.合式公式: 命题符号与联结词组成 不是合式公式的例子：pqr；(p(rq)7.公式的类型：重言式、永真式、可满足式 重言式(永真式)：都是1 矛盾式(永假式)：都是0 可满足式：有1，也有0二. 联结词：否定 ： p 非p合取： pq p并且q(或“p与q”)析取： pq p或q蕴涵： pq 如果p，则q等价： pq p当且仅当q本书规定的联结词优先顺序为：( )， ，对于同一优先级的联结词，先出现者先运算。例2令 p：北京比天津人口多。 q：2+24. r：乌鸦是白色的。 求下列复合命题的真值：(1)(qr)(pr) (2)(pr)(pr) 解：p、q、r的真值分别：1、1、0 (1) 1 (2) 0例3 求下列公式的真值表，并求成真赋值和成假赋值。判断公式类型(1)(pp)(qq)(2)(pq)r (3)(pq)qr 解：先做真值表（1） 是永真式，00，01，10，11是成真赋值，没有成假赋值。（2） 是可满足式，011是成假赋值，其余是成真赋值。（3） 是永假式，都是成假赋值，没有成真赋值。第2章 命题逻辑等值演算一：验证两个公式是否等值： 方法一：真值表 方法二：等值演算1.双重否定律 A A2.幂等律A AA,A AA 3.交换律AB BA，AB BA4.结合律(AB)C A(BC) (AB)C A(BC) 5.分配律A(BC) (AB)(AC) （对的分配律）A(BC) (AB)(AC)（对的分配律）6.德摩根律(AB) AB(AB) AB 7.吸收律A(AB) A，A(AB) A 8.零律A1 1,A0 0 9.同一律A0 A，A1 A 10.排中律AA 1 11.矛盾律AA 0 12.蕴涵等值式AB AB13.等价等值式AB (AB)(BA)例1.用等值演算法验证等值式(pq)r (pr)(qr) 解：方法一：真值表方法二：等值演算：(pr)(qr) (pr)(qr)(蕴含等值式) (pq)r(分配律) (pq)r(德摩根律) (pq)r (蕴含等值式) 二：基本概念（理解）：1. 在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，称这样的简单合取式（简单析取式）为极小项（极大项）。2. 定理2.4 设mi与Mi是命题变项p1,p2,pn形成的极小项和极大项，则 mi Mi， Mi mi 3. 极小项构成的析取范式称为主析取范式。 极大项构成的合取范式称为主合取范式。4. 定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。 表 p,q,r形成的极小项与极大项 三. 范式的求法（计算）方法一、等值演算法(1)消去联结词、(若存在)。 AB AB AB (AB)(AB)(2)否定号的消去(利用德摩根律)。 (3)利用分配律： A(BC) (AB)(AC)求析取范式， A(BC) (AB)(AC)求合取范式。 并化成极小（大）项.(4)表示成主析取（合取）范式.方法二、真值表法(1)写出A的真值表，(2)找出成真（假）赋值，得到极小（大）项，(3)表示成主析取（合取）范式.例2 求命题公式 pq 的主析取范式和主合取范式。解：方法一：等值演算(1)求主合取范式pq pq M2(2)求析取范式pq pq （p（qq） （(pp)q） (pq)(pq)(pq)(pq) (pq)(pq)(pq) m0m1m3 方法二：真值表2.主析取范式： 成真赋值有：00，01，11 所以：pq m0m1m3 pqp qq0010111001113.主合取范式： 成假赋值：10 所以： pq pq M2第3章 命题逻辑的推理理论一.判断推理是否正确的方法：q 真值表法 q 等值演算法 q 主析取范式法例1判断下列推理是否正确。（方法一：等值演算法） 下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。解：设p:马芳下午去看电影，q:马芳下午去游泳。 前提： pq，p 结论： q 推理的形式结构： (pq)p)q (pq)p)q (pq)p) q (pq)p) q (pp )(qp) q (qp) q 1由定理 3.1可知，推理正确。例2判断下列推理是否正确。（方法二：主析取范式法 ） 解：设p：今天是1号，q：明天是5号。 前提：pq，q 结论： p 推理的形式结构： (pq)qp (pq)qp (pq)qp (pq)q)p pq (pq)(pq) (pq)(pq) m0m2m3 主析取范式不含m1，故不是重言式（01是成假赋值），所以推理不正确。第4章 一阶逻辑基本概念一. 一阶逻辑命题符号化的三个基本要素：个体词：a，b，c；x，y，z谓词：F，G，H量词：全称量词 “” ；存在量词 “$”例1. x是有理数。x是个体词，“是有理数”是谓词，记为G，命题符号化为G(x)。例2将下列命题符号化，并讨论真值。（1）所有的人长着黑头发。（2）没有人登上过木星。（3）在美国留学的学生未必都是亚洲人。解：没有提出个体域，所以认为是全总个体域。（1）所有的人长着黑头发。 令F(x):x长着黑头发， M(x):x是人。命题符号化为 x(M(x)F(x)。 命题真值为假。（2）没有人