习题1.1
1.下列句子中,哪些是命题?哪些不是命题?如果是命题,指出它的真值。
⑴中国有四大发明。
⑵计算机有空吗?
⑶不存在最大素数。
⑷21+3<5。
⑸老王是山东人或河北人。
⑹2与3都是偶数。
⑺小李在宿舍里。
⑻这朵玫瑰花多美丽呀!
⑼请勿随地吐痰!
⑽圆的面积等于半径的平方乘以 。
⑾只有6是偶数,3才能是2的倍数。
⑿雪是黑色的当且仅当太阳从东方升起。
⒀如果天下大雨,他就乘班车上班。
解:⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题,其中⑴⑶⑽⑾是真命题,⑷⑹⑿是假命题,⑸⑺⒀的真值目前无法确定;⑵⑻⑼不是命题。
2. 将下列复合命题分成若干原子命题。
⑴李辛与李末是兄弟。
⑵因为天气冷,所以我穿了羽绒服。
⑶天正在下雨或湿度很高。
⑷刘英与李进上山。
⑸王强与刘威都学过法语。
⑹如果你不看电影,那么我也不看电影。
⑺我既不看电视也不外出,我在睡觉。
⑻除非天下大雨,否则他不乘班车上班。
解:⑴本命题为原子命题;
⑵p:天气冷;q:我穿羽绒服;
⑶p:天在下雨;q:湿度很高;
⑷p:刘英上山;q:李进上山;
⑸p:王强学过法语;q:刘威学过法语;
⑹p:你看电影;q:我看电影;
⑺p:我看电视;q:我外出;r:我睡觉;
⑻p:天下大雨;q:他乘班车上班。
3. 将下列命题符号化。
⑴他一面吃饭,一面听音乐。
⑵3是素数或2是素数。
⑶若地球上没有树木,则人类不能生存。
⑷8是偶数的充分必要条件是8能被3整除。
⑸停机的原因在于语法错误或程序错误。
⑹四边形ABCD是平行四边形当且仅当它的对边平行。
⑺如果a和b是偶数,则a+b是偶数。
解:⑴p:他吃饭;q:他听音乐;原命题符号化为:p∧q
⑵p:3是素数;q:2是素数;原命题符号化为:p∨q
⑶p:地球上有树木;q:人类能生存;原命题符号化为:?p→?q
⑷p:8是偶数;q:8能被3整除;原命题符号化为:p?q
⑸p:停机;q:语法错误;r:程序错误;原命题符号化为:q∨r→p
⑹p:四边形ABCD是平行四边形;q:四边形ABCD的对边平行;原命题符号化为:p?q。
⑺p:a是偶数;q:b是偶数;r:a+b是偶数;原命题符号化为:p∧q→r
4. 将下列命题符号化,并指出各复合命题的真值。
⑴如果3+3=6,则雪是白的。
⑵如果3+3≠6,则雪是白的。
⑶如果3+3=6,则雪不是白的。
⑷如果3+3≠6,则雪不是白的。
⑸3是无理数当且仅当加拿大位于亚洲。
⑹2+3=5的充要条件是3是无理数。(假定是10进制)
⑺若两圆O1,O2的面积相等,则它们的半径相等,反之亦然。
⑻当王小红心情愉快时,她就唱歌,反之,当她唱歌时,一定心情愉快。
解:设p:3+3=6。q:雪是白的。
⑴原命题符号化为:p→q;该命题是真命题。
⑵原命题符号化为:?p→q;该命题是真命题。
⑶原命题符号化为:p→?q;该命题是假命题。
⑷原命题符号化为:?p→?q;该命题是真命题。
⑸p:3是无理数;q:加拿大位于亚洲;原命题符号化为:p?q;该命题是假命题。
⑹p:2+3=5;q:3是无理数;原命题符号化为:p?q;该命题是真命题。
⑺p:两圆O1,O2的面积相等;q:两圆O1,O2的半径相等;原命题符号化为:p?q;该命题是真命题。
⑻p:王小红心情愉快;q:王小红唱歌;原命题符号化为:p?q;该命题是真命题。
习题1.2
1.判断下列公式哪些是合式公式,哪些不是合式公式。
⑴(p∧q→r)
⑵(p∧(q→r)
⑶((?p→q)?(r∨s))
⑷(p∧q→rs)
⑸((p→(q→r))→((q→p)?q∨r))。
解:⑴⑶⑸是合式公式;⑵⑷不是合式公式。
2.设p:天下雪。
q:我将进城。
r:我有时间。
将下列命题符号化。
⑴天没有下雪,我也没有进城。
⑵如果我有时间,我将进城。
⑶如果天不下雪而我又有时间的话,我将进城。
解:⑴?p∧?q
⑵r→q
⑶?p∧r→q
3.设p、q、r所表示的命题与上题相同,试把下列公式译成自然语言。
⑴r∧q
⑵? (r∨q)
⑶q? (r∧? p)
⑷(q→r)∧(r→q)
解:⑴我有时间并且我将进城。
⑵我没有时间并且我也没有进城。
⑶我进城,当且仅当我有时间并且天不下雪。
⑷如果我有时间,那么我将进城,反之亦然。
4. 试把原子命题表示为p、q、r等,将下列命题符号化。
⑴或者你没有给我写信,或者它在途中丢失了。
⑵如果张三和李四都不去,他就去。
⑶我们不能既划船又跑步。
⑷如果你来了,那末他唱不唱歌将看你是否伴奏而定。
解:⑴p:你给我写信;q:信在途中丢失;原命题符号化为:(?p∧? q)∨(p∧q)。
⑵p:张三去;q:李四去;r:他去;原命题符号化为:?p∧?q→r。
⑶p:我们划船;q:我们跑步;原命题符号化为:?(p∧q)。
⑷p:你来了;q:他唱歌;r:你伴奏;原命题符号化为:p→(q?r)。
5. 用符号形式写出下列命题。
⑴假如上午不下雨,我去看电影,否则就在家里读书或看报。
⑵我今天进城,除非下雨。
⑶仅当你走,我将留下。
解:⑴p:上午下雨;q:我去看电影;r:我在家读书;s:我在家看报;原命题符号化为:(?p→q)∧(p→r∨s)。
⑵p:我今天进城;q:天下雨;原命题符号化为:?q→p。
⑶p:你走;q:我留下;原命题符号化为:q→p。
习题1.3
1.设A、B、C是任意命题公式,证明:
⑴A?A
⑵若A?B,则B?A
⑶若A?B,B?C,则A?C
证明:⑴由双条件的定义可知A?A是一个永真式,由等价式的定义可知A?A成立。
⑵因为A?B,由等价的定义可知A?B是一个永真式,再由双条件的定义可知B?A 也是一个永真式,所以,B?A成立。
⑶对A、B、C的任一赋值,因为A?B,则A?B是永真式,即A与B具有相同的真值,又因为B?C,则B?C是永真式,即B与C也具有相同的真值,所以A与C也具有相同的真值;即A?C成立。
2.设A、B、C是任意命题公式,
⑴若A∨C?B∨C, A?B一定成立吗?
⑵若A∧C?B∧C, A?B一定成立吗?
⑶若?A??B,A?B一定成立吗?
解:⑴不一定有A?B。若A为真,B为假,C为真,则A∨C?B∨C成立,但A?B 不成立。
⑵不一定有A?B。若A为真,B为假,C为假,则A∧C?B∧C成立,但A?B不成立。
⑶一定有A?B。
3.构造下列命题公式的真值表,并求成真赋值和成假赋值。
⑴q∧(p→q)→p
⑵p→(q∨r)
⑶(p∨q)?(q∨p)
⑷(p∧?q)∨(r∧q)→r
⑸((?p→(p∧?q))→r)∨(q∧?r)
解:⑴q∧(p→q)→p的真值表如表1.24所示。
表1.24
使得公式q∧(p→q)→p成真的赋值是:00,10,11,使得公式q∧(p→q)→p成假的赋值是:01。
⑵p→(q∨r)的真值表如表1.25所示。
表1.25
使得公式p→(q∨r)成真的赋值是:000,001,010,011,101,110,111,使得公式p→(q∨r)成假的赋值是:100。
⑶(p∨q)?(q∨p)的真值表如表1.26所示。
表1.26
所有的赋值均使得公式(p∨q)?(q∨p)成真,即(p∨q)?(q∨p)是一个永真式。
⑷(p∧?q)∨(r∧q)→r的真值表如表1.27所示。
表1.27
111,
使得公式(p∧?q)∨(r∧q)→r成假的赋值是:100。
⑸((?p→(p∧?q))→r)∨(q∧?r)的真值表如表1.28所示。
表1.28
使得公式((?p→(p∧?q))→r)∨(q∧?r)成真的赋值是:000,001,010,011,101,110,111,使得公式((?p→(p∧?q))→r)∨(q∧?r)成假的赋值是:100。
4.用真值表证明下列等价式:
⑴?(p→q)?p∧?q
证明:证明?(p→q)?p∧?q的真值表如表1.29所示。
表1.29
由上表可见:?(p→q)和p∧?q的真值表完全相同,所以?(p→q)?p∧?q。
⑵p→q??q→?p
证明:证明p→q??q→?p的真值表如表1.30所示。
表1.30
由上表可见:p→q和?q→?p的真值表完全相同,所以p→q??q→?p。
⑶?(p?q)?p??q
证明:证明?(p?q)和p??q的真值表如表1.31所示。
表1.31
由上表可见:?(p?q)和p??q的真值表完全相同,所以?(p?q)?p??q。
⑷p→(q→r)?(p∧q)→r
证明:证明p→(q→r)和(p∧q)→r的真值表如表1.32所示。
表1.32
由上表可见:p→(q→r)?(p∧q)→r。
⑸p→(q→p)? ?p→(p→?q)
证明:证明p→(q→p)和?p→(p→?q)的真值表如表1.33所示。
表1.33
由上表可见:p→(q→p)和?p→(p→?q)的真值表完全相同,且都是永真式,所以p→(q →p)??p→(p→?q)。
⑹?(p?q)?(p∨q)∧?(p∧q)
证明:证明?(p?q)和(p∨q)∧?(p∧q)的真值表如表1.34所示。
表1.34
由上表可见:?(p?q)和(p∨q)∧?(p∧q)的真值表完全相同,所以?(p?q)?(p∨q)∧?(p∧q)
⑺?(p?q)?(p∧?q)∨(?p∧q)
证明:证明?(p?q)和(p∧?q)∨(?p∧q)的真值表如表1.35所示。
表1.35
由上表可见:?(p?q)和(p∧?q)∨(?p∧q)的真值表完全相同,所以?(p?q)?(p∧?q)∨(?p∧q)。
⑻p→(q∨r)?(p∧?q)→r
证明:证明p→(q∨r)和(p∧?q)→r的真值表如表1.36所示。
表1.36
由上表可见:p→(q∨r)和(p∧?q)→r的真值表完全相同,所以p→(q∨r)?(p∧?q)→r。
5. 用等价演算证明习题4中的等价式。
⑴?(p→q)
??(?p∨q) (条件等价式) ?p∧?q (德·摩根律)
⑵?q→?p
???q∨?p (条件等价式) ?q∨?p (双重否定律)
??p∨q (交换律)
? p→q (条件等价式)
⑶?(p?q)
??((p→q)∧(q→p)) (双条件等价式) ??((?p∨q)∧(?q∨p)) (条件等价式) ?(p∧?q)∨(q∧?p) (德·摩根律) ?((p∧?q)∨q)∧((p∧?q)∨?p) (分配律)
?(p∨q)∧(?q∨?p) (分配律)
?(?p∨?q)∧(q∨p) (交换律)
?(p→?q)∧(?q→p) (条件等价式) ?p??q (双条件等价式) ⑷p→(q→r)
??p∨(?q∨r) (条件等价式)
?(?p∨?q)∨r (结合律)
??(p∧q)∨r (德·摩根律)
?(p∧q)→r (条件等价式) ⑸p→(q→p)
??p∨(?q∨p) (条件等价式) ?T
?p→(p→?q)
?p∨(?p∨?q) (条件等价式) ?T
所以p→(q→p)? ?p→(p→?q)
⑹?(p?q)
??((p∧q)∨(?p∧?q)) (例1.17)
?(p∨q)∧(?p∨?q) (德·摩根律) ?(p∨q)∧?(p∧q) (德·摩根律) 所以?(p?q)?(p∨q)∧?(p∧q)
⑺?(p?q)
??((p→q)∧(q→p)) (双条件等价式) ??((?p∨q)∧(?q∨p)) (条件等价式) ?(p∧?q)∨(?p∧q) (德·摩根律)
⑻p→(q∨r)
??p∨(q∨r) (条件等价式)
?(?p∨q)∨r (结合律)
??(p∧?q)∨r (德·摩根律)
?(p∧?q)→r (条件等价式)
6.试用真值表证明下列命题定律。
⑴结合律:(p∨q)∨r?p∨(q∨r),(p∧q)∧r?p∧(q∧r)
证明:证明结合律的真值表如表1.37和表1.38所示。
表1.37
表1.38
由真值表可知结合律成立。
⑵分配律:p∧(q∨r)?(p∧q)∨(p∧r),
p∨(q∧r)?(p∨q)∧(p∨r)
证明:证明合取对析取的分配律的真值表如表1.39所示,析取对合取的的分配律的真值表如表1.40所示。
表1.39
表1.40
由真值表可知分配律成立。
⑶假言易位式:p→q??q→?p
证明:证明假言易位式的真值表如表1.41所示。
表1.41
由真值表可知假言易位律成立。
⑷双条件否定等价式:p?q??p??q
证明:证明双条件否定的真值表如表1.42所示。
表1.42
由真值表可知双条件否定等价式成立。
习题 1.4
1.用真值表或等价演算判断下列命题公式的类型。
⑴(p∨?q)→q
??(p∨?q)∨q (条件等价式)
?(?p∧q)∨q (德·摩根律)
?q (可满足式)(吸收律)
⑵?(p→q)∧q
??(?p∨q)∧q (条件等价式)
?(p∧?q)∧q (德·摩根律)
?F(永假式)(结合律、矛盾律)
⑶(p→q)∧p→q
?(?p∨q)∧p→q (条件等价式)
?(?p∧p)∨(q∧p)→q (分配律)
?(q∧p)→q (同一律、矛盾律)
??(q∧p)∨q (条件等价式)
?(?q∨?p)∨q (德·摩根律)
?T(永真式) (零律、排中律)
⑷(p→q)∧q
?(?p∨q)∧q (条件等价式)
?q(可满足式)(吸收律)
⑸(p→q)→(?q→?p)
?(p→q)→(p→q) (假言易位式)
?T(永真式)
⑹((p→q)∧(q→r))→(p→r)
??((?p∨q)∧(?q∨r))∨(?p∨r) (条件等价式)
?(p∧?q)∨(q∧?r)∨(?p∨r) (德·摩根律)
?(p∧?q)∨((?p∨q∨r)∧(?p∨?r∨r)) (分配律)
?(p∧?q)∨(?p∨q∨r) (同一律、排中律、零律)?(?p∨q∨r∨p)∧(?p∨q∨r∨?q) (分配律)
?T(永真式)
⑺?p→(p→q)
? p∨(?p∨q) (条件等价式)
?T(永真式)
⑻p→(p∨q∨r)
??p∨(p∨q∨r) (条件等价式)
?T(永真式)
2.用真值表证明下列命题公式是重言式。
⑴(p∧(p→q))→q
(p∧(p→q))→q的真值表如表1.43所示。由表1.43可以看出(p∧(p→q))→q是重言式。
表1.43
⑵(?q∧(p→q))→?p
(?q∧(p→q))→?p的真值表如表1.44所示。由表1.44可以看出(?q∧(p→q))→?p是重言式。
表1.44
⑶(?p∧(p∨q))→q
(?p∧(p∨q))→q的真值表如表1.45所示。由表1.45可以看出(?p∧(p∨q))→q是重言式。
表1.45
⑷((p→q)∧(q→r))→(p→r)
((p→q)∧(q→r))→(p→r)的真值表如表1.46所示。由表1.46可以看出((p→q)∧(q→r))→(p→r)是重言式。
表1.46
⑸((p∨q)∧(p→r)∧(q→r))→r
((p∨q)∧(p→r)∧(q→r))→r的真值表如表1.47所示。由表1.47可以看出((p∨q)∧(p →r)∧(q→r))→r是重言式。
表1.47
⑹((p→q)∧(r→s))→((p∧r)→(q∧s))
((p→q)∧(r→s))→((p∧r)→(q∧s))的真值表如表1.48所示。由表1.48可以看出((p→q)∧(r→s))→((p∧r)→(q∧s))是重言式。
表1.48
⑺((p?q)∧(q?r))→(p?r)
((p?q)∧(q?r))→(p?r)的真值表如表1.49所示。由表1.49可以看出((p?q)∧(q?r))→(p?r)是重言式。
表1.49
3.用等价演算证明题2中的命题公式是重言式。
⑴(p∧(p→q))→q
??(p∧(?p∨q))∨q
?(?p∨(p∧?q))∨q
?((?p∨p)∧(?p∨?q))∨q
?(?p∨?q)∨q
?T
⑵(?q∧(p→q))→?p
?(?q∧(?p∨q))→?p
??(?q∧(?p∨q))∨?p
?(q∨(p∧?q))∨?p
?(?p∨q)∨(p∧?q)
??(p∧?q)∨(p∧?q)
?T
⑶(?p∧(p∨q))→q
?(?p∧q)→q
??(?p∧q)∨q
?p∨?q∨q
?T
⑷((p→q)∧(q→r))→(p→r)
??((?p∨q)∧(?q∨r))∨(?p∨r)
?(p∧?q)∨(q∧?r)∨(?p∨r)
?(p∧?q)∨((?p∨q∨r)∧(?p∨?r∨r))
?(p∧?q)∨(?p∨q∨r)
?(?p∨q∨r∨p)∧(?p∨q∨r∨?q)
?T
⑸((p∨q)∧(p→r)∧(q→r))→r
?((p∨q)∧(?p∨r)∧(?q∨r))→r
?((p∨q)∧(?(p∨q)∨r))→r
?((p∨q)∧r)→r
??((p∨q)∧r)∨r
??(p∨q)∨?r∨r
?T
⑹((p→q)∧(r→s))→((p∧r)→(q∧s))
??((?p∨q)∧(?r∨s))∨(?(p∧r)∨(q∧s))
?((p∧?q)∨(r∧?s))∨((?p∨?r)∨(q∧s))
?((p∧?q)∨(r∧?s))∨((?p∨?r∨q)∧(?p∨?r∨s))
?((p∧?q)∨(r∧?s)∨(?p∨?r∨q))∧((p∧?q)∨(r∧?s)∨(?p∨?r∨s)) ?((r∧?s)∨((?p∨?r∨q∨p)∧(?p∨?r∨q∨?q)))∧((r∧?s)∨
((?p∨?r∨s∨p)∧(?p∨?r∨s∨?q)))
?((r∧?s)∨T)∧((r∧?s)∨(?p∨?q∨?r∨s))
?(r∧?s)∨(?p∨?q∨?r∨s)
?(?p∨?q∨?r∨s∨r)∧(?p∨?q∨?r∨s∨?s)
?T
⑺((p?q)∧(q?r))→(p?r)
?((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))→(p?r)
??((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))∨(p∧r)∨(?p∧?r)
?(p∧?q)∨(p∧r)∨(r∧?q)∨(q∧?r)∨(q∧?p)∨(?p∧?r)
?((p∧(?q∨r))∨?(?q∨r))∨(r∧?q)∨(q∧?p)∨(?p∧?r)
?((?(?q∨r)∨(?q∨r))∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?(T∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r)
?p∨(q∧?r)∨(r∧?q)∨(q∧?p)∨(?p∧?r)
?p∨(q∧?r)∨((q∧?p)∨(?p∧?r))∨(r∧?q)
?p∨(q∧?r)∨((?p∧(q∨?r))∨?(q∨?r))
?p∨(q∧?r)∨?p∨(?q∧r)
?T
4.证明下列等价式:
⑴((p→r)∧(q→r))
?(?p∨r)∧(?q∨r)
?(?p∧?q)∨r
??(p∨q)∨r
?(p∨q)→r
⑵(p→q)∧(p→?q)
?(?p∨q)∧(?p∨?q)
??p∨(q∧?q)
??p∨F
??p
⑶p∧(p→q)
?p∧(?p∨q)
?(p∧?p)∨(p∧q)
?F∨(p∧q)
?p∧q
习题 1.5
1.求下列命题公式的析取范式。
⑴(p∧?q)→r
??(p∧?q)∨r
??p∨q∨r
⑵?(p→q)→r
???(?p∨q)∨r
?(?p∨q)∨r
??p∨q∨r
⑶p∧(p→q)
? p∧(?p∨q)
?(p∧?p)∨(p∧q)
? p∧q
⑷(p→q)∧(q∨r)
?(?p∨q)∧(q∨r)
? q∨(?p∧r)
⑸?(p∨?q)∧(r→t)
?(?p∧q)∧(?r∨t)
?(?p∧q∧?r)∨(?p∧q∧t)
2. 求下列命题公式的合取范式。
⑴?(p→q)
??(?p∨q)
?p∧?q
⑵?q∨(p∧q∧r)
?(?q∨p)∧(?q∨q)∧(?q∨r)
?(?q∨p)∧(?q∨r)
⑶(?p∧q)∨(p∧?q)
?((?p∧q)∨p)∧((?p∧q)∨?q))
?(?p∨p)∧(q∨p)∧(?p∨?q)∧(q∨?q)
?(p∨q)∧(?p∨?q)
⑷?(p?q)
??((p∧q)∨(?p∧?q))
?(?p∨?q)∧(p∨q)
⑸?(p→q)→r
???(?p∨q)∨r
?(?p∨q)∨r
??p∨q∨r
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答:(1),(4) 2、下列公式中哪些就是永真式?( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答:(2),(3),(4) 3、设有下列公式,请问哪几个就是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答:(2),(3),(4),(5),(6) 4、公式?x((A(x)→B(y,x))∧ ?z C(y,z))→D(x)中,自由变元就是( ),约束变元就是( )。 答:x,y, x,z 5、判断下列语句就是不就是命题。若就是,给出命题的真值。( ) (1) 北京就是中华人民共与国的首都。 (2) 陕西师大就是一座工厂。 (3) 您喜欢唱歌不? (4) 若7+8>18,则三角形有4条边。 (5) 前进! (6) 给我一杯水吧! 答:(1) 就是,T (2) 就是,F (3) 不就是 (4) 就是,T (5) 不就是 (6) 不就是 6、命题“存在一些人就是大学生”的否定就是( ),而命题“所有的人都就是要死的”的否定就是( )。 答:所有人都不就是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义就是( )。 (1) ?x ?y(x+y=0) (2) ?y ?x(x+y=0) 答:(1)对任一整数x 存在整数 y 满足x+y=0(2)存在整数y 对任一整数x 满足x+y=0 9、设全体域D 就是正整数集合,确定下列命题的真值: (1) ?x ?y (xy=y) ( ) (2) ?x ?y(x+y=y) ( ) (3) ?x ?y(x+y=x) ( ) (4) ?x ?y(y=2x) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 就是奇数,Q(x):x 就是偶数,谓词公式 ?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2就是偶数或-3就是负数”的否定就是( )。 答:2不就是偶数且-3不就是负数。 12、永真式的否定就是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不? (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不? B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
《离散数学》考试题库及答案 一、 填空 10% (每小题 2分) 1、 若P ,Q 为二命题,Q P ?真值为1,当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元,A 的论域为D ,A (x )关于y 的自由的, 则 被称为全称量词消去规则,记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% (每小题 3分) 1、 下列各符号串,不是合式公式的有( )。 A 、R Q P ?∧∧)(; B 、)()((S R Q P ∧→→; C 、R Q P ∧∨∨; D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有( )。 A 、2是素数; B 、x+5 > 6; C 、地球外的星球上也有人; D 、这朵花多好看呀!。 3、 下列公式是重言式的有( )。 A 、)(Q P ??; B 、Q Q P →∧)(; C 、P P Q ∧→?)(; D 、P Q P ?→)( 4、 下列问题成立的有( )。 A 、 若C B C A ∨?∨,则B A ?; B 、若C B C A ∧?∧,则B A ?; C 、若B A ???,则B A ?; D 、若B A ?,则B A ???。 5、 命题逻辑演绎的CP 规则为( )。 A 、 在推演过程中可随便使用前提; B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果; C 、如果要演绎出的公式为C B →形式,那么将B 作为前提,设法演绎出C ;
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月19日前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值是 1 . 2.设P :他生病了,Q :他出差了.R :我同意他不参加学习. 则命题“如果他生病或出差了,我就同意他不参加学习”符号化的结果为 (PQ)R . 3.含有三个命题变项P ,Q ,R 的命题公式PQ 的主析取范式是 (PQR) (PQR) . 4.设P(x):x 是人,Q(x):x 去上课,则命题“有人去上课.” 可符号化为 (x)(P(x) →Q(x)) . 5.设个体域D ={a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) . 6.设个体域D ={1, 2, 3},A(x)为“x 大于3”,则谓词公式(x)A(x) 的真值为 . 7.谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 . 8.谓词命题公式(x)(P(x) Q(x) R(x ,y))中的约束变元为 X . 三、公式翻译题 1.请将语句“今天是天晴”翻译成命题公式. 1.解:设P :今天是天晴; 则 P . 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. 解:设P :小王去旅游,Q :小李去旅游, 则 PQ . 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. 解:设P:明天天下雪 。 Q:我去滑雪 则 P Q . 4.请将语句“他去旅游,仅当他有时间.”翻译成命题公式. 7.解:设 P :他去旅游,Q :他有时间, 则 P Q . 5.请将语句 “有人不去工作”翻译成谓词公式. 11.解:设P(x):x 是人,Q(x):x 去工作,
《离散数学》题库与答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?( A ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答:在第三章里面有公式(1)是附加律,(4)可以由第二章的蕴含等值式求出(注意与吸收律区别) 2、下列公式中哪些是永真式?( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答:(2),(3),(4)可用蕴含等值式证明 3、设有下列公式,请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答:(2)是第三章的化简律,(3)类似附加律,(4)是假言推理,(3),(5),(6)都可以用蕴含等值式来证明出是永真蕴含式 4、公式x((A(x)B(y,x))z C(y,z))D(x)中,自由变元是( ),约束变元是( )。 答:x,y, x,z(考察定义在公式x A和x A中,称x为指导变元,A为量词的辖域。在x A和x A的辖域中,x的所有出现都称为约束出现,即称x为约束变元,A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y,x)和z C(y,z)中y为自由变元,x和z为约束变元,在D(x)中x为自由变元) 5、判断下列语句是不是命题。若是,给出命题的真值。( )
(1)北京是中华人民共和国的首都。(2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗?(4) 若7+8>18,则三角形有4条边。 (5) 前进!(6) 给我一杯水吧! 答:(1)是,T (2)是,F (3)不是(4)是,T (5)不是(6)不是(命题必须满足是陈述句,不能是疑问句或者祈使句。) 6、命题“存在一些人是大学生”的否定是( ),而命题“所有的人都是要死的”的否定是( )。 答:所有人都不是大学生,有些人不会死(命题的否定就是把命题前提中的量词“换成存在,换成”,然后将命题的结论否定,“且变或或变且”) 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校(2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校答:(1)P ?(注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的)(2)Q P→ ? P? ?(4)Q P? →(3)Q 8、设个体域为整数集,则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答:(1)对任一整数x存在整数y满足x+y=0 (2)存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合,确定下列命题的真值: (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答:(1)F (反证法:假若存在,则(x- 1)*y=0 对所有的x都成立,显然这个与前提条件相矛盾) (2)F (同理)(3)F (同理)(4)T(对任一整数x存在整数y满足条件y=2x 很明显是正确的)
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈>∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
第一章习题 1.1判断下列语句是否为命题,若是命题请指出是简单命题还是复合命题。(1)2是无理数。 (2)5能被2整除。 (3)现在开会吗? (4)x+5>0 (5)这朵花真是好看! (6)2是素数当且仅当三角形有三条边。 (7)雪是黑色的当且仅当太阳是从东方升起。 (8)2000年10月1日天气晴好。 (9)太阳系以外的星球上有生物。 (10)小李在宿舍里。 (11)全体起立。 (12)4是2的倍数或是3的倍数。 (13)4是偶数且是奇数。 (14)李明和王华是同学。 (15)蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化,并讨论他们的真值。 1.3判断下列各命题的真值。 (1)若2+2=4,则3+3=6; (2)若2+2=4,则3+3≠6; (3)若2+2≠=4,则3+3=6; (4)若2+2≠=4,则3+3≠=6; (5)2+2=4,当且仅当3+3=6; (6)2+2=4,当且仅当3+3≠6; (7)2+2≠4,当且仅当3+3=6; (8)2+2≠4,当且仅当3+3≠6; 1.4将下列命题符号化,并讨论其真值。 (1)如果今天是1号,则明天是2号; (2)如果今天是1号,则明天是3号; 1.5将下列命题符号化。 (1)2是偶数不是素数; (2)小王不但聪明而且用功; (3)虽然天气冷。老王还是来了; (4)他一边吃饭,一边看电视; (5)如果天下大雨,他就乘公交汽车来; (6)只有天下大雨,他才乘公交汽车来; (7)除非天下大雨,否则他不乘公交汽车来; (8)不经一事,不长一智; 1.5设p,q的真值为0 ,r,s的真值为1,求下列命题公式的真值。(1)p∨(q∧r);
本科高等数学离散数学试题及答案 一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=____________________; ρ(A) - ρ(B)=__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G=?(P→Q)∧R,则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为__________,分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B=_________________________; A?B=_________________________;A-B=_____________________ . 7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有__________________________,_____________________________, __________________________. 9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B,|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A={2, 3, 4, 5, 6},R是A上的整除,则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树,则G中增加_________条边才能把G变成完全图。
第一章 定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A(吸收律) 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值是 1或T . 2.设P :他生病了,Q :他出差了.R :我同意他不参加学习. 则命题“如 果他生病或出差了,我就同意他不参加学习”符号化的结果为 (P ∨Q )→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) . 4.设P (x ):x 是人,Q (x ):x 去上课,则命题“有人去上课.” 可符号化为 ?x(P(x) ∧Q(x)) . 5.设个体域D ={a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) . 6.设个体域D ={1, 2, 3},A (x )为“x 大于3”,则谓词公式(?x )A (x ) 的真值为 0(F) . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天是天晴”翻译成命题公式. 设P :今天是晴天。 姓 名: 学 号: 得 分: 教师签名:
《离散数学》期末复习题 一、填空题(每空2分,共20分) 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c},B={a,b,c,d,e},则A?B= 。 4、集合A={1,2,3,4},B={1,3,5,7,9},则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3},A上的二元运算定义为:a* b = a和b两者的最大值,则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法,是加法的幂等元, 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
离散数学试题及答案 一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=____________________; ρ(A) - ρ(B)=__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G=?(P→Q)∧R,则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为__________,分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B=_________________________; A?B =_________________________;A-B=_____________________ . 7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有__________________________, _____________________________, __________________________. 9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B,|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A={2, 3, 4, 5, 6},R是A上的整除,则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树,则G中增加_________条边才能把G变成完全图。
离散数学试题一(A 卷答案) 一、(10分)证明(A ∨B )(P ∨Q ),P ,(B A )∨P A 。 二、(10分)甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛,下列4 种判断都是正确的: (1)甲和乙只有一人参加; (2)丙参加,丁必参加; (3)乙或丁至多参加一人; (4)丁不参加,甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、(10分)指出下列推理中,在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1),US (3)xP (x ) P (4)P (y ) T (3),ES (5)Q (y ) T (2)(4),I (6)xQ (x ) T (5),EG 四、(10分)设A ={a ,b ,c},试给出A 上的一个二元关系R ,使其同时不满足自反性、反自反性、 五、(15分)设函数g :A →B ,f :B →C , (1)若f o g 是满射,则f 是满射。 (2)若f o g 是单射,则g 是单射。 六、(15分)设R 是集合A 上的一个具有传递和自反性质的关系,T 是A 上的关系,使得T R 且R ,证明T 是一个等价关系。 七、(15分)若
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答:(1),(4) 2、下列公式中哪些是永真式?( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答:(2),(3),(4) 3、设有下列公式,请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答:(2),(3),(4),(5),(6) 4、公式 x((A(x) B(y ,x)) z C(y ,z))D(x)中,自由变元是( ),约束变元是( )。 答:x,y, x,z 5、判断下列语句是不是命题。若是,给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗? (4) 若7+8>18,则三角形有4条边。 (5) 前进! (6) 给我一杯水吧! 答:(1) 是,T (2) 是,F (3) 不是 (4) 是,T (5) 不是 (6) 不是 6、命题“存在一些人是大学生”的否定是( ),而命题“所有的人都是要死的”的否定是( )。 答:所有人都不是大学生,有些人不会死 7、设P :我生病,Q :我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答:(1)对任一整数x 存在整数 y 满足x+y=0(2)存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合,确定下列命题的真值: (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 是奇数,Q(x):x 是偶数,谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2是偶数或-3是负数”的否定是( )。 答:2不是偶数且-3不是负数。 12、永真式的否定是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答:(2) 13、公式(?P ∧Q)∨(?P ∧?Q)化简为( ),公式 Q →(P ∨(P ∧Q))可化简为( )。 答:?P ,Q →P
离散数学练习题 第一章 一.填空 1.公式) ∨ ? ∧的成真赋值为 01;10 ? p∧ ( (q ) p q 2.设p, r为真命题,q, s 为假命题,则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01;10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式,B为重言式,则B A∨的类型为重言式 5.设p, q均为命题,在不能同时为真条件下,p与q的排斥也可以写成p与q的相容或。 二.将下列命题符合化 1. 7不是无理数是不对的。 解:) ? ?,其中p: 7是无理数;或p,其中p: 7是无理数。 (p 2.小刘既不怕吃苦,又很爱钻研。 解:其中 ?p: 小刘怕吃苦,q:小刘很爱钻研 p∧ ,q 3.只有不怕困难,才能战胜困难。 解:p →,其中p: 怕困难,q: 战胜困难 q? 或q →,其中p: 怕困难, q: 战胜困难 p? 4.只要别人有困难,老王就帮助别人,除非困难解决了。 解:) → ?,其中p: 别人有困难,q:老王帮助别人,r: 困难解决了 p (q r→ 或:q ?) (,其中p:别人有困难,q: 老王帮助别人,r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解:q p?,其中p: 整数n是偶数,q: 整数n能被2整除 三、求复合命题的真值 P:2能整除5, q:旧金山是美国的首都, r:在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解:p, q 为假命题,r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题 目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识 点,重点复习,争取尽快掌握。本次形考书面作业是第一次作业,大家要认真及时地 完成集合论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答 过程,要求本学期第11周末前完成并上交任课教师(不收电子稿)。并在03任务界 面下方点击“保存”和“交卷”按钮,完成并上交任课教师。 一、填空题 1.设集合{1,2,3},{1,2} ==,则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}},A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} . 2.设集合A有10个元素,那么A的幂集合P(A)的元素个数为 1024 . 3.设集合A={0, 1, 2, 3},B={2, 3, 4, 5},R是A到B的二元关系, 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} . 4.设集合A={1, 2, 3, 4 },B={6, 8, 12},A到B的二元关系 R=} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R-1={<6,3>,<8,4>} 5.设集合A={a, b, c, d},A上的二元关系R={, , ,
离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,并在07任务界面下方点击“保存”和“交卷”按钮,以便教师评分.作业应手工书写答题,字迹工整,解答题要有解答过程,完成后上交任课教师(不收电子稿). 一、填空题 1.命题公式() →∨的真值是 1 . P Q P 2.设P:他生病了,Q:他出差了.R:我同意他不参加学习.则命题“如果他生病或出差了,我就同意他不参加学习”符号化的结果为P∨Q→R . 3.含有三个命题变项P,Q,R的命题公式P∧Q的主析取范式是(P∧Q∧┐R)∨(P∧Q∧R) . 4.设P(x):x是人,Q(x):x去上课,则命题“有人去上课.”可符号化为?x ( P ( x) ∧Q ( x)). 5.设个体域D={a, b},那么谓词公式) xA? ∨ x ?消去量词后的等值式为 yB ( ) (y (A(a)∨A(b))∨(B(a) ∧B(b)). 6.设个体域D={1, 2, 3},A(x)为“x大于3”,则谓词公式(?x)A(x) 的真值为0 . 7.谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y .8.谓词命题公式(?x)(P(x) →Q(x) ∨R(x,y))中的约束变元为x . 三、公式翻译题 1.请将语句“今天是天晴”翻译成命题公式. 解:
1 / 15 离散数学(2)复习题 一、单项选择题 1、由集合运算定义,下列各式正确的有( A )。 A.X ?X ?Y B.X ?X ?Y C.X ?X ?Y D.Y ?X ?Y 2、设A B -=?,则有( C )。 A.B =? B.B ≠? C.A B ? D.A B ? 3、对任意的集合A 、全集U ,下列命题为假的是( D )。 A.A ?? =A , B.A ?U = U C.A ?? = ?, D.A ?U = U 4、集合A={1,2,…,10}上的关系R={