任意命题公式的真值表 .doc

实验报告

实验名称：任意命题公式的真值表

实验目的与要求：通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，包括联结词、真值表、运算的优先级等，提高学生编写实验报告、总结实验结果的能力，培养学生的逻辑思维能力和算法设计的思想，能够独立完成简单的算法设计和分析，进一步用它们来解决实际问题，帮助学生学习掌握C/C++语言程序设计的基本方法和各种调试手段，使学生具备程序设计的能力。

实验内容提要：求任意一个命题公式的真值表

实验步骤：（一）、关于命题公式的形式和运算符（即联结词）的运算

首先根据离散数学的相关知识，命题公式由命题变元和运算符（即联结词）组成，命题变元用大写字母英文表示（本次试验没有定义命题常元T和F，即T、F都表示命题变元），每个命题变元都有两种真值指派0和1，对应于一种真值指派，命题公式有一个真值，由所有可能的指派和命题公式相应的真值按照一定的规范构成的表格称为真值表。

目前离散数学里用到的包括扩充联结词总共有九种，即析取（或）、合取（与）、非、蕴含、等值、与非、或非、异或、蕴含否定，常用的为前五种，其中除了非运算为一元运算以外，其它四种为二元运算。所以本次实验设计时只定义了前五种运算符，同时用“/”表示非，用“*”表示合取，用“+”表示析取，用“”表示蕴含，用“:”表示等值，且这五种运算符的优先级依次降低，如果需用括号改变运算优先级，则用小括号()改变。

以下为上述五种运算符运算时的一般真值表，用P和Q表示命题变元：

非，用“/”表示

P

/P

0

1

1

0

2．合取（与），用“*”表示

P

Q

P*Q

0

0

0

0

1

0

1

0

0

1

1

1

3．析取（或），用“+”表示

P

Q

P+Q

0

0

0

0

1

1

1

0

1

1

1

1

4.蕴含，用“”表示

P

Q

PQ

0

0

1

0

1

1

1

0

0

1

1

1

5.等值，用“:”表示

P

Q

P:Q

0

0

1

0

1

0

1

0

0

1

1

1

（二）、命题公式真值的计算

对于人来说，计算数学表达式时习惯于中缀表达式，例如a*b+c，a*（b+c）等等，而对于计算机来说，计算a*b+c还好，计算a*（b+c）则困难，因为括号的作用改变了运算的顺序，让计算机识别括号而改变计算顺序显得麻烦。经理论和实践研究，用一种称之为后缀表达式（逆波兰式）的公式形式能让计算机更容易计算表达式的真值。例如上面的a*（b+c），其后缀表达式为abc+*，计算时从左边开始寻找运算符，然后按照运算符的运算规则将与其相邻的前面的一个（非运算时为一个）或两个（其它四种运算为两个）操作数运算，运算结果取代原来的运算符和操作数的位置，然后重新从左边开始寻找运算符，开始下一次计算，比如上式，从左边开始寻找运算符，先找到+，则计算b+c，结果用d表示，这时后缀表达式变为ad*，又重新开始从左边开始寻找运算符，找到*，则计算a*d，运算结果保存在原来ad*所占的位置，即a位，也就是第一位。

系统初始化

系统初始化

开始

输入命题公式

是否合法

将中缀表达式化为后缀表达式

统计变元

生成二进制加法器并指派真值

由后缀表达式计算命题公式的真值

统计最小项和最大项

真值是否指派完毕

输出主析取范式和主合取范式

结束

是

是

否

否

实验结果与结论：(1)、非运算

(2)、与运算

(3)、或运算

(4)、蕴含

(5)、等值

(6)综合公式

写这个程序花了不少时间，而且时间相对集中，除了上课外，在电脑前都是在做这个，连续做了几天。刚开始时并没有完全按照软件设计的步骤去写，而是知道总体方框后，一个模块一个模块去求解，至于每个模块怎么写，则是在写的过程中逐步建立和完善的。

有些知识没有学到，比如如何求逆波兰式，只得借书回来看，上网找到的资料不够详细或者几乎没解释，难以理解。当然了，程序是自己写的，自己看得懂就好多了，别人又