《离散数学第1章习题答案》由会员分享，可在线阅读，更多相关《离散数学第1章习题答案（23页珍藏版）》请在金锄头文库上搜索。
1、第 1 章 命题逻辑1#include#include#include#define MAX_STACK_SIZE 100 typedef int ElemType;typedef structElemType dataMAX_STACK_SIZE;int top; Stack;void InitStack(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; i
2、nt 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-dataS-top;S-top-;return 1;void conversion(int N)int e;Stack *S=(Stack*)malloc(sizeof(Stack);InitStack(S); while(N)第 1 章 命题逻辑2Push(S,N%2); N=N/2;while(!Empty(S)Pop(S,&e);printf(%d ,e
3、);void main() int n;printf(请输入待转换的值n：n);scanf (%d,&n);conversion(n);习题1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？(1)离散数学是计算机专业的一门必修课。(2)李梅能歌善舞。(3)这朵花真美丽！(4)。(5)只要我有时间，我就来看你。(6)x。(7)尽管他有病，但他仍坚持工作。(8)太阳系外有宇宙人。(9)小王和小张是同桌。(10)不存在最大的素数。解 在上述 10 个句子中，(3)是感叹句，因此它不是命题。(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。其余语句都是可判断真假的陈述句，
4、所以都是命题。其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。2.判断下列各式是否是命题公式，为什么？(1)(P(PQ)。(2)(PQ)(QP)。(3)(PQ)(QP)。(4)(QRS) 。(5)(PQR)S。(6)(R(QR)(PQ)。解 (1)是命题公式。(2)不是命题公式，因为括号不配对。第 1 章 命题逻辑3(3)是命题公式。(4)是命题公式。(5)不是命题公式，因为 QR 没有意义。(6)不是命题公式，因为 R(QR)(PQ) 没有意义。3.将下列命题符号化：(1)我们不能既划船又跑步。(2)我去新华书店，仅当我有时间。(3
5、)如果天下雨，我就不去新华书店。(4)除非天不下雨，我将去新华书店。(5)张明或王平都可以做这件事。(6)“2 或 4 是素数，这是不对的”是不对的。(7)只有休息好，才能工作好。(8)只要努力学习，成绩就会好的。(9)大雁北回，春天来了。(10)小张是山东人或河北人。解 (1)符号化为(PQ)，其中，P：我们划船，Q：我们跑步。(2)符号化为 QR，其中，R ：我有时间，Q：我去新华书店。(3)符号化为 PQ，其中，P：天下雨，Q ：我去新华书店。(4)符号化为PQ，其中，P：天下雨，Q ：我去新华书店。(5)符号化为 PQ，其中，P：张明可以做这件事，Q：王平可以做这件事。(6)符号化为(
6、 (PQ )，“2 或 4 是素数，这是不对的”是不对的，其中，P ：2 是素数，Q：4 是素数，。(7)符号化为 QP，其中，P ：休息好，Q：工作好。(8)符号化为 PQ，其中，P ：努力学习，Q：成绩就会好的。(9)符号化为 PQ，其中，P：大雁北回，Q：春天来了。(10)符号化为 PQ，其中， P：小张是山东人，Q：小张是河北人。4.构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？(1)(P Q)。(2)P(Q R)。(3)(PQ)(P Q)。(4)P(QP)。解 (1)P Q P Q (PQ)0 0 0 1 1001第 1 章 命题逻辑41 0 1 11100
7、由真值表可知，公式(PQ)的成真赋值为：01，成假赋值为 00、10、11。(2) P Q R QR P(QR)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10111011100000111由真值表可知，公式 P(QR)的成真赋值为：101、110、111，成假赋值为000、001、010、011、100。(3)P Q ( P Q) PQ (PQ)( PQ )0 0 0 1 1 0 1 1100010001111由真值表可知，公式(PQ)(PQ)的成真赋值为： 00、01、10、11，没有成假赋值。(4)P Q QP P(QP)0 0 0 1 1 0 1 11
8、0111011由真值表可知，公式P(Q P)的成真赋值为：00、10、11，成假赋值为：01。5.分别用真值表法和公式法判断下列命题公式的类型：(1)(PQ )(PQ )。(2)(PQ )(PQ )。(3)(PQ)(QR)(R PQ)。(4)(PQ R)(PRQ)。(5)(QP)( PQ)。(6)(PQ)(PQ)。(7)(PQ )(PQ)。解 (1)真值表法：P Q PQ P Q (PQ)(PQ)0 0 0 1 010010第 1 章 命题逻辑51 0 1 1110101由真值表可知，公式(PQ) (PQ)为可满足式。公式法：因为(PQ)(PQ)(PQ)(PQ)(PQ)(P Q)，所以，公式(
9、PQ )(PQ )为可满足式。(2)真值表法：P Q P Q P Q (PQ)(PQ)0 0 0 1 1 0 1 1000101111111由真值表可知，公式(PQ) (PQ)为重言式。公式法：因为(PQ)(PQ)(PQ)(PQ)PQP QT，所以，公式(PQ)(PQ )为重言式。(3)真值表法：P Q R PQ QR RP Q (PQ)(Q R )(RPQ)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111110011101110111111110100000000由真值表可知，公式(PQ)(QR)(R PQ)为矛盾式。公式法：因为(PQ)(QR)(R PQ
10、)(P Q)QR(R PQ)F，所以，公式(P Q)(QR)(R PQ)为矛盾式。(4)真值表法：P Q R PQR PRQ (PQR )(PRQ)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111111010000001000000010由真值表可知，公式(PQ R)(PRQ)为可满足式。公式法：因为(PQR)(PRQ)( PQ)R)(P RQ)( PQR)(PRQ)( PQR)所以，公式(PQR)(PRQ)为可满足式。(5)真值表法：P Q QP PQ (QP)(P Q)0 0 1 0 0第 1 章 命题逻辑60 1 1 0 1 1011100000由真
11、值表可知，公式(QP)( PQ )为可矛盾式。公式法：因为(QP)(P Q)(QP)(P Q )(QP)(P Q) F，所以，公式为可矛盾式。(6)真值表法：P Q PQ (PQ) (PQ)(PQ)0 0 0 1 1 0 1 1011001101111由真值表可知，公式(PQ)(PQ)为永真式。公式法：因为(PQ)(PQ)(P Q)(QP )(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)T所以，公式(PQ)(PQ)为永真式。(7)真值表法：P Q PQ P Q (P Q)(PQ )0 0 0 1 1 0 1 1000101110000由真值表可知，公式(PQ)(PQ)为矛盾式。公式法：因为(
12、PQ)(PQ)(PQ)(PQ) F，所以，公式(P Q)(PQ)为矛盾式。6.分别用真值表法和公式法证明下列各等价式：(1)(PQ )PPQ。(2)(PQ)(PQ)P。(3)(PQ )PPQ。(4)P(QR )(PQ)( PR)。(5)(PQ)( RQ)(P R)Q)。(6)(PQ AC)(APQC )(A(PQ )C。(7)(PQ)PQ。(8)(PQ)PQ。证明 (1)真值表法：P Q PQ (P Q)P PQ0 0 0 1 1 0 1 1011101000100第 1 章 命题逻辑7由真值表可知，(PQ)PPQ。公式法：(PQ)P(PP)(QP)PQ。(2)真值表法：P Q PQ (PQ
13、)(P Q ) P0 0 0 1 1 0 1 1110011001100由真值表可知，(PQ)(PQ)P。公式法：(PQ)(PQ)(PQ)(PQ)P(QQ)P。(3)真值表法：P Q P Q (PQ)P PQ0 0 0 1 1 0 1 1000111011101由真值表可知，(PQ)PPQ。公式法：(PQ)P(PP)(QP)PQ。(4)真值表法：P Q R PQ PR (PQ)(P R) P( QR)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111110011111101011111000111110001由真值表可知，P(QR)(P Q)(PR)。公式法：P(QR)P(QR)(PQ)(PR)(PQ)(P R)。(5)真值表法：P Q R PQ RQ (PQ)(RQ) ( PR)Q0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111110011101110111011001110110011由真值表可知，(PQ)(R Q)(PR)Q)。公式法：(PQ)(RQ )(PQ)(RQ)(PR )Q(PR)Q(PR)Q)。(6)真值表法：第 1 章 命题逻辑8P
