當值演演算法

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) 德摩根定律