命题公式真值表的自动生成系统

学校代码10126 学号00847085 分类号密级

本科毕业论文（设计）

学院、系软件学院

专业名称软件工程

年级 08 级

学生姓名解慧

指导教师赵玉兰

2012 年05月27 日

命题公式真值表自动生成系统

作者：解慧

指导教师：赵玉兰摘要命题逻辑是离散数学中重要组成部分之一。真值表是命题逻辑中使用的一类数学表，它是以表格的直观形式表示与判定判断真值和推理有效性的一种逻辑方法。在命题逻辑中运用真值表方法,可以在有限的步骤内直观地显示任意一个真值形式的真值情况,判定任意一个真值形式的一些重要性质,因此,真值表方法是一种有力的逻辑工具。本文采用面向对象Java语言实现了将输入的任一命题公式生成真值表。首先对命题表达式进行解析，得出命题变元及变元的个数，由此得出要给命题变元赋几次不同的逻辑值，然后将中缀表达式转化成后缀表达式，再对后缀表达式进行计算，从而得出命题公式的真值表。

关键词命题公式，真值表，中缀，后缀

Automatic generating system the truth table

of the propositional formula

Author：Xie Hui

Tutor：Zhao Yulan Abstract Propositional logic is an important part of discrete mathematics. The truth table is a class of mathematical table used in the propositional logic, it is a logical method to expressed and judgment to determine the true value and reasoning effectiveness by tabular forms of intuition. In propositional logic using truth table method,visual indication of the true value of any one of the propositional logic in a finite number of steps.So we can determine some important properties of any propositional logic. Therefore, the truth table method is a powerful tool of logic. In this paper, I used object-oriented Java language to generate the truth table when input either a propositional formula. First of all parse the propositional expressions,and come to the propositional variables and variables number,the resulting give propositional variables conferred a number of different logical values. Then,make infix expression into postfix expression,and calculated on the postfix expression to arrive at the truth table of the propositional formula.

Key words Propositional formula, truth table, infix expression, postfix expression

目录

第一章绪论 (1)

1．1 背景 (1)

1．2 意义 (1)

1．3 本文的主要工作 (2)

1．4 本文的组织结构 (2)

第二章命题逻辑的相关知识 (3)

2．1 命题及逻辑联词 (3)

2．2 命题公式的定义 (3)

2．3 命题公式的类型 (4)

2．4 真值表 (4)

第三章命题公式真值表的生成算法的设计和实现 (5)

3．1 命题公式真值表的生成算法的设计 (5)

3．2 命题公式真值表的实现 (7)

3．2．1 界面的实现 (7)

3．2．2 检查输入公式合法性的实现 (9)

3．2．3 提取命题变元及其个数的实现 (12)

3．2．4 逻辑表达式求值的实现 (13)

3．3程序运行结果 (17)

第四章总结 (18)

致谢 (19)

参考文献 (20)

第一章绪论

1．1 背景

数理逻辑是由德国数学哲学家G.W.Leibnitz在17世纪中叶创立的。1847年英国数学家G.Boole在《逻辑的数学分析》中发展了逻辑代数；1879年德国数学家F.L.G.Frege 在《表意符号》中引入了量词、约束变元；1930年奥地利裔美籍数学家K.Godel证明了完全性定理，完善了数理逻辑的基础。在此之间，意大利数学家G.Peano、英国数学家A.de Morgen和B.A.W.Russell等在丰富发展数理逻辑的过程中也做出了骄人的工作。

研究人的思维形式和规律的科学称为逻辑学。由于研究对象和方法的各有侧重而分为形式逻辑、辩证逻辑和数理逻辑。数理逻辑是用数学方法研究推理，是研究推理中前提和结论之间的形式关系的科学。所谓推理就是由一个或几个判断推出一个新判断的思维形式。这里所说的数学方法就是建立一套表意符号体系，对具体的事物进行抽象的形式研究的方法。因此数理逻辑又称符号逻辑。

由于数理逻辑是采用数学的符号化的方法来研究命题间最一般的真值规律，而不涉及判断一个命题本身如何取真取假，抛开命题的具体含义，以抽象的形式讨论逻辑关系，这就导致了数理逻辑中所讨论的命题与自然用语的差异。联结词∧、∨、﹁同构成计算机的与门、或门和非门电路是相对应的。从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。也正是数理逻辑应用于实际特别是应用于计算机学科推动了数理逻辑的发展。

命题逻辑和一阶谓词逻辑是数理逻辑的基础。数理逻辑是研究演绎方法的科学，它从形式结构方面，来研究推理和证明。

命题逻辑是离散数学中重要组成部分之一。真值表是命题逻辑中使用的一类数学表，它是以表格的直观形式表示与判定判断真值和推理有效性的一种逻辑方法。在命题逻辑中运用真值表方法，可以在有限的步骤内直观地显示任意一个真值形式的真值情况，判定任意一个真值形式的一些重要性质，因此，真值表方法是一种有力的逻辑工具。1．2 意义

命题公式推理的自动化，以及自动定理证明特别吸引人们深入研究，这是因为所有

数学以及许多技术领域都可以用一定的形式系统来表述。在这个飞速发展的信息时代使用计算机进行快速而准确的推理已经成为可能。自动推理可以避免令人乏味和容易出错的详细证明构造过程。随着变量个数的增加，真值表的行数也急剧地增一加。依靠人工计算真值表不但工作量大，效率低，更主要的是容易出错。一旦出错，该表就变得毫无用处。命题公式真值表自动生成算法研究可以为研究推理的自动化奠定基础。如果掌握好了它，就等于是在推理自动化的旅程上开了一个好头。

命题逻辑解决的主要问题是：判断命题公式的类型（重言式、矛盾式和可满足式）；求给定命题公式的主析取范式和主合取范式，判断由若干前提推出一个结论的论证的有效性等。解决这类问题主要有两种方法：一种是利用等值演算进行推证，另一种方法是真值表法。利用命题公式的真值表，可以求命题公式的主范式、判断命题公式的类型以及进行命题逻辑的推理等。因此，本文给出的命题公式真值表自动生成算法，为利用计算机解决命题逻辑中的其他问题奠定了基础。

1．3 本文的主要工作

本文以命题公式真值表生成为目标，利用JA V A语言从简单明了的界面接收一个逻辑表达式，得到该逻辑表达式之后，对其进行语法语义检查，检查通过后，解析得到变元的列表及变元的个数，然后根据变元的个数确定真值表的行数，其行数也是所有变元的取值范围的个数，然后再将十进制转化成对应的二进制，然后再根据变元的顺序，从前到后替换各个变元，从而得到含数字的中缀表达式，然后依次将每个逻辑表达式转化成后缀表达式，最后再对后缀表达式进行计算，将命题公式的真值表以友好的方式反映给用户。

1．4 本文的组织结构

第一章介绍命题公式真值表自动生成系统的开发背景、意义、本文的主要工作及组织结构；

第二章回顾了离散数学中命题逻辑的相关知识；

第三章给出命题公式真值表自动生成的算法设计与实现；

第四章是对本次毕业设计的总结。

第二章命题逻辑的相关知识

2．1 命题及逻辑联词

命题是一个非真即假（不可兼）的陈述句，一般用“0”表示假，“1”表示真。真值联结词是指仅仅表示复合命题与肢命题之间真假关系的联结词，定义如下：

（1）否定，﹁

命题P的否定命题是﹁P，读作非P。P真，当且仅当﹁P假。

（2）合取，∧

命题P与Q的合取是命题P∧Q，读作P与Q。P∧Q“真”，当且仅当P与Q都真。（3）析取，∨

命题P与Q的析取是命题P∨Q，读作P或Q。P∨Q“假”，当且仅当P与Q都假。命题P与Q的析取是命题P∨Q取真值时，允许P和Q同时取得真值真，即P与Q可以同真，因而也说析取∨是可兼或。

（4）条件，→

命题P与Q组成条件命题P→Q，读作若P则Q。其中P称前件，Q称后件。P→Q 假，当且仅当P真而Q假。

条件命题P→Q当前件P取值为假时，无论后件取值是真还是假，它都为真，即从假的前件出发不管推段出的后件是真还是假，P→Q都为真。P→Q在P为假时被规定为真的规定称“实质蕴含”规定。

（5）双条件，?

命题P与Q组成条件命题P?Q，读作P当且仅当Q。P?Q取真，当且仅当P与Q 取相同的真值，即同取真值真或同取真值假。

2．2 命题公式的定义

以下三条规定了命题公式的归纳定义：

（1）命题常元和命题变元是命题公式，也称为原子公式或原子。

（2）如果A ，B 是命题公式，那么（┐A），（A ∧B ），（A ∨B ），（A→B），（A ?B ）也是命题公式。

（3）只有有限步引用（1），（2）所组成的符号串是命题公式。

2．3 命题公式的类型

（1）重言式（又叫永真式）是指在一个命题形式中不论其中的变项取什么值，该命题形式的值总是真的。

（2）矛盾式（又叫永假式）是指在一个命题形式中不论其中的变项取什么值，该命题形式的值总是假的。

（3）可满足式是指在一个命题形式中不论其中的变项取什么值，该命题形式的值至少在一种情况下是真的。

2．4 真值表

设F 为含有命题变元n P P P ,,,21???的命题公式，给n P P P ,,,21???一组确定的取值，称为公式F 关于n P P P ,,,21???的一组真值指派。含有n 个命题变元的公式有n 2组不同的真值指派，对于每一组真值指派，公式都有一个确定的真值由于命题公式是形式化的方法，无二义性，公式与其命题变元之间的真值关系可以用真值表的方法方便直观地表示出来。 例如命题公式)()(S Q Q P →?∧?的真值表见表2.1。

表2.1 命题公式)()(S Q Q P →?∧?的真值表

第三章命题公式真值表的生成算法的设计和实现

3．1 命题公式真值表的生成算法的设计

真值表中命题变元的取值具有如下规律：每列中0和1是交替出现的，而且0和1连续出现的个数是相同。N个命题变元的每组赋值的生成算法正是基于这种思想。所以首当其冲要解决的问题就是给每个命题变元的赋值问题。

接下来就要考虑命题公式的求值问题。由于命题公式的输入是中缀表达式，而且对于复杂的命题公式来说，无疑增加了算法的复杂度。这时，可以先将中缀表达式转化为后缀表达式，遇到操作符先判断是一元操作符还是二元操作符，然后再取出对应的操作数，计算后得出真值表。

基于以上问题的分析，可以得出算法的整体思路为：首先从客户端接收一个逻辑表达式，得到该逻辑表达式之后，对其进行简单的语法语义检查（是否包含规定字符以外的字符，以及字符串是否是合法的命题公式）。然后对该表达式进行解析，在解析过程中主要是：解析变元的个数（如m），同时得到变元的列表，然后根据变元的个数确定真值表的行数(例n，计算方法为n=2m)，其行数也是所有变元的取值范围的个数（从全为0到全为1），然后再将0-(n-1)转化成对应的二进制（m位的二进制），然后再根据变元的顺序，从前到后替换各个变元，从而得到含数字的中缀表达式，然后依次将每个逻辑表达式转化成后缀表达式，最后再对后缀表达式进行计算。将最后的计算结果存放在二维数组中，最终显示在界面，如果在整个系统中，如果有任何异常出现，则会系统捕获，最后以友好的方式反映给用户。流程图见3.1。

图3.1 命题公式真值表的生成算法流程图

在本系统中支持命题变元数量为n(n>0)的表达式输入，在此我们仅以P∧Q为例，更复杂的逻辑表达式处理方式与此相同，首先确定有两个变元，那么它的真值表应该是四行，变元列表为P，Q其的取值范围为（00,01,10,11）。其恰好对应的是十进制的0,1,2,3。在本系统中从十进制出发，将其转化成对应的二进制，对每个二进制，用第一个数字替换第一个变元，用第二个替换第二个变元，依次类推。例如在n=2时，对应的二进制为10，上图对应的逻辑表达式是1∧0，然后再对该中缀表达式，转化成后缀表达式（10∧），再对后缀进行计算即可。以P∧Q为例的流程图见图3.2。

3．2 命题公式真值表的实现

3．2．1 界面的实现

MainFrame是界面类，它用于接收用户的输入，以及显示界面。本类的实现主要是采用Eclipse图形化插件直接绘制而成。

界面实现代码为：

public class MainFram extends JFrame implements ActionListener{

private JTextField textField;

public JButton button;

private JTable table;

public MainFram() {

getContentPane().setLayout(null);

JLabel label = new JLabel("请输入逻辑表达式：");

label.setBounds(10, 36, 123, 15);

getContentPane().add(label);

textField = new JTextField();

textField.setBounds(136, 33, 337, 21);

getContentPane().add(textField);

textField.setColumns(10);

button = new JButton("查看真值表");

button.addActionListener(this);

button.setBounds(212, 83, 118, 29);

getContentPane().add(button);

JLabel lblNewLabel = new JLabel("Copy right by imu @ All Reserved by Xiehui 2012/05/10");

lblNewLabel.setBounds(88, 492, 337, 15);

getContentPane().add(lblNewLabel);

table = new JTable();

table.setCellSelectionEnabled(true);

JScrollPane scrollPane = new JScrollPane(table);

scrollPane.setBounds(10, 154, 460, 251);

getContentPane().add(scrollPane);

JLabel label_1 = new JLabel("温馨提示：合取用∧;析取用∨;条件用→;双条件用←;否定用~");

label_1.setForeground(new Color(255, 0, 0));

label_1.setBounds(59, 445, 359, 15);

getContentPane().add(label_1);

this.setBounds(350, 120, 499, 544);

this.setTitle("逻辑表达式转真值表系统Ver2.0");

this.setVisible(true);

}

运行界面如图3.3。

图3.3 命题公式真值表自动生成系统运行界面

3．2．2 检查输入公式合法性的实现

BdsCheck类中主要是对比表达式的语法的简单检测。

在此类中，主要做的是简单的语法检查，首先判断一个表达式是否为命题公式，判断命题公式是否由字符限定（输入的字符只能在字母以及~，(，)，∧，∨，→，←特殊字符中）组成，再判断输入的字符串是否合法，比如说字母后面不能紧跟一个字母；左括号后面不能跟“∧”等等。

代码如下：

public class BdsCheck { //检查合法性

public boolean checkOk(String str){

if(isBds(str) || checkYufa(str))

return true;

else return false;

}

}

下面代码判断命题公式是否由字符限定（输入的字符只能在字母以及~，(，)，∧，∨，→，←特殊字符中）组成。

private boolean isBds(String str){

String pat = "[A-Z~()∧∨→←] ";

if(str.matches(pat)){

return false;

}else{

return true;

}

}

判断输入的串是否合法，例如∧后面不能直接跟∧，∨，→，←等。

private boolean checkYufa(String str){

boolean result = false;

ArrayList list = new ArrayList();

list.add(")");

list.add("∧");

list.add("∨");

list.add("→");

list.add("←");

ArrayList list2 = new ArrayList();

list.add("∧");

list.add("∨");

list.add("→");

list.add("←");

for(int i=0;i

String temp = String.valueOf(str.charAt(i));

String tempNext = String.valueOf(str.charAt(i+1));

if(temp.matches("[A-Z]")&&tempNext.matches("[A-Z]")){

result = true;

}else if(list2.contains(temp)&&list.contains(tempNext)){

result = true;

}else if("(".equals(temp)&&list2.contains(tempNext)){

result = true;

}else if("~".equals(temp)&&list.contains(tempNext)){

result = true;

}else if(")".equals(temp)&&("(".equals(tempNext)||"~".equals(tempNext))){ result = true;

}

}

return result;

}

}

在此类中，没有对所有的语法错误做出判断，当输入其他的错误时，在MainFrame 类中做了捕获。

错误提示界面如图3.4及图3.5。

图3.4 左括号后直接跟逻辑联结词的错误提示界面

图3.5 连续输入两个字母的错误提示界面3．2．3 提取命题变元及其个数的实现

GetChar类提取命题变元，getCount类提取命题变元的个数。代码如下：

public class GetChar {// 获取变元列表

public static List getChars(String s){

List list = new ArrayList();

for(int i=0;i

String temp = String.valueOf(s.charAt(i));

if(temp.matches("[A-Z]")){

if(!list.contains(temp)){

list.add(temp);

}

}

}

return list;

}

public static int getCount(String ss){ // 获取变元的个数

List list = getChars(ss);

return list.size();

}

}

3．2．4 逻辑表达式求值的实现

Jisuan类实现了将命题公式的中缀表达式形式转化为后缀表达式形式，compare 类定义比较运算符之间的优先级，calculate类完成了后缀表达式的求值，后缀表达式的运算顺序就是操作符出现的先后顺序，getData类获取真值表的二维真值矩阵，从而实现逻辑表达式的求值。

代码如下：

public class Jisuan {

public static ArrayList transform(String midfix) {

int len = midfix.length();// 获取中缀表达式的长度

midfix=midfix+ '#';// 让中缀表达式以'#'结尾

Stack stack = new Stack();// 保存操作符的栈

stack.push('#');// 首先让'#'入栈

ArrayList postfix = new ArrayList();// 保存后缀表达式的列表

for (int i = 0; i < len + 1; i++) {

char temp=midfix.charAt(i);

if (Character.isDigit(temp)) {// 当前字符是一个数字

postfix.add((temp-'0'));

} else {// 当前字符是一个操作符

switch (temp) {

case '(':// 如果是左括号

stack.push(temp);// 左括号只是放入到栈中，不放入到后缀表达式中

break;

case ')':// 如果是右括号

while (stack.peek() != '(') {

postfix.add(stack.pop());// 右括号是不入栈的

}

stack.pop();// 弹出'('

break;

default:// 默认情况下:∧∨←→

while (stack.peek() != '#'

&& compare(stack.peek(), temp)) {

postfix.add(stack.pop());// 不断弹栈，直到当前的操作符的优先级高于栈顶操作符

}

if (temp != '#') {// 如果当前的操作符不是'#'(结束符)，那么入操作符栈

stack.push(temp);// 最后的标识符'#'是不入栈的

}

break;

}

}

}

return postfix;

}

定义比较运算符之间的优先级，如果是peek优先级高于cur，返回true，默认都是peek优先级要低。代码如下：

public static boolean compare(char peek, char cur) {

if(peek == '~' && (cur == '∧' || cur == '∨'|| cur == '←' || cur == '→')){

return true;//否定的优先级最高

}else if (peek == '→' && (cur == '←' || cur == '→')) {