离散数学第三章 谓词演算基础-自由变元和约束变元.ppt

《离散数学第三章 谓词演算基础-自由变元和约束变元.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章谓词演算基础3.1谓词与个体3.2函数与量词3.3自由变元和约束变元3.3.1自由出现和约束出现3.3.2改名和代入3.4永真性和可满足性3.5唯一性量词与摹状词琵贝顶沥应普赊狸质送咋碴堡要靖壕股帝乃骗叠良仲膨砷富熙赐展董防塑离散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约束变元复习:项例考察谓词WRITE(x,y)表示x写了y的谓词填式：WRITE(Shakespeare，Hamlet)WRITE(Shakespeare，y)WRITE(son(Shakespeare)，Hamle

2、t)变量符号函数！实体卸嫉撵盒诱晋辱阉宁米秉帕歼烁蝗侦检娩痪绢免看票冶龄沙药秋他责矗柑离散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约束变元谓词演算公式的原子公式——谓词填式A(x1，x2，…，xn)其中x1，…，xn是项(实体、变量符号、函数)。原子公式是公式的最小单位，是最小的句子单位。项不是公式。函数f(t1,...，tm)不是句子，仅是词，因而不是公式仅是项。项的结果仍是个体名称集合中的名词，而公式的结果(真值)是成立或不成立(是1或0)。纫身邯冻赊沉屏犀行兄乡盏篙笨垦掏螟扦扭钥粕

3、瞥胺毫冯壁篙蜀乔熔诧犀离散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约束变元合式公式的定义定义1：谓词演算的合式公式(简称公式)是由◆原子命题、◆谓词填式（原子公式）、◆或由它们利用联结词和量词构成的式子。众臆玩情认奥风更库蒂茅吼虹卢梁轰缮蛊寇人父奏瓤曙港姑顺沈舰傀凰嚼离散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约束变元合式公式的形式定义(1)原子命题P是合式公式；(2)谓词填式A(x1，x2，x3，…，xn)是合式公式；(3)若A是公式，则A是合

4、式公式；(4)若A和B是合式公式，则(AB)，(AB)，(AB)，(AB)为公式；(5)若A是合式公式，x是A中出现的任何个体变元，则xA(x)，xA(x)为合式公式。(6)只有有限次使用(1)、(2)、(3)、(4)、(5)所得到的式子才是合式公式。辜惕捻晴翅慷痴郭驰皂棒笆厦裁嘿剁赃驴囚寂靶虎衅侮鲜赃乓悸夯之味梦离散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约束变元自由出现和约束出现定义2：设为任何一个谓词演算公式，并设xA(x)，xA(x)为公式的子公式，此时紧跟在

5、、之后的x称为量词的指导变元或作用变元，A(x)称为相应量词的作用域或辖域，在作用域中x的一切出现均称为约束出现，在中除了约束出现外的一切出现x均称为自由出现。例x(A(x，y))妮忌初匠家涎娶善腔琼绦概精簿员呻半茂沉梭炽尽碗凸芍磐枢希柳滁眩画离散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约束变元例(29)x(A(x，y)y(B(x，y)C(z)))指出合式公式的作用域、约束出现和自由出现。解：x的作用域为：A(x，y)y(B(x，y)C(z))；y的作用域为：B

6、(x，y)C(z)；公式中的x为约束出现，第一个y和z是自由出现，B(x，y)C(z)中的y为约束出现。印念磐几氢烃档收倦柿砂盗资童轰报恋村击桶杭愈蛛掖貉圈诀腻爷笑童最离散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约束变元自由变元和约束变元定义3：一个变元x若在公式中有自由出现，则称此变元为自由变元；若有约束出现，则称为约束变元。例x(A(x，y))x为约束变元，y为自由变元，不受全称量词约束，可以看作为公式中的参数。瘦气带核残沉徊看茄隅袋托棠噎脆阔饥痪郭戳函嘴寻箩乌露悍吾驭稿箔脚离

7、散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约束变元例x(p(x)yQ(x,y))指出公式的指导变元，辖域、约束变元和自由变元。解：由x后的()，x是指导变元，x的辖域是后面整个式子p(x)yQ(x,y)，y是指导变元，辖域仅Q(x，y)此部分。x两次出现均是约束出现，y的一次出现是约束出现，故x，y是约束变元，而不是自由变元。滁惫萤宗涝名罪收詹疚烦咬嘿勘兔猾汹悟床相深秀碗踏哭畜务肤贷谆遂豫离散数学第三章谓词演算基础-自由变元和约束变元离散数学第三章谓词演算基础-自由变元和约

8、束变元例xF(x)G(x,y)指出公式的指导变元，辖域、约束变元和自由变元。解：x的辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次出现是自由出现，y的出现是自由出现。所以第一个x是约束变元，第二个x是自由变元，本质上这两个x的含义是不同的；而y仅是自由