离散数学作业布置
第1次作业（P15）
1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0
（2）（p↔r）∧(﹁q∨s)=（0↔1）∧(1∨1)=0∧1 =0
（3）（﹁p∧﹁q∧r）↔(p∧q∧﹁r)=（1∧1∧1）↔ (0∧0∧0)=0
(4)（ r∧s）→(p∧ q)=（0∧1）→(1∧0)=0→0=1
1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则 也是无理数。另外只有6能被2整除，6才能被4整除。” 解： p: π是无理数 1
q: 3是无理数 0
r: 是无理数 1
s: 6能被2整除 1
t: 6能被4整除 0
命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。
（4）(p→q) →(﹁q→﹁p)
（5）(p∧r) ↔ (﹁p∧﹁ q)
（6）((p→q) ∧(q→r)) →(p→r)
解： （4）
p q p→q q p q→ p (p→q)→( q→ p)
0 0 1 1 1 1 1
0 1 1 0 1 1 1
1 0 0 1 0 0 1
1 1 1 0 0 1 1
所以公式类型为永真式 ，最后一列全为1
（5）公式类型为可满足式（方法如上例），最后一列至少有一个1
（6）公式类型为永真式（方法如上例，最后一列全为1）。
第2次作业（P38）
2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q)
(2)(p→(p∨q))∨(p→r)
(3)(p∨q)→(p∧r)
解：(1) ﹁(p∧q→q) undefined﹁(﹁(p∧q) ∨q) undefined(p∧q) ∧﹁qp∧(q ∧﹁q)
p∧0 0
所以公式类型为矛盾式
(2)（p→(p∨q)）∨(p→r) undefined (﹁p∨(p∨q))∨(﹁ p∨r) undefined﹁p∨p∨q∨r1
所以公式类型为永真式
(3) (p∨q) → (p∧r) undefined ￢(p∨q) ∨ (p∧r) undefined (￢p∧￢q) ∨(p∧r)
易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
P q r ￢p∧￢q p∧r (￢p∧￢q) ∨(p∧r)
0 0 0 1 0 1
0 0 1 1 0 1
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 0 0 0
1 0 1 0 1 1
1 1 0 0 0 0
1 1 1 0 1 1
所以公式类型为可满足式
2.4 用等值演算法证明下面等值式：
(2) ( (p→q)∧(p→r) ) (p→(q∧r))
(4)(p∧﹁q)∨(﹁p∧q) (p∨q)∧﹁(p∧q)
证明（2）(p→q)∧(p→r)
( ﹁p∨q)∧(﹁p∨r)
﹁p∨(q∧r))
p→(q∧r)
（4）(p∧﹁q)∨(﹁p∧q) undefined (p∨(﹁p∧q)) ∧(﹁q∨(﹁p∧q) )
(p∨﹁p)∧(p∨q)∧(﹁q∨﹁p) ∧(﹁q∨q)
1∧(p∨q)∧ (﹁p∨﹁q)∧1
(p∨q)∧﹁(p∧q)
第3次作业（P38）
2.5 求下列公式的主析取范式, 并求成真赋值:
(1)( ￢p→q) →(￢q∨p)
(2) (￢p→q) ∧q∧r
(3)(p∨ (q∧r)) →(p∨q∨r)
(4) ￢(p→q) ∧q∧r
解：
(1)(￢p→q) →(￢q∨p)
undefined￢(p∨q) ∨(￢q∨p)
undefined￢p∧￢q ∨￢q ∨p
undefined￢q ∨p (吸收律)
(￢p∨p)∧￢q ∨p∧(￢q∨q)
undefined￢p∧￢q∨p∧￢q ∨p∧￢q ∨p∧q
undefinedm0∨m2∨m2∨m3
undefinedm0∨m2∨m3
成真赋值为 00, 10, 11.
(2) (￢p→q) ∧q∧r
undefined (p∨q) ∧q∧r
undefined (p∧q∧r) ∨q∧r
undefined (p∧q∧r) ∨(￢p ∨p) ∧q∧r
undefinedp∧q∧r∨￢p ∧q∧r∨p∧q∧r
m3∨m7
成真赋值为011，111.
(3) (p∨(q∧r)) →(p∨q∨r)
undefined￢(p∨(q∧r)) ∨(p∨q∨r)
undefined￢p∧￢(q∧r) ∨(p∨q∨r)
undefined￢p∧(￢q∨￢r)∨(p∨q∨r)
undefined￢p∧￢q∨￢p∧￢r∨p∨q∨r
undefined￢p∧￢q∧(r∨￢r)∨￢p∧(q∨￢q)∧￢r∨p∧(q∨￢q) ∧(r∨￢r)
∨ (p∨￢p) ∧q∧(r∨￢r)∨(p∨￢p) ∧(q∨￢q) ∧r
undefinedm0∨m1∨m2∨m3∨m4∨m5∨m6∨m7, 为重言式.
(4) ￢(p→q) ∧q∧r
undefined￢(￢p∨q) ∧q∧r
undefined (p∧￢q) ∧q∧r
undefined p∧(￢q ∧q)∧r
undefined0
主析取范式为0, 无成真赋值, 为矛盾式.
第4次作业（P38）
2.6 求下列公式的主合取范式, 并求成假赋值:
(1) ￢(q→￢p) ∧￢p
(2)(p∧q) ∨ (￢p∨r)
(3)(p→(p∨q)) ∨r
解：
(1) ￢(q→￢p) ∧￢p
undefined￢(￢q∨￢p) ∧￢p
undefinedq∧p ∧￢p
undefinedq∧0
undefined0
undefinedM0∧M1∧M2∧M3
这是矛盾式. 成假赋值为 00, 01, 10, 11.
(2)(p∧q) ∨ (￢p∨r)
undefined(p∧q) ∨￢p∨r
undefined(p∨￢p)∧(￢p ∨q)∨r
(￢p ∨q)∨r
￢p ∨q∨r
undefinedM4, 成假赋值为100.
(3)(p→(p∨q)) ∨r
undefined(￢p∨(p∨q)) ∨r
undefined(￢p∨p)∨q ∨r
1
主合取范式为p.r.s1, 为重言式.
第5次作业（P41）
(1) (￢p∨q) ∧ (￢p∨r) ∧ (￢q∨￢r) ∧ (p∨￢r) ∧r
(2) ￢((p∨q) ∧ ￢p→q)
解：
(1) (￢p∨q) ∧ (￢p∨r) ∧ (￢q∨￢r) ∧ (p∨￢r) ∧r
第一次循环 S0=Φ, S1=｛￢p∨q,￢p∨r,￢q∨￢r,p∨￢r,r｝, S2=Φ
由￢p∨r, p∨￢r消解得到λ
输出“no”，计算结束
(2) ￢((p∨q) ∧ ￢p→q)
undefined￢(￢((p∨q) ∧ ￢p) ∨q)
((p∨q) ∧ ￢p) ∧￢q
undefined (p∨q) ∧ ￢p ∧￢q
第一次循环 S0=Φ, S1=｛p∨q,￢p, ￢q｝, S2=Φ
由p∨q,￢p消解得到q,
由q, ￢q消解得到λ,
输出“no”，计算结束
2.33 用消解法判断下述公式是否可满足的:
(1) p∧ (￢p∨￢q) ∧q
(2) (p∨q) ∧(p∨￢q) ∧(￢p∨ r)
解：
(1) p∧ (￢p∨￢q) ∧q
第一次循环 S0=Φ, S1=｛p, ￢p∨￢q, q｝, S2=Φ
由p, ￢p∨￢q消解得到￢q,
由q, ￢q消解得到λ,
输出“no”，计算结束
(2) (p∨q) ∧(p∨￢q) ∧(￢p∨ r)
第一次循环 S0=Φ, S1=｛p∨q, p∨￢q, ￢p∨ r｝, S2=Φ
由p∨q, p∨￢q消解得到p,
由p∨q, ￢p∨ r消解得到q ∨r,
由p∨￢q, ￢p∨ r消解得到￢q ∨r,
由p, ￢p∨ r消解得到r,
S2=｛p, q ∨r, ￢q ∨r, r｝
第二次循环 S0=｛p∨q, p∨￢q, ￢p∨ r｝, S1=｛p, q ∨r, ￢q ∨r, r｝, S2=Φ
由p∨q, ￢q ∨r消解得到p∨r,
由p∨￢q, q ∨r消解得到p∨r,
由p∨￢q, q ∨r消解得到p∨r,
由￢p∨ r, p 消解得到r,
S2=｛p∨r｝
第三次循环 S0=｛p, q ∨r, ￢q ∨r, r｝, S1=｛p∨r｝, S2=Φ
S2=Φ
输出“yes”，计算结束
第6次作业（P52）
3.6 判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给
出)和判断过程(至少给出两种判断方法):
(1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三.
(2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一.
(3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一.
(4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二.
(5)若今天是星期一, 则明天是星期二或星期三. 今天是星期一. 所以明天是星期二.
(6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三.
设p: 今天是星期一, q: 明天是星期二, r: 明天是星期三.
(1)推理的形式结构为
(p→r) ∧p→r
此形式结构为重言式, 即
(p→r) ∧pr
所以推理正确.
(2)推理的形式结构为
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议