1.1算法：是对特定问题求解步骤的一种描述，是指令的有限序列。
程序：当一个算法用某种程序设计语言来描述时，得到的就是程序，也就是说,程序是用某种程序设计语言对算法的具体实现.
算法有输入、输出、确定性、能行性和有限性等特征，当不具备有穷性时，只能叫做计算过程，而不能称之为算法，算法可以终止，而程序没有此限制。
1.2程序证明和程序测试的目的各是什么？
程序证明是确认一个算法能正确无误的工作.
程序测试的目的是发现错误
1-9解: n!的递归定义：
1
1
)!
1
(*
{
!=
≥
-
=n
n
n
n
n
求解n!的递归函数
long Factorial (long n)
{
if(n<0)
{
cout<<”error!”;
exit(0);
}
if(n==0)
return 1;
else return n *Factorial (n-1);
}
1-10使用归纳法，证明上题所设计的计算n！的递归函数的正确性
证明(归纳法证明)：
(1)首先，如果n=0，那么程序执行
if(n==0)
return 1;
返回1,算法显然正确;
(2)假定函数Factorial对n
else return k *Factorial (k-1);
因为Factorial (k-1)正确，所以，当n=k时，程序运行正确
综合以上两点，可得程序正确.
证毕.
2-1, 简述衡量一个算法的主要性能标准,说明算法的正确性与健壮性的关系答: 衡量一个算法的主要性能指标有:
正确性，简单性，高效低存储，最优性
算法的正确性与健壮性的关系:
所谓算法的正确性:是指在合法的输入下，算法应实现预先规定的功能和计算精度要求;所谓算法的健壮性，是指当输入不合法时，算法应该能按某种预定的方式做出适当的处理;
正确的算法不一定的是健壮的，健壮的算法也不一定是完全正确的.正确性和健壮性是相互补充的.一个可靠的算法，要求能在正常情况下正确的工作，而在异常情况下，亦
能做出适当处理.
2-9(1)设计一个C/C++程序，实现一个n*m 的矩阵转置，原矩阵与其转置矩阵保存在二维数组中.
V oid reverse(int **a,int **b,int n,int m) {
For(int i=0;i For(int j=0;j (2)使用全局变量count,改写矩阵转置程序，并运行修改后的程序以确定此程序所需的程序步 V oid reverse(int **a,int **b,int n,int m,int &count) { int i=0; count++; int j=0; count++; For(;i For(;j { count++; b[j][i]=a[i][j]; count++; } } 2-10 试用定义证明下列等式的正确性 （1） 当 1n ≥ 时，22 5825n n n -+≤，所以，可选 5c =，01n =。对于0n n ≥， 22()5825f n n n n =-+≤，所以，22582()n n n -+=O 。 （2） 当 8n ≥ 时，2222 582524n n n n n -+≥-+≥，所以，可选 4c =，08n =。对 于0n n ≥，22()5824f n n n n =-+≥，所以，22 582()n n n -+=Ω。 （3） 由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以2 2 582()n n n -+=Θ。 2-11. (1) 当3n ≥时，3 l o g l o g n n n << ，所以()20l o g f n n n n =+<，3()log 2g n n n n =+>。可选 21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 （2） 当 4n ≥ 时，2log log n n n <<，所以 22()/log f n n n n =<，22()log g n n n n =≥。可选 1c =，04n =。对于 0n n ≥，2()()f n n cg n <≤，即 ()(())f n g n =O 。 （3）因为 log log(log )()(log )n n f n n n ==，()/log log 2n g n n n n ==。当 4n ≥ 时， l o g (l o g )()n f n n n =≥，()log 2n g n n n =<。所以，可选 1c =，04n =，对于0n n ≥， ()()f n cg n ≥，即 ()(())f n g n =Ω 2-16 使用递推关系式计算求n!的递归函数的时间(即分析1-9题中的函数的时间复杂度),要求使用替换和迭代两种方法分别计算之. 解: 分析1-9题中的函数的时间复杂度:用基本运算乘法的运算次数作为衡量时间复杂度的量 当n=0时，程序执行if(n==0) return 1;,并没有做乘法，故T(0)=0;当n>=1时程序执行n *Factorial (n-1);此时T(n)= T(n-1)+1故: 11 )1({)(=≥+-=n n n T n T 替换法: T(0)=0,T(1)=1,T(2)=2----- 总结得到:T(n)=n; 归纳法证明: (1),当n=0时,T(0)=0,结论成立; (2)假设当k 迭代法: T(n)=T(n-1)+1 =(T(n-2)+1)+1=((T(n-3)+1)+1)+1=....=T(0)+1+1......+1(n 个1)=n 2-19 利用递归树计算递推方程2 )2/(2)(n n T n T += 2)1(=T 假设n=2k ,那么,总共有logn+1(即k+1)层,非递归部分之和为 n2+n2/21+n2/22+…+n2/2k=(1+1/2+1/22+1/23+…+1/2logn)n2 =2n2=O(n2) 5-4. SolutionType DandC1(int left,int right) { while(!Small(left,right)&&left { int m=Divide(left,right); if(x else if(x>P[m]) left=m+1; else return S(P) } } 5-7. t emplate int SortableList { if (left<=right) { int m=left+(right-left+1)/3; if (x else if (x>l[m]) return BSearch(x,m+1,right); else return m; } return -1; } 5-8三分搜索算法的做法是:它先将待查元素X与n/3处的元素比较，然后将X与2n/3处的元素比较,比较的结果或者找到X,或者将范围缩小到原来的n/3 int Search3(int a[],int left,int right,int x) /*递归算法*/ { int l,u; if(left<=right) { l=left+(right-left+1)/3; u=left+(right-left+1)*2/3; if(x==a[u]) return u; else if(x==a[l]) return l; else if(x>a[u]) return Search3(a, u+1, right,x); else if(x>a[l]) return Search3(a, l+1, u-1,x); else return Search3(a, left, l-1,x); } return -1; } void main() { int n,*a; int x,i; cout<<"Please input n:"; cin>>n; a=new int[n]; //动态数组 int location=-1; for(i=0;i { a[i]=i+1; } cout<<"Please input the search x:"; cin>>x; cout< } void main() /*非递归算法*/ { int a[15]; int x,i; int location=-1; for(i=0;i<15;i++) { a[i]=i+1; } cin>>x; i=0; int j=14,l,u; while(i<=j) { l=i+(j-i)/3; u=i+(j-i)*2/3; if(x==a[u]) { location=u; break; } else if(x==a[l]) { location=l; break; } else if(x>a[u]) i=u+1; else if(x j=l-1; else { i=l+1; j=u-1; } } cout< } 5-12 Void stoogesort(nt a[],int left,int right) { if(a[left]>a[right]) swap(a,left,right); if(left+1>=right) return; int k=(right-left+1)/3; stoogesort(a,left,right-k); stoogesort(a,left+k,right); stoogesort(a,left,right-k); } 证明: 元素个数n=right-left+1; (1)若为空表或只有一个元素(n=1时,即left+1==right)时，程序执行if(a[left]>a[right]) swap(a,left,right);之后，执行if(left+1>=right) return;即此时程序做了一次元素之间的 比较之后，不做任何操作，显然正确. (2)假设当n< right-left+1(n>=2)时，算法正确，即对于所有元素个数小于n的元素集, 算法能正确排序. 那么,当n= right-left+1时，算法执行程序段: int k=(right-left+1)/3; stoogesort(a,left,right-k); // 序列的前2/3的子序列有序 stoogesort(a,left+k,right);//使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较大的数，即序列后1/3的位置上数均大于前2/3的数，但此时，前2/3的序列并不一定是有序的。 stoogesort(a,left,right-k);// 使序列的前2/3有序 经过三次递归，最终使序列有序，所以，当n= right-left+1时,算法正确. 由以上两点可知，算法正确. 分析算法的时间复杂度: 排序算法，基本运算仍然是元素之间的比较, 最坏情况发生在序列按递减次序排列 所以，算法时间复杂度为: ()()010T =T =，()21T =，()2313n n ?? T =T + ??? 。 设322i n ?? = ??? ，则log 1log31n i -=-。 ()2431331139n n n ???? ??T =T +=T ++ ? ????????? 49319n ??=T ++ ???= 12 2333313i i i i n --????=T +++++?? ??????? ()31322 i i -=T + ()3132 2i = - log 1 log31312222 n n --=??- log3 log31 3n -≤? log3log31n -??=O ? ? ?? 冒泡排序最坏时间复杂度为() 2 n O ，队排序最坏时间复杂度为()log n n O ，快速排序最坏 时间复杂度为()log n n O 。所以，该算法不如冒泡排序，堆排序，快速排序。 5-13. template do { mid=(left+right)/2; if(a[mid] else if(a[mid]>b[i]) right=mid; else {cnt=mid; break;} }while(left if(a[left] else cnt=left-1; if(k>cnt) { if(cnt>0) { for(j=0;j { temp[j]=a[r]; r++; } left=cnt; k-=cnt; } else { temp[j]=b[i]; left=0; k--; } } else { for(j=0;j { temp[j]=a[r]; r++; } left=cnt; k-=cnt; return temp[k-1]; } } } } 6-1设有背包问题实例，n=7，(w0,w1,w2,w3,w4,w5,w6)=(2,3,5,7,1,4,1)， (p0,p1,p2,p3,p4,p5,p6)=( 10,5,15,7,6,18,3)，M=15。求这一实例的最优解及最大收益. 解: 首先，选择最优量度标准为收益重量比; 其次, 依据收益重量比的非增次序对输入(物品)进行排序 (p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3) 对物品排序结果为:4,0,5,2,6,1,3 最后，进行贪心选择: X=(4) X=(4,0) X=(4,0,5) (剩余载重)U=14 U=12 U=8 (收益) P=6 P=6+10=16 P=16+18=34 X=(4,0,5,2) X=(4,0,5,2,6) X=(4,0,5,2,6,1(2/3)) (剩余载重)U=3 U=2 U=0 (收益) P=34+15=49 P=49+3=52 P=52+2/3*5=55.33 所以,最优解为x=(1,2/3,1,0,1,1,1); 即装入第0,2,4,5,6物品和第1个物品的2/3 最大收益: P=55.33 6-2,0/1背包问题是一种特殊的背包问题，装入背包的物品不能分割,只允许或者整个物品装入背包，或者不装入，即xi=0,或1,(0<=i 解: 首先，选择最优量度标准为收益重量比; 其次, 依据收益重量比的非增次序对输入(物品)进行排序 (p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3) 对物品排序结果为:4,0,5,2,6,1,3 最后，进行贪心选择: X=(4) X=(4,0) X=(4,0,5) (剩余载重)U=14 U=12 U=8 (收益) P=6 P=6+10=16 P=16+18=34 X=(4,0,5,2) X=(4,0,5,2,6) X=(4,0,5,2,6) (剩余载重)U=3 U=2 继续考察第1和第3个 (收益) P=34+15=49 P=49+3=52 物品,都不能装入. 所以,贪心法求得的0/1背包问题的最优解为x=(1,0,1,0,1,1,1);即装入第0,2,4,5,6物品 最大收益: P=52 但实际上，当y=(1,1,1,0,1,1,0) 即装入第0,1,2,4,5物品,可获收益为P=54,所以，贪心法求得的0/1背包问题的解x一定不是最优解. 原因是: 对于0/1背包问题，贪心法并不能保证使其单位载重下的收益最大，因为通常在背包没还装满时，却再也装不下任何物品，这样，就使得单位载重下的物品收益减少,所以， 0/1背包问题通常不能用贪心法求解. 6-3 设有带时限的作业排序实例n=7，收益(p0, p1, p2, p3, p4, p5, p6)=(3,5,20,18,1,6,30)，作业的时限(d0, d1, d2, d3, d4, d5, d6)=(1,3,4,3,2,1,2),给出以此实例为输入，执行函数JS 得到的用最优解和最大收益。 解:X={5,6,3,2} 最大收益为74 函数JS 如下: int JS(int *d, int *x, int n) { //设p 0≥p 1≥…≥p n 1 int k=0; x[0]=0; for (int j=1; j while (r>=0 && d[x[r]]>d[j] && d[x[r]]>r+1)r--; //搜索作业j 的插入位置 if((r<0 || d[x[r]]<=d[j]) && d[j]>r+1){ //若条件不满足，选下一个作业 for (int i=k; i>=r+1; i--) x[i+1]=x[i]; //将x[r]以后的作业后移 x[r+1]=j; k++; //将作业j 插入r+1处 } } return k; } 在执行JS 函数之前，必须先对输入(即作业)按作业的收益非增次序排序，结果为: 6,2,3,5,1,0,4 接着执行JS 函数: 最初, 解集合X 为空 首先, 考虑作业6, 假设将其加入集合X, 即x[0]=6; 考虑X 中的作业能否均如期完成,因为此时X 中只有作业6,其截止时限为2,故,能如 期完成,此时,将作业6加入作业子集X 中,此时，子集X 中的最大可用下标k=0; 接着，考虑作业2. 首先搜索作业2在X 集合中的插入位置，使得X 集合中的元素按作业的截止时限的非减次序排序,因为d6=2,而d2=4,所以，可将作业2插在作业6的后面，即x[1]=2,得到X=(6,2), 考虑X 中的作业能否均如期完成?因为d6=2>=1, d2=4>=2,所以，X 中作业均能如期完成，将作业2加入子集X 中. 子集X 中的最大可用下标k=k+1=1 X: 0 1 2 3 4 5 6 k 0 1 2 3 4 5 6 X: k 考虑作业3. 首先搜索作业3在X 集合中的插入位置，使得X 集合中的元素按作业的截止时限的非减次序排序,因为d6=2, d2=4,而d3=3所以，可将作业3插在作业6的后面,作业2的前面，得到X=(6,3,2), 考虑X 中的作业能否均如期完成?因为d6=2>=1, d3=3>=2, d2=4>=3所以，X 中作业均能如期完成，将作业2加入子集X 中. 子集X 中的最大可用下标k=k+1=2 考虑作业5. 首先搜索作业5在X 集合中的插入位置，使得X 集合中的元素按作业的截止时限的非减次序排序,因为d6=2, d2=4, d3=3而d5=1所以，可将作业5插在作业6的前面,得到X=(5,6,3,2), 考虑X 中的作业能否均如期完成?因为d5=1>=1,d6=2>=2, d3=3>=3, d2=4>=4所以，X 中作业均能如期完成，将作业5加入子集X 中. 子集X 中的最大可用下标k=k+1=3 考虑作业1. 首先搜索作业1在X 集合中的插入位置，使得X 集合中的元素按作业的截止时限的非减次序排序,因为d5=1,d6=2, d3=3,d2=4,而d1=3所以，可将作业1插在作业2的前面,作业3的后面,得到X=(5,6,3,1,2), 0 1 2 3 4 5 6 X: k 0 1 2 3 4 5 6 X: k 0 1 2 3 4 5 6 X: k 0 1 2 3 4 5 6 X: k 0 1 2 3 4 5 6 X: k 0 1 2 3 4 5 6 X: 考虑X 中的作业能否均如期完成?因为d5=1>=1,d6=2>=2, d3=3>=3, d1=3<4所以，X 中1作业不能如期完成，所以，不能将作业1加入子集X. 接着考虑作业0,4均不能加入子集X, 故，执行JS 得到的最优解为X=(5,6,3,2),最大收益为P=p5+p6+p3+p2=30+20+18+6=74 6-17,最佳装载问题是将一批集装箱装上一艘载重为C 的轮船，其中集装箱i 的重量为wi(0<=i<=n-1),最优装载问题是指在装载体积不受限制的情况下,求使得装箱数目最多的装载方案. (1)按贪心策略的要求,给出关于上述最优化问题的形式化描述. (2)给出贪心法求解这一问题的最优量度标准; (3)讨论其最优解的最优子结构. (4)编写装箱问题的贪心算法; (5)设有重量为(4,6,3,5,7,2,9)的7个集装箱，轮船载重为26,求最优解. 解;(1),形式化描述如下： 给定C>0, w i >0 10-≤≤n i 求X=(10} 1,0{)...,,(1210-≤≤∈-n i x x x x x i n ) 使得 C w x n i i i ≤∑-=10 并且使∑-=1 n i i x 最大 （2）以重量作为最优量度标准，以重量最轻者先装来选择集装箱装上船 （3）设(x 0,x 1,----x n-1)是最优装载问题的最优解，则易知(x 1,x 2,----x n-1)是轮船载重为C-x 0w 0且待装船的集装箱为{1，3----n-1}时相应最优装载问题的一个最优解，即最优装载问题具有最优子结构特性。否则，假设(x 1,x 2,----x n-1)不是子问题的最优解，假设有另一个解Z=(z 1, z 2,---- z n-1)是子问题的最优解，则有： 则：i n i i n i z x x x ∑ ∑ -≤≤-≤≤+ <+ 1 101 10且C z w w x i n i i ≤+ ∑-≤≤1 100，即(x 0，z 1, z 2,-- z n-1)是最优装载问 题的最优解,与(x 0,x 1,----x n-1)是最优装载问题的最优解矛盾，所以, (x 1,x 2,----x n-1)是子问题的最 优解,故最优装载问题具有最优子结构特性。 (4) 参考程序1 /*箱子信息结构体*/ struct goodinfo { float w; /*箱子重量*/ int X; /*箱子存放的状态*/ k 0 1 2 3 4 5 6 X: k , 00111111x w C z w z x i n i i i n i i n i -≤<∑ ∑∑-≤≤-≤≤-≤≤且 int flag; /*箱子编号*/ }; /*按物品重量做升序排列*/ void sort(goodinfo goods[],int n) { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].w { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; } } /*用贪心法对物品进行选择装入*/ void loading(goodinfo goods[],float M,int n) { float cu; int i,j; int A=0;/*对装入箱子进行计数*/ for(i=1;i<=n;i++)/*赋初值*/ goods[i].X=0; cu=M; /*船的剩余载重*/ for(i=1;i { if(goods[i].w>cu)/*当该箱重量大于剩余载重跳出*/ break; goods[i].X=1; A++; cu=cu-goods[i].w;/*确定船的剩余载重*/ } for(j=2;j<=n;j++)/*对箱子按序号大小作升序排列*/ { goods[0]=goods[j]; i=j-1; while (goods[0].flag { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; } cout<<"①最优解为:"< for(i=1;i<=n;i++) { cout<<" 第"< cout< } cout<<"<0：未装入；1：装入>"< cout< cout<<"②最多能装入的箱子数为:"; cout< } (5) 首先，选择最优量度标准为重量; 其次, 依据集装箱重量的非减次序对输入(物品)进行排序 对集装箱的排序结果为:5,2,0,3,1,4,6 最后，进行贪心选择: X=(5) X=(5,2) X=(5,2,0) (剩余载重)U=24 U=21 U=17 X=(5,2,0,3) X=(5,2,0,3,1) X=(5,2,0,3,1) (剩余载重)U=12 U=6 所以，最优解为X=(0,1,2,3, 5),最优解值为5 参考程序2 ?public static float loading(float c, float [] w, int [] x) ?{ ?int n=w.length; ?Element [] d = new Element [n]; ?for (int i = 0; i < n; i++) ?d[i] = new Element(w[i],i); ?MergeSort.mergeSort(d); ?float opt=0; ?for (int i = 0; i < n; i++) x[i] = 0; ?for (int i = 0; i < n && d[i].w <= c; i++) { ?x[d[i].i] = 1; ?opt+=d[i].w; ? c -= d[i].w; ?} ? return opt; } 7-5设有4 个矩阵连乘积ABCD ：A: 45*8, B: 8*40, C: 40*25, D: 25*10, ,请求出它们的最优计算次序和计算量。 解：p0=45，p1=8，p2=40，p3=25，p4=10 可只给出矩阵形式 计算m 矩阵为： m[0][1]= p0*p1* p2=45*8*40=14400; m[1][2]= p1*p2* p3=8*40*25=8000; m[2][3]= p2*p3* p4=40*25*10=11250; m[0][2]= m[0][0]+m[1][2]+p0*p1* p3=8000+45*8*25=8000+9000=17000 = m[0][1]+m[2][2]+p0*p2* p3=14400+45*40*25=14400+45000 m[1][3]= m[1][1]+m[2][3]+p1*p2* p4=11250+8*40*10=11250+3200 = m[1][2]+m[3][3]+p1*p3* p4=8000+8*25*10=10000 m[0][3]= m[0][0]+m[1][3]+p0*p1* p4=10000+45*8*10=10000+3600=13600 = m[0][1]+m[2][3]+p0*p2* p4=14400+11250+45*40*10= =m[0][2]+m[3][3]+p0*p3* p4=17000+45*25*10=17000+11250=28250 这4个矩阵相乘需要的最小数量乘法的次数=13600 最优计算次序A （（BC ）D ） 7-9给定字符串A=“xzyzzyx ”和B=“zxyyzxz ”，使用LCS 算法求最长公共子串，并给出一个最长公共子串。 提示：从上到下，从左往右计算C 矩阵，依据C 矩阵，求得最长公共子序列 解：计算求得C 矩阵如下， 0 14400 17000 13600 m= 0 8000 10000 0 11250 0 0 0 0 0 s= 1 1 2 2 2 3 依矩阵C可求得两个最长公共子序列分别为xyzz 和zyyx （求一个即可） 7-17设流水作业调度的实例为n=7，(a0, a1, a2, a3, a4, a5, a6)=(6,2,4,1,7,4,7), (b0, b1, b2, b3, b4, b5, b6)=(3,9,3,8,1,5,6).请使用流水作业调度的Johnson算法求使完成时间最小的最优调度,并求该最小完成时间。 提示：依据调度规则，求得最优调度次序 解:；令mi=min{ai，bi} 0<=i<7 即得: m0=b0=3, m1=a1=2, m2=b2=3, m3=a3=1, m4=b4=1, m5=a5=4 m6=b6=6 考虑mi,对其从小到大排序得(m3,m4,m1,m0,m2,m5,m6) 考虑mi序列(如果序列中下一个数mi是ai,则作业i放在最左的空位，否则，作业i放在最右的空位)得: 最优调度顺序(3,1,5,6,2,0,4) 依据最优调度在两台处理机上处理作业，最小完成时间:36(画出如教材P170的图7-17的形式即可求得最小完成时间36) 8-1． 状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一个状态。 显示约束：用于规定每个xi取值的约束条件称为显示约束 隐式约束：用于判定一个候选解是否为可行解的条件 问题状态：在状态空间树中的每个节点称为一个问题状态 解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。未检测的结点称为活结点 扩展结点：算法从x出发，访问x的摸个后继结点y，则x被称为扩展结点 约束函数：一个约束函数是关于部分向量的函数Bk(x0,x1.....xk),它被定义为：如果可以判定Y的子树上不含任何答案状态，则Bk(x0,x1.....xk)为false,否则为true. 剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态节点数，他们统称为剪枝函数 8-2 #include #include int count=0;//记录可行解的个数 //先将书中的递归变为如下非递归函数，再在输出一个可行解之后，加上break; int place(int k,int xk,int *x) { for(int j=0;j if(x[j]==xk || abs(x[j]-xk)==abs(j-k))//相互冲突,return 0; return 0; return 1;//互不冲突,return 1 } void NQueens(int n,int *x) { int k=0; x[k]=-1; while(k>=0) { x[k]=x[k]+1; while (x[k] x[k]=x[k]+1; if(x[k] if (k==n-1)//找到一个可行解，输出 { cout<<"The solution is: "; for(int j=0;j cout< cout< // break;//删除，则可输出所有可行解。 count++; } else //找到安置第K个皇后合法的位置，但只是部分向量，所以，继续安置下一个皇后，首先将下个皇后放在棋盘外面 { k=k+1; x[k]=-1; } else k--;//找不到安置第K个皇后合法的位置，回溯到k-1，将K-1皇后安置到下一个位置x[k]=x[k]+1; } } void main() { int n; cout<<"Please input the number n:"; cin>>n; int *x=new int[n]; /* for(int i=0;i { x[i]=-1; }*/ NQueens(n,x); cout<<"the number of the solutions is:"< } 8-3 #include #include int place(int k,int n,int xk,int *x) { for(int i=xk;i { for(int j=0;j if(x[j]==i || abs(x[j]-i)==abs(j-k))//相互冲突，检测下一个位置i=i+1 j=k; if(j==k)//互不冲突 return i; } return -1; } void NQueens(int n,int *x) { int k=0; while(k>=0) { int f=place(k,n,x[k],x); if(f!=-1) { x[k]=f; if(k==n-1) { cout<<"The solution is: "; for(int i=0;i cout< cout< x[k]=0; k--; x[k]+=1; } else k++; } else { x[k]=0; k--; x[k]+=1; } } } void main() { int n; cout<<"Please input the number n:"; cin>>n; int *x=new int[n]; for(int i=0;i { x[i]=0; } NQueens(n,x); } 离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论 离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素； 7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}} 习题参考解答 习题 1、（3）P：银行利率降低 Q：股价没有上升 P∧Q （5）P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 Q P? （7）P：不识庐山真面目 Q：身在此山中 Q→P，或～P→～Q （9）P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 P→Q∧R ，Q→T 2、（1）T （2）F （3）F （4）T （5）F （6）T （7）F （8）悖论 习题 1（3） ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ → （4） ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不， 不， 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解：根据给定的条件有下述命题公式： （A →（CD ））∧～（B ∧C ）∧～（C ∧D ） （～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） （（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ） 习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为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）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1. （2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式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年”既可以化 答:列出两种符号化的真值表： 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式//最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （6）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p) 第一章 命题逻辑 习题1.11．解 ⑴不是陈述句，所以不是命题。 ⑵x 取值不确定，所以不是命题。 ⑶问句，不是陈述句，所以不是命题。 ⑷惊叹句，不是陈述句，所以不是命题。 ⑸是命题，真值由具体情况确定。 ⑹是命题，真值由具体情况确定。 ⑺是真命题。 ⑻是悖论，所以不是命题。 ⑼是假命题。 2．解 ⑴是复合命题。设p ：他们明天去百货公司；q ：他们后天去百货公司。命题符号化为q p ∨。 ⑵是疑问句，所以不是命题。 ⑶是悖论，所以不是命题。 ⑷是原子命题。 ⑸是复合命题。设p ：王海在学习；q ：李春在学习。命题符号化为p ∧q 。 ⑹是复合命题。设p ：你努力学习；q ：你一定能取得优异成绩。p →q 。 ⑺不是命题。 ⑻不是命题 ⑼。是复合命题。设p ：王海是女孩子。命题符号化为：?p 。 3．解 ⑴如果李春迟到了，那么他错过考试。 ⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。 ⑶李春错过考试当且仅当他迟到了。 ⑷如果李春迟到了并且错过了考试，那么他没有通过考试。 4．解 ⑴?p →(q ∨r )。⑵p →q 。⑶q →p 。⑷q → p 。 习题1.2 1．解 ⑴是1层公式。 ⑵不是公式。 ⑶一层： p ∨q ，?p 二层：?p ?q 所以，)()(q p q p ??→∨是3层公式。 ⑷不是公式。 ⑸(p →q )∧?(?q ?( q →?r ))是5层公式，这是因为 一层：p →q ，?q ，?r 二层：q →?r 三层：?q ?( q →?r ) 四层：?(?q ?( q →?r )) 2．解 ⑴A =(p ∨q )∧q 是2层公式。真值表如表2-1所示： 表2-1 ⑵p q p q A →→∧= )(是3层公式。真值表如表2-2所示： 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 离散数学第四版课后答案 第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9）， （10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： G ? ? 第十四章部分课后习题参考答案 5、设无向图 G 有 10 条边，3 度与 4 度顶点各 2 个，其余顶点的度数均小于 3，问 G 至 ? 、 少有多少个顶点？在最少顶点的情况下，写出度数列、 解：由握手定理图 G 的度数之和为： 2 10 20 ( ) (G ) 。 3 度与 4 度顶点各 2 个，这 4 个顶点的度数之和为 14 度。 其余顶点的度数共有 6 度。 其余顶点的度数均小于 3，欲使 G 的顶点最少，其余顶点的度数应都取 2, 所以，G 至少有 7 个顶点, 出度数列为 3,3,4,4,2,2,2, ?( ) 4 , ( ) 2 . G G 7、设有向图 D 的度数列为 2，3，2，3，出度列为 1，2，1，1，求 D 的入度列，并求 ?(D ), (D ) ， ?(D ), ( ) , ?? D ( D ), (D ) . 解：D 的度数列为 2，3，2，3，出度列为 1，2，1，1，D 的入度列为 1,1,1,2. ?( ) 3, ( ) 2 , ? D D (D ) 2, ( ) 1, ?? D ( D ) 2, ( D ) 1 8、设无向图中有 6 条边，3 度与 5 度顶点各 1 个，其余顶点都是 2 度点，问该图有多少 个顶点？ 解：由握手定理图 G 的度数之和为： 2 6 12 设 2 度点 x 个，则 3 1 5 1 2x 12 ， x 2 ，该图有 4 个顶点. 14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出 3 种非同 构的无向图，其中至少有两个时简单图。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化； 18、设有 3 个 4 阶 4 条边的无向简单图 G 1、G 2、G 3，证明它们至少有两个是同构的。 证明：4 阶 4 条边的无向简单图的顶点的最大度数为 3，度数之和为 8，因而度数列 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列, 并给出各命题的: (1)2+2＝4 当且仅 当3+3＝6. (2)2+2＝4 的充要 条件是3+3 6. (3)2+2 4 与3+3 ＝6 互为充要条件. (4)若2+24, 则 3+36, 反之亦然. (1)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. (2)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (3) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (4) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. 1.13．将下列命题符号化, 并给出各命题的真值:(1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p q 1. (2) q p 1. (3) p q 1. (4) p r 当p 0 时为真; p 1 时为假. 1.14．将下 列 . (1) 刘 晓月跑得快, 跳得高. (2) 老王是山东 人或河北人. (3)因为天气冷, 所以我穿了羽 绒服. (4)王欢与李乐组成一个 小组. (5)李辛与李末是兄弟. (6)王强与刘威都学 过法语. (7)他一面 吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他 迟到了. (12)2 与4 都是素数, 这是不对的. (13)“2或4 是素数, 这是不对的”是不对的. 运 关 运关 n 第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭： （1）整数集合Z和普通的减法运算。封闭,不满足 交换律和结合律，无零元和单位元 （2） 非零整数集合普通的除法运算。不封闭 （3）全体n n 实矩阵集合（R）和矩阵加法及乘法运算，其中 n2。 封闭均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵； （4）全体n n实可逆矩阵集合关于矩阵加法及乘法运算，其中 n2。不封闭 （5）正实数集合和算，其中运算定义为： 不封闭因为 1 ?1 1 1 ? 1 ? 1 ?1? R （6）n于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（1），零元是0；1单位元是1 n （7）A = { a, a,?, a} n 算定义如下： 封闭不满足交换律，满足结合律， （8）S = 于普通的加法和乘法运算。 封闭均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S 是关于普通的加法和乘法运算。加 法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = ,S 关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律 5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题 1 < >> >> 7．设 * 为 Z 上的二元运算 ? , x y ∈Z ， X * Y = min ( x ，y ),即 x 和 y 之中较小的数. (1)求 4 * 6，7 * 3。 4, 3 (2)* 在 Z 上是否适合交换律，结合律，和幂等律 满足交换律，结合律，和幂等律 (3)求*运算的单位元，零元及 Z 中所有可逆元素的逆元。 单位元无，零元 1, 所有元素无逆元 8． S Q Q 为有理数集，*为 S 上的二元运算， a,b>, 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： 证明 设A 上定义的二元关系R 为： ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ① 对任意＜x,y ＞∈A ，因为x y =x y ，所以 ＜＜x,y ＞, ＜x,y ＞＞∈R 即R 是自反的。 ② 设＜x,y ＞∈A ，＜u,v ＞∈A ，若 ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ?u v =x y ?＜＜u,v ＞,＜x,y ＞＞∈R 即R 是对称的。 ③ 设任意＜x,y ＞∈A ，＜u,v ＞∈A ，＜w,s ＞∈A ，对 ＜＜x,y ＞, ＜u,v ＞＞∈R ∧＜＜u,v ＞, ＜w,s ＞＞∈R ?（x y =u v ）∧（u v =w s ）?x y =w s ?＜＜x,y ＞, ＜w,s ＞＞∈R 故R 是传递的，于是R 是A 上的等价关系。 3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使 习题3.7 1. 列出关系}6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z 中所有有序4元组。 解 }6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z ,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><= ><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3,1,1,3,2,1,2,3,1,1,3,2,1 2. 列出二维表 3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。 表3.18 航班信息 航空公司 航班 登机口 目的地 起飞时间 Nadir 112 34 底特律 08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛 09:10 Nadir 322 34 底特律 09:44 解 略 3. 当施用投影运算5,3,2π到有序5元组> 1-1，1-2 （1）解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P ∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P →Q e)设P：四边形ABCD是平行四边形。Q ：四 边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。 （P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨ N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打 字机作输出设备。P∧Q 1-3 （1）解： a)不是合式公式，没有规定运算符次序（若 规定运算符次序后亦可作为合式公式） b)是合式公式 c)不是合式公式（括弧不配对） d)不是合式公式（R和S之间缺少联结词） e)是合式公式。 （2）解： 习题 1-5 （1）证明： a)(P∧(P→Q))→Q (P∧(┐P∨Q))→Q (P∧┐P)∨(P∧Q)→Q (P∧Q)→Q ┐(P∧Q)∨Q ┐P∨┐Q∨Q ┐P∨T T b)┐P→(P→Q) P∨(┐P∨Q) (P∨┐P)∨Q T∨Q T c)((P→Q)∧(Q→R))→(P→R) 因为(P→Q)∧(Q→R)(P→R) 所以(P→Q)∧(Q→R)为重言式。 d)((a∧b)∨(b∧c) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a) 因为((a∧b)∨(b∧c)∨(c∧a)) ((a∨c)∧b)∨(c∧a) ((a∨c)∨(c∧a))∧(b∨(c∧a)) (a∨c)∧(b∨c)∧(b∨a) 所以((a∧b)∨(b∧c) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a)为重言式。 （2）证明： a)(P→Q)P→(P∧Q) 解法1： 设P→Q为T （1）若P为T，则Q为T，所以P∧Q为T，故P→(P∧Q)为T （2）若P为F，则Q为F，所以P∧Q为F，P→(P∧Q)为T 命题得证 解法2： 设P→(P∧Q)为F ，则P为T，(P∧Q)为F ，故必有P为T，Q为F ，所以P→Q为F。 解法3： (P→Q) →(P→(P∧Q)) ┐(┐P∨Q)∨(┐P∨(P∧Q)) ┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q)) T 所以(P→Q)P→(P∧Q) b)(P→Q)→Q P∨Q 设P∨Q为F，则P为F，且Q为F， 故P→Q为T，(P→Q)→Q为F， 所以(P→Q)→Q P∨Q。 c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q 设R→Q为F，则R为T，且Q为F，又P∧┐P为F 所以Q→(P∧┐P)为T，R→(P∧┐P)为F 所以R→(R→(P∧┐P))为F，所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))为F 即(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q成立。 （3）解： a) P→Q表示命题“如果8是偶数，那么糖果是甜的”。 b)a)的逆换式Q→P表示命题“如果糖果是甜的，那么8是偶数”。 c)a)的反换式┐P→┐Q表示命题“如果8不是偶数，那么糖果不是甜的”。 d)a)的逆反式┐Q→┐P表示命题“如果糖果不是甜的，那么8不是偶数”。（4）解： a)如果天下雨，我不去。 设P：天下雨。Q：我不去。P→Q 逆换式Q→P表示命题:如果我不去，则天下雨。 逆反式┐Q→┐P表示命题:如果我去，则天不下雨 b)仅当你走我将留下。 设S：你走了。R：我将留下。R→S 逆换式S→R表示命题：如果你走了则我将留下。 逆反式┐S→┐R表示命题：如果你不走，则我不留下。 c)如果我不能获得更多帮助，我不能完成个任务。 设E：我不能获得更多帮助。H：我不能完成这个任务。E→H 逆换式H→E表示命题：我不能完成这个任务，则我不能获得更多帮助。 逆反式┐H→┐E表示命题：我完成这个任务，则我能获得更多帮助（5）试证明P Q，Q逻辑蕴含P。 证明：解法1： 本题要求证明(P Q) ∧Q P, 设(P Q) ∧Q为T，则(P Q)为T，Q为T ，故由的定义，必有P为T。 所以(P Q) ∧Q P 解法2： 由体题可知，即证((P Q)∧Q)→P是永真式。 ((P Q)∧Q)→P (((P∧Q) ∨(┐P∧┐Q)) ∧Q)→P (┐((P∧Q) ∨(┐P∧┐Q)) ∨┐Q) ∨P (((┐P∨┐Q) ∧(P∨Q)) ∨┐Q) ∨P ((┐Q∨┐P∨┐Q) ∧(┐Q∨P∨Q)) ∨P ((┐Q∨┐P) ∧T) ∨P ┐Q∨┐P∨P离散数学第三版课后习题答案
离散数学课后习题答案
离散数学习题解答
屈婉玲版离散数学课后习题答案【1】
离散数学课后习题答案 (邱学绍)
离散数学课后习题答案(左孝凌版)
离散数学课后答案
离散数学第四版课后标准答案
最新离散数学习题答案
离散课后习题答案
离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案
离散数学最全课后答案(屈婉玲版)
离散课后习题答案4
离散数学习题详细答案
离散数学课后习题答案_(左孝
离散数学课后习题答案二
离散数学课后习题答案
离散数学课后习题答案_(左孝凌版)
相关主题
文本预览