第一章数理逻辑
逻辑思维（又称抽象思维）是人运用概念、判断和推理反映事物本质与规律的认识过程（图1.1），它是人类特有的能力，是人类文明延绵不绝、科学技术持续进步的原动力。具备较强的逻辑思维能力是学习科技知识、进行科学研究、从事技术开发的先决条件。逻辑思维在信息科学技术领域显得尤为重要，只有具备强大的逻辑思维能力，才能胜任该领域的研究工作，才能胜任大型复杂软件的编写与调试工作。
图1.1. 逻辑思维
第一节逻辑学概论
逻辑思维是有规律的，逻辑学是专门研究逻辑思维规律性的学科。本节简述逻辑学的基本内容和发展历史。
1.1. 逻辑思维的基本规律
逻辑思维的作用，就是根据一定的前提，通过合理的推导，得到
一定的结论。
例1.1．苏格拉底是柏拉图的导师，柏拉图是亚里士多德的导师，因此，苏格拉底是亚里士多德的师爷。
分析：苏格拉底、柏拉图和亚里士多德是人类文明史上著名的哲学家，有着师徒传承关系。这是一个逻辑思维过程，其作用就是根据‘苏格拉底是柏拉图的导师’和‘柏拉图是亚里士多德的导师’这两个前提，得到‘苏格拉底是亚里士多德的师爷’这个结论。
例1.2. 子非鱼，安知鱼之乐？
分析：这是惠子对庄子说的一句话。可以将这句话改写为‘你不是鱼，所以你不知道鱼的快乐’，这是一个逻辑思维过程，其作用就是根据‘你不是鱼’这个前提，导出‘你不知道鱼的快乐’这个结论。
逻辑学之父亚里士多德总结出了逻辑思维的以下四条基本规律。
表1.1. 逻辑思维的四条基本规律
下面来看看不满足这些基本规律的实例。
例1.3. 有个小伙子上了火车，一看座无虚席，就厚着脸皮硬往一位老
大爷身边挤座儿。老大爷不高兴了，说：“小伙子，别硬坐了，座位已经满了。”小伙子嘻皮笑脸地说：“老大爷，没办法,我买的就是硬坐票。”分析：这个小伙子在说话时故意把“硬座”变换成“硬坐”，这是偷换概念，违背了同一律。
图1.2. 自相矛盾
例1.4．楚国有个卖兵器的人在街上叫卖。他说：“我的矛是最锋利的，能刺穿任何东西。”他又说：“我的盾是最坚固的，不能被任何东西刺穿。”这时，人群中有人问道：“如果用你的矛去戳你的盾，会怎么样呢？”楚人听后哑口无言。
分析：假设楚人说的两句话都是真的，就可以做以下推理：一方面，因为‘楚人的矛能刺穿任何东西’，所以‘楚人的矛能刺穿楚人的盾’；另一方面，因为‘楚人的盾不能被任何东西刺穿’，所以‘楚人的矛不能刺穿楚人的盾’。这样一来，就得到了两个相互矛盾的结论，根据矛盾律，这两个结论不可能同时为真，因此，楚人的话至少有一句是假的。
例1.5．有个人说：“‘华盛顿是第一任美国总统’是不对的，‘华盛顿
不是第一任美国总统’也是不对的。”
分析：‘华盛顿是第一任美国总统’和‘华盛顿不是第一任美国总统’互为否命题。根据排中律，这两个命题必须有一个是真的。根据历史知识，第一个命题是真的。这个人违背了排中律。
例1.6．南宋初年，宰相秦桧诬陷抗金名将岳飞谋反。虽然秦桧用尽一切卑鄙手段，捏造罪名刑讯逼供，但连一件像样的罪证也找不到。然而秦桧在宋高宗赵构的支持下，仍然把岳飞问成死罪。抗金名将韩世忠感到不平，就去质问秦桧：“你们说岳飞造反，有什么确凿证据？”秦桧不敢明确回答，只好含糊其辞地说：“这样的证据‘莫须有’。”韩世忠听了以后气愤地说：“只凭‘莫须有’这三个字，怎么能使天下人心服！”岳飞最后惨死于风波亭。
图1.3. 风波亭
分析：秦桧采用的是‘有罪推定’原则，先假定‘岳飞有罪’，如果找不到岳飞无罪的确凿证据，就不能否认这个假设，因此岳飞有罪。这样的思维方式违背了充足理由律，不能令人信服。在我国以前的司法
实践中，常年采用‘有罪推定’原则，造成了许多冤假错案。我国的现代法律则采用了更为合理的‘无罪推定’原则，先假定‘嫌疑人无罪’，如果找不到嫌疑人有罪的确凿证据，就认为嫌疑人无罪。疑罪从无是司法实践的巨大进步，可以最大限度地减少冤假错案。按照无罪推定原则，岳飞是无罪的。
1.2．命题、推理和论证
从结构来看，逻辑思维是由命题和推理两部分组成的。
命题是在思维过程中有确定真假值的陈述句，它是逻辑思维的基本单元。在例1.3中，‘华盛顿是第一任美国总统’和‘华盛顿不是第一任美国总统’都是陈述句，前者是真的，后者是假的，因此都是命题。如果一个命题为真，就用符号1表示；如果一个命题为假，就用符号0表示。
疑问句、祈使句和感叹句等非陈述句虽然可以出现在思维过程中，但要么可以被直接去掉，要么可以被改写为陈述句，而不会影响思维本身。
例1.7. 现象会受到因素什么样的影响呢？如果因素对现象有影响，并且因素对现象的影响不是负面的，那么因素对现象的影响就必然是正面的。
分析：可以将上述思维过程改写为‘如果因素对现象有影响，并且因素对现象的影响不是负面的，那么因素对现象的影响就是正面的。’由此可见，‘现象会受到因素什么样的影响呢？’这个疑问句不会影
响思维本身，可以被去掉。但疑问句具有重要的辅助作用，有助于提出问题，聚焦问题。
在逻辑思维过程中，所涉及的所有陈述句都必须有确定的真假值，虽然思维者并不一定知道它究竟是真是假。
例1.8. 上帝存在。
分析：上帝要么存在要么不存在，不可能既存在又不存在，因此这句话要么真要么假，有确定的真值。人类到目前为止，既没有找到上帝存在的确凿证据，也没有找到上帝不存在的确凿证据，因此并不知道这句话究竟是真是假，虽然如此，这并不妨碍这句话成为命题。现代科学认为，‘上帝存在或者不存在’只是一个信仰问题，而不是一个科学问题。
有一类天生违背排中律的陈述句，既不真也不假，被称为悖论。悖论不能作为逻辑思维的前提，否则得到的结论就靠不住。不过在正常的逻辑思维中，所遇到的陈述句基本上都不是悖论，所以不用过分担心悖论。
推理是假设一个或者多个命题（前提）为真，推出另一个命题（结论）为真的思维形式。
例1.9. 因为1x =，所以ln 0x =。
分析：这是从前提‘1x =’为真，推出结论‘ln 0x =’为真的推理。 例1.10. 荷兰在西欧，阿姆斯特丹是荷兰的首都，所以阿姆斯特丹在西欧。
分析：这是从前提“荷兰在西欧”和“阿姆斯特丹是荷兰的首都”为真，推出结论“阿姆斯特丹在西欧”为真的推理。
可以将推理分为以下两类。
演绎推理：如果前提为真，结论就一定为真的推理。
归纳推理：即使前提为真，结论也不一定为真的推理。
例1.11. 任何人都会死。苏格拉底是人，所以苏格拉底会死。
分析：这是演绎推理，因为从‘任何人都会死’和‘苏格拉底是人’这两个前提为真，一定能够保证‘苏格拉底会死’这个结论为真。
例1.12. 有些人会死。苏格拉底是人，所以苏格拉底会死。
分析：这是归纳推理，因为从“有些人会死”和“苏格拉底是人”这两个前提为真，不能保证“苏格拉底会死”这个结论为真。
从功能角度来看，逻辑思维就是用某些理由（论据，前提）去支持或反驳某个观点（论点，结论）的过程，因此也被称为论证。可以将论证分为以下两类。
有效论证：如果论据为真，就能保证论点为真的论证。
无效论证：即使论据为真，也不能保证论点为真的论证。无效论证有时也被称为归纳论证。
例1.13. 最早的采用图形用户界面的计算机是苹果公司开发的，因而不是IBM公司开发的。
分析：这个论证的论点是‘最早的采用图形用户界面的计算机不是
IBM 公司开发的’，论据是‘最早的采用图形用户界面的计算机是苹果公司开发的’，从论据到论点只做了一步推理。
例1.14. 因为x y =，y z =，所以x z =；又因为z w =，所以x w =。 分析：这个论证的结论是“x w =”，前提是‘x y =’、‘y z =’和‘z w =’，从前提到结论做了两步推理，第一步推理是从前提‘x y =’和‘y z =’推得了中间结论‘x z =’，第二步推理是从中间结论‘x z =’和前提‘z w =’推得了论点‘x w =’。这个论证在复数范围内是有效的。 例1.15. 因为x y ≠，y z ≠，所以x z ≠。
分析：这个论证在复数范围内是无效的。
在数学领域，每个定理都要求已知条件（论据）成立能够保证结论（论点）成立，只有通过有效论证才能证明定理。因此，基于演绎推理的有效论证是建立数学大厦的主要工具。
例1.16. 如果10010个个体中的某100个个体都具有某种属性，则所有个体都具有这种属性。
这个论证是归纳论证，因为样本没有穷尽总体中的所有个体，即使a b =对所有样本都为真，也不能保证a b =对总体中所有个体都为真。尽管如此，如果所选取的样本具有代表性，结论还是相当可靠的。
以物理学、化学、生物学等为代表的实验科学的主要研究方法，就是通过对个别情况的实验研究，通过归纳找到一般性规律。由于实验的数量有限，不可能穷尽所有情况，所发现的规律不能够保证对所
有情况都成立，因此这些规律只能被称为定律，不能被称为定理。随着科学技术的不断进步，需要对某些定律进行修改，建立新的定律。
随着物联网时代和大数据时代的来临，能够获得的样本数据越来越多，结论变得越来越可靠，量变最终导致了质变，人工智能先后在语音识别、图像识别、自然语言理解、语音合成、智能博弈、自动回答问题、自动决策等领域取得了突破性进展，成功超越了人类，迎来了机器智能时代。
1.3．逻辑学的历史
历史上，逻辑学经历了三个发展阶段：古典逻辑、布尔代数和数理逻辑。
第一阶段：古典逻辑。古希腊哲学家亚里士多德发现了逻辑思维的四条基本规律，提出了著名的三段论规则，奠定了古典逻辑的基础。由于许多推理规则不能用三段论来表达，古典逻辑的适用范围是比较狭窄的。
第二阶段：布尔代数。德国哲学家莱布尼茨设想将思维约化为符号演算。英国数学家布尔建立了布尔代数，在一定程度上将思维约化为代数运算，初步实现了莱布尼茨的梦想。布尔代数只能模拟比较简单的逻辑思维。
第三阶段：数理逻辑。德国数学家弗雷格建立了数理逻辑，比较成功地将思维约化为逻辑运算，较好地实现了莱布尼茨的梦想。数理逻辑的宗旨是用数学方法研究逻辑思维的规律。数理逻辑在计算机科学技术领域有着广泛的应用，从硬件设计、软件设计、软件正确性证
明直至人工智能，处处都离不开数理逻辑。
习题
1．逻辑学是什么？
2．什么是命题？
3．什么是演绎推理？什么是归纳推理？
4．什么是有效论证？什么是无效论证。
5．数理逻辑的宗旨是什么？
名人轶事
亚里士多德
亚里士多德（公元前384~前322），古希腊伟大的哲学家、科学家和教育家。他是柏拉图的学生，亚历山大的老师。公元前335年，他在雅典办了一所叫吕克昂的学校，被称为逍遥学派。他几乎对每个学科都做出了贡献。他的写作涉及伦理学、形而上学、心理学、经济学、神学、政治学、修辞学、自然科学、教育学、诗歌、风俗，以及雅典法律。亚里士多德的著作构建了西方哲学的第一个广泛系统，包含道德、美学、逻辑和科学、政治和玄学。
莱布尼茨
特弗里德·威廉·莱布尼茨（1646~1716），德意志哲学家、数学家，历史上少见的通才。他和牛顿先后独立发明了微积分，他所使用的微积分符号被广泛采用。他被公认为十七世纪最伟大的理性主义哲学家
之一。他在哲学方面的工作预见了现代逻辑学和分析哲学的诞生。莱布尼茨在政治学、法学、伦理学、神学、哲学、历史学、语言学诸多方向都留下了著作。
布尔
乔治·布尔（1815~1864），英国数学家。英国数学家，生于1815年。布尔家境贫寒，一边养家一边奋斗，与1835年开办了自己的学校。1849年，布尔受邀担任爱尔兰科克女王学院的数学教授。1854年，布尔出版了《思维规律的研究》，书中介绍了布尔代数。1857年，布尔当选为伦敦皇家学会会员，不久荣获该会的皇家奖章。1864年，布尔死于肺炎。
由于布尔在符号逻辑运算领域的卓越贡献，很多计算机语言将逻辑运算称为布尔运算，将计算结果称为布尔值。
弗雷格
弗里德里希·路德维希·戈特洛布·弗雷格（1848~1925），德国数学家、逻辑学家和哲学家。是数理逻辑和分析哲学的奠基人。
离散数学形成性考核作业（四） 数理逻辑部分 本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整，抄写题目，解答题有解答过程。 第6章命题逻辑 1．判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题． （1）8能被4整除． （2）今天温度高吗？ （3）今天天气真好呀！ （4）6是整数当且仅当四边形有4条边． （5）地球是行星． （6）小王是学生，但小李是工人． （7）除非下雨，否则他不会去． （8）如果他不来，那么会议就不能准时开始． 解：此题即是教材P.184习题6（A）1 （1）、（4）、（5）、（6）、（7）、（8）是命题，（2）、（3）不是命题。 其中（1）、（5）是简单命题，（4）、（6）、（7）、（8）是复合命题。 2．翻译成命题公式 （1）他不会做此事． （2）他去旅游，仅当他有时间． （3）小王或小李都会解这个题． （4）如果你来，他就不回去． （5）没有人去看展览． （6）他们都是学生． （7）他没有去看电影，而是去观看了体育比赛． （8）如果下雨，那么他就会带伞． 解：此题即是教材P.184习题6（A）2
会带伞。 ：如果下雨，那么他就：他会带伞。 ：天下雨。）（。是去观看了体育比赛。：他没有去看电影，而。 ：他去观看了体育比赛：他去看电影。）（：他们都是学生。 ）（：没有人去看展览。 ：有人去看展览。）（去。 ：如果你来，他就不回：他回去。：你来。）（道题。：小王或小李都会解这：小李会解这道题。 ：小王会解这道题。）（时间。 ：他去旅游，仅当他有：他有时间。 ：他去游泳。）（：他不会做此事。：他会做此事。）（Q P Q P Q P Q P P P P Q P Q P Q P Q P Q P Q P P P →∧???→∧→?87654321 3．设P ，Q 的真值为1；R ，S 的真值为0，求命题公式(P ∨Q )∧R ∨S ∧Q 的真值． 解：此题即是教材P.184习题6（A ）4（2） (P ∨Q )真值为1，(P ∨Q )∧R 真值为0，S ∧Q 真值为0， 从而(P ∨Q )∧R ∨S ∧Q 真值为0。 4．试证明如下逻辑公式 （1） ┐（A ∧┐B ）∧（┐B ∨C ）∧┐C ? ┐（A ∨C ） （2） (P →Q )∧(Q →R )∧┐R ??P （此题即是教材P.185习题6（A ）5（1）、（4）） ) 7() () 8()6)(5()7()4)(2()6()4)(3()5()4()3()1() 2()() 1()(), (),(由由由由由证明：结论：前提：T B A T B A T A T B P C P C B T B A P B A B A C C B B A ∨??∧????∨?∨??∧?∨??∨??∧? ) 4)(3() 5()4()2)(1()3() 2() 1(), (),(由由证明：结论：前提：T P P R T R P P R Q P Q P P R R Q Q P ??→→→??→→
该笔记适用于任何版本的数理逻辑！ 绪论 一、数理逻辑研究什么？ ★研究前提和结论的可推导性关系，它是由命题的逻辑形式而非内容所决定的 二、数理逻辑如何研究？ ★形式语言 第一章预备知识 第一节集合 一、集合 1、集合的内涵和外延（所有元素的共同性质/构成集合的所有元素） 2、有序偶和笛卡儿集 二、关系 1、概念：集合S上的n元关系R 2、特殊情况：集合S上的一元关系R（集合S上的性质R） 三、函数（映射） 1、概念：函数（集合＋有序偶＋性质）、定义域dom（f）、值域ran（f） 2、概念：f（x）（函数f在x处的值） 3、概念：f：S－>T（函数f是由S到T的映射）、满射、一一映射 四、等价 1、概念：关系R是集合S上的等价关系（自反＋对称＋传递） 2、概念：元素x的R等价类 3、性质：R等价类对集合S的一个划分（两两不相交，且并为S） 五、基数 1、概念：S～T（两个集合S和T是等势的） 2、概念：集合S的基数|S|（集合中的元素个数） 3、概念：可数无限集
第二节归纳定义和归纳证明 一、归纳定义 1、集合的归纳定义 ⑴、直接生成某些元素 ⑵、给出运算，将其作用在已有元素上，以产生新的元素 ⑶、只有这样才是集合中的元素，除此之外，再也没有了 2、典例：自然数集N的两个归纳定义 二、归纳证明 1、归纳定理：设R是一个性质，如果 ⑴、R（0） ⑵、对于任何n∈N，如果R（n），则R（n’） 那么，对于任何n∈N，都有R（n） 2、概念：归纳基础、归纳步骤（包括归纳变元和归纳假设）、归纳命题、归纳证明 3、概念：串值归纳法及其变形 三、递归定义 1、递归定义（在归纳定义的集合上，定义函数） 在自然数集N上定义一个这样的函数f：g，h是N上的已知函数 f（0）＝g（0） f（n’）＝h（f（n）） 2、递归定义原理（这样的函数是存在而且唯一的）
“离散数学”数理逻辑部分考核试题答案 ━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━ 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：p∧q，其中，P：小刘怕吃苦；q：小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→p，其中，P：怕敌人；q：战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：r→(p→p)，其中，P：别人有困难；q：老张帮助别人；r：困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P：小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A：((p q)((p q) (p q))) r （1）B：(p(q p)) (r q) （2）C：(p r) (q r) （3）E：p(p q r) （4）F：(q r) r 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。 3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分） （0）设y=2|x|，x为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，x为实数。令P：y在x=0处可导，q：y在x=0处连续。由此，p为假，q为真。本题推理符号化为：(p q) q p。由p、q的真值，计算推理公式真值为假，由此，本题推理不正确。 （1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令p:2是素数，q:3是素数，r:5是奇数，s:6是奇数。由此，p=1，q=1，r=1，s=0。本题推理符号化为： ((p q) →s) p q) →(r s)。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算（5分） 1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。共2分） （0）求公式p→((q∧r) ∧(p∨(q∧r)))的主析取范式。 解：p→((q∧r) ∧(p∨(q∧r)))p∨(q∧r∧p) ∨(q∧r∧q∧r) p∨(q∧r∧p) ∨0 (p∧q∧r) ∨ (p∧1∧1) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨m7 (p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨m7 m0∨m1∨m2∨m3∨m7. （1）求公式((p→q)) ∨(q→p)的主合取范式。 解：((p→q)) (q→p) (p→q) (p→q) (p→q) p q M2.
离散数学数理逻辑部分综合练习辅导 一、单项选择题 1．设P ：我将去打球，Q ：我有时间．命题“我将去打球，仅当我有时间时”符号化为( )． A ．P Q → B ．Q P → C ．Q P ? D ．Q P ?∨? 因为语句“仅当我有时间时”是“我将去打球”的必要条件，所以选项B 是正确的． 正确答案：B 一般地，当语句是由“……，仅当……”组成，它的符号化用条件联结词→． 问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，会符号化吗？ 2．设命题公式G ：)(R Q P ∧→?，则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( )． A ．0, 0, 0 B ．0, 0, 1 C ．0, 1, 0 D ．1, 0, 0 个人收集整理 勿做商业用途 当P 为真值为1时，P ?的真值为0，无论()Q R ∧的真值是1还是0，命题公式G 的真值为1．所以选项D 是正确的． 正确答案：D 3．命题公式P ∨Q 的合取范式是 ( )． A ．P ∧Q B ．（P ∧Q ）∨（P ∨Q ） C ．P ∨Q D ．?（?P ∧?Q ） 复习合取范式的定义： 定义6.6.2 一个命题公式称为合取范式，当且仅当它具有形式： A 1∧A 2∧…∧A n ， （n ≥1） 其中A 1，A 2，…，A n 均是由命题变元或其否定所组成的析取式． 由此可知，选项B 和D 是错的．又因为P ∧Q 与P ∨Q 不是等价的，选项A 是错的．所以，选项C 是正确的． 正确答案：C 4．命题公式)(Q P →?的析取范式是( )． A ．Q P ?∧ B Q P ∧? C ．Q P ∨? D ．Q P ?∨ 复习析取范式的定义： 定义6.6.3 一个命题公式称为析取范式，当且仅当它具有形式： A 1∨A 2∨…∨A n ， （n ≥1） 其中A 1，A 2，…，A n 均是有命题变元或其否定所组成的合取式． 公式)(Q P →?与Q P ?∧是等价的，Q P ?∧满足析取范式的定义，所以，
离散数学作业6 数理逻辑部分概念及性质 单项选择题 1．设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符号化为( )． A．P ∨ P? ?Q→B．Q P?D．Q P→C．Q 答 B 2．设命题公式G：) ?，则使公式G取真值为1的P，Q，R赋值 → P∧ (R Q 分别是( )． A．0, 0, 0 B．0, 0, 1 C．0, 1, 0 D．1, 0, 0 答 D 3．命题公式(P∨Q)→R的析取范式是( )． A．?(P∨Q)∨R B．(P∧Q)∨R C．(P∨Q)∨R D．(?P∧?Q)∨R 答 D 4．命题公式（P∨Q）的合取范式是( )． A．（P∧Q）B．（P∧Q）∨（P∨Q） C．（P∨Q）D．?（?P∧?Q） 答 C 5．命题公式) ?的析取范式是( )． P→ (Q A．Q ?D．Q ∨ P∨ P? ?C．Q ∧B Q P? P∧ 解()() ?→???∨ P Q P Q ?∧? P Q 答 A 6．下列等价公式成立的为( )． A．?P∧?Q?P∨Q B．P→(?Q→P) ??P→(P→Q) C．Q→(P∨Q) ??Q∧(P∨Q) D．?P∨(P∧Q) ?Q 解A．?P∧?Q??(P∨Q) B．P→(?Q→P)??P∨(Q∨P)? P∨(?P∨Q)??P→(P→Q) C．Q→(P∨Q)??Q∨(P∨Q) D．?P∨(P∧Q)?(?P∨P)∧(?P∨Q)?1∧(?P∨Q)??P∨Q
答 B 7．下列公式成立的为( )． A ．?P ∧?Q ?P ∨Q B ．P →?Q ??P →Q C ．Q →P ? P D ．?P ∧(P ∨Q )?Q 解 A ．?P ∧?Q ??(P ∨Q ) B ．P →?Q ??P ∨?Q C ．(Q →P )→P ??(?Q ∨P )∨P ?(Q ∧?P )∨P ?(Q ∨P )∧(?P ∨P ) ?(Q ∨P )∧1?P ∨Q （不是永真式） D ．?P ∧(P ∨Q )?Q （析取三段论，P171公式(10)） 答 D 8．下列公式中 ( )为永真式． A ．?A ∧? B ? ?A ∨?B B ．?A ∧?B ? ?(A ∨B ) C ．?A ∧?B ? A ∨B D ．?A ∧?B ? ?(A ∧B ) 解 A ．A B A B ?∧???∨?/，1A B A B ?∧???∨??/ B ．()A B A B ?∧???∨，()1A B A B ?∧???∨? C ．A B A B ?∧??∨/，1A B A B ?∧??∨?/ D ．()A B A B ?∧???∧/，()1A B A B ?∧???∧?/ 答 B 9．下列公式 ( )为重言式． A ．?P ∧?Q ?P ∨Q B ．(Q →(P ∨Q ))?(?Q ∧(P ∨Q )) C ．(P →(?Q →P ))?(?P →(P →Q )) D ．(?P ∨(P ∧Q )) ?Q 解 A ．P Q P Q ?∧??∨/，1P Q P Q ?∧??∨?/ B ．(())1Q P Q Q P Q →∨??∨∨? (())()()()1Q P Q Q P Q Q P Q ?∧∨??∧∨?∧?∧??/ (())(())1Q P Q Q P Q →∨??∧∨?/ C ．()()()()P Q P P Q P P P Q P P Q →?→??∨∨?∨?∨??→→ (P →(?Q →P ))?(?P →(P →Q ))?1 D ．()()()P P Q P P P Q P Q Q ?∨∧??∨∧?∨??∨?/ (())1P P Q Q ?∨∧??/ 答 C 10．设A （x ）：x 是人，B （x ）：x 是学生，则命题“不是所有人都是学生”可符号化为（ ）．
逻辑推理（一） 专题简析： 逻辑推理题不涉及数据，也没有几何图形，只涉及一些相互关联的条件。它依据逻辑汇率，从一定的前提出发，通过一系列的推理来获取某种结论。 解决这类问题常用的方法有：直接法、假设法、排除法、图解法和列表法等。 逻辑推理问题的解决，需要我们深入地理解条件和结论，分析关键所在，找到突破口，进行合情合理的推理，最后作出正确的判断。 推理的过程中往往需要交替运用“排除法”和“反正法”。要善于借助表格，把已知条件和推出的中间结论及时填入表格内。填表时，对正确的（或不正确的）结果要及时注上“√”（或“×”），也可以分别用“1”或“0”代替，以免引起遗忘或混乱，从而影响推理的速度。 推理的过程，必须要有充足的理由或重复内的根据，并常常伴随着论证、推理，论证的才能不是天生的，而是在不断的实践活动中逐渐锻炼、培养出来的。 例题1： 星期一早晨，王老师走进教室，发现教室里的坏桌凳都修好了。传达室人员告诉他：这是班里四个住校学生中的一个做的好事。于是，王老师把许兵、李平、刘成、张明这四个住校学生找来了解。 （1）许兵说：桌凳不是我修的。 （2）李平说：桌凳是张明修的。 （3）刘成说：桌凳是李平修的。 （4）张明说：我没有修过桌凳。 后经了解，四人中只有一个人说的是真话。请问：桌凳是谁修的？ 根据“两个互相否定的思想不能同真”可知：（2）、（4）不能同真，必有一假。 假设（2）说真话，则（4）为假话，即张明修过桌凳。 又根据题目条件了：只有1人说的是真话：可退知：（1）和（3）都是假话。由（1）说的可退出：桌凳是许兵修的。这样，许兵和张明都修过桌凳，这与题中“四个人中只有一个人说的是真话”相矛盾。 因此，开头假设不成立，所以，（2）李平说的为假话。由此可退知（4）张明说了真话，则许兵、刘成说了假话。所以桌凳是许兵修的。 练习1： 1、小华、小红、小明三人中，有一人在数学竞赛中得了奖。老师问他们谁是获奖者，小华说是小红，小红说不是我，小明也说不是我。如果他们当中只有一人说了真话。那么，谁是获奖者？ 2、一位警察，抓获4个盗窃嫌疑犯A、B、C、D，他们的供词如下： A说：“不是我偷的”。 B说：“是A偷的”。 C说：“不是我”。 D说：“是B偷的”。 他们4人中只有一人说的是真话。你知道谁是小偷吗？ 3、有500人聚会，其中至少有一人说假话，这500人里任意两个人总有一个说真话。说真话的有多少人？说假话的有多少人？ 例题2： 虹桥小学举行科技知识竞赛，同学们对一贯刻苦学习、爱好读书的四名学生的成绩作了
数理逻辑的心得 数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。是大四接触到的，现简单介绍一下数理逻辑的发展史，算是一点感悟吧 1数理逻辑的发展前期 ·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论 ·初创时期——逻辑代数时期（17世纪末） ·资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。 ·人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。 ·莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想： ·提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。 ·使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。 ·布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。 数理逻辑的奠基时期 ·弗雷格(G. Frege, 1848~1925)：《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。 ·皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统。 ·罗素(Bertrand Russell, 1872~1970)：《数学原理》(与怀特黑合著，1910, 1912, 1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。 ·逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。 ·各种各样的非经典逻辑的发展：路易斯(Lewis, 1883~1964)的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。 集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。 ·罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。 ·布劳维尔(Brouwer, 1881~1966)的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。 ·希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将
作业答案：数理逻辑部分 P14：习题一 1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （3 答：简单命题，真命题。 （9）吸烟请到吸烟室去！ 答：不是命题。 （12）8是偶数的充分必要条件是8能被3整除。 答：复合命题，假命题。 14、讲下列命题符号化。 （6）王强与刘威都学过法语。 答：:p 王强学过法语；:q 刘威学过法语。 符号化为： p q ∧ （10）除非天下大雨，他就乘班车上班。 答：:p 天下大雨；:q 他乘班车上班。 符号化为： p q → （13）“2或4是素数，这是不对的”是不对的。 答：:p 2是素数；:q 4是素数。 符号化为：(())p q ??∨ 15、设:p 2+3=5. :q 大熊猫产在中国。 :r 太阳从西方升起。 求下列复合命题的真值。 （2）(())r p q p →∧?? （4）()(())p q r p q r ∧∧???∨?→ 解答： p 真值为1；q 真值为1；r 真值为0. （2）p q ∧真值为1；()r p q →∧真值为1；p ?真值为0； 所以(())r p q p →∧??真值为0. （4） p q r ∧∧?真值为1，p q ?∨?真值为0，()p q r ?∨?→真值为1； 所以()(())p q r p q r ∧∧???∨?→真值为1. 19、用真值表判断下列公式的类型。 （4）()()p q q p →→?→?
所以为重言式。 )s 所以为可满足式。 P36:习题二 3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。 （1）()p q q ?∧→ 解答： 所以为永假式。 （2）(())()p p q p r →∨∨→ 解答： 所以因为永真式。 （3）()()p q p r ∨→∧
离散数学 期中课程设计作业 班级：10级计算机 组员：杨鑫 学号：09
数理逻辑怎样用于实际的应用 我们现在在学离散数学,对于离散数学中的数理逻辑这一部分存在很多盲点,那么这看似高深莫测的数理逻辑在实际生活中有着怎样的用处呢,下面让我们来讨论一下. 我们先看数理逻辑的定义:数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。虽然名称中有逻辑两字，但并不属于单纯逻辑学范畴。数理逻辑是用数学的方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支，计算机科学，人工智能，语言学等学科有密切的联系，并且日益显示出它的主要作用和更加广泛的应用前景. 数理逻辑中的逻辑运算又称布尔运算，它是用数学的方法解决或研究逻辑问题，即用离散的符号“1”和“0”表示逻辑中的“真”和“假”再加上一套与之相关的“与”、“或”、“非”为运算基础的逻辑运算规则解决实际逻辑问题的方法，从而实现复杂逻辑运算到简单的数值计算的转化。下面我们就逻辑运算在电路设计中的运用加以探讨： 某公司王某欲搬入新房，搬迁前需要完成电路的设计安装，由于该房深处闹市，四周楼房林立，严重影响了客厅的采光，于是王某想设计一个电路，要求客厅四盏灯由一个开关控制，开关按下一次亮一盏灯，再按一下亮两盏，以此类推，直到按下第五次时所有灯熄灭。假设四个灯依次为A、B、C、D，灯亮为1，灯灭为0，开关有脉冲输入为1，否则为0，则根据题意可得真值表（如图１）： 设第ｎ号灯的上一状态为Nｎ，第ｎ＋１号灯现在在的状态为Nｎ＋１，脉冲输入状态为M，则有： Nｎ＋１=Nｎ∧M（N0与M的且运算） 其中Ｎｎ＝ＮＡ∧ＮＢ．．．∧Ｎｎ－１ 灯亮的条件为（A∧┐B∧┐C∧┐D）∨（A∧B∧┐C∧┐D）∨（A∧B∧C∧┐D）∨（A∧B∧C∧D） 如Ｂ灯亮的条件是Ａ灯亮并且有脉冲输入，C灯亮的条件是ＡＢ都亮并且有脉冲输入。该电路功能由一个与门电路和一个计数触发器连接即可完成，当开关第5次输入后计数器输出信号置0，灯全部关闭，此时设备全部复位。如图２。
数理逻辑的现实意义 摘要：数理逻辑并不仅仅局限于抽象的符号运算，它同样可以帮助我们了解和解决很多现实问题。数理逻辑在写作、创新思维、人工智能应用等方面有着重要的作用。运用逻辑性思维能使我们正确的选题与写作；它与一个人的创新能力有着极为密切的关系；同时也是人工智能科学发展必不可少的。 关键词：数理逻辑写作创新思维人工智能 大多数人都认为数理逻辑是一门艰深、抽象甚至有点枯燥的学科,这一点也许除了很少一些从事数理逻辑研究的专家会反对。但是，在我们的生活中，数理逻辑也有着重要的现实意义。数理逻辑是用数学方法研究思维形式的逻辑结构及其规律的学科。所谓数学方法，是指用一套表意符号即形式语言系统表达思维的形式结构和规律，从而把对思维的研究转化为对符号的研究。以便摆脱自然语言的歧义性，构成能像算术或代数那样的严格精确的演算系统。由于它运用了数学方法来研究逻辑和数学基础，本身成为数学的一个分支，同时又由于它的基本研究对象仍然以逻辑为主，因而，作为现代化的逻辑, 它又渗透到现代数学的各个分支中。集论的深入研究必须严格地运用数理逻辑作为重要的工具，这不用多说翻开现代数学的各种教程，映入眼帘的是许许多多数理逻辑的符号和表示式。如果没有数理逻辑的初步知识，一些新出版的教科书和刊物上的论文就根本没法读。一个定理的证明，用古典数学的表达方法常常是不十分精确而且有时是冗长的，而用数理逻辑来进行证明，那就简明而且精确严密得多了。现代数学各大分支基本上都用了公理方法，于是，数理逻辑就更成为不可或缺的工具了。 一、数理逻辑在写作中的应用 从逻辑角度看，数理逻辑也是研究演绎的科学，演绎方法包括演绎推理，以演绎推理为基础的证明和公理方法。从根本上讲它是传统逻辑的发展，是现代的精确的形式逻辑。演泽推理是指由一般性的前提推出特殊的结论的推理。推理能力的强弱，直接关系到论文说理是否透彻，分析是否具体，论证是否严密，文章是否更具有逻辑性和说服力。因此，逻辑推理能力在论文写作中至关重要。在选题、立意、结构、表述中运用概念和判断进行推理的过程，也就构成了一个完整的形式逻辑思维运行的过程。而写作活动本身就是一种思维活动，而且对思维的要求比较高。一篇论文的写作总有几个步骤，即从纷繁的材料和模糊的意念中，经过抽象概括，使思维明确化，选择一个合适的选题；接着对资料加以深入分析，形成层次；最后，构建论文结构，表述论文思想。事实上，论文写作过程就是一
离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）． 一、填空题 1．命题公式() →∨的真值是 1 ． P Q P 2．设P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为P∨Q→R ． 3．含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是(P∧Q∧┐R)∨(P∧Q∧R) ． 4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为?x ( P ( x) ∧Q ( x))． 5．设个体域D＝{a, b},那么谓词公式) xA? ∨ x ?消去量词后的等值式为 yB ( ) (y (A(a)∨A(b))∨(B(a) ∧B(b))． 6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为0 ． 7．谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(?x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 解：
数理逻辑介绍 1.若干哲学观点 分析哲学也称为语言哲学和逻辑哲学，开始于德国数学家弗雷格对于自然语言的逻辑分析工作，后被奥地利哲学家维特根斯坦发扬光大，使得近代哲学研究成功转型为语言分析，并成为现代哲学研究的主流。学习分析哲学有利于澄清我们对于一些常用概念的认识。以下所列条目是基于本人的理解和独立思考而提出的观点，欢迎批评、指正。 认知对象：客观世界中存在的事物，这是第一认知对象。人们在认知过程中所形成的抽象概念是第二认知对象。概念是人们头脑中的观念，所反映的是对象的相似性（similarity）和不变性（invariance），也称为模式（mode），包括结构模式、行为模式和关系模式。这些抽象模式称为概念的内涵（intension）或者所指（referent）。概念是人们对于客观对象进行抽象所得的观念。一旦形成就拥有不依赖于客观对象的独立存在性。例如，“圆”这个概念来自于客观事物，又超越和独立于客观事物，有自己确定的内涵。因此，概念不是客观事物的附属，而是思维世界中的独立存在。柏拉图（Plato）称之为理念（idea），并且认为理念是独立于物质世界的另一种存在。概念是没有真假对错之分的，它是一个模式，按照该模式可以对现实对象进行归类。例如，我们可以用圆这个概念对事物进行归类，将所有近似圆形的事物归为一类。同类事物具有相同的性质，相同的性质具有相同的作用。因此，对事物进行归类有利于我们有效地认识和应用事物。当然，我们的认知并不满足于获得一些概念，还会继续探索这些概念的属性和相互作用，等等。因此，概念是人类认知的结果，也是进一步认知的对象。 命题：在思维中将某对象归于某模式，即认为某对象具有某性质或者模式，这种思维中的归属联系就是命题。因此，命题也是人们头脑中的一种观念，不过，命题与概念不同，它不是一种模式，不是由客观对象身上升华而成的模式，而仅仅是将一个给定对象与某概念进行联接，将对象归于这个概念所划定的类。如果说概念是进行思维概括操作的结果，那么命题可以说是简单的思维联接操作的结果。因此，命题是有真假对错之分的。如果命题所指代的归属关系是客观存在的，则该命题为真（true），否则为假（false）。 语言：是一个符号系统，用于表达和记录思维中的概念和命题。语言由符号（symbol）和语法（grammar）组成。语法是符号组成语句的规则。语句的功能就是描述我们思维中的概念和命题。在语言中，概念通常用一个简短的名字进行表示，称为词语（word），比较复杂的概念往往用固定词组（set phrase）表示。一个词语所表示的概念称为词语的含义（meaning）或者语义（semanteme）。在一个语言中，定义一个概念就是用词语和句子对概念内涵进行充分而明确地描述。仅仅是表达一个命题的句子称为陈述句（statement），被表达的命题称为该陈述句的语义（semanteme）或者含义（meaning）。有些感叹句、反问句其实也表达了命题，但是它们还有其它的语用表达功能，包括传递说话人的情感、意愿等等。需要注意的是，并非任何陈述句都表达一个命题。例如，“我正在说假话”是陈述句，但其所表达的语义不是命题。 思考：“今天是星期一”所表达的是命题吗？ 语句分析：弗雷格将一个句子的成分分为主词、谓词和量词等三个部分。主词表示对象。谓词表示对象的性质、状态和动作，相当于定语和谓语（把状语和补语视为谓语的一部分）。量词用以表示主词所表示的对象的数量，只有两种，即全称量词和存在量词，分别表示“所有”和“存在”。例如，“有的果子成熟了更可口”，其中量词是“有的”，主词是“果子”，谓词有两个，即“成熟了”和“更可口”。我们将要学习的一阶逻辑是对弗雷格的这种 1
离散数学作业7答案(数理逻辑部分)
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）． 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 P ∨Q →R ． 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧┐R) ∨(P ∧Q ∧R) ． 4．设P (x )：x 是人，Q (x )：x 去上课，则命题“有人去上课．” 可符号化为 ? x ( P ( x ) ∧ Q ( x )) ． 5．设个体域D ＝ {a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值 式为 (A(a) ∨A(b)) ∨ (B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0 ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题
离散数学形成性考核作业(四） 数理逻辑部分 本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整,抄写题目，解答题有解答过程。 第６章命题逻辑 1.判断下列语句是否为命题,若是命题请指出是简单命题还是复合命题． （1）8能被4整除． (２）今天温度高吗? （３)今天天气真好呀! （４）6是整数当且仅当四边形有４条边． (5）地球是行星. （6)小王是学生,但小李是工人． （7)除非下雨,否则他不会去. （8)如果他不来,那么会议就不能准时开始. 解:此题即是教材P.18４习题6(A)1 （１）、（4)、（5)、（6)、（7）、（８)是命题,(2）、(3）不是命题。 其中(1）、(5)是简单命题,(４）、（６）、（7）、(8)是复合命题。 2．翻译成命题公式 （1）他不会做此事. (2)他去旅游,仅当他有时间． （3）小王或小李都会解这个题. (４)如果你来,他就不回去. (5）没有人去看展览． (6）他们都是学生． （7）他没有去看电影，而是去观看了体育比赛. （８）如果下雨，那么他就会带伞． 解:此题即是教材P.1８４习题6(A）2
会带伞。：如果下雨，那么他就：他会带伞。：天下雨。）（。 是去观看了体育比赛。：他没有去看电影，而。 ：他去观看了体育比赛：他去看电影。）（：他们都是学生。 ）（：没有人去看展览。：有人去看展览。）（去。：如果你来，他就不回：他回去。 ：你来。）（道题。 ：小王或小李都会解这：小李会解这道题。 ：小王会解这道题。）（时间。 ：他去旅游，仅当他有：他有时间。：他去游泳。）（：他不会做此事。 ：他会做此事。）（Q P Q P Q P Q P P P P Q P Q P Q P Q P Q P Q P P P →∧???→∧→?87654321 3．设P ，Q 的真值为1；R ,S 的真值为0，求命题公式（P ∨Q )∧Ｒ∨S ∧Q 的真值． 解：此题即是教材P.1８4习题６(A ）４(2) (P ∨Q ）真值为1,(P ∨Ｑ)∧Ｒ真值为0，S ∧Q 真值为0, 从而(P ∨Q ）∧R ∨S ∧Q 真值为０。 4．试证明如下逻辑公式 (1) ┐（A ∧┐B )∧(┐B ∨C )∧┐Ｃ ? ┐（A ∨C ) (2) (P →Ｑ）∧（Q →Ｒ)∧┐Ｒ ??Ｐ （此题即是教材P ．185习题６(A ）5(1)、(4)） ) 7()()8()6)(5() 7()4)(2() 6()4)(3() 5() 4() 3()1() 2()() 1()(),(),(由由由由由证明：结论： 前提： T B A T B A T A T B P C P C B T B A P B A B A C C B B A ∨??∧????∨?∨??∧?∨??∨??∧? ) 4)(3()5() 4()2)(1() 3() 2() 1(),(),(由由证明：结论： 前提： T P P R T R P P R Q P Q P P R R Q Q P ??→→→??→→
数理逻辑发展史 *数理逻辑主要包括5个部分: 逻辑演算, 证明论, 公理集合论, 递归论和模型论. *数理逻辑从十七世纪末叶莱布尼茨(G. Leibniz, 1646-1716, 德国)起, 至今约有三百年历史. *数理逻辑的发展分为三阶段. *第一阶段: 这是开始用数学方法研究和处理形式逻辑的时期, 是初始阶段. *莱布尼茨: 1646-1716, 德国 *布尔(G. Boole): 1815-1864, 英国 *德?摩根(A. De Morgan): 1806-1876, 英国 *E. Schr?der: 1841-1902, 德国 共延续二百年, 其成果是逻辑代数和关系逻辑. *戈特弗里德?威廉?莱布尼茨(Gottfried Wilhelm Leibniz) 莱布尼茨生于莱比锡, 他的母亲是莱比锡大学哲学系副主任的第三个妻子. 虽然他的父亲在他6岁时就已去世, 但年幼的莱布尼茨经过父亲的谆谆教诲, 已经产生了读书和学习的愿望. 在他年轻时,他就自学了拉丁语并钻研了拉丁文的经典著作以及他父亲丰富藏书中的哲学和神学著作. 1661年, 他进入莱比锡大学学习, 在那里他用大部分时间学习哲学.他在1663年取得学士学位, 在1664年取得硕士学位, 但是
尽管准备了法学博士的学位论文, 大学却拒绝授予他学位, 也许因为教师中的一些政治问题. 莱布尼茨因此离开了莱比锡并于1667年从纽伦堡的阿尔特多夫大学取得了学位. 同时, 莱布尼茨在1663年在耶纳大学的一次短暂停留中接触到了高等数学, 并开始研究他希望是他对哲学最具创造性的贡献的细节问题, 创立一种人类思想的字母表, 即一种将所有基本概念用符号表示并通过符号的组合表示更复杂的思想的方法. 尽管莱布尼茨从未完成这一规划, 他的最初思想包含在他1666年的《论组合的艺术》里, 他在论文中独立推导出了帕斯卡的算术三角形以及其中包含的量的各种关系. 但这一寻找表达思想的适当符号和组合它们的方式的兴趣最终使他发明了我们今天使用的微积分的符号. 莱布尼茨结束大学学业后不久, 他首先为美茵茨选帝侯从事外交方面的工作, 而在他以后的生涯的大部分时间他是汉诺威公爵的顾问. 虽然有许多时期他的工作使他极为忙碌, 但他总能找到时间钻研数学思想并在这一领域同遍及欧洲的同事们维持着活跃的通信交流.
第一章数理逻辑 逻辑思维（又称抽象思维）是人运用概念、判断和推理反映事物本质与规律的认识过程（图1.1），它是人类特有的能力，是人类文明延绵不绝、科学技术持续进步的原动力。具备较强的逻辑思维能力是学习科技知识、进行科学研究、从事技术开发的先决条件。逻辑思维在信息科学技术领域显得尤为重要，只有具备强大的逻辑思维能力，才能胜任该领域的研究工作，才能胜任大型复杂软件的编写与调试工作。 图1.1. 逻辑思维 第一节逻辑学概论 逻辑思维是有规律的，逻辑学是专门研究逻辑思维规律性的学科。本节简述逻辑学的基本内容和发展历史。 1.1. 逻辑思维的基本规律 逻辑思维的作用，就是根据一定的前提，通过合理的推导，得到
一定的结论。 例1.1．苏格拉底是柏拉图的导师，柏拉图是亚里士多德的导师，因此，苏格拉底是亚里士多德的师爷。 分析：苏格拉底、柏拉图和亚里士多德是人类文明史上著名的哲学家，有着师徒传承关系。这是一个逻辑思维过程，其作用就是根据‘苏格拉底是柏拉图的导师’和‘柏拉图是亚里士多德的导师’这两个前提，得到‘苏格拉底是亚里士多德的师爷’这个结论。 例1.2. 子非鱼，安知鱼之乐？ 分析：这是惠子对庄子说的一句话。可以将这句话改写为‘你不是鱼，所以你不知道鱼的快乐’，这是一个逻辑思维过程，其作用就是根据‘你不是鱼’这个前提，导出‘你不知道鱼的快乐’这个结论。 逻辑学之父亚里士多德总结出了逻辑思维的以下四条基本规律。 表1.1. 逻辑思维的四条基本规律 下面来看看不满足这些基本规律的实例。 例1.3. 有个小伙子上了火车，一看座无虚席，就厚着脸皮硬往一位老
大爷身边挤座儿。老大爷不高兴了，说：“小伙子，别硬坐了，座位已经满了。”小伙子嘻皮笑脸地说：“老大爷，没办法,我买的就是硬坐票。”分析：这个小伙子在说话时故意把“硬座”变换成“硬坐”，这是偷换概念，违背了同一律。 图1.2. 自相矛盾 例1.4．楚国有个卖兵器的人在街上叫卖。他说：“我的矛是最锋利的，能刺穿任何东西。”他又说：“我的盾是最坚固的，不能被任何东西刺穿。”这时，人群中有人问道：“如果用你的矛去戳你的盾，会怎么样呢？”楚人听后哑口无言。 分析：假设楚人说的两句话都是真的，就可以做以下推理：一方面，因为‘楚人的矛能刺穿任何东西’，所以‘楚人的矛能刺穿楚人的盾’；另一方面，因为‘楚人的盾不能被任何东西刺穿’，所以‘楚人的矛不能刺穿楚人的盾’。这样一来，就得到了两个相互矛盾的结论，根据矛盾律，这两个结论不可能同时为真，因此，楚人的话至少有一句是假的。 例1.5．有个人说：“‘华盛顿是第一任美国总统’是不对的，‘华盛顿
一、命题逻辑 3．将下列命题符号化。 （3）如果公用事业费用增加或者增加基金的要求被否定，那么当且仅当现有计算机设不适用的时候，才需购买一台新计算机； （5）虽然天气很好，老王还是不来； （7）停机的原因在于语法错误或程序错误； 解：（3）设P：公用事业费用增加；Q：要求增加基金； R：现有计算机设备适用；S：购买一台计算机； 则命题可符号化为：()() P Q R S ∨?→??。 （5）设P：天气很好；Q：老王来； 则命题可符号化为：P Q ∧?。 （7）设P：停机的原因在于语法错误；Q：停机的原因在于程序错误。 则命题可符号化为：P Q ∨。 4．设命题P：这个材料很有趣；Q：这些习题很难；R：这门课程使人喜欢。将下列句子符号化。 （4）这个材料很有趣意味着这些习题很难，反之亦然； （5）或者这个材料很有趣，或者这些习题很难，并且两者恰具其一。 解：（4）P Q ?（5）()() P Q P Q ∧?∨?∧或者()() P Q P Q ∨∧?∨? 12．用基本等价公式的转换方法验证下述论断是否有效。 （1）P→Q,R∧S,┐Q?P∧S； （2）┐(P∧┐Q),┐Q∨R,┐Q?┐P； （3）P,Q→R,R∨S?Q→S。 解：（1）()()()(()())() P Q R S Q P S P Q R S Q P S →∧∧∧?→∧=??∨∧∧∧?∨∧ ()()1 P Q R S Q P S P Q R S =∧?∨?∨?∨∨∧=∨∨?∨?≠ （2）(()())()() P Q Q R Q P P Q Q R Q P ?∧?∧?∨∧?→?=∧?∨∧?∨∨? ()()()1 P Q Q P P Q P Q =∧?∨∨?=∧?∨?∧?= （3）(()())()()()() P Q R R S Q S P Q R R S Q S ∧→∧∨→→=?∨∧?∨?∧?∨?∨ (())()1 P R Q S Q S P R Q S =?∨?∧∨?∨?∨=?∨?∨?∨≠ 14．符号化下列论断，并用演绎法验证论断是否正确。 （1）有红、黄、蓝、白四队参加足球联赛。如果红队第三，则当黄队第二时，蓝队第四； 或者白对不是第一，或者红队第三；事实上，黄队第二。因此，如果白队第一，那 么蓝队第四； 证明：设P：红队第三；Q：黄队第二；R：蓝队第四；S：白队第一。 则上述句子可符号为：() P Q R →→，S R ?∨，Q S R ?→ ①S P ?∨ ②S ③P ④() P Q R →→⑤Q R → ⑥Q ⑦R ⑧S R →P P（附加前提）T，①，②，I P T，③，④，I P T，⑤，⑥，I CP，②，⑦ （2）如果6是偶数，则2不能整除7；或者5不是素数，或者2整除7；5是素数。因