命题逻辑判定系统中基本真值矩阵的生成算法.pdfVIP

( ) 第 19 卷第 1 期 甘肃联合大学学报 自然科学版 Vol . 19 No . 1 　 ( ) 2005 年 1 月 Journal of Gansu Lianhe University Natural Sciences J an 2005 　 ( ) 　　文章编号 : 1672691X 2005 命题逻辑判定系统中基本真值矩阵的生成算法 张会凌 (甘肃联合大学 数学与信息学院 ,甘肃 兰州 730000) 摘 　要 : 给出了求含任意 n 个命题变元的命题公式F 的基本真值矩阵的四个算法 ,从而为利用计算机处理命题 逻辑的判定问题奠定了核心基础. 关键词 :命题逻辑 ;基本真值矩阵 ;递归矩阵生成算法 ;数列生成算法 ;移位生成算法 中图分类号 :TP399 ;TP301 　　　文献标识码 :A 判定问题, 第一步总要先列出一个由命题变元的 1 　问题的提出 所有可能的取值组成的表. 命题逻辑的判定问题包含计算给定命题公式 设所讨论的命题公式中共有 m 个命题变元 的真值并列出其真值表; 判断一个命题公式是否 ( ) P1 , P2 , …, Pm m 是正整数 . 由于每个命题变元 为永真式, 是否为永假式, 是否是可满足的; 求给 的真值每次只能在 0 和 1 二者 中取一, P1 , P2 , 定命题公式的主合取范式与主析取范式; 判断由 …, Pm 的任意一种取值就构成一个由0 和 1 组成 若干个假设推出一个结论的论证的有效性等. 这 的 m 个元素的可重复排列. 所有这些排列共有 些问题构成了命题逻辑的主要内容. 迄今为止, 解 m m 2 种. 以每个排列作为一行, 可构成一个 2 ×m 决判定问题的方法主要有两种. 一种是利用重写 矩阵, 也就是高级编程语言中的一个二维数组, 如 ( ) 规则 rewrite rule 进行等价推演, 另一种方法是真 下表所示. 为了方便, 称其为基本真值矩阵, 记为 值表法. Am . 对于任意一个给定的命题公式, Am 的任一行 当命题变元的个数较多且所给的命题公式的 ( ) 都是一个确定的真值指派 赋值 . 结构比较复杂时, 这两种方法都显得不够理想. 此 正确计算出 Am 并让