离散数学(01)

常熟理工学院20 ～20 学年第学期《离散数学》考试试卷（试卷库01卷）试题总分： 100 分考试时限：120 分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）1.下列表达式正确的有( )（A）（B）（C）（D）2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为真。

（A）（B）（C）（D）3.集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y A}，则R 的性质为( )（A）自反的（B）对称的（C）传递的，对称的（D）传递的4.设，，其中表示模3加法，*表示模2乘法，在集合上定义如下运算：有称为的积代数，则的积代数幺元是( )（A）<0，0> （B）<0，1> （C）<1，0> （D）<1，1>5.下图中既不是Eular图，也不是Hamilton图的图是( )6.设为无向图，，则G一定是( )（A）完全图（B）树（C）简单图（D）多重图7.设P：我将去镇上,Q：我有时间。

命题“我将去镇上,仅当我有时间”符号化为（）。

（A） P Q （B）Q P （C）P Q （D）8.在有n个结点的连通图中,其边数（）（A）最多有n-1条（B）最多有n 条（C）至少有n-1条（D）至少有n条9.设A－B＝,则有（）（A）B＝（B）B（C）A B （D）A B10.设集合A上有3个元素,则A上的不同的等价关系的个数为（）（A）5 （B）7 （C）3 （D）6二、填空题（每题2分，共20分）1．n个命题变元组成的命题公式共有种不同的等价公式。

2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。

3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。

4．设T是一棵树，则T是一个连通且的图。

离散数学（一）知识梳理•逻辑和证明部分o命题逻辑题型▪命题符号化问题将自然语言转为符号化逻辑命题▪用命题变量来表示原子命题▪用命题联结词来表示连词▪命题公式的类型判断判断命题公式是否是永真式、矛盾式、可能式▪利用真值表判断▪利用已知的公式进行推理判断▪利用主析取和合取范式判断▪定理：A为含有n个命题变元的命题公式，若A的主析取范式含有2^n个极小项，则A为重言式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为矛盾式；若A的主合取范式含有2^n个极大项，则A为矛盾式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为重言式▪翻译：一个命题公式化成主范式后，若所有项都分布在主析取范式中（主合取范式为1）则为重言式；若所有项都分布在主合取范式中（主析取范式为0）则为矛盾式；若均有分布，则为可满足式。

【思想来源：真值表法求主范式】▪一个质析取式是重言式的充要条件是其同时含有某个命题变元及其否定式；一个质合取式是矛盾式的充要条件是其同时含有某个命题变元及其否定式▪一个析取范式是矛盾式当且仅当它的每项都是矛盾式；一个合取范式是重言式当且仅当它的每项都是重言式▪求（主）析取或合取范式▪等值演算法▪ 1. 利用条件恒等式消除条件（蕴含和双条件）联结词，化简得到一个范式▪ 2. 在缺项的质项中不改变真值地添加所缺项，化简得到一个主范式▪ 3. 找出包含所有命题变元排列中剩余项，凑出另一个主范式（思想上类似于真值表法）▪真值表法▪ 1. 画出命题公式真值表▪ 2. 根据真值表结果求出主范式▪主析取范式：真值为1的所有项，每一项按对应01构成极小项▪主合取范式：真值为0的所有项，每一项按对应01构成极大项▪形式证明与命题推理利用推理规则构造一个命题公式的序列，证明结论▪形式证明：命题逻辑的论证是一个命题公式的序列，其中每个公式或者是前提，或者是由它之前的公式作为前提推得的结论，序列的最后一个是待证的结论，这样的论证也称为形式证明。

CIS 607: Mathematical Basis for ComputingSOLUTIONS OF HOMEWORK 1Homework 1 -- Propositional Logic, Predicate Logic and ProofsDue Date: February 14, 2017In this homework, you will answer the following questions. Prepare a pdf file for your solutions and upload that pdf file into the blackboard system.Q1)Let p and q be the propositionsp : I bought a lottery ticket this week.q : I won the million dollar jackpot.Express each of these propositions as an English sentence.∙p →qo If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.∙￢p ∨(p ∧q)o Either I did not buy a lottery ticket this week, or else I did buy one and won the million dollar jackpot on Friday.∙￢p →￢qo If I did not buy a lottery ticket this week, then I did not win the million dollar jackpot on Friday.Q2)Let p and q be the propositionsp : It is below freezing.q : It is snowing.Write these propositions using p and q and logical connectives (including negations).∙It is not below freezing and it is not snowing.o(￢p ∧￢q)∙If it is below freezing, it is also snowing.o p →q∙Either it is below freezing or it is snowing, but it is not snowing if it is below freezing.o(p ∨ q) ∧ ( p →￢q)Q3)Construct a truth table for each of these compound propositions.∙p →(￢q ∨r)∙(p →q) ∧(￢p →r)∙(￢p ↔￢q) ↔(q ↔r)∙Show that ￢(p ↔q) and p ↔￢q are logically equivalent.o p q ￢(p ↔q) p ↔￢qo T T F Fo T F T To F T T To F F F F∙Show that (p →q) →r and p →(q →r) are not logically equivalent.o p q r (p →q) →r p →(q →r)o F F F F TQ5)Determine the truth value of each of these statements if the domain consists of all integers.∙∀n(n + 1 > n)o T∙∃n(2n = 3n)o T (when n=0)∙∃n(n = −n)o T (when n=0)∙∀n(3n ≤4n)o F (when n is a negative integer)Q6)Suppose that the domain of the propositional function P(x) consists of the integers 1, 2, and 3. Write out each of these propositions using disjunctions, conjunctions, and negations.∙∃xP(x)o P(1) ∨P(2) ∨P(3)∙∀xP(x)o P(1) ∧P(2) ∧P(3)∙￢∃xP(x)o￢ (P(1) ∨P(2) ∨P(3))∙￢∀xP(x)o￢ (P(1) ∧P(2) ∧P(3))Express the negations of each of these statements so that all negation symbols immediately precede predicates.∙∀x∃y∀zT (x, y, z)o∃x∀y∃z￢T (x, y, z)∙∀x∃yP(x, y) ∨∀x∃yQ(x, y)o∃x∀y￢P(x, y) ∧∃x∀y￢Q(x, y)∙∀x∃y(P(x, y) ∧∃zR(x, y, z))o∃x∀y(￢P(x, y) ∨∀z￢R(x, y, z))∙∀x∃y(P(x, y) →Q(x, y))o∃x∀y(P(x, y) ∧￢Q(x, y))Q8)∙Determine whether ∀x(P(x) →Q(x)) and ∀xP(x) →∀xQ(x) are logically equivalent. Justify your answer.o NOTo P: is even number, Q: is odd numbero∀x P(x) →∀xQ(x) is true since ∀xP(x) is false and ∀xQ(x) is falseo But ∀x(P(x) →Q(x)) is false∙Determine whether ∀x(P(x) ↔Q(x)) and ∀x P(x) ↔∀xQ(x) are logically equivalent. Justify your answer.o NOTo P: is even number, Q: is odd numbero∀x P(x) ↔∀xQ(x) is true since ∀xP(x) is false and ∀xQ(x) is falseo But ∀x(P(x) ↔Q(x)) is false∙Show that ∃x(P(x) ∨Q(x)) and ∃xP(x) ∨∃xQ(x) are logically equivalent.o if ∃x(P(x) ∨Q(x)) is trueo P(a) ∨Q(a) is true for a constant ‘a’ (∃-inst)o If P(a) is true →∃xP(x)is true →∃xP(x) ∨∃xQ(x) is trueo If Q(a) is true →∃xQ(x)is true →∃xP(x) ∨∃xQ(x) is trueoo if ∃x(P(x) ∨Q(x)) is falseo→ there is no constant such that P(a) ∨Q(a) is trueo→ there is no constant such that P(a) is true or there is no constant such that Q(a) is trueo→∃xP(x) is false and ∃xQ(x) is falseo→∃xP(x) ∨∃xQ(x) is falseQ9)∙Use rules of inference to show that if ∀x(P(x) →(Q(x) ∧S(x))) and ∀x(P(x) ∧R(x)) are true, then ∀x(R(x) ∧S(x)) is true.Step Reason1.∀x(P(x) → (Q(x) ∧ S(x))) Premise2.∀x(P(x) ∧ R(x)) Premise3.P(a) ∧ R(a) for arbitrary a UI from 24.P(a) for arbitrary a Simplification from 35.R(a) for arbitrary a Simplification from 36.P(a) → (Q(a) ∧ S(a))) for arbitrary a UI from 17.(Q(a) ∧ S(a)) for arbitrary a MP from 4 and 68.S(a) for arbitrary a Simplification from 79.R(a) ∧ S(a) for arbitrary a Conjunction from 5 and 810.∀x(R(x) ∧ S(x)) UG from 9∙Use rules of inference to show that if ∀x(P(x) ∨Q(x)), ∀x(￢Q(x) ∨S(x)), ∀x(R(x)→￢S(x)), and ∃x￢P(x) are true, then ∃x￢R(x) is true.Step Reason1.∀x(P(x) ∨ Q(x)) Premise2.∀x(￢Q(x) ∨ S(x)) Premise3.∀x(R(x) →￢S(x)) Premise4.∃x￢P(x) Premise5.￢P(a) for some a EI from 46.P(a) ∨ Q(a) UI from 17.Q(a) for some a Disjunctive Syllogism from 5 and 68.￢Q(a) ∨ S(a) UI from 29.S(a) for some a Disjunctive Syllogism from 7 and 810.R(a) →￢S(a) UI from 311.￢R(a) for some a Modes Tollens from 9 and 1012.∃x￢R(x) Existential Generalization (EG) from 11Q10)∙Use a direct proof to show that every odd integer is the difference of two squares.Direct Proofo Let n be an odd integer such that n=2k+1 where k is an integer (definition of odd integers) o Let squares of two integers k and (k+1) such as k2 and (k+1)2= k2+2k+1o(k+1)2 - k2 = 2k+1o So, n is the difference of two squares.o QED∙Show that if n is an integer and n3+ 5 is odd, then n is even using a proof by contraposition.Proof by Contrapositiono Assume n is an odd integer (negation of even is odd)o So, n=2k+1 where k is an integer (definition of odd integers)o n3 + 5 = (2k+1)3 + 5 = 8k3+12k2 +6k+1+5 = 2(4k3+6k2 +3k+3)o So, n3 + 5 = 2m where m is an integer such that m = (4k3+6k2 +3k+3)o Thus, n3 + 5 is an even integer (negation of “n3 + 5 is odd”)o Then, n is even (not odd)o QED.∙Prove that if n is an integer and 3n + 2 is even, then n is even using a proof by contradiction.Proof by Contradictiono Assume that n is an odd integer (negation of even is odd)o So, n=2k+1 where k is an integer (definition of odd integers)o3n+2 = 3(2k+1)+2 = 6k+5 = 2(3k+2)+1o So, 3n+2 = 2m+1 where m is an integer such that m=3k+2o Thus, 3n+2 is odd (contradiction with our assumption “3n + 2 is even”)o So, n is eveno QED.。

习题一1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明.答：此命题是简单命题，其真值为1.（2是无理数.答：此命题是简单命题，其真值为1.（3）3是素数或4是素数.答：是命题，但不是简单命题，其真值为1.x+<（4）235答：不是命题.（5）你去图书馆吗？答：不是命题.（6）2与3是偶数.答：是命题，但不是简单命题，其真值为0.（7）刘红与魏新是同学.答：此命题是简单命题，其真值还不知道.（8）这朵玫瑰花多美丽呀！答：不是命题.（9）吸烟请到吸烟室去！答：不是命题.（10）圆的面积等于半径的平方乘以π.答：此命题是简单命题，其真值为1.（11）只有6是偶数，3才能是2的倍数.答：是命题，但不是简单命题，其真值为0.（12）8是偶数的充分必要条件是8能被3整除.答：是命题，但不是简单命题，其真值为0.（13）2008年元旦下大雪.答：此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解:（1）p：中国有四大发明.（2）p:错误!未找到引用源。

是无理数.（7）p:刘红与魏新是同学.（10）p:圆的面积等于半径的平方乘以π.（13）p:2008年元旦下大雪.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.（1是有理数.是无理数.p.q.其否定式q的真值为1.（2不是无理数.答：是有理数. p 不是无理数. q 是有理数. 其否定式q 的真值为1.（3）2.5是自然数.答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1.（4）ln1是整数.答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1.4.将下列命题符号化，并指出真值. （1）2与5都是素数答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1.（2）不但π是无理数，而且自然对数的底e 也是无理数.答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数.答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧⌝，其真值为1. （4）3是偶素数.答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数.答：p ：4是素数，q ：4是偶数，符号化为p q ⌝∧⌝，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数.（4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数.答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ⌝∨⌝，其真值为1.(5) 符号化：r s ⌝∨⌝，其真值为0. 6.将下列命题符号化.（1）小丽只能从筐里拿一个苹果或一个梨.答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ⌝∧∨∧⌝. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化答:列出两种符号化的真值表：p q0 0 0 00 1 1 11 0 1 11 1 0 1根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式.8.将下列命题符号化,并指出真值.（1）只要错误!未找到引用源。

院（系） 班级 学号（9位） 姓名 ———————————阅————卷————密————封————装————订————线——————————第 1 页/共 39 页常熟理工学院20 ～20 学年第 学期《离散数学》考试试卷（试卷库01卷）试题总分： 100 分 考试时限：120 分钟题号 一 二 三 四 五 总分 阅卷人 得分一、单项选择题（每题2分，共20分）1. 下列表达式正确的有( )（A ） Q Q P ⇒ → ⌝ ) ( （B ）P Q P ⇒∨（C ）P Q P Q P ⇔⌝∧∨∧)()( （D ）T Q P P ⇔→→)(2. 设P ：2×2=5，Q ：雪是黑的，R ：2×4=8，S ：太阳从东方升起，下列( )命题的真值为真。

（A ）R Q P ∧→ （B ）S P R ∧→ （C ）R Q S ∧→ （D ）)()(S Q R P ∧∨∧ 3. 集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y ∈A}，则R 的性质为( )（A ）自反的 （B ）对称的 （C ）传递的，对称的 （D ）传递的4. 设>=< },2,1,0{1G ，>=<},*1,0{2G ，其中 表示模3加法，*表示模2乘法，在集合21G G ⨯上定义如下运算：,,,,21G G d c b a ⨯>∈<><∀有,,,,>*>=<<∙><d b c a d c b a 称>∙⨯<,21G G 为21G G ⨯的积代数，则21G G ⨯的积代数幺元是( )（A ）<0，0>（B ）<0，1>（C ）<1，0>（D ）<1，1>5. 下图中既不是Eular 图，也不是Hamilton 图的图是( )6. 设>=<E V G ,为无向图，23,7==E V ，则G 一定是( )（A ）完全图 （B ）树 （C ）简单图 （D ）多重图7. 设P ：我将去镇上,Q ：我有时间。

#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAX_STACK_SIZE 100 typedef int ElemType; typedef struct{ElemType data[MAX_STACK_SIZE];int top;} Stack;void lnitStack(Stack *S){S->top=-1;}int Push(Stack *S,ElemType x){if(S->top==MAX_STACK_SIZE-1){printf("\n Stack is full!");return 0;}S->top++;S->data[S->top]=x;return 1;}int Empty(Stack *S){return (S->top==-1);}int Pop(Stack *S,ElemType *x){if(Empty(S)){printf("\n Stack is free!");return 0;}*x=S->data[S->top];S_>top__;return 1;}void conversion(int N){int e;Stack *S=(Stack*)malloc(sizeof(Stack));InitStack(S); while(N){Push(S,N%2);"}while(!Empty(S)){Pop(S, &e);printf("%d ",e);}}void main(){ int n;printf(" 请输入待转换的值n: \n");scanf ("%d",&n);conversion(n);1. 判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？(1) 离散数学是计算机专业的一门必修课。