《离散数学》习题与解答 第一篇数理逻辑 第一章命题逻辑 1- 1 (1)指出下列语句哪些是命题，哪些不是命题，如果是命题指出他的真值 a)离散数学是计算机科学系的一门必修棵 b)口裁吗？ c)明天我去看电影 d)请勿随地吐痰 e)不存在最大质数 f)如果我掌握了英语，法语，那么学习其他欧洲的语言就容易多了 g)9+5<12 h)x<3 i)月球上有水 j)我正在说假话 ［解］ a)不是命题 b)是命题，真值视具体情况而定 c)不是命题 d)是命题，真值为t e)是命题，真值为t f)是命题，真值为f g)不是命题 h)是命题，真值视具体情况而定 i)不是命题 1-2(1)用P表示命题“天下雪”，(又表示命题“我将去镇上”川表示命题“我有时间”.以符号形式写出下列命题： (a)如果天不下雪和我有时间，那么我将去镇上. (b)我将去镇上，仅当我有时间. (c)天不下雪 (d)天下雪，那么我不去镇上 ［解］ a)(-］ PAR)-Q b)Q-> R c)q P d)P->n Q 1-2(2)将下而这段陈述屮所出现的原子命题符号化，并指出他们的真值，然后将这段陈述屮的每一命题符号化、吃是有理数是不对的.2是偶素数.2或4是素数.如杲2是素数则3也是素数.2是素数当且仅当3也是素数. ［解］:陈述屮出现5个原子命题，将他们符号化为：
P:、血是有理数Q：2是素数R：2是偶数S:3是素数 U:4是素数其真值为F 其真值为T 其真值为T 其真值为T 其真值为F 陈述中各命题符号化为： -1 P;QAR;QVU;Q->S;Q< = >S 1- 2 (3)将下列命题符号化 a)如果3+3=6,则雪是白色的. b)如果3+3H6,则雪是白色的 c)如果3+3=6,则雪不是白色的. d)如果3+3H6,则雪不是白色的 e)王强身体很好，成绩也很好. f)四边形ABCD是平行四边形，仅当其对边平行 ［解］:设P: 3+3二6 Q:雪是白色的 R:王强成绩很好S:王强身体很好 U:四边形ABCD是平行四边形V:四边形ABCD的对边是平行的于是： a)可表示为:P—Q b)可表示为：P~*Q c)可表示为：P—-］ Q d)可表示为：1 P-*-| Q e)可表不为：SAR f)可表示为:U< = >V 1-3 (1)判别下列公式中哪些是合式公式，那些不是合式公式 a)(Q-RAS) b)(p< = >(R->s)) c)(G P-Q)f (Q-P))) d)(RS-T) e)((P- (Q->R)) - ((Pf Q)-* (P~R))) ［解］: a)不是合式公式(若规定运算符优先级后也可以作为合式公式) b)是合式公式 c)不是合式公式(括号不配对) d)不是合式公式 e)是合式公式 1-3(2)对下列各式用指定的公式进行代换： a)(((A->B)->B)->A),用(A-C)代换A,用((B/\C) -A 代换B。 b)((A-B)V(B-A),用B 代换A, A 代换B. ［解］:a)((( (A-*C) - ((BAC) - A)) - ((BAC) ->A)) -> (A-C)) b) ((B->A) V(A->B)) 1- 3(3)用符号形式写出下列命题
11.群和编码Group and coding §11.1 二进编码和查错 coding of binary information and error detection Alphabet 字母集。B ＝{0,1}. message 从有限alphabet 中选取有限多个符号组成的一个序列。 word m 个0和1组成的一个序列。 B ＝B ×B ×……×B （m 个）。 B m 的加法⊕： (x 1,x 2,…,x m )⊕(y 1,y 2,…,y m ) =(x 1+y 1 ,x 2+y 2,…,x m +y m ) B m 中共有2m 个元素, B m 的阶是2m 。 0＝(0,0,……,0). 由于disterbance （noise ）x ≠x t 。 用编码方法查错、纠错。 取n>m ，一一对应 e ：B m →B n ，
称e是（m,n）编码函数。 b∈B m，e(b)∈B n叫做b的码词Code word e(b)比b多几位0，1用来查错和纠错。 将要发出的word b编码得到x=e(b),发送后接收到x t，如果没有干扰，x＝x t，b＝e-1(x t). 如果有干扰，x和x t有≤k位出错，即有1位到k位错误。 x的权（weight）：x含有1的个数，记做|x|. 奇偶校验码parity check code： 如果b＝b1b2…b m， 令e(b)＝b1b2…b m b m+1, b m+1=0, if |b|是偶数， b m+1=1, if |b|是奇数。 b m+1=0, 当且仅当b含有偶数个1。 m＝3 e(000)=0000 e(001)=0011 e(010)=0101 e(011)=0110 e(100)=1001 e(101)=1010 e(110)=1100 e(111)=1111 对任意b，e(b)的权总是偶数。 设b=111，x＝e(b)=1111. 如果接收到有一位错x t＝1101， x t的权是奇数，发现有错。 x t的权是偶数，无法判断有错。 例3．（m，3m）编码函数： e：B m→B3m， b＝b1b2…b m， e(b)＝b1b2…b m b1b2…b m b1b2…b m. e(000)=000000000