当值算法

A. 离散数学 等值演算法

设p:派赵出国，q:派钱出国，r:派孙出国，s:派李出国，t:派周出国。则各条件分别符号化为:

(1)p→q，(2)(sVt),(3)(qA7r)V(-q^r)，(4)(rAs)V(→rA-s)，(5)1-+(p^q) 要求满足各条件，

因而要求(1)~(5)的合取式为真.设:A≈(p→q)A(sV1)八((q八→r)V(→qλr))A((rAs)V(r八-s))∩(t→(p^q))

为了求出各派遣方案,应求出A的析取范式，最好是主析取范式，主析取范式中含的极小项个数为派遣方案数，由各极小项的成真赋值给出如何派法.所以要求出A的主析取范式。

下面给出求A的主析取范式的主要步骤:

易知，成真赋值为00110与11001。

方案1：孙、李出国，而赵.钱、周不去。
方案2：赵、钱、周出国，而孙、李不去。

(1)当值算法扩展阅读

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系， 因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。

离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个着名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一，它是在1852年，由英国的一名绘图员弗南西斯·格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。

那么这能否从数学上进行证明呢？100多年后的1976年，肯尼斯·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）使用计算机辅助计算，用了1200个小时和100亿次的判断，终于证明了四色定理，轰动世界，这就是离散数学与计算机科学相互协作的结果。

B. .用等值算法证明:((p∨q)→r)→p

1((p∨q)→r)→p<=>┐((p∨q)→r)vp<=>┐(┐(p∨q)vr)vp<=>((p∨q)∧┐r)vp<=>(p∨qvp)∧(┐rvp)

2证明：对于任意的<x,y>属于R1∪R2,<x,y>属于R1或<x,y>属于R2,.因为R1和R2具有对称性,所以<y,x>属于R1或<y,x>属于R2,得<y,x>属于R1∪R2.R1∪R2满足对称性得证.

3

设 P:逻辑学难学,Q:许多学生喜欢逻辑学, R:数学容易学

前提：PvQ,R→┐P

结论：┐Q→┐R

证明：

(1)┐Q P(附加前提)

(2)PvQ P

(3)┐Q→P T(2)E

(4)P T(1)(3)I

(5)R→┐P P

(6)P→┐R T(5)E

(7)┐R T(4)(6)I

(8)┐Q→┐R CP

4

用哈夫曼树编码

把出现频率化为权重形式,得

【0】0.27,【1】0.26,【2】0.16,【3】0.02,【4】0.02,

【5】0.07,【6】0.06,【7】0.04,【8】0.05,【9】0.05

左子树标记0,右子树标记1,得到哈弗曼编码

0:100 1:10 2:1113:00000 4:00001

5:1101 6:1100 7:0001 8:0010 9:0011

C. 等值算法p<=>(p^q)v(p^┐q)

(p^q)v(p^┐q)=((p^q)vp)^((p^q)v┐q)=(p^(pvq))^((pv┐q)^(qv┐q))=p^(pv┐q)=p

D. 离散数学，用等值算法求下列公式的主析取范式 （p→q）^（r→q） 求过程，谢谢！

（p→q）^（r→q）
<=>（┐p∨q）^（┐r∨q）
<=>（┐p^q）∨（┐p^┐r）∨（q∧┐r）
<=>（┐p^q∧(r∨┐r)）∨（┐p^(q∨┐q)∧┐r）∨（(p∨┐p)∧q∧┐r）
<=>（┐p^q∧r）∨（┐p^q∧┐r）∨（┐p^┐q∧┐r）∨（p∧q∧┐r）

E. 用等值算法

(q∧(p?q))→?(p∨?q) ? ?(q∧(p?q))∨?(p∨?q) 变成 合取析取 ? ?(q∧((p→q)∧(q→p)))∨?(p∨?q) 变成 合取析取 ? ?(q∧((?p∨q)∧(?q∨p)))∨?(p∨?q) 变成 合取析取 ? (?p∧q)∨(?q∨?((?p∨q)∧(?q∨p))) 德摩根定律 ? (?p∧q)∨(?q∨(?(?p∨q)∨?(?q∨p))) 德摩根定律 ? (?p∧q)∨(?q∨((p∧?q)∨(q∧?p))) 德摩根定律 ? (?p∧q)∨?q∨((p∧?q)∨(?p∧q)) 结合律 ? (?p∧q)∨?q∨(p∧?q)∨(?p∧q) 结合律 ? ?q∨(p∧?q)∨(?p∧q) 等幂律 ? ?q∨(?p∧q) 合取析取 吸收率 ? ?q∨?p 合取析取 吸收率是可满足式

F. 离散数学，用等值算法判定下列公式的类型，要过程，谢谢

(q∧(p↔q))→¬(p∨¬q)
⇔ ¬(q∧(p↔q))∨¬(p∨¬q) 变成 合取析取
⇔ ¬(q∧((p→q)∧(q→p)))∨¬(p∨¬q) 变成 合取析取
⇔ ¬(q∧((¬p∨q)∧(¬q∨p)))∨¬(p∨¬q) 变成 合取析取
⇔ (¬p∧q)∨(¬q∨¬((¬p∨q)∧(¬q∨p))) 德摩根定律
⇔ (¬p∧q)∨(¬q∨(¬(¬p∨q)∨¬(¬q∨p))) 德摩根定律
⇔ (¬p∧q)∨(¬q∨((p∧¬q)∨(q∧¬p))) 德摩根定律
⇔ (¬p∧q)∨¬q∨((p∧¬q)∨(¬p∧q)) 结合律
⇔ (¬p∧q)∨¬q∨(p∧¬q)∨(¬p∧q) 结合律
⇔ ¬q∨(p∧¬q)∨(¬p∧q) 等幂律
⇔ ¬q∨(¬p∧q) 合取析取 吸收率
⇔ ¬q∨¬p 合取析取 吸收率

是可满足式

G. 用等值算法求公式┐(p→q)的主析取范式和主合取范式。

¬(P∨Q)→R⇔¬(¬(PVQ))∨R⇔(PVQ)VR⇔PVQVR
使该式为真,则P,Q,R中至少有一项为真即可,因此所有成真赋值范式如下：
P Q R；0 0 1；0 1 0；0 1 1；1 0 0；1 0 1；1 1 0；1 1 1

另外，已知：p->q ┐pvq，那么 ┐（pq），┐( (p->q ) ^ (q->p) )，┐( (┐pvq ) ^ (┐qvp) )

┐ (┐pvq ) v ┐ (┐qvp)(p ^ ┐q ) v (q ^ ┐p)。则(p v q ) ^ (┐p v ┐ q)(p ^ (┐p v ┐q)) v (q ^ (┐p v ┐ q))，(p ^ ┐q ) v (q ^ ┐p) 左边

(7)当值算法扩展阅读：

等值演算

如果两个公式A与B含有相同的命题变元，如果在所有指派下，A与B的真值都相同，则说明这两个公式是等值的。等值算法是利用已知的等值式通过代换得到新的等值式。

判断两个公式是否等值，最直接的方法就是用真值表法，判断A与B是否在所有指派下同真值，或者判断A等价B是否是重言式。但是当命题变元较多的是时候，真值表法判断公式等值的工作量是很大的。这时，等值算法的强大功能就凸显出来了。

H. 离散数学等值算法证明，第一，第三问

（1）
(p∧q)∨(p∧¬q)
⇔p∧（q∨¬q）分配率
⇔p∧TRUE
⇔p

（2）
¬(p↔q)
⇔¬((p→q)∧(q→p)) 变成 合取析取
⇔¬((¬p∨q)∧(¬q∨p)) 变成 合取析取
⇔¬((¬p∨(p∧q))∧(¬q∨(p∧q))) 吸收率 反过来用
⇔¬((¬p∧¬q)∨(p∧q)) 分配率 把上式中(p∧q)看成一个整体来处理
⇔¬(¬p∧¬q)∧¬(p∧q) 德摩根定律
⇔(p∨q)∧¬(p∧q) 德摩根定律