离散数学形成性考核作业（四） 数理逻辑部分 本课程形成性考核作业共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 ??→→→??→→
形式系统由{∑, TERM, FORMULA, AXIOM, RULE}等5个部分构成，其中 称为符号表，TERM 为项集；FORUMULA 为公式集；AIXIOM 为公理集；RULE 为推理规则集。： 1、 符号表∑为非空集合，其元素称为符号。 2、 设∑* 为∑上全体字的组合构成的集合。项集TERM 为∑* 的子集，其元素称为项； 项集TERM 有子集V ARIABLE 称为变量集合，其元素称为变量。F(X) a, X, 3、 设∑* 为∑上全体字的组合构成的集合。公式结FORMULA 为∑* 的子集，其元素称为公式；公式集有子集ATOM ，其元素称为原子公式。 A(f(a,x1,y)), A →B 4、 公理集AXIOM 是公式集FROMULA 的子集，其元素称为公理。 5、 推理规则集RULE 是公式集FORMULA 上的n 元关系集合，即 RULE=)}2(|{n FORMULA r n n n r ?∧≥∧?是正整数， 其元素称为形式系统的推理规则。 其中公式集和项集之间没有交叉，即TERM ∩FORMULA =φ，公式和项统称为表达式。 由定义可知，符号表∑、项集TERM 、公式集FORMULA 是形式系统的语言部分。而公理集AXIOM 、推理规则集RULE 为推理部分 形式系统特性 1、 符号表∑为非空、可数集合（有穷、无穷都可以）。 2、 项集TERM 、公式集FORMULA 、公理集AXIOM 和推理规则集RULE 是递归集合， 即必须存在一个算法能够判定给定符号串是否属于集合（可判定的）。 3、 形式系统中的项是用来描述研究的对象，或者称为客观世界的。而公式是用来描述 这些研究对象的性质的。这个语言被称为对象语言。定义公式和项产生方法的规则称为词法。 公理： I ))((A B A →→ II ))()(())(((C A B A C B A →→→→→→ III ))())()(((A B B A →→?→? 证明：A →A (1) A →(A →A) ((A →(B →C))→((A →B)→(A →C)) ((A →(B →A))→((A →B)→(A →A)) ((A →((A →A)→A))→((A →(A →A))→(A →A)) A →((A →A)→A)) (A →(A →A))→(A →A) (A →(A →A)) A →A
“离散数学”数理逻辑部分考核试题答案 ━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━ 一、命题逻辑基本知识（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.
第二篇集合与关系 集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。 随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。 现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。 本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。 第2-1章集合及其运算 §2-1-1 集合的概念及其表示 一、集合的概念 “集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作
玛 氏 食 品 ( 中国 ) 有 限 公 司 姓名：武英杰 性别：男 1-25 题均为选择题，只有一个正确答案。答案写在( ) 内 1-6 题根据下列数字规律，选择( )内应填数字： ( B ) 1、 2，9，16，23，30，（ ） A.35 B.37 C.39 D.41 ( C ) 2、 5，11，20，32，（ ） A ．43 B ．45 C ．47 D ．49 ( C )3、 1，2，3，5，（ ），13 A 9 B 11 C 8 D7 ( A )4、 5，7，（ ），19，31，50 A 12 B 13 C 10 D11 ( C )5、 8，4，2，2，（ ） A 、2 B 、3 C 、4 D 、5 ( C)6、 14，20，29，41，( ) A.45 B.49 C.56 D.72 ( A ) 7、. 15.025.053÷?的值是： A ．1 B ．1.5 C ．1.6 D ．2.0 ( C ) 8、 1994年第二季度全国共卖出汽车297600辆，与上年同期相比增长了 24%。上年同期卖出多少辆汽车?
A．714224 B．226176 C．240000 D．369024 ( D ) 9、甲、乙两地相距42公里，A、B两人分别同时从甲乙两地步行出发， A的步行速度为3公里/小时，B的步行速度为4公里/小时，问A、B步行几小时后相遇？ A. 3 B. 4 C. 5 D. 6 ( A)10、一根绳子长40米，将它对折剪断；再对剪断；第三次对折剪断，此时每根绳子长多少米？ A、5 B、10 C、15 D、20 ( B ) 11、如果一米远栽一棵树，则285米远可栽多少棵树？ A、285 B、286 C、287 D、284 (B ) 12、在一本300页的书中，数字“1”在书中出现了多少次？ A、140 B、160 C、180 D、120 ( D ) 13、自然数A、B、 C、 D的和为90，已知A加上2，B减去2，C乘以 2，D除以2之后所得结果相同，则B等于（） A、26 B、24 C、28 D、22 ( B ) 14、某人工作一年的报酬是18000元和一台全自动洗衣机,他干了7个月, 得到9500和一台全自动洗衣机,问这台洗衣机值多少元? A.8500元 B.2400元 C.2000元 D.1700元 ( B ) 15、橱窗：商品；相当于 A 电影：明星 B 书架：书籍 C 宇宙：星球 D 餐馆：厨师
浅谈数理逻辑在计算机科学中的应用 文章整理编辑---论文文库工作室（QQ1548927986） 摘要：数理逻辑是离散数学课程中研究推理的逻辑学科，它为确定一个给出的论证是否有效提供各种法则和技巧，在计算机科学里用来检验程序的正确性，也可以验证定理和推论，同时在计算机模型、计算机程序设计语言、计算机硬件系统等方面有着重要作用。研究数理逻辑在计算机科学领域中的应用，必须从研究数理逻辑的符号化开始讨论、加以分析、验证结论。 关键词：数理逻辑；命题逻辑；一阶逻辑；推理理论 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。其内容大致包含数理逻辑、集合论、代数结构、组合数学、图论和初等数论6部分，这6部分从不同的角度出发，研究各种离散量之间数与形的关系。本文主要研究数理逻辑部分在计算机科学领域中的应用。 1.为计算机的可计算性研究提供依据 数理逻辑分为命题逻辑和一阶逻辑两部分，命题逻辑是一阶逻辑的特例。在研究某些推理问题时，一阶逻辑比命题逻辑更准确。数理逻辑中的可计算谓词和计算模型中的可计算函数是等价的,互相可以转化，计算可以用函数演算来表达，也可以用逻辑系统来表达。 某些自然语言的论证看上去很简单，直接就可以得出结论，但是通过数理逻辑中的两种符号化表达的结果却截然不同，让人们很难理解，这就为计算机的可计算性研究埋下伏笔。下面举一个简单例子加以说明。 例1 凡是偶数都能被2整除。6是偶数，所以6能被2整除。 可见，一个复杂的命题或者公式可以利用符号的形式来说明含义，来判断正确性，这使得计算机科学中的通过复杂文字验证的推理过程变得简单、明了了。 2.为计算机硬件系统的设计提供依据 数理逻辑部分在计算机硬件设计中的应用尤为突出，数字逻辑作为计算机科学的一个重要理论，在很大程度上起源于数理逻辑中的布尔运算。计算机的各种运算是通过数字逻辑技术实现的，而代数和布尔代数是数字逻辑的理论基础，布尔代数在形式演算方面虽然使用了代数的方法，但其内容的实质仍然是逻辑。范式正是基于布尔运算和真值表给出的一个典型公式。 下面以计算机科学中比较典型的开关电路的设计为实例说明数理逻辑中布尔代数和范式的应用。整个开关电路从功能上可以看做是一个开关，把电路接通的状态记为1（即结果为真），把电路断开的状态记为0（即结果为假），开关电路中的开关也要么处于接通状态，要么处于断开状态，这两种状态也可以用二值布尔代数来描述，对应的函数为布尔函数，也叫线路的布尔表达式。接通条件相同的线路称为等效线路，找等效线路的目的是化简线路，使线路中包含的节点尽可能地少。利用布尔代数可设计一些具有指定的节点线路，数学上既是按给定的真值表构造相应的布尔表达式，理论上涉及到的是范式理论，但形式上并不难构造。 例2 关于选派参赛选手，赵，钱，孙三人的意见分别是：赵：如果不选派甲，那么不选派乙。钱：如果不选派乙，那么选派甲；孙：要么选甲，要么选乙。以下诸项中，同时满足赵，钱，孙三人意见的方案是什么？ 解答：把赵，钱，孙三个人的意见看做三条不同的线路，对三条线路化简得到接通状态
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个
数理逻辑的心得 数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。是大四接触到的，现简单介绍一下数理逻辑的发展史，算是一点感悟吧 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)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个
作业答案：数理逻辑部分 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 ∨→∧
數理邏輯與集合論作業二 1. 解：該題應該理解為此列表中每一句都是形如“i: 在這個列表中，恰有i條語句為假”的形式。 a)思路：考慮這100句裡可能有幾句為真。是否可能沒有一句為真？是否可能 祗有一句為真，是哪一句？是否可能多餘等於兩句為真？ b)思路：“至少i+1句為假”蘊含“至少i句為假”，若第i句為真，則1…… i-1句都為真，所以第 100, 99, 98, ……句都為假，一直到第50句為真 c) 思路同上，但是…… 2. 解答：如果我說右邊的路通往遺跡你將回答“是”，對嗎？ 3.
解答： ))))a q p b p q c q p d q p →∧→?→? 4. 也就是上述描述是否自相矛盾？ 5. 解答： 条件符号化 ::::(1)(2)(C G)(3)(G W)G W (4)G W G W S C G W S C G W S C C G W C C S C S →?∧=?∨???∧?=∨→?????男管家廚師園丁雜役假設為真，則由（2）得：再由（1）得：但無法判定的真假 假設為假，則由（3）得：再由（4）得：由（1）得：綜上所述：和說了假話，，的話真假未知 6. 四个朋友被认定为非法进入某计算机系统的嫌疑人。他们已对调查员作了陈述。
艾丽斯说“卡罗斯干的” 约翰说“我没幹。” 卡罗斯说“戴安娜干的。” 戴安娜说“卡罗斯说是我幹的，他说谎。” a）如果调查员知道四个嫌疑人中恰有一人说真话，那么准幹的？解释你的推理。 b）如果调查员知道恰有一人说谎，谁干的？解释你的推理。 解：前提符號化為 （1）A: C （2）J: ? J （3）C: D （4）D: ? (C: D) a) 祗有一句話為真，而（3）（4）有且僅有一句為真，分別討論（3）（4）為真的情況。 b）分析步驟同上。 7. 用真值表證明德摩根律和吸收律。 解答略 8. 使用等值演算證明下列命題公式為永真式（不得用真值表） 解答： a
“离散数学”数理逻辑部分考核试题答案 --------------------------- ★----------------------------- 一、命题逻辑基本知识（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 一9一；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=O。本题推理符号化为：（（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 ∧-「)))：= 一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) U (~p ∧(q ∨-q) ∧(r ∨一r)) ∨m7 二(一P ∧—q ∧ F ∨ (一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) U (P → q)
2006年的考题 一、A={a,b,c},B={X|a∈X且X?A},求B-A, B-{A}, ∪B, ∩B。 二、A={1,2,3,5,9},R是A上的关系且R={
1.用真值表判断下列公式的类型（重言式、矛盾式还是普通式）： (1)p→(p∨q∨r) (2)(p→╕p)→╕q (3)╕(q→r)∧r (4)(p→q)→(╕q→╕p) (5)(p∧r) (╕p∧╕q) (6)((p→q)∧(q→r))→(p→r) (7)(p→q) (r s) 2.求下列公式的成真赋值 (1)╕p→q (2)p∨╕q (3)(p∧q)→╕p (4)╕(p∨q)→q 3.求下列公式的成假赋值 (1)╕(╕p∧q)∨╕r (2)(╕q∨r)∧(p→q) (3)(p→q)∧(╕(p∧r)∨p) 4.已知p→(p∨q)是重言式，╕(p→q)∧q是矛盾式，试判断(p→(p ∨q))∧(╕(p→q)∧q)及(p→(p∨q)) ∨(╕(p→q)∧q)的类型。
5.用等值演算法证明下列等值式 (1)p<=>(p∧q)∨(p∧╕q) (2)((p→q)∧(p→r))<=>(p→(p∧r)) (3)╕(p q)<=>(p∨q)∧╕(p∧q) (4)(p∧╕q)∨(╕p∧q)<=>(p∨q)∧╕(p∧q) 6.求下列公式的主析取范式和主和取范式 (1)(p∧q)∨r (2)(p→q)∧(q→r) (3)(p∧q)→q (4)(p q)→r (5)╕(r→p)∧p∧q 7.前提：╕p∨q，╕q∨r，r→s，p 结论：s 根据前提，证明结论 8.根据以下前提：p→(q→r)，q→(r→s)，证明：(p∧r)→s 9.前提：╕(p→q)∧q，p∨q，r→s 结论1：r
结论2：s 结论3：r∨s 证明从此前提出发，推出的结论1，结论2，结论3都是正确的。 10．证明下列各推理 (1)前提：p→(q→r)，p，q 结论：r∨s (2)前提：p→(q→r)，s→p，q 结论：s→r (3)前提：p→╕q，╕r∨q，r∧╕s 结论：╕p
离散数学形成性考核作业(四） 数理逻辑部分 本课程形成性考核作业共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 ??→→→??→→
《离散数学》单元测试（数理逻辑部分） 一、填空题 1. 命题公式)(r q p G →?→=，则G 共有 个不同的解释，使公式G 为假的解释是 和 ，把G 在其所有解释下所取真值列成一个表，称为G 的 ，并可以通过它判定该公式的类型是 。 2. 在谓词逻辑中将下面命题符号化： a) 在北京工作的人未必都是北京人。（设F （x ）：x 在北京工作，G （x ）：x 是北京人） 。 b) 没有不犯错的人。（设F （x ）：x 是人，G （x ）：x 犯错误） 。 3. 将公式化成与之等值的前束范式， =→?→???)))()((),((x R z zQ y x yP x 。 4. 设谓词的定义域为},,{c b a ，将表达式))()((y yS x R x ?∧?中的量词消除，写成与之等值的命题公式 是 。 二、单项选择题 1. 一个公式在等值的意义下，下面哪个写法是唯一的（ ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 2. 设命题公式P Q P G →∧=)(，则G 是（ ）。 A. 永假式 B. 永真式 C. 可满足式 D. 析取范式 3. 设命题公式)(),(P Q P H Q P G ?→→=→?=，则G 与H 的关系是（ ）。 以上都不是。 .;.;.;.D H G C G H B H G A ???
4. 已知命题))((R Q P G ∧→?=，则所有使G 取真值1的解释是（ ）。 A. （0，0，0），（0，0，1），（1，0，0） B. （1，0，0），（1，0，1），（1，1，0） C. （0，1，0），（1，0，1），（0，0，1） D. （0，0，1），（1，0，1），（1，1，1） 5. 设I 是如下一个解释，0 101),(),(),() ,(},,{b b P a b P b a P a a P b a D =， 则在解释I 下取真值为1的公式是（ ）。 ),(.);,(.);,(.);,(.y x yP x D x x xP C y x yP x B y x yP x A ??????? 6. 下面给出的一阶逻辑等值式中，（ ）是错的。 .(()())()(); .(()())()(); .()(()); .()(()). A x A x B x xA x xB x B x A x B x xA x xB x C xA x x A x D A xB x x A B x ?∨??∨??∨??∨??????→???→ 三、判断题 1. 判断下列陈述是否是命题？ a) 3是无理数。 b) 什么时候开会呀？ c) 2310x +≤。 d) 苹果树和梨树都是落叶乔木。 e) 吃一堑，长一智。 f) 李辛与李末是兄弟。 2. 设A 与B 均为含n 个命题变项的公式，判断下列命题的真值。 a) A ?B 当且仅当 A B 是可满足式。 b) 若A 为重言式，则A 的主析取范式中含有2n 个不同的极小项。 c) A 为矛盾式，当且仅当A 的主合取范式中含有2n 个不同的极大项。 d) 任何公式A 都能等值地化为联结词集{∧、∨} 中的公式。 3. 任何一阶逻辑公式都存在唯一与之等值的前束范式。
第1章 命题逻辑 一、单项选择题 1. 下列命题公式等值的是( ) B B A A Q P Q Q P Q B A A B A A Q P Q P ),()D (),()C () (),()B (,)A (∧∨?∨∨?∨→→→?→→∨?∧? 2. 设命题公式G ：)(R Q P ∧→?,则使公式G 取真值为1的P ， Q ，R 赋值分别是 ( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 3. 命题公式Q Q P →∨)(为 ( ) . (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 4 命题公式)(Q P →?的主析取范式是( )． (A) Q P ?∧ (B) Q P ∧? (C) Q P ∨? (D) Q P ?∨ 5. 前提条件P Q P ,?→的有效结论是( )． (A) P (B) P (C) Q (D)Q 6. 设P ：我将去市里，Q ：我有时间．命题“我将去市里，仅当我有时间时”符号化为( ) Q P Q P Q P P Q ?∨??→→)D ()C ()B ()A ( 二、填空题 , 1. 设命题公式G ：P ?(Q P )，则使公式G 为假的真值指派是 2. 设P ：我们划船，G ：我们跑步，那么命题“我们不能既划船，又跑步”可符号化为 3. 含有三个命题变项P ，Q ，R 的命题公式P Q 的主析取范式是 4. 若命题变元P ，Q ，R 赋值为(1,0,1)，则命题公式G ＝)())((Q P R Q P ∨??→∧的 真值是 5. 命题公式P ?P Q 的类型是 ． 6. 设A ，B 为任意命题公式，C 为重言式，若C B C A ∧?∧，那么B A ?是 式(重言式、矛盾式或可满足式) 三、解答化简计算题 [ 1. 判别下列语句是否命题如果是命题，指出其真值. (1) 中国是一个人口众多的国家. (2) 存在最大的质数. (3) 这座楼可真高啊！ (4) 请你跟我走! (5) 火星上也有人. 2.作命题公式))(()(P Q P Q P ∨∧→→的真值表，并判断该公式的类型． 3. 试作以下二题：(1) 求命题公式(P Q )(P Q )的成真赋值． (2) 设命题变元P ,Q ,R 的真值指派为(0,1,1),求命题公式 ))()(()(Q R Q P R P →?∨→?∧?的真值． 4. 化简下式命题公式))()((P Q P Q P ∧?∧?∨∧ '