吉林大学 人工智能原理 下

10/28/20231第四章可分解产生式系统的搜索策略学习目标：

了解一般的与/或图搜索问题，掌握与/或图的启发式搜索算法AO*。了解博弈树搜索问题，掌握博弈树搜索中的极小极大方法和α-β剪枝搜索方法。重点：

AO*算法，α-β剪枝算法。

10/28/20232第二章可分解产生式系统中提到的与/或树表示，其中加到每一个节点上AND或OR的标记是取决于该节点对其父节点的关系。如复合状态分解后拥有一组“与”关系的后继节点；而分量状态经可应用规则作用后，生成一组“或”关系的后继节点。与/或树是本章介绍的与/或图的特例。在一般与/或图中，一个节点可能是复合状态的组成部分，而同时又是一个规则应用的结果，很难说明它是与后继还是或后继．因此，不再区别AND节点或OR节点．但在称谓上沿用习惯，仍把这种结构称作与/或图。

4.1与/或图搜索10/28/20233

例.一个与/或图10/28/20234与/或图搜索

定义：与/或图是一种超图．在超图中父亲节点和一组后继节点用超弧连接．超弧又叫k-连接符．

k-连接符:一个父节点指向一组k个有与关系的后继节点，这样一组弧线称为一个k-连接符．

k>1时，用一圆弧标记此连接符。Note:若所有的连接符都是1-连接符，则得到的就是与/或图的特例--普通有向图。10/28/20235与/或图搜索与/或树:每一个节点最多只有一个父亲的与/或图．根节点:在AND/OR树或AND/OR图中没有父节点的节点.叶节点:在AND/OR树或AND/OR图中没有后继的节点．终止节点:满足终止条件的节点．

10/28/20236与/或图搜索一个可分解的产生式系统定义一个隐含的与/或图．图的根节点表示产生式系统的初始状态描述，连接符表示对一状态描述应用产生式规则或把这一状态描述分解成若干组成部分．可分解产生式系统的任务:从隐含的与/或图出发找出一个从根节点出发到终止节点集的解图。10/28/20237例重写规则：n0→n1n0→n5，n4n1→n2n1→n3n2→n3n2→n5，n4n3→n5，n6n4→n5n4→n8n5→n7,

n8n5→n6n6→n7,

n810/28/20238练习1：假定我们有一个产生式系统，基于如下重写规则：

R1：n0→n1,n2R5：n2→n6,n7R2：n0→n2,n3R6：n3→n5,n6R3：n1→n2R7：n4→n2R4：n1→n4R8：n5→n7请用与/或图表示此产生式系统。10/28/20239练习2：一个产生式系统使用下面一组重写规则，这些重写规则把左面的数字转换成右边的数字串。6→3,34→3,16→4,23→2,14→2,22→1,1使用这些规则把6转换成由1组成的数字串。请用与/或图表示此产生式系统。

10/28/202310与/或图搜索定义

设N是与/或图G的终止节点集合，图G中无回路，从节点n出发到N的一个解图是与/或图G的一个子图，用G’表示，递归定义如下：

1.若n是N中的一个元素，则G’只包括节点n；10/28/202311与/或图搜索2.若n有一个从n出发的连接符k指向后继节点集合｛n1，…，nk｝，而每一个ni都有从ni出发的解图，则G’由节点n、连接符k、｛n1，…，nk｝中的每一个节点到N的解图所构成；3.否则，G没有从n出发到N的解图．10/28/202312n0n1n3n5n6n8n7an0n4n5n7n8bn0n4n5n7n8c10/28/202313与/或图搜索加权与/或图：权加在连接符上。假定所有连接符的费用均大于某一小的正数ε。使用连接符的费用可以计算解图的费用．设从节点n到终止节点集合N的解图的费用用

k(n,N)表示，则k(n,N)递归定义如下：

1.若n是N中的元素，则k(n,N)=0；

10/28/202314与/或图搜索2.若有从n出发的一个连接符指向它的解图后继节点｛n1，…，ni｝，设此连接符的费用为Ci，则:k(n,N)=Ci+k(n1,N)+…+k(ni,N)最佳解图：具有最低费用的解图10/28/202315设k-连接符的费用为k，计算k(n0,N)n0n1n3n5n6n8n7an0n4n5n7n8bn0n4n5n7n8c10/28/202316与/或图搜索假定h*(n)是从n出发的最佳解图的费用，

h(n)是h*(n)的估计值。利用h(n)指导对AND/OR图的启发式搜索。10/28/202317与/或图搜索在AND/OR图中，对任意连接符的单调限制是

h(n)≤c+h(n1)+…+h(nk)其中，n是任意节点，c是从n出发的连接符的费用，n1，…，nk是n的在此连接符下的后继节点。Note:若对于所有的终止节点，都有h(n)＝0，则单调限制还隐含着h对所有的节点n，都有：h(n)≤h*(n)。

10/28/202318

搜索过程还要标记能解节点（SOLVED），为此给出如下定义：

能解节点（SOLVED）

①终止节点是能解节点；

②若非终止节点有“或”子节点时，其子节点有一能解，则该非终止节点是能解节点；

③若非终止节点有“与”子节点时，若其子节点均能解，则该非终止节点是能解节点。10/28/2023194.2与/或图的搜索算法……算法AO*AO*算法解析：回忆：普通图搜索中的A算法：对当前搜索图的“前沿”（即在OPEN表中的节点）节点进行评价，选取f值最小的节点进行扩展。回想一下，f是如何定义的？

f(n)=g(n)+h(n)，其中

g(n)：已经求得的当前搜索图中从初始节点到当前节点n的最优路径费用。

h(n)：从n到目标节点的最优路径费用的估计值。结论：对节点n的评价，实际上是对

"初始节点--节点n--目标节点"这一条路径的评价。10/28/202320AO*算法解析：在与/或图搜索中，由于“与”节点的存在，单纯对一个节点的评价已经不能反映解图的全面情况。与/或图中的解图相当于普通图中的解路径。从"对节点n的评价，实际上是对'初始节点--节点n--目标节点'这一条路径的评价"这一思路出发，可以很容易的想到，能否通过对局部解图进行评价，来达到类似于普通图中A*搜索的目的。AO*算法，正是这样的一种适用于与/或图的搜索算法。10/28/202321AO*算法解析：AO*算法可以划分为两个阶段。第一阶段：自顶向下的图生成过程。（对于每一个已经扩展了的节点，算法都有一个指针，指向该节点的后继节点中费用值小的那个连接符。）从初始节点出发，先通过有指针标记的连接符，向下搜索，一直到找到未扩展的节点为止（找到目前为止费用值最小的一个局部解图）。然后对其中一个非终止节点进行扩展，并对其后继节点赋费用值和加能解标记。10/28/202322AO*算法解析：第二阶段：费用值计算过程。

完成自下向上的费用值修正计算、指针的标记以及节点的能解标记。10/28/202323AO*算法解析：两个图

G：搜索图

G’：局部解图（准部分解图）（可能变化的）两个函数

h(n)：启发函数（静态）对h*(n)的估计

q(n)：费用函数（动态变化）两重循环外层：从上向下扩展内层：从下向上修改费用q值、标记指针10/28/202324AO*算法解析：两种标记

SOLVED：标记能解节点

—表明此节点的解图已找到指针：标记连接符，用于计算G’10/28/2023251与/或图搜索……算法AO*ProcedureAO*1．建立一个只由根节点构成的搜索图G．

s的费用q(s):=h(s),G’:=G．如果s是目标，标记s为SOLVED.

2．Untils被标记为SOLVED，do：10/28/202326

3．begin4．通过跟踪从s出发的有标记的连接符计算部分解图G’（G的连接符将在以后的步骤中标记）

5．在G’中选一个非终止的叶节点n.

6．扩展节点n产生n的所有后继，并把它们连到图G上，对于每一个不曾在G中出现的后继nj，q(nj):=h(nj)，如果这些后继中某些节点是终止节点，则用SOLVED标记。与/或图搜索……算法AO*10/28/2023277．S:＝{n}；建立一个只由n构成的单元素集合S。

8．UntilS变空，do：

9．begin10．从S中删除节点m，满足m在G中的后裔不出现在S中

与/或图搜索……算法AO*10/28/20232811．按以下步骤修改m的费用q(m)：对于每一从m出发的指向节点集合{n1i，…，nki}的连接符，计算qi(m)=ci+q(n1i)+…+q(nki)，q(m):＝min{qi(m)}。(1)将指针标记加到实现此最小值的连接符上。(2)如果本次标记与以前的不同，抹去先前的标记。(3)如果这个连接符指向的所有后继节点都标记了SOLVED，则把m标上SOLVED．与/或图搜索……算法AO*10/28/20232912．如果m标记了SOLVED或者如果m的修改费用与以前的费用不同，则把m的通过指针标记的连接的所有父节点加到S中．13．end14．end

与/或图搜索……算法AO*10/28/2023302AO*算法应用举例设某个问题的状态空间如图所示。

h

(n0)＝0，h(n1)＝2，h(n2)＝4，h(n3)＝4，h(n4)＝1，h(n5)＝1，h(n6)＝2，h(n7)＝h(n8)＝0（目标节点）。

假设k-连接符的费用值为k。10/28/202331

图4.3(a)一次循环后10/28/202332图4.3(b)两次循环后10/28/202333图4.3(c)三次循环后010/28/202334图4.3(d)四次循环后10/28/202335从n0开始，沿指向连接符的指针找到的解图即为搜索的结果。n0给出的修正费用值q(n0)＝5就是解图的费用值。图4.3(e)搜索得到的解图10/28/202336Note（1）在第6步扩展节点n时，若不存在后继节点（即陷入死胡同），则可在第11步中对m（即n）赋一个高的q值，这个高的q值会依次传递到s，使得含有节点n的子图具有高的q（s），从而排除了被当作候选局部解图的可能性。10/28/202337(2)如果一个与／或图存在解图，如果对于图中所有的节点n都有h（n）≤h*（n），并且启发函数h满足单调限制，则AO*算法必然终止于找出最佳解图。10/28/202338练习1’：

假定我们有一个产生式系统，基于如下重写规则：R1：n0→n1,n2R5：n2→n6,n7R2：n0→n2,n3R6：n3→n5,n6R3：n1→n2R7：n4→n2R4：n1→n4R8：n5→n7（1）用与/或图表示此产生式系统。（2）若h(n0)=0,h(n1)=2,h(n2)=4,h(n3)=4,h(n4)=3,h(n5)=1,h(n6)=0,h(n7)=0,为启发函数，k-连接符的费用为k，求n0到{n6,n7}的最佳解图。（要求：使用AO*算法，画出各次循环图，标明各点费用q(n)，画出最后的最佳解图，并指明最佳解图的费用）

10/28/202339练习2’：

一个产生式系统使用下面一组重写规则，这些重写规则把左面的数字转换成右边的数字串。

6→3,34→3,16→4,23→2,14→2,22→1,1

使用这些规则把6转换成由1组成的数字串。假设k-连接符的费用是k，用数字1标记的节点的h函数值是0，用数字n(n≠1)标记的节点的h函数值是n。请用AO*算法描述解题过程（要求：画出各次循环图，标明各点费用q(n)，画出最后的最佳解图，并指明最佳解图的费用）。10/28/2023404.4博弈树搜索

博弈具有竞争或对抗性质的行为称为博弈行为。比如日常生活中的下棋，打牌等。在这类行为中，参加斗争或竞争的各方各自具有不同的目标或利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。博弈论GameTheory

博弈论就是研究博弈行为中斗争各方是否存在着最合理的行为方案，以及如何找到这个合理的行为方案的数学理论和方法。博弈论亦名“对策论”、“赛局理论”，属应用数学的一个分支,目前在生物学，经济学，国际关系，计算机科学,政治学，军事战略和其他很多学科都有广泛的应用。10/28/202341博弈论历史博弈论思想古已有之，我国古代的《孙子兵法》就不仅是一部军事著作，而且算是最早的一部博弈论专著。博弈论最初主要研究象棋、桥牌、赌博中的胜负问题，人们对博弈局势的把握只停留在经验上，没有向理论化发展。近代对于博弈论的研究，开始于策墨洛（Zermelo），波雷尔（Borel）及冯·诺伊曼（vonNeumann）。1928年，冯·诺依曼证明了博弈论的基本原理，从而宣告了博弈论的正式诞生。1944年，冯·诺依曼和摩根斯坦共著的划时代巨著《博弈论与经济行为》将双人博弈推广到n人博弈结构并将博弈论系统地应用于经济领域，从而奠定了这一学科的基础和理论体系。1950～1951年，约翰·福布斯·纳什（JohnForbesNashJr）利用不动点定理证明了均衡点的存在，为博弈论的一般化奠定了坚实的基础。纳什的开创性论文《n人博弈的均衡点》（1950），《非合作博弈》（1951）等等，给出了纳什均衡的概念和均衡存在定理。此外，塞尔顿、哈桑尼的研究也对博弈论发展起到推动作用。今天博弈论已发展成一门较完善的学科。10/28/202342博弈分类-根据不同的基准有不同的分类合作博弈和非合作博弈。它们的区别在于相互发生作用的当事人之间有没有一个具有约束力的协议，如果有，就是合作博弈，如果没有，就是非合作博弈。从行为的时间序列性，分为静态博弈和动态博弈静态博弈是指在博弈中，参与人同时选择或虽非同时选择但后行动者并不知道先行动者采取了什么具体行动；动态博弈是指在博弈中，参与人的行动有先后顺序，且后行动者能够观察到先行动者所选择的行动。“囚徒困境”就是同时决策的，属于静态博弈；而棋牌类游戏等决策或行动有先后次序的，属于动态博弈。按照参与人对其他参与人的了解程度分为完全信息博弈和不完全信息博弈。完全博弈是指在博弈过程中，每一位参与人对其他参与人的特征、策略空间及收益函数有准确的信息。如果参与人对其他参与人的特征、策略空间及收益函数信息了解的不够准确、或者不是对所有参与人的特征、策略空间及收益函数都有准确的信息，在这种情况下进行的博弈就是不完全信息博弈。

10/28/202343囚徒困境警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：若一人认罪并作证检举对方（称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监10年。若二人都保持沉默（称互相“合作”），则二人同样判监半年。若二人都互相检举（互相“背叛”），则二人同样判监2年。假定：每个参与者（即“囚徒”）都是利己的，即都寻求最大自身利益，而不关心另一参与者的利益。参与者某一策略所得利益，如果在任何情况下都比其他策略要低的话，此策略称为“严格劣势”，理性的参与者绝不会选择。没有任何其它力量干预个人决策，参与者可完全按照自己意愿选择策略。10/28/202344试设想困境中两名理性囚徒会如何作出选择：若对方沉默，背叛会让我获释，所以会选择背叛。若对方背叛指控我，我也要指控对方才能得到较低的刑期，所以也是会选择背叛。二人面对的情况一样，所以二人的理性思考都会得出相同的结论——选择背叛，结果二人同样服刑2年。这显然不是顾及团体利益的最优解决方案。以全体利益而言，如果两个参与者都合作保持沉默，两人都只会被判刑半年，总体利益更高，结果也比两人背叛对方、判刑2年的情况较佳。但根据以上假设，二人均为理性的个人，且只追求自己个人利益。均衡状况会是两个囚徒都选择背叛，结果二人判决均比合作为高，总体利益较合作为低。这就是“困境”所在。10/28/2023454.4博弈树搜索

对于单人博弈的一些问题，可用一般的搜索技术进行求解，本节着重讨论双人完备信息这一类博弈问题的搜索策略。双人、具有完备信息博弈问题的特点：（1）双人对弈，对垒的双方轮流走步。（2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。（3）零和。即对一方有利的棋，对另一方肯定不利，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，另一方输，或者双方和棋。10/28/202346零和博弈（zero-sumgame）：是指博弈的参与者中,一方之所得是它方之所失,总量上看,支付水平不起变化或者为零。非零和博弈是一种非合作下的博弈，博弈中各方的收益或损失的总和不是零值。在经济学研究中很有用。

在这种状况时，自己的所得并不与他人的所失的大小相等，连自己的幸福也未必建立在他人的痛苦之上，即使伤害他人也可能“损人不利己”，所以博弈双方存在“双赢”的可能，进而合作。譬如，在恋爱中一方受伤的时候，对方并不是一定得到满足。也有可能双方一起能得到精神的满足。也有可能双方一起受伤。通常，彼此精神的损益不是零和的。比如目前的中美关系，就并非“非此即彼”，而是可以合作双赢。10/28/202347无处不在的博弈日常生活中的一切，均可从博弈得到解释，大到美日贸易战，小到今天早上你突然生病。“自然”是研究单人博弈的重要假定。农夫种庄稼也是同自然进行博弈的一个过程。自然的策略可以是：天旱、多雨、风调雨顺。农夫对应的策略分别是：防旱、防涝、放心地休息。当然，“自然”究竟采用哪种策略并不确定，于是农夫只有根据经验判断或气象预报来确定自己的行动。如果估计今年的旱情较重，就可早做防旱准备；如果估计水情严重，就早做防涝准备；如果估计是风调雨顺，农夫就可以悠哉悠哉了。10/28/202348双人博弈：夫妻吵架夫妻双方都有两种策略，强硬或软弱。博弈的可能结果有四种组合：夫强硬妻强硬、夫强硬妻软弱、夫软弱妻强硬、夫软弱妻软弱。商业界常见，如两个空调厂家的价格战10/28/202349智猪博弈（Pigs’payoffs）智猪博弈讲的是：猪圈里有两头猪，一头大猪，一头小猪。猪圈的一边有个踏板，每踩一下踏板，在远离踏板的猪圈的另一边的投食口就会落下少量的食物。如果有一只猪去踩踏板，另一只猪就有机会抢先吃到另一边落下的食物。当小猪踩动踏板时，大猪会在小猪跑到食槽之前刚好吃光所有的食物；若是大猪踩动了踏板，则还有机会在小猪吃完落下的食物之前跑到食槽，争吃到另一半残羹。

10/28/202350两只猪各会采取什么策略？小猪将选择“搭便车”策略，也就是舒舒服服地等在食槽边；而大猪则为一点残羹不知疲倦地奔忙于踏板和食槽之间。“小猪躺着大猪跑”的现象是由于故事中的游戏规则所导致的。规则的核心指标是：每次落下的食物数量和踏板与投食口之间的距离。

10/28/202351如果改变一下核心指标，猪圈里还会出现同样的“小猪躺着大猪跑”的景象吗？试试看。

改变方案一：减量方案。投食仅原来的一半分量。结果：是小猪大猪都不去踩踏板了。如果目的是想让猪们去多踩踏板，这个游戏规则的设计显然是失败的。

10/28/202352

改变方案二：增量方案。投食为原来的2倍分量。结果：小猪、大猪都会去踩踏板。谁想吃，谁就会去踩踏板。反正对方不会一次把食物吃完。小猪和大猪相当于生活在物质相对丰富的“共产主义”社会，所以竞争意识却不会很强。

对于游戏规则的设计者来说，这个规则的成本相当高（每次提供双份的食物）；而且因为竞争不强烈，想让猪们去多踩踏板的效果并不好。

10/28/202353

改变方案三：减量加移位方案。投食仅原来的一半分量，但同时将投食口移到踏板附近。结果：小猪和大猪都在拼命地抢着踩踏板。等待者不得食，而多劳者多得。每次的收获刚好消费完。

对于游戏设计者，这是一个最好的方案。成本不高，但收获最大。

10/28/202354原版的“智猪博弈”故事给了竞争中的弱者（小猪）以等待为最佳策略的启发。但是对于社会而言，因为小猪未能参与竞争，小猪搭便车时的社会资源配置的并不是最佳状态。为使资源最有效配置，规则的设计者是不愿看见有人搭便车的，政府如此，公司的老板也是如此。而能否完全杜绝“搭便车”现象，就要看游戏规则的核心指标设置是否合适了。许多人并未读过“智猪博弈”的故事，但是却在自觉地使用小猪的策略。股市上等待庄家抬轿的散户；等待产业市场中出现具有赢利能力新产品、继而大举仿制牟取暴利的游资；公司里不创造效益但分享成果的人，等等。因此，对于制订各种经济管理的游戏规则的人，必须深谙“智猪博弈”指标改变的个中道理。10/28/2023554.4博弈树搜索双人、具有完备信息博弈的实例有：一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。对于带机遇性的任何博弈，因不具有完备信息，不属这里讨论范围，但有些论述可推广到某些机遇博弈中应用。10/28/202356一、博弈树博弈问题可以用产生式系统的形式来描述。例如中国象棋，状态描述：棋盘上棋子各种位置布局产生式规则：各类棋子的合法走步目标：将（帅）被吃掉规则作用于初始状态描述及其所有的后裔状态描述，就产生了博弈图或博弈树．

10/28/202357？？博弈问题为什么可以用与/或图表示

可以这样来看待这个问题：当轮到我方走棋时，只需从若干个可以走的棋中，选择一个棋走就可以了。从这个意义上说，若干个可以走的棋是“或”的关系。而对于轮到对方走棋时，对于我方来说，必须能够应付对手的每一种走棋。这就相当于这些棋是“与"的关系。因此，博弈问题可以看成是一个与/或图，但是与一般的与/或图并不一样，是一种特殊的与/或图。10/28/202358Grundy博弈Grundy博弈是一个分钱币的游戏。分钱币问题是一种简单的博弈问题。有一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去直到有一位选手先无法把钱币再分成不相等的两堆时就得认输（直到桌子上的每堆硬币都是一个或两个为止，谁先遇到这种情况谁就算是输了）。以下用MIN代表对方，MAX代表我方。10/28/202359Grundy博弈状态空间图10/28/202360实现一种取胜的策略就是搜索一个解图的问题，解图就代表一种完整的博弈策略。问题：对于简单的游戏，采用与寻找AND／OR图解图相类似的技术是可以解决的．但是，对于复杂的游戏，这种方法是根本行不通的．中国象棋，每个势态有40种不同的走法，如果一盘棋双方平均走50步，则总节点数约为10161个。要考虑完整的搜索策略，就是用亿次机来处理，花的时间也得比宇宙的年龄还长。10/28/202361

对于西洋跳棋、国际象棋大致也如此，博弈树大约有1040个节点，象棋博弈树大约有10120个节点．假设每1／3毫微秒产生一个节点，产生整个跳棋的博弈树也需要1021个世纪。而围棋更复杂了。因此，对于实际的博弈问题，无论是从空间，还是从时间上来说，要想通过生成其所有状态空间图的方法来得到取胜策略，都是不可能的。10/28/202362

思考：对于一个优秀的博弈者来说，应考虑的不只是对方一步的走法，而是若干步的走法。而且这一过程一般来说是动态进行的，也就是说，在考虑若干步走法以后，下了一步棋，而在对方走棋之后，还要再次考虑若干步走法，决定下一步的走法，而不是一劳永逸，搜索一次就决定了所有的走法。10/28/202363

二、极小极大过程

极小极大过程模拟的就是人的一种思维过程。是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。下面的讨论规定：顶节点深度d＝0，MAX代表程序方，MIN代表对手方，且MAX先走。10/28/202364静态估值函数e(p)：建立在该棋的各种知识和特征上。对在一定深度处的节点所代表的局面进行评价优劣的估计值．静态估值函数因游戏而异．

如果对自己（MAX）有利，则取正值，越大，表示对我方越有利。等于正无穷大时，表示我方必胜。如果对自己不利，则取负值．越小，表示对我方越不利。等于负无穷大时，表示对方必胜。10/28/202365极小极大过程基本思想：当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度以内的所有状态，计算所有叶节点的静态估值函数值。然后逆向计算：对于我方要走的节点（MAX节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（MIN节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。10/28/202366极小极大原则

MAX节点在其MIN子节点的倒推值中选max；

MIN节点在其MAX子节点的倒推值中选min倒推值在极小极大过程中，第i层节点根据第i+1层节点的值使用极小极大原则而获得的值。极小极大过程1.按宽度优先生成0至L层所有节点。2.使用静态估值函数计算第L层节点的函数值。3.按极小极大原则计算各层节点的倒推值，直到求出初始节点的倒推值为止。实现该倒推值的走步就是相对好的走步。10/28/202367例10/28/202368MINIMAX过程①T:＝（s，MAX），OPEN:＝（s），CLOSED:＝（）；开始时树由初始节点构成，OPEN表只含有s。②LOOP1:IFOPEN＝（），THENGOLOOP2；③n:＝FIRST（OPEN），REMOVE（n，OPEN），

ADD（n，CLOSED）；④IFn可直接判定为赢、输或平局

THENe(n):＝∞∨－∞∨0，GOLOOP1ELSEEXPAND（n）→{ni}，ADD（{ni}，T）

IFd（ni）＜L,THENADD（{ni}，OPEN），GOLOOP1

ELSE计算e(ni)，GOLOOP1；ni达到深度L，计算各端节点e值。

10/28/202369⑤LOOP2：IFCLOSED＝NILTHENGOLOOP3

ELSEnp:＝FIRST（CLOSED）；⑥IFnp∈MAX，且对np的任意子节点nci，e（nci）都有值

THENe（np）:＝max{e（nci）}，REMOVE（np，CLOSED）；若MAX所有子节点均有值，则该MAX取其极大值。

IFnp∈MIN，且对np的任意子节点nci，e（nci）都有值

THENe（np）:＝min{e（nci）}，REMOVE（np，CLOSED）；若MIN所有子节点均有值，则该MIN取其极小值。⑦GOLOOP2；⑧LOOP3：IFe（s）有值,THENEXIT（END∨M（Move，T））；若s有值，则结束或标记走步。10/28/202370在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。设程序方MAX的棋子用（×）表示对手MIN的棋子用（○）表示

MAX先走。静态估计函数e(p)：(1)若p是MAX获胜的格局，则e(p)＝∞；(2)若p是MIN获胜的格局，则e(p)＝－∞。(3)若p对任何一方来说都不是获胜的格局，则

e(p)＝（所有空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角线）的总数－（所有空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角线）的总数）一字棋游戏10/28/202371

例如，当p的格局如上图时，则可得e(p)＝6－4＝2；设考虑走两步的搜索过程。利用棋盘对称性的条件，则第一次调用算法产生的搜索树如图4.8所示.10/28/202372图4.8一字棋第一阶段搜索树

10/28/202373图4.9一字棋第二阶段搜索树

10/28/202374图4.10一字棋第三阶段搜索树

10/28/202375极小极大过程的问题把搜索的产生过程与尖端节点的静态估值过程完全分开．在搜索树完全产生之后，才开始对尖端节点的估值．这种分开进行的方式导致博弈树搜索的低效率：节点数将随着搜索深度的增加呈指数增长。这极大地限制了极小极大搜索方法的使用。解决方法：让搜索树的产生过程与静态估值与返回值的过程同时进行，在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数，从而使搜索效率大为提高。----α-β过程10/28/202376三、博弈搜索的α-β过程最早在1956年JohnMcCarthy构思了α-β搜索，但他并没有发表。1958年Newell等人开发的国际象棋程序NSS使用了一个简化版本的α-β搜索，它是第一个使用α-β搜索的国际象棋程序。根据Nilsson,1971所述，(Samuel,1959,1967)的西洋跳棋程序也使用了α-β搜索。描述α-β搜索的论文最早发表于20世纪60年代（Hart和Edwards,1961;Brudno,1963;Slagle,1963b)。Slagle和Dixon于1969年在他们的玩Kalah游戏的程序中第一次实现了完整的α-β搜索。α-β搜索也被用于JohnMcCarthy的一个学生写的Kotok国际象棋程序中。Knuth和Moore(1975)提供了α-β搜索的历史，及其正确性证明与时间复杂性分析。1982年Pearl证明了α-β搜索在所有固定深度的博弈树搜索算法中是渐进最优的。IBM研制的“深蓝”国际象棋程序采用的就是这种搜索算法，该程序战胜了卡斯帕罗夫。10/28/202377某博弈问题示意图10/28/202378图4.10一字棋第三阶段搜索树

10/28/202379图一字棋第一阶段α-β剪枝方法

10/28/202380（1）α剪枝：如果一个MIN节点的β值小于或等于它的某一个MAX祖先节点的α值，则剪枝发生在该MIN节点之下：终止这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个β值。

（2）β剪枝：如果一个MAX节点的α值大于或者等于它的某一个MIN祖先节点的β值，则剪枝发生在该MAX节点之下．终止这个MAX节点以下的搜索过程。该MAX节点的最终返回值可以置成它的α值．剪枝规则10/28/202381图4.11α-β搜索过程的博弈树10/28/202382（1）比较都是在极小节点和极大节点间进行的，极大节点和极大节点的比较，或者极小节点和极小节点间的比较是无意义的。（2）在比较时注意是与“祖先层"节点比较，不只是与父辈节点比较。当然，这里的"祖先层"节点，指的是那些已经有了值的节点。

（3）当只有一个节点的"固定"以后，其值才能够向其父节点传递。

（4）α-β剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的，α-β剪枝并没有因为提高效率，而降低得到最佳走步的可能性。

（5）在实际搜索时，并不是先生成指定深度的搜索图，再在搜索图上进行剪枝。如果这样，就失去了α-β剪枝方法的意义。在实际程序实现时，首先规定一个搜索深度，然后按照类似于深度优先搜索的方式，生成节点。在节点的生成过程中，如果在某一个节点处发生了剪枝，则该节点其余未生成的节点就不再生成了。进行α-β剪枝注意的问题：10/28/202383若以最理想的情况进行搜索，即对MIN节点先扩展最低估值的节点（若从左向右顺序进行，则设节点估计值从左向右递增排序），MAX先扩展最高估值的节点（设估计值从左向右递减排序），则当搜索树深度为D，分枝因数为B时，若不使用α-β剪枝技术，搜索树的端节点数BD；若使用α-β剪枝技术．可以证明理想条件下生成的端节点数最少，有ND=2BD/2-1（D为偶数）

ND=B(D+1)/2+B(D-1)/2-1（D为奇数）

比较后得出最佳α-β搜索技术所生成深度为D处的端节点数约等于不用α-β搜索技术所生成深度为D／2处的端节点数。因此，在使用相同存储空间的条件下，α-β过程能把搜索深度扩大一倍．α-β剪枝的效率10/28/202384以上介绍的各种博弈搜索技术可用于求解所提到的一些双人博弈问题。但是这些方法还不能全面反映人们弈棋过程实际所使用的一切推理技术，也未涉及棋局的表示和启发函数问题。例如一些高明的棋手，对棋局的表示有独特的模式，他们往往记住的是一个可识别的模式集合，而不是单独棋子的具体位置。此外有些博弈过程，在一个短时期内短兵相接，进攻和防御的战术变化剧烈，这些情况如何在搜索策略中加以考虑。还有基于极小极大过程的一些方法都设想对手总是走的最优走步，即我方总应考虑最坏的情况，实际上再好的选手也会有失误，如何利用失误加强攻势，也值得考虑。再一点就是选手的棋风问题。总之要真正解决具体的博弈搜索技术，有许多更深入的问题需要作进一步的研究和探讨。10/28/2023851．用可分解产生式系统求解问题时，求解过程可归结为对一个隐含的与/或图进行搜索。初始状态对应于与或图的根节点，规则对应于k-连接符，结束条件的数据库对应于一组终止节点集合，搜索策略的任务就是找到从初始节点s到一组终止节点集N的一个解图。解图及其费用值可由递归定义给出。

2．若s→N集存在解图，当h（n）≤h*（n）且h（n）满足单调限制条件时，AO*算法一定能找到最佳解图，即在这种情况下，AO*具有可采纳性。

小结10/28/2023863．博弈问题可用产生式系统来描述，求解过程也是一个对与/或图进行搜索的问题。针对双人完备信息的博弈问题，通常可行的实用策略是搜索被限制在一定的范围，搜索的目标是确定一步好棋，等对手回手后，再继续搜索。MINIMAX就是按这种思想建立的过程，而α-β过程是MINIMAX过程的改进，并可提高效率。10/28/202387多人游戏中的最优决策许多流行的游戏允许多于两个的参加者。让我们来看看如何把极小极大思想推广到多人游戏中。这在技术上看比较直接。首先我们需要把每一个上的单一值替换成一个向量值。例如在一个三人A,B,C的游戏中，每个节点都与一个向量(vA,vB,vC)相关联。对于终止状态，这个向量给出了从每个人角度出发得到的状态效用值（在二人零和游戏中，由于效用值总是正好相反，所以二维向量可以简化为一个单一值）。简单的实现这个方法是让评估函数返回一个效用向量值。10/28/202388考虑在图中的博弈树上标为X的节点。在这个状态，轮到游戏者C选择做什么。两种选择导致的终止状态的效用值向量分别为(vA=1,vB=2,vC=6)和(vA=4,vB=2,vC=3)。由于6大于3，所以C应该选择第一种走法。1，2，61，2，61，2，61，5，26，1，21，5，25，4，51，2，66，1，24，2，37，4，15，1，11，5，25，4，57，7，1行棋方ABCA图有三个游戏者(A,B,C)的博弈树中的前三层，节点标有从每个游戏者出发的值。根节点标示了最佳步骤10/28/202389任何玩过诸如Diplomacy（外交游戏）这样的多人游戏的人很快会意识到这比双人游戏要复杂得多。多人游戏通常会涉及在游戏者之间出现正式的联盟的情况。随着游戏的进行，联盟也建立或者解散。我们如何去理解这种行为呢？是否在多人游戏中对每一个游戏者来说联盟是最优策略的一个自然结果？看起来可能是这样的。例如A和B相对比较弱，而C很强。那么对于A和B而言，他们一起进攻C比等C逐个消灭它们要好，这样通常是最优的。如此，合作从纯自私的行为中涌现出来。当然一旦C在联合攻击下被削弱，联盟就失去了价值，于是A或B就会破坏协议。某些情况下，外在的联盟仅仅是把将要发生的具体化。在另一些情况下，违反盟约会损害社会声誉，所以游戏者要在毁约得到直接利益和被认为不可信任而带来的长期弊端之间进行权衡。10/28/202390如果游戏是非零和的，那么合作也可能发生在两人游戏中。例如，假设有一个终止状态的效用值向量是（vA=1000,vB=1000)，并且1000对于两个游戏者都是最高的可能效用值。那么双方的最优策略就是做一切可能的招数来达到这个状态—也就是说，双方会自动合作来达到共同渴望的目标。10/28/202391产生式系统表示及其搜索方法基本内容产生式系统概念基本工作过程（ProcedurePRODUCTION）产生式系统工作方式：正向、反向、双向产生式系统控制策略不可撤回式：爬山函数试探式：回溯：BACKTRACK、BACKTRACK1

图搜索：GRAPHSEARCH、A算法、A*算法特殊产生式系统可交换、可分解(ProcedureSPLIT)可分解产生式系统的搜索策略：与或图的启发式搜索算法AO*

博弈树搜索MINIMAX过程、α-β过程10/28/20239210/28/20239310/28/202394第三部分逻辑表示及推理方法常用的知识表示方法：非结构化方法逻辑表示法QA3,STRIPS,DART,MOMO产生式系统DENDRAL，MYCIN结构化方法框架语义网络过程式知识表示法10/28/202395第五章谓词演算（复习）数理逻辑思想的起源：Leibnitz之梦产生的历史：Boole的工作、Frege的工作发展的现实：计算机学科的基础（软件到硬件）古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。命题逻辑又是谓词逻辑的一种简单情形。逻辑研究的基本内容语法语言部分：基本符号集、公式形成规则推理部分：公理集、推理规则语义语法和语义之间的关系：可靠性、完备性基本问题逻辑表示下的判定问题10/28/202396一、命题逻辑1命题一句有真假意义的话。用大写英文字母P，Q，…，P1，P2，…，表示。

例：上海是中国最大的城市。今天是星期日。所有素数都是奇数。1+1=2。我不会解答这道题。别的星球上有生物。长春今天下雪。如果太阳从西方升起，你就可以长生不老。

严禁吸烟。今天的温度有多少度？全体起立！今天好冷啊！我正在说谎。10/28/2023972真值

如果一个命题是真的，就说它的真值是T；

如果一个命题是假的，就说它的真值是F。

T和F统称为命题的真值。

也用T代表一个抽象的真命题，用F代表一个抽象的假命题。

10/28/2023983联结词～、∨、∧、→、↔设P是一个命题，命题“P是不对的”称为P的否定，记以～P，读作非P。例.Q:张三是好人。～Q：张三不是好人。语义规定：～P是真的当且仅当P是假的。设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以P

Q，读作P析取Q。例.

P：今天下雪，Q：今天刮风，

P

Q：今天下雪或者刮风。语义规定：P

Q是真的当且仅当P,Q中至少有一个为真。10/28/202399设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以P

Q，读作P合取Q。例.P：2

2=5，Q：雪是黑的，

P

Q：2

2=5并且雪是黑的。语义规定：P

Q是真的当且仅当P和Q都是真的。设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以P

Q。例.P：f(x)是可微的，

Q：f(x)是连续的，

P

Q：若f(x)是可微的，则f(x)是连续的。语义规定：

P

Q是假的当且仅当P是真的而Q是假的。10/28/2023100设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以P

Q。语义规定：

P

Q是真的当且仅当P，Q或者都是真的，或者都是假的。例P：a2+b2=a2，

Q：b=0，

P

Q：a2+b2=a2当且仅当b=0。五种逻辑联结词的优先级按如下次序递增：

，

，

，

，～例.符号串P

Q

R

Q

～S

R

意味着： ((P

(Q

R))

(Q

((～S)

R)))10/28/20231014复合命题用联结词将简单命题连接的结果。5原子命题的抽象。用大写的英文字母P，Q，R，…等表示。6文字原子或原子的否定。7子句有限个文字的析取式称为一个子句。特别，没有文字的子句称为空子句，记为

。只有一个文字的子句称为单元子句。8短语有限个文字的合取式称为一个短语。10/28/2023102复合命题的抽象公式的形成规则--是如下定义的一个符号串：

(1)原子是公式；

(2)F、T是公式；

(3)若G，H是公式，则(～

G)，(G

H)， (G

H)，(G

H)，(G

H)是公式；

(4)所有公式都是有限次使用(1)，(2)，(3)

得到的符号串。9公式10/28/2023103设G是命题公式,A1,…,An是出现在G中的所有原子。指定A1,…,An的一组真值,则这组真值称为G的一个解释。设G是公式，I是G的一个解释，G在I下的真值记为TI(G)。例.G=P

Q，设解释I，I’如下：

I： I’：

则TI(G)=T，TI’(G)=F

注意：该例子中写成G=T或G=F是错误的！10解释PQ

TT

PQ

TF

10/28/202310411真值表

公式G在其所有可能的解释下所取真值的表，称为G的真值表。有n个不同原子的公式，共有2n个解释。

12恒真公式公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的.10/28/202310513恒假公式

公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的.14可满足公式

公式G称为可满足的，如果它不是恒假的。G是恒真的iff

～

G是恒假的。G是可满足的iff

至少有一个解释I，使G在I下为真。若G是恒真的，则G是可满足的；反之不对。如果公式G在解释I下是真的，则称I满足G；

如果G在解释I下是假的，则称I弄假G。

10/28/2023106例.考虑G1=～(P→Q)→P，G2=(P→Q)P，

G3=P

～P。PQG1PQG2PG3FFTFFFFFFTTFTFTFTFTTFFTTTTTT10/28/202310715判定问题能否给出一个可行方法，对任意的公式，判定其是否是恒真公式。命题逻辑可判定？原因？因为一个命题公式的原子数目有限(n)，从而解释的数目是有限的(2n)，所以命题逻辑的判定问题是可解的(可判定的，可计算的).10/28/202310816公式等价称公式G，H是等价的，记以G=H，如果G，H在其任意解释I下，其真值相同。公式G，H等价iff

公式G

H恒真。

基本等价式1) (G

H)=(G

H)

(H

G)；2) (G

H)=(～G

H)；3) G

G=G，G

G=G；(等幂律)4) G

H=H

G，G

H=H

G； (交换律)5) G

(H

S)=(G

H)

S，

G

(H

S)=(G

H)

S；(结合律)10/28/20231096) G

(G

H)=G，G

(G

H)=G；(吸收律)7) G

(H

S)=(G

H)

(G

S)，

G

(H

S)=(G

H)

(G

S)；(分配律)8) G

F=G，G

T=G；(同一律)9) G

F=F，G

T=T；(零一律)10)～(G

H)=～G

～H，

～(G

H)=～G

～H。(DeMorgan律)11)G

～G=T；G

～G=F（互补律）12)～～G=G（双重否定律）10/28/202311017公式的蕴涵设G，H是两个公式。称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作G

H。公式G蕴涵公式Hiff

公式G

H是恒真的。设G1,…,Gn，H是公式。称H是G1,…,Gn的逻辑结果(或称G1,…,Gn共同蕴涵H)，当且仅当(G1

…

Gn)

H。例如，P，P

Q共同蕴涵Q。

10/28/2023111基本蕴涵式

P

Q

PP

Q

QP

P

QQ

P

Q～P

(P

Q)Q

(P

Q)～(P

Q)

P10/28/2023112基本蕴涵式

～(P

Q)

～QP，Q

P

Q～P，P

Q

QP，P

Q

Q～Q，P

Q

～PP

Q，Q

R

P

RP

Q，P

R，Q

R

R

10/28/202311318范式有限个短语的析取式称为析取范式；有限个子句的合取式称为合取范式。特别，一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。例如，P，P

Q，P

Q，(P

Q)

(～P

～Q)是析取范式。

P，P

Q，P

Q，(P

Q)

(～P

R)是合取范式。

10/28/2023114化范式方法：步1.

使用基本等价式，将G中的逻辑联结词

，

删除。步2.

使用～(～H)=H和摩根律，将G中所有的否定号～都放在原子之前。

步3.

反复使用分配律，即可得到等价于G的范式。

10/28/202311519演绎设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列：

G1,G2,…,Gk

其中，Gi

（1≤i≤k）或者属于S，或者是某些Gj

(j<i)的逻辑结果。并且Gk就是G。称公式G为“此演绎的”逻辑结果，或称从S演绎出G。有时也记为S

G。

10/28/2023116例.设S={P

Q，Q

R，P

M，～M}则下面的公式序列:

～M，P

M，～P，P

Q，Q，Q

R，R

就是从S推出R的一个演绎。演绎方法的可靠性与完备性设S是公式集合，G是一个公式。于是，从S演绎出G的充要条件是G是S的逻辑结果。10/28/2023117命题逻辑的缺陷

把问题看成一个个孤立的命题，忽略了问题之间的联系，无法描述客观事物的结构，不能反映某些重要的常见的逻辑思维过程。1繁琐例.表述集合个体性质及相互关系

S={1,2,…,50}表述S中元素大于3这样一个性质，需要1>3,2>3,…,50>3等50个命题。10/28/20231182不能描述问题间的逻辑联系例如，逻辑学中著名的三段论：

P：凡人必死

Q：张三是人

R：张三必死

在命题逻辑中：应该有(P

Q)

R，从而公式(P

Q)

R应该是恒真的。显然该公式不是恒真的，解释{P，Q，～R}就能弄假该公式。10/28/2023119原因：命题R是和命题P,Q有关系的，只是这种关系在命题逻辑中无法表示。因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，这正是谓词逻辑所要研究的问题。10/28/2023120为了表示出这三个命题的内在关系，需要引进谓词的概念。例如，在前面的例子“张三是人”中的“是人”是谓语，称为谓词，“张三”是主语，称为个体。10/28/2023121二、谓词逻辑

1谓词可以独立存在的物体称为个体。如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常指一个命题里的思维对象。设D是非空个体名称集合，定义在Dn上取值于{T，F}上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。10/28/2023122例.D={2,3,4}设P(x)：x大于3，则P(x)为一元谓词。指定元素--命题：P(2)=F,P(3)=F,P(4)=T设P(x,y)：x大于y,则P(x,y)为二元谓词。指定元素--命题：P(2,3)=F,P(4,2)=T设P(x,y,z)：若x+y-1=z，则P(x,y,z)为T，否则为F。则P(x,y,z)为三元谓词。指定元素--命题：P(2,3,4)=T,P(4,2,2)=F10/28/2023123例.用谓词的概念可将三段论做如下的符号化：令

H(x)表示“x是人”，

M(x)表示“x必死”。则三段论的三个命题表示如下：

P：H(x)

M(x)

Q：H(张三)

R：M(张三)10/28/2023124若想得到“命题”P的否定“命题”，应该就是“命题”～P。但是，

～P=～(H(x)

M(x))

=～(～H(x)

M(x))

=H(x)

～M(x)亦即，“命题”P的否定“命题”是“所有人都不死”。这和人们日常对命题“所有人都必死”的否定的理解，相差得实在太远了.10/28/2023125原因－－命题P的确切意思应该是：“对任意x，如果x是人，则x必死”。但是

H(x)

M(x)

中并没有确切的表示出“对任意x”这个意思，亦即H(x)

M(x)不是一个命题。因此，在谓词逻辑中除引进谓词外，还需要引进“对任意x”这个语句，及其对偶的语句“存在一个x”。

10/28/20231262量词定义语句“对任意x”称为全称量词，记以

x；语句“存在一个x”称为存在量词，记以

x。这时，命题P就可确切地符号化如下：

x(H(x)

M(x))

命题P的否定命题为：

～

P=～(

x(H(x)

M(x)))=

x(H(x)

～M(x))

亦即“有一个人是不死的”。这个命题确实是“所有人都要死”的否定。

三段论的三个命题，在谓词逻辑中是如下这样表示的：

P：

x(H(x)

M(x))

Q：H(张三)

R：M(张三)10/28/2023127量词的语义规定

xG(x)取T值

对任意x

D，G(x)都取T值；

xG(x)取T值

至少有一个x0

D，使G(x0)取T值语义上，当D={x0,x1,…}是可数集合时，

xG(x)等价于G(x0)

G(x1)

…

xG(x)等价于G(x0)

G(x1)

…10/28/2023128例.将下列命题符号化：１)一切事物都是发展变化的

xF(x)其中F(x)：x是发展变化的２)存在着会说话的机器人

x(F(x)G(x))其中F(x)：x会说话G(x):x是机器人如果没有明确给出个体域，则认为个体域为一切事物。10/28/20231293)每个计算机学院的学生都学离散数学。D：全校学生集合P(x)：x是计算机学院的学生R(x):x学离散数学

x(P(x)→R(x))4）存在着偶素数D：正整数集合E(x)：x是偶数P(x)：x是素数

x(E(x)P(x))10/28/20231305)每个人都会犯错误R(x):x是人P(x):x会犯错误

x(R(x)→P(x))10/28/20231313约束变量、自由变量

在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串(公式)中，称变量的出现是约束的，当且仅当它出现在使用这个变量的量词范围之内；称变量的出现是自由的，当且仅当这个出现不是约束的。

称变量是约束的，如果至少有一个它的出现是约束的；称变量是自由的，如果至少有一个它的出现是自由的。例如，

x(P(x，y)

Q(x，z))

R(x