HNU_AI_作业2--逻辑、概率、贝叶斯网络

参考：
灭绝星辰_人工智能-清览作业2
HNU岳麓山大小姐_人工智能导论：清览作业

一、真值表推理

1.请用真值表的方法证明下列语句是有效的，可满足的，还是不可满足的？（20分）

a)（P∧Q）∨¬Q

该语句在某一个模型中为真，为可满足的；

b)（(P∧Q)→R）↔（（P→R）∨（Q→R））

该语句在所有模型中都为真，为有效的；

二、一阶逻辑表达式转CNF，归结算法

2.考虑下列的一阶逻辑表达式：
其中x,y,z,w,s,t是变量，a,b,c是常数。
a)讲1,2,3式子转换为CNF形式(9分)
b)从上述知识库(KB)中使用归结算法证明结论equal(c,a)。 (16分)

a)转换为CNF形式

1式：∀x [equal(x,x)]

• 消除蕴含词→；
  • 该式无蕴涵词，无操作
• 将¬内移：
  • 该式无¬，无操作
• 变量标准化：
  • 该式不需重命名变量，无操作
• 消除存在量词∃：
  • 该式无∃，无操作
• 删除全称量词∀：
  • 直接删除：equal(x,x)
• 将∧分配到∨中：
  • 该式无∧，无操作

1式转换为CNF形式：equal(x,x)

2式：∀y,z [equal(y,z)→equal(z,y)]

• 消除蕴含词→；
  • ∀y,z [¬equal(y,z)∨equal(z,y)]
• 将¬内移：
  • 上式无需再内移
• 变量标准化：
  • 该式不需重命名变量，无操作
• 消除存在量词∃：
  • 该式无∃，无操作
• 删除全称量词∀：
  • 直接删除：¬equal(y,z)∨equal(z,y）
• 将∧分配到∨中：
  • 该式无∧，无操作

2式转换为CNF形式：¬equal(y,z)∨equal(z,y）

3式：∀w,s,t [equal(w,s) ∧ equal(s,t) →equal(w,t)]

• 消除蕴含词→；
  • ∀w,s,t [¬(equal(w,s) ∧ equal(s,t) )∨equal(w,t)]
• 将¬内移：
  • ∀w,s,t [¬equal(w,s)∨¬equal(s,t) ∨equal(w,t)]
• 变量标准化：
  • 该式不需重命名变量，无操作
• 消除存在量词∃：
  • 该式无∃，无操作
• 删除全称量词∀：
  • 直接删除：¬equal(w,s)∨¬equal(s,t) ∨equal(w,t)
• 将∧分配到∨中：
  • 该式无∧，无操作

3式转换为CNF形式：¬equal(w,s)∨¬equal(s,t) ∨equal(w,t)

b)归结算法

• 整理前面的式子，得：
  1-CNF：equal(x,x)
  2-CNF：¬equal(y,z)∨equal(z,y)
  3-CNF：¬equal(w,s)∨¬equal(s,t) ∨equal(w,t)
  4：equal(b,a)
  5：equal(b,c)
• 归结算法：
  • 给2-CNF中的y,z赋值代换(y=b,z=c)：6：¬equal(b,c)∨equal(c,b)
  • 将6式与5式消解：7：equal(c,b)
  • 给3-CNF中的w,s,t赋值代换(w=c,s=b,t=a)：8：¬equal(c,b)∨¬equal(b,a) ∨equal(c,a)
  • 将8式与4式、7式消解：9：equal(c,a)
  • 9式与¬equal(c,a)消解，为空

原命题equal(c,a)得证；

ANSWER:

三、表达式转换为CNF形式

3.把下列表达式转换为CNF形式 (10分)

(∀x∀y∃z q(z,y,x)) →(¬∃x{ ∀y [p(x,y)→q(x,y)] })

• 消除蕴含词→；
  • ¬(∀x∀y∃z q(z,y,x)) ∨(¬∃x{ ∀y [¬p(x,y)∨q(x,y)] })
• 将¬内移：
  • (∃x∃y∀z ¬q(z,y,x)) ∨(∀x{ ∃y ¬[¬p(x,y)∨q(x,y)] })
  • (∃x∃y∀z ¬q(z,y,x)) ∨(∀x{ ∃y [p(x,y)∧¬q(x,y)] })
• 变量标准化：
  • (∃x∃y∀z ¬q(z,y,x)) ∨(∀m{ ∃n [p(m,n)∧¬q(m,n)] })
• 消除存在量词∃：
  • 前面两个∃不受其他量词限定，直接替换为常量： ∀z ¬q(z,C1,C2)) ∨(∀m{ ∃n [p(m,n)∧¬q(m,n)] })
  • 后面的∃受其他量词m限定，替换为F(m)： ∀z ¬q(z,C1,C2)) ∨(∀m [p(m,F(m))∧¬q(m,F(m))] )
• 删除全称量词∀：
  • 直接删除：¬q(z,C1,C2)) ∨[ p(m,F(m))∧¬q(m,F(m)) ]
• 将∧分配到∨中：
  • [¬q(z,C1,C2)) ∨p(m,F(m)) ]∧ [ ¬q(z,C1,C2)) ∨¬q(m,F(m))]

四、概率

4.考虑从一副标准的52张纸牌（不含大小王）中分发每手5张牌的扑克牌域。假设发牌人是公平的。
a)在联合概率分布中共有多少个原子事件（即，共有多少种5张手牌的组合）？(5分)
b)每个原子事件的概率是多少？(5分)
c)拿到大同花顺（即同花的A、K、Q、J、10）的概率是多少？(5分)
d)四同张（4张相同的牌，分别为4种花色）的概率是多少？(5分)

52张纸牌（不含大小王）：

• 13张一组；黑桃、红桃、梅花、方块四种花色表示各组
• 每组花色的牌包括从1-10（1通常表示为A）以及J、Q、K标示的13张牌

a)原子事件的个数

从52张不同的牌中取5张：
$$C_{52}^5=\frac{52\ast 51\ast 50\ast 49\ast 48}{5\ast 4\ast 3\ast 2\ast 1}=2598960$$

b)原子事件的概率

从52张不同的牌中取到一个原子事件的概率：
$$P_1=\frac{1}{C_{52}^5}=\frac{1}{\frac{52\ast 51\ast 50\ast 49\ast 48}{5\ast 4\ast 3\ast 2\ast 1}}=\frac{1}{2598960}$$

c)大同花顺（即同花的A、K、Q、J、10）的概率

大同花顺包括四种原子事件：
全为黑桃/红桃/梅花/方块的A、K、Q、J、10
$$P_2=4\ast P_1=\frac{4}{2598960}=\frac{1}{649740}$$

d)四同张（4张相同的牌，分别为4种花色）的概率

四同张包括13钟情况：
分别为黑桃、红桃、梅花、方块的1-10、K、Q、J；
组合中的另一张，从剩下的52-4=48张牌中任选一个，有48种情况：
$$P_3=13\ast 48\ast P_1=\frac{13\ast 48}{2598960}=\frac{1}{4165}$$

五、贝叶斯网络

5. 参考下图中的贝叶斯网络，其中布尔变量I=聪明(intelligence) H=诚实(Honest) P=受欢迎的(Popular) L=大量的竞选资金 E=竞选成功

(a) 根据该网络结构，是否可以得到P(I,L,H)=P(I)P(L)P(H),如果不是，请给出正确的表达式； (6分)
(b)根据该网络结构计算P(i,h,¬l,p,¬e)的值，只有答案没有步骤不得分；(8分)
©假设已知某个人是诚实的，没有大量的竞选资金但是竞选成功了，那么他是聪明的概率是多少？只有答案没有过程不得分。(11分)

a)P(I,L,H)与P(I)P(L)P(H)

• 不能得到得到P(I,L,H)=P(I)P(L)P(H)；
• 原因：贝叶斯网络中有H指向L的有向边，说明L是H的条件概率， 此两者并不独立；
• 正确表达式为：

$$\begin{gathered} P(I,L,H)=P(I)P(L，H) \\ =P(I)P(L|H)P(H) \end{gathered}$$

b)计算P(i,h,¬l,p,¬e)

$$\begin{gathered} P(i,h,\neg l,p,\neg e)=P(\neg e|p)\ast P(p|i,h,\neg l)\ast P(i,h,\neg l) \\ =P(\neg e|p)\ast P(p|i,h,\neg l)\ast P(i)\ast P(\neg l|h)\ast P(h) \end{gathered}$$
由贝叶斯网络，得：
$$\begin{gathered} P(\neg e|p)=1-0.6=0.4 \\ P(p|i,h,\neg l)=0.4 \\ P(i)=0.5 \\ P(\neg l|h)=1-0.3=0.7 \\ P(h)=0.1 \end{gathered}$$
代入，得：
$$\begin{gathered} P(i,h,\neg l,p,\neg e)=0.4\ast 0.4\ast 0.5\ast 0.7\ast 0.1 \\ =0.0056 \end{gathered}$$

c) 求P(i|h,¬l,e)

$$P(i|h,\neg l,e)=\frac{P(i,h,\neg l,e)}{P(h,\neg l,e)}$$
其中
$$\begin{gathered} P(i,h,\neg l,e)=P(i,h,\neg l,p,e)+P(i,h,\neg l,\neg p,e) \\ P(i,h,\neg l,p,e)=P(e|p)\ast P(p|i,h,\neg l)\ast P(i)\ast P(\neg l|h)\ast P(h) \\ =0.6\ast 0.4\ast 0.5\ast 0.7\ast 0.1=0.0084 \\ P(i,h,\neg l,\neg p,e)=P(e|\neg p)\ast P(\neg p|i,h,\neg l)\ast P(i)\ast P(\neg l|h)\ast P(h) \\ =0.1\ast (1-0.4)\ast 0.5\ast 0.7\ast 0.1=0.0021 \\ 所以P(i,h,\neg l,e)=0.0084+0.0021=0.0105 \end{gathered}$$

$$\begin{gathered} P(h,\neg l,e)=P(i,h,\neg l,e)+P(\neg i,h,\neg l,e) \\ 由上式，P(i,h,\neg l,e)=0.0105 \\ P(\neg i,h,\neg l,e)=P(\neg i,h,\neg l,p,e)+P(\neg i,h,\neg l,\neg p,e) \\ P(\neg i,h,\neg l,p,e)=P(e|p)\ast P(p|\neg i,h,\neg l)\ast P(\neg i)\ast P(\neg l|h)\ast P(h) \\ =0.6\ast 0.3\ast 0.5\ast 0.7\ast 0.1=0.0063 \\ P(\neg i,h,\neg l,\neg p,e)=P(e|\neg p)\ast P(\neg p|\neg i,h,\neg l)\ast P(\neg i)\ast P(\neg l|h)\ast P(h) \\ =0.1\ast (1-0.3)\ast 0.5\ast 0.7\ast 0.1=0.00245 \\ 所以P(\neg i,h,\neg l,e)=0.0063+0.00245=0.00875 \\ P(h,\neg l,e)=0.0125+0.00875=0.01925 \end{gathered}$$
代入，得：
$$P(i|h,\neg l,e)=\frac{P(i,h,\neg l,e)}{P(h,\neg l,e)}=\frac{0.0105}{0.01925}\approx 0.545$$

另解：
$$\begin{gathered} P(i|h,\neg l,e)=\alpha P(i,h,\neg l,e)=\alpha P(e|i,h,\neg l)P(i)P(h)p(\neg l|h) \\ =\alpha \ast (P(e|p)P(p|i,h,\neg l)P(i)P(h)p(\neg l|h)+P(e|\neg p)P(\neg p|i,h,\neg l)P(i)P(h)p(\neg l|h)) \\ =\alpha \ast (0.6\ast 0.4\ast 0.5\ast 0.1\ast 0.7+0.1\ast 0.6\ast 0.5\ast 0.1\ast 0.7) \\ =\alpha \ast 0.0105 \end{gathered}$$

$$\begin{gathered} P(\neg i|h,\neg l,e)=\alpha P(\neg i,h,\neg l,e)=\alpha P(e|\neg i,h,\neg l)P(\neg i)P(h)p(\neg l|h) \\ =\alpha \ast (P(e|p)P(p|\neg i,h,\neg l)P(\neg i)P(h)p(\neg l|h)+P(e|\neg p)P(\neg p|\neg i,h,\neg l)P(\neg i)P(h)p(\neg l|h)) \\ =\alpha \ast (0.6\ast 0.3\ast 0.5\ast 0.1\ast 0.7+0.1\ast 0.7\ast 0.5\ast 0.1\ast 0.7) \\ =\alpha \ast 0.00875 \end{gathered}$$

归一化：
$$\begin{gathered} \alpha \ast 0.0105+\alpha \ast 0.00875=1 \\ 所以\alpha =51.9480519 \\ P(i|h,\neg l,e)=\alpha \ast 0.0105=0.5454\dots \dots \end{gathered}$$