PM讲义-第2章-数理逻辑基础.pptVIP

姜秀柱 计算机学院 程序设计方法学 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 第2章 数理逻辑基础 提纲 命题 谓词 自由变量和受约束变量 文本替换 数组的解释 Objectives： 回顾基本概念 掌握文本替换方法 理解数组的解释方法 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 第2章 数理逻辑基础 一、命题 1. 定义：命题是按下列规则构成的： T和F是命题 一个标识符是命题 如果b是一个命题，那么（?b）是命题 如果b和c是命题，那么（b?c）、（ b ? c ）、 （ b ? c ） 、 （ b = c ） 是命题。 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 一、命题 2. 一种状态下命题的值 定义1：状态是标识符集到值T和F上的一个函数。例： 令状态s是由{( a,F ) ，(b,T)，(y,T)}定义的函数，用s(a)=F, s(b)=T 定义2：如果命题e中的每个标识符在状态s下都有对应的值T或F，则称命题e在状态s下是有意义的。 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 一、命题 定义3：设命题e在状态s中是有意义的，那么在状态s下命题e的值s(e)是这样得到的：将命题e中的所有标识符用它在状态s中的值代入，这样就变成一个常量命题，由此计算出命题的值。例： 令： S={（b,T），(c,F)}, e= ?b ? c 则：S（e）= ?T ? F = F 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 一、命题 3. 作为状态集的命题 一个命题值的真假完全由状态决定 可以用命题描述状态（集） 一个状态集对应多个命题。即用命题描述状态是不唯一的 例：两个状态{(a,F), (b,T),(c,T),(d,F)}和{(a,T),(b,T),(c,F),(d,F)}可以用命题(b?c??d) ? (a?b)来表示。 用命题T表示状态集的全集，用命题F表示空集。 S1 S2 S3 Sn 命题1 命题n 使命题成立 使命题成立 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 二、谓词Predicates 1. 谓词的描述 将命题进行下面的扩展就成为谓词： 将命题中标识符由任何具有T和F值的表达式（如xy）替代，这样的表达式称为原子表达式 在命题中引进量词?、?等。 例: (a?b?c) ==》(x=y)?(yz)?(x+yz) (?i: m=in:x*i0) 2. 谓词的求值 例：令S={(x,1),(y,3),(z,5),(b,T)} e = ((x=y) ?(yz) ?(x+yz) ?b) 则：S(e)= (1=3) ?(35) ?(1+35) ?T)=T 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 三、量词Quantification 1. 存在量词?（Existential Quantification） (?i: m=in: Ei) ? (Em ? Em+1 ?… ? En-1) 读做：“至少存在一个整数i，满足i在m和n-1之间，使得Ei成立” 2. 全称量词?（Universal Quantification） (?i: m=in: Ei) ? (Em ? Em+1 ? … ? En-1) (?i: m=in: Ei) ? ?(?i: m=in: ? Ei) 3. 其它量词： N(计数量词)，?（求和量词），?（连承量词） 讨论： 当m=n时，如何？ 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 四、自由标识符和受约束标识符 对于谓词： (?i: m=in:x*i0) 等价于 (x0 ? m0) ?(x0 ? n=0) 即该谓词的值依赖于m,n,x，而不依赖于i。 把m,n,x,称为自由标识符，而像 i 这样的标识符称为受约束的标识符。 在一个表达式中，一个标识符不可以既是受约束的又是自由的，也不可以同时受到两个不同的量词的约束。例： i0 ? (? i: m=in:x*i0) (? i: m=in:x*i0) ? (? i: m=in:y*i0) 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 五、文本替换（Textual Substitution） 1. 定义： 设E和e是表达式，x是标识符，则记号 表示E中所有自由出现的x同时用e来代换而得到的表达式。 为有效起见，代换必须产生一个语法正确的表达式。 如果代换可能使e中的某个标识符变成受约束的，那么应在代换之前将E中的标识符做适当的改变，以免产生矛盾。 例: 2010年6月8日 姜秀柱 计算机学院 程序设计方法学 * 例 E = u*xy and ?i:0