命题逻辑的计算机实现

【摘要】命题逻辑是逻辑学的基础，要实现逻辑学的计算机处理首先需要实现命题逻辑的计算机处理。由于每个命题公式都与一个由小项下标组成的集合相对应，这样实现命题逻辑的计算机实现就可以通过集合这个工具，首先将命题逻辑转化成集合，然后在计算机上对集合进行表示和处理，最后再将由集合处理的结果还原成命题逻辑的形式输出。本设计主要是基于这一集合理论，在计算机上实现命题逻辑中的两个最基本的处理，命题公式的证明和命题公式的主析取范式求解。

【关键词】命题变元；命题公式；小项；主析取范式

1.离散数学基础

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

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

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

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

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

（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个整数都是该字符所对应的小项下标。

4.总结

由于每个命题公式都有与其等价的主析取范式，主析取范式中每一个小项下标都转化成十进制数，并将这些十进制数放入一个集合中，这个集合就与主析取范式形成了一一对应的关系，进而可以推出每一个命题公式都可以用一个集合来表示，一组等价的命题公式与唯一一个集合形成一一对应的关系。

参考文献

[1]徐凤生，郭长友，刘建军，等.离散数学及其应用[M].北京：机械工业出版社，2006.

[2]蒋立源，康慕宁，冯博琴.编译原理（第三版）[M].西安：西北工业大学出版社，2006.

[3]H.M.Deitel，P.J.Deitel著.施平安，译.C++程序设计教程（第四版）[M].北京：清华大学出版社，2004.

[4]耿素云，屈婉玲，张立昂.离散数学[M].北京：清华大学出版社，2006.

[5]陈意云.编译原理与技术（第2版）[M].合肥：中国科学技术大学出版社，2004.

[6]齐治昌，谭庆平，宁洪.软件工程[M].北京：高等教育出版社，2004.

[7]Michael J Pont.Software Engineering with C++ and CASE Tools.Addison Wesley，2006.

[8]张宏林.Visual C++ 6.0程序设计[M].北京：人民邮电出版社，2008.

作者简介：李亚男，大学本科，现就读于德州学院信息管理学院2012级计算机科学与技术（软件外包）专业。

指导老师：郑文艳。