第1章 命题逻辑第1章 命逻辑题逻辑.ppt

《离散数学》 南京邮电大学计算机学院 计算机科学与技术系 张 琳 概 述 　关于这门课程，有几点要提醒大家注意的： 本身比较抽象，概念多，比较枯燥，内容一环扣一环，难学好。 要学好也不难。建议各位上课认真听讲，踏踏实实地学好每一个基本概念，基本内容，这样课后就不用花太多的时间复习。 作业建议独立完成，不会解答的可以讨论，但不会可以不做，一定要向别人请教，直到弄懂为止。千万不要抄作业！ 说　明 总学时：64学时 答疑时间：每周三上午第5节课 答疑地点：上课教室 总评成绩：平时成绩占30%，期中成绩占10%，期末成绩占60%。（每周三收作业） 联系方式：zhangl@njupt.edu.cn 例2：他虽聪明但不用功。 　　这里原子命题也是P.Q.　联结词“虽…但”也是“与”，所以公式应为： P　　　Q。 例3：如果明天上午七点不下雨，则我去学校。 　　P：明天上午七点下雨；Q：我去学校。“如果…则”与“若，则”一致，所以公式为： 　　P　　Q。 例4：除非你努力，否则你将失败。 例3：如果明天上午七点不下雨，则我去学校。 　　P：明天上午七点下雨；Q：我去学校。“如果…则”与“若，则”一致，所以公式为： 　　P　　Q。 例4：除非你努力，否则你将失败。 　　P：你努力；Q：你将失败。“除非…否则”相当于“如果不…那么…”，所以译为：　 　　　P　　Q　　　　Q　　P 例2　P46例题6 （a）或者是天晴，或者是下雨。 （b）如果是天晴，我去看电影。 （c）如果我去看电影，我就不看书。 结论：如果我在看书则天在下雨。 M：天晴；Q：下雨；S：我看电影； R：我看书。 对 于有如下性质 : 除了以下几个联结词外，没有其他联结词了，也就是这九个联结词足够表达命题关系了。我们命题公式的定义就可以推广为由这九个联结词依照一定规律构成的。 1-6　其他联结词 九个联结词之间的关系： (1) 可由 与 表示. (2) (3) 1-6　其他联结词 （2） 能否由 或 V表达？ 不能 或 表示，而 或 不能表示上述几个联结词。 所以这四行可由前五个联结词表示，从而几个联结词可由 因为（1）二元联结词不能用一元联结词表示，所以 不是最小联结词。 1-6　其他联结词 或 才是最小联结词组。 又 所以 也是最小联结词组 同理 所以 也是最小联结词组 所以我们共介绍的几个联结词，可由 或 ， ， 表达出来。 1-6　其他联结词 我们在介绍命题的十个定律时，发现除对合律外，其它定律都是成对出现的。（交换律、结合律、幂等律、分配律、De · Morgen律、同一律、否定律、吸收律、零律）把这样公式称为具有对偶规律。 比如 ： De · Morgen 律 这样的公式称为具有对偶规律 1-6　其他联结词 我们分两部分学习，先学习对偶式 （必须将A先化为仅含有 形式后再变，遇到其他联结词只能先化为 ） 一、1．定义 在给定的命题公式中，将联结词 换成 , 将 换成 ，若有特殊变元F和T亦相互取代，所得公式A*称为A的对偶式。显然A也是A*的对偶式 1-7　对偶与范式 例如： 对偶 注意：“ ”不变 又如 1-7　对偶与范式 对偶律： 设A和A*是对偶式， 是出现在Ａ和Ａ*中的原子变元，则： 设 是出现在Ａ和Ａ*中的所有原子变元，如果A B，则A* B* 1-7　对偶与范式 范式： 为什么