离散数学重修习题集.doc

离散数学重修****题集
重修****题集
第一、二章
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:我在家读书;S:我在家看报;原命题符号化为:(?P→Q)∧(P→R∨S)。
⑵ P:我今天进城;Q:天下雨;原命题符号化为:?Q→P。
⑶ P:你走;Q:我留下;原命题符号化为:Q→P。
4)用等价演算证明下列命题公式是否为重言式。
⑴(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
- 1 -
重修****题集
?(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
5)写出下列命题公式的对偶式。
⑴?(?P∧?Q)∧R的对偶式是:?(?P∨?Q)∨R
⑵(P∨?Q)∧(R∨P)对偶式是(P∧?Q)∨(R∧P)
⑶ P→((Q→R)∧(P∧?Q))
??P∨((?Q∨R)∧(P∧?Q))
?(?P∨?Q)∧(?P∨?Q∨R)
所以P→((Q→R)∧(P∧?Q))的对偶式是(?P∧?Q)∨(?P∧?Q∧R)
⑷(P?Q)→R
??(P?Q)∨R
??(P→Q)∨?(Q→P)∨R
??(?P∨Q)∨?(?Q∨P)∨R
?(P∧?Q)∨(?P∧Q)∨R
所以(P?Q)→R的对偶式是(P∨?Q)∧(?P∨Q)∧R
6)写出下列命题公式的主析取范式和主合取范式
⑴(P→Q)∧(Q→R)
?(?P∨Q)∧(?Q∨R)
?((?P∨Q)∧?Q)∨((?P∨Q)∧R)
?(?P∧?Q)∨(?P∧R)∨(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)(主析取范式) ?∑0,1,3,7
- 2 -
重修****题集
?∏2,4,5,6
?(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∧R)∨(?P∧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)(主析取范式)
?∑1,3,5,6,7
?∏0,2,4
?(P∨Q∨R)∧(P∨?Q∨R)∧(?P∨Q∨R)(主合取范式)
7)推理理论证明题:
⑴ P∧Q,(P?Q)→(T∨S)?(T∨S)
证明:
⑴P∧Q P
⑵P T⑴
⑶Q T⑴
⑷P→Q T⑶
⑸Q→P T⑵
⑹(P→Q)∧(Q→P) T⑷⑸
⑺P?Q T⑹
⑻(P?Q)→(T∨S) P
⑼T∨S T⑺⑻
⑵?(P→Q)→?(R∨S),(Q→P)∨?R,R?P?Q
证明:
⑴R P
⑵(Q→P)∨?R P
⑶Q→P T⑴⑵析取三段论
⑷R∨S