1、离散数学第1章习题答案#include#include#define MAX_STACK_SIZE 100 typedef int ElemType;typedef structElemType dataMAX_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-dataS-top=x;return 1;int Empty(Stack
2、*S)return (S-top=-1);int Pop(Stack *S,ElemType *x)if(Empty(S)printf(n Stack is free!);return 0;*x=S-dataS-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( 请输入待转换的值
3、n: n);scanf (%d,&n);conversion(n);1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？(1)离散数学是计算机专业的一门必修课。(2)李梅能歌善舞。(3)这朵花真美丽！(4)3 + 26。(5)只要我有时间，我就来看你。(6)x=5o(7)尽管他有病，但他仍坚持工作。(8)太阳系外有宇宙人。(9)小王和小张是同桌。(10)不存在最大的素数。解 在上述10个句子中，(3)是感叹句，因此它不是命题。 (6)虽然是陈述句，但它没有确定的值,(9)、因此它也不是命题。其余语句都是可判断真假的陈述句，所以都是命题。其中： (1)、(4)、(8)、是简
4、单命题，、(2)、(5) 、(7)、(10)是复合命题。2.判断下列各式是否是命题公式，为什么？(1)( P (PV Q)。(2)( p Q (Q P)。(3)( P Q) (Q P) o(4)( Q RA S。(5)( PV QR So(6)( R (Q Ri (P Q)。解(1)是命题公式。(2)不是命题公式，因为括号不配对。(3)是命题公式。(5)不是命题公式，因为 QR没有意义。不是命题公式，因为 R (Q R) (P Q没有意义。 3将下列命题符号化：(1)我们不能既划船又跑步。(2)我去新华书店，仅当我有时间。(3)如果天下雨，我就不去新华书店。(4)除非天不下雨，我将去新华书店。
5、(5)张明或王平都可以做这件事。(6)“ 2或4是素数，这是不对的”是不对的。(7)只有休息好，才能工作好。(8)只要努力学习，成绩就会好的。(9)大雁北回，春天来了。(10)小张是山东人或河北人。(1)符号化为(PA Q，其中，P：我们划船，Q:我们跑步。符号化为Q R,其中，R：我有时间，Q：我去新华书店。符号化为P Q,其中，P：天下雨，Q我去新华书店。符号化为P Q其中,P：天下雨，Q我去新华书店。符号化为PA Q,其中,P：张明可以做这件事， Q王平可以做这件事。符号化为(PV Q),“2或4是素数，这是不对的”是不对的，其中,P: 2是素数,素数，。(8)(9)符号化为符号化为符号
6、化为(10)符号化为PP,其中,Q其中,Q,其中,Q其中,P：P：P：休息好，Q工作好。努力学习，Q：成绩就会好的。大雁北回，Q:春天来了。P：小张是山东人， Q小张是河北人。(1)(PV Q。PA (QV F)。(PVQ ( PAQ。P (Q P)。解(1)PQPV Q(PV Q00100101101011104.构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值?由真值表可知，公式 (PV Q)的成真赋值为：01,成假赋值为 00、10、11。P Q RQV RPA (QV F)0 0 0000 0 1100 1 0100 1 1101 0 0001 0 1111 1
7、0111 1 111由真值表可知，公式 PA (QV R)的成真赋值为：101、110、111,成假赋值为 000、001、010、011、100。P Q(P V QPA Q(PV C) ( PA Q0 01110 10011 00011 1001由真值表可知，公式 (PV Q) ( PA Q的成真赋值为：00、01、10、11,没有成假赋值。01。由真值表可知，公式P QQ PP (Q P)0 0110 1001 0111 111P (Q P)的成真赋值为：00、10、11,成假赋值为:5.分别用真值表法和公式法判断下列命题公式的类型:(1)(PV Q)(PA Q)。(2)(PA Q)(PV
8、 Q)。(3)(PV Q)A (QV R) A (RV PV Q)。(4)(PA Q F) (PA RA Q。(5)(Q P) A(PA Q)。(6)(P Q(P Q)。(7)(PA Q) A(PV Q)。解(1)真值1表法：P QPV QPA Q(PV Q (PA 00 00010 11001 01001 1111由真值表可知，公式(PV Q ( PA Q)为可满足式。公式法：因为(PV Q) (PA Q (PV Q V (PA Q ( PA Q V ( PA Q，所以，公式(PV Q ( PA(2)真值表法:PQPA QPV Q(PAQ (PVQ00001010111001111111由真
9、值表可知，公式(PA Q (PV Q)为重言式。公式法：因为(PA Q (PV Q (PA Q) V (PV Q PV QV PV Q T,所以，公式(PA Q (PV Q为重言式。(3)真值表法：P Q RPV QQ RRV PV Q(PV Q A (QV F) A (RV PV Q0 0 011100 0 110100 1 011100 1 111101 0 001101 0 100101 1 011001 1 11110由真值表可知，公式(PV Q A (QV F) A (RV PV Q为矛盾式。公式法：因为(PV Q A (QV F) A (RV PV Q ( PV Q A QA FA
10、 ( FA PA Q F,所以，公式(PV Q A (QV F) A (RV PV Q 为矛盾式。(4)真值表法：P Q RPA Q RPA RA Q(PA Q F) (PA RA Q0 0 01000 0 11000 1 01000 1 11001 0 01001 0 11001 1 00111 1 1100由真值表可知，公式(PA Q & (PA FA Q为可满足式。公式法：因为(PA Q F) (PA FA Q ( ( P A Q V R V (PA FA Q(P A QA F) V (PA FA Q ( P A CA F)所以，公式(PA Q F) (PA F Q为可满足式。(5)真值
11、表法：PQQ PPA Q(Q P) A ( PA Q00100010101010011100由真值表可知，公式(Q P) A ( PA Q为可矛盾式。公式法：因为(Q P) A ( PA Q ( QV P) A ( PA Q (QA P) A ( PA Q F,所以，公式为可矛(6)真值表法:P QP Q(P Q(P Q (P Q0 00010 11111 01111 1001由真值表可知，公式(P Q(PQ)为永真式。公式法：因为(PQ)(P Q(P Q A (QP)(PA Q) V ( PA Q)(PV Q) A (PVQ) ( pvQ) A (PV Q) T所以，公式(P Q (P Q为
12、永真式。(7)真值表法：PQPA QPV Q(PA Q A (PVQ00000010101001011110由真值表可知，公式(PA Q A (PV Q为矛盾式。公式法：因为(PA Q) A (PV Q (PA Q) A ( PA Q F,所以，公式(PA Q A (PV Q为矛盾式。6.分别用真值表法和公式法证明下列各等价式：(1)( PV Q A P PA Q(2)(PV Q V ( PA Q P。(3)( PA Q V P PV Q(4)P (QA F) (PQ A (P R)。(5)( PQ A (RQ (PV R) Q。(6)( PA QA A C) A (A PV QV C) (A
13、A (P Q) C。(P Q P Q(8)(PC) P Q证明(1)真值表法：PQPV Q(PV Q A PPA Q00000011111010011100由真值表可知，(PV Q) A P PA Q公式法：(PV Q A P (PA P) V (QA P) PA Q(2)真值表法：PQPA Q(PVQ V( PA QP00111011111000011000由真值表可知， (PV Q) V ( P QP。公式法：(PV Q) V ( PA Q) ( PA Q) V ( PA Q PA ( QV Q) P。(3)真值表法：PQPA Q(PA Q V PPV Q00011010111000011
14、111由真值表可知，(PA Q) V PPV Q公式法：(PA Q V P (PVP) A (QVP)PV Q(4)真值表法：P Q R| P QP R(P Q) A (P RP ( QA R)0 0 011110 0 111110 1 011110 1 111111 0 000001 0 101001 1 010001 1 11111由真值表可知，P (QA R) (P Q A (P R)。公式法：P (QA F) PV (QA F)(PV Q) A ( PV R) (P Q)A (P R)。(5)真值表法：P Q RP QR Q(P Q) A (R Q(P V R Q0 0 011110
15、0 110000 1 011110 1 111111 0 001001 0 100001 1 011111 1 11111由真值表可知，(PQ A (R Q) (PV R) Q)。公式法：(P Q A (R Q) ( PV Q) A ( RV Q) ( PA R V Q(PV R V Q (PV R) Q。(6)真值表法：P Q A CP Q(PA CA A C) A (A P V QV C)(AA (P Q) C0 0 0 01110 0 0 11110 0 1 01000 0 1 11110 1 0 00110 1 0 10110 1 1 00110 1 1 10111 0 0 00111
16、 0 0 10111 0 1 00111 0 1 10111 1 0 01111 1 0 11111 1 1 01001 1 1 1111由真值表可知，(PA QA A C) A (A PV QV C) (AA (P Q) G公式法：(PA QA A C) A (A PV QV C ( PV QV AV C A ( AV PV QV C)(PV QV AV C) A ( AV PV QV C)(PV QV A) A (AV PV Q) V C(PA QA A V (AAPA Q) V C(A A ( PA Q V (PA Q) V C(A A (P Q) V C(AA (P Q) Co(7)真
17、值表法:由真值表可知,公式法： (PQ(8)真值表法:由真值表可知,公式法： (PQP QP Q(P QP Q0 01000 11001 01001 1011P QA Q)(PV Q)P QP QP Q(P Q :P Q0 01000 10111 00111 1011(P Q(P Q P Q(PV Q)(PA Q) P Q(1)若AV CBV C,则AB。若AA CBA C,则AB。若AB,则AB。若A CB C,则AB。若A CB C,则ABo解(1)不正确。例如，设有一赋值: A= T,B= F, C= T,贝U AV C BV C,但A B不成立。不正确。1例如，设有赋值宜：A= T,
18、B= 1-,C= F,则 AA c Ba C,但 AB不成立。正确。因:为 A B (AE) A ( BA (AV B) A (BV A (BA) A (A B)7.设A B C为任意的三个命题公式,试问下面的结论是否正确?A B,所以，若 A B,则A Bo(4)不正确。例如，设有一赋值:A= T,B= F, C= T,则 A C B C,B不成立。正确。因为，若 A C BC与B C等值。当A C与B C都为真时，A和C等值且B和C等值，从而 A和B等值，此时 A B;当A C与B C都为假时，A和C不等值且 B和C也不等值，从 而A和B等值，此时A Bo总之有，若A C B C,则A B
19、o8.试给出下列命题公式的对偶式：(1)( PA Q) V R。(2)T V (PA Q o(3)( PV Q) A Fo(4)(PA Q A ( PV Q o解(1)对偶式为(PV Q) A Ro(2)对偶式为FA (PV Q) o(3)对偶式为(PA Q) V To对偶式为 (PV Q V ( PA Q) o9.分别用真值表法、分析法和公式法证明下列蕴涵式：(1)(P Q P。(2)( P Q) Q PV Q(3)P Q P (PA Q) o(4)( P Q) A (Q F) (P R) o证明(1)真值表法：P QP Q(P QP0 01000 11001 00111 1101由真值表可
20、知， (P Q) P。分析法：若 (P Q)为真，则P Q为假，从而P为真，而Q为假故(P Q Po公式法：因为 (P Q) P ( PV Q V P T,所以(P Q Po(2)真值表法：PQP Q(P Q QPV Q00100011111001111111由真值表可知，(P Q Q PV Q分析法：若PV Q为假，都P和Q为假，于是P Q为真，从而(P Q) Q为假。故(P Q) Q PV Q公式法：因为(P Q Q) (PVQ ( ( PV Q V Q) V (PVQ(PV Q) A Q) V ( PV Q)(PA Q) V (QA Q) V (PV Q)(PV Q) V (PV Q所以
21、，(P Q Q PV Q(3)真值表法：P QPA QP QP (PA Q)0 00110 10111 00001 1111由真值表可知，P Q P (PA Q。分析法：若P (PA Q为假，则P为真且PA Q为假，于是P为真且Q为假，从而P Q为假。故P Q P (P A Q o公式法：因为(P Q) (P (PA Q)(PV Q) V (PV (PA Q(PAQ) V (PV (PA Q)(PAQ) V (PV Q(PAQ) V(PA Q)T所以，P Q P (PA Q o(4)真值表法：P Q RP QQ R(P Q A (Q F)P R0 0 011110 0 111110 1 010
22、010 1 111111 0 001001 0 101011 1 010001 1 11111由真值表可知，(P Q A (Q R) (PF) o分析法：若P R为假，则P为真而R为假。当Q为真时，Q R为假；当Q为假时，P Q为假。从而 不管Q取什么值，都有(P Q A (Q R)为假。故(P Q A (Q F) (P R)。公式法：因为(PC) A (Q R) (PF) ( PV Q A ( QV F) V ( PV F)(PA Q) V (QA R V PV R(PA Q) V ( QV PV R A ( RV PV R)(PA Q) V (QV PV R)(PV QV PV R A (
23、 QV QV PV R)T所以，(P Q A (Q & (PR o10.将下列命题公式化成与之等价的仅含联结词 或 的公式：(1)PA (Q F) o(2)( P (QA R) V PoPA Q(P Q)(P Q(P QPV Q(PAQ PQ (P(PV P)P PP V Q(P Q(P Q)(P Q)P A QP Q(P P)(Q Q所以(1) PA (QF) PA (QV R)P(Pa P)p PP a ( Q(P P) (Q Q)Q) (R R)PA (QR)P A ( Q Q)(P ( Q Q)PA ( QV RQ Q) (R RQ Q) (R R) (P ( Q Q) ( Q Q)(R R)PA ( Q)P(Q)P R)(2)( PP A ( Q Q) P R) ( Q Q) P R)(P P) ( Q QP R ( Q Q)P 电(QQ)P R ( Q(QA R) V P ( PV (QA R) V PQP R)(P P) V (Q R)(Q R) V P(P P) V (Q R)(Q R) V P(P P) (P P)(Q R) (Q R) ( Q R)(Q R) vp(p P) ( p P) ( Q R)(Q R) ( Q R) (Q R) ( p P)(PP)(QR) (QR)
