命题逻辑的计算机实现

2013-08-15德州学院信息管理学院李亚男郑文艳

电子世界 2013年19期

德州学院信息管理学院李亚男郑文艳

1.离散数学基础

数理逻辑研究的中心问题是推导，而推理的前提和结论都是可以判断真假的陈述句，即命题。因此命题是逻辑推导的基本单位。在命题逻辑中，对命题的成分不再细分，因而命题也是命题逻辑中的最小的研究单位。根据命题的结构形式，可以把命题分为原子命题和复合命题。简单的说，原子命题是能够判断真假的陈述句，而复合命题是由原子命题组成的。

命题公式由以下四条约定进行递归定义：

（1）单个命题变元是命题公式。

（2）如果A是命题公式，那么「A也是命题公式。

（3）如果A，B是命题公式，那么（A∧B），（A∨B），（A→B）和（A←→B）都是命题公式。

（4）经过有限次的使用（1）、（2）、（3）所组成的有意义的符号串都是命题公式。

2.主要功能模块设计与实现

整个功能模块包括文本字符分析模块，字符的集合表示模块，集合运算模块以及显示模块，此处仅以文本字符分析模块为例进行详细说明。

本模块的主要功能是将欲处理的命题公式从对话框提取出来，然后放入相应的变量里面，为第一遍扫描和第二遍扫描做准备。

2.1 第一遍扫描

（1）主要目的

统计出所输入的命题公式中命题变元的个数并将命题变元按顺序存入容器，为字符的集合表示模块做准备，同时将操作符统一变成一个，为建立语法树做准备。

（2）实现方法

从变量的第一个字符开始，依次遍历到字符串变量的最后一个字符。如过遇到的是字符则首先判断该字符是否在字符容器里面，若在字符容器里面，则仅将该字符放入字符队列里面，若不在字符容器里面则不仅将该字符放到字符队列里面还要将该字符放到字符容器里面。如遇到的是操作符，则首先判断是那种操作符，如果是否定词或析取词或合取词，则将其直接放入字符队列，如若是条件词或双条件词，首先去掉一个或两个字符然后再放入字符队列。在这里字符容器主要用于存放命题变元并且统计命题变元的个数，字符队列用来存放第一遍扫描的结果。因为在命题公式里面，有的操作符不只一个字符，如双条件命题连接词（<->）是有3个字符表示的，在这里将其后两个字符去掉，仅留第一个字符“<”放入字符队列。条件连接词（->）像双条件命题连接词一样，仅将“-”放入字符队列，为第二遍扫描建语法树提供方便。

2.2 第二遍扫描

（1）主要目的

建立语法树，为集合运算作准备。

（2）实现方法

准备四个栈，分别是两操作数栈和两个运算符栈。两个操作数栈分别记为操作数SA栈和操作数SB栈，其中操作数SB栈为辅助栈，操作数SA栈用来存放第二遍扫描后语法树中的操作数。两个运算符栈分别记为运算符YA栈和运算符YB栈，其中运算符YB栈为辅助栈，运算符YA栈用来存放第二遍扫描后语法树中的运算符。

首先在运算符YA栈中放入字符串起始符号（如#），然后从字符队列里面依次取字符，判断是否为命题变元，若是则放入操作数SA栈，若不是字符而是运算符则首先取运算符YA栈的栈顶元素Top，令该运算符与刚取出的栈顶元素Top比较运算符的优先级，若其优先级大于栈顶运算符则将该运算符进运算符YA栈，若相等则运算符YA栈弹出一元素（括号匹配），若其优先级小于栈顶运算符则弹出运算符YA栈顶元素，让该元素进运算符YB栈。接着判断刚弹出的运算符是几目运算符，根据运算符的目数从操作数SA栈弹出相应个数的操作数进操作数SB栈，这样循环下去直到字符队列中的字符都被遍历一次。

在完成上述操作后，最后令操作数依次出操作数SB栈，进操作数SA栈；令运算符依次出运算符YB栈进运算符YA栈。

到此第二此扫描后建立的语法树就存于操作数SA栈和运算符SB栈中，集合运算模块将用到这两个栈里的数据。

3.重要算法

整个过程涉及到三个重要算法，字符到小项下标的编码，整型数到字符的转化，以及小项下标到主析取范式的译码。此处仅以字符到小项下标的编码为例进行详细说明。

对于给定的字符ch，首先遍历存放命题变元的数组ch_table[]，确定ch在数组ch_table[]中的下标ch_index（例如：ch_table[]中的命题变元为P，Q，R，T，则字符Q所对应的下标就是2）。建立自增量conbase=pow（2，variablenum-ch_index-1），用于下标基数base的增加。开始基变量设为base=0-conbase，其后每循环一次基变量自增2*conbase，在每次循环中紧接base后的conbase个整数都是该字符所对应的小项下标。