一.实验内容

（1）求任意一个命题公式的真值表。

（2）利用真值表求任意一个命题公式的主范式。

（3）利用真值表进行逻辑推理。

注：（2）和（3）可在（1）的基础上完成。

二.实验目的

真值表是命题逻辑中的一个十分重要的概念，利用它几乎可以解决命题逻辑中的所有问题。例如，利用命题公式的真值表，可以判断命题公式的类型、求命题公式的主范式、判断两命题公式是否等价，还可以进行推理等。

本实验通过编写一个程序，让计算机给出命题公式的真值表，并在此基础上进行命题公式类型的判定、求命题公式的主范式等。目的是让学生更加深刻地理解真值表的概念，并掌握真值表的求解方法及其在解决命题逻辑中其他问题中的应用。

三.算法的主要思想

利用计算机求命题公式真值表的关键是：①给出命题变元的每一组赋值；②计算命题公式在每一组赋值下的真值。

真值表中命题变元的取值具有如下规律：每列中0和1是交替出现的，且0和1连续出现的个数相同。n个命题变元的每组赋值的生成算法可基于这种思想。

含有n个命题变元的命题公式的真值的计算采用的方法为“算符优先法”。

为了程序实现的方便，约定命题变元只用一个字母表示，非、合取、析取、条件和双条件联结词分别用！、&、|、－、＋来表示。

算符之间的优先关系如表1-32所示：

表1-32 算符优先级

＋   －    |    &    !    （   ）   #

＋

－

|

&

!

（

）

#

＞   ＜   ＜   ＜   ＜    ＜  ＞   ＞

＞   ＞   ＜   ＜   ＜    ＜  ＞   ＞

＞   ＞   ＞   ＜   ＜    ＜  ＞   ＞

＞   ＞   ＞   ＞   ＜    ＜  ＞   ＞

＞   ＞   ＞   ＞   ＞    ＜  ＞   ＞

＜   ＜   ＜   ＜   ＜    ＜  ＝    E

＞   ＞   ＞   ＞   ＞    E   ＞   ＞

＜   ＜   ＜   ＜   ＜   ＜   E    ＝

为实现算符优先算法，我们采用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。

四.算法的具体实现　　

（1）定义全局的属性：

　　　　（这里栈就直接调用C++有的库#include<stack>,就不用自己再写栈的代码）

　　　　 运算符栈OPTR

　　　　 操作数或运算结果栈OPND

　　　　 常量操作字符集合operateChar

　　　　 公式中的变元VarList　　

stack<bool> OPND;//操作数或运算结果栈

stack<char> OPTR;//运算符栈

const char operateChar[8] = { '+', '-', '|', '&', '!', '(', ')','#' };//运算符(+:等价、-:蕴涵、|:析取、&:合取、!:否定

string VarList;//保存公式中的变元

（2）判断字符是否是运算符

//判断字符是否是运算符

bool In(char ch) {

	for (int i = 0; i < (int)strlen(operateChar); i++)

		if (operateChar[i] == ch)

			return true;

	return false;

}

（3）比较运算符的优先级

　　　　 这里可以直接用二维字符数组实现运算符优先级表，将OPTR的栈顶运算符(theta1)与新输入的运算符(theta1)作比较，各自按照operateChar的顺序赋值就可以得到优先级

//比较运算符的优先级

char Precede(char theta1, char theta2) {

	//运算符优先级表

	char operate_Table[8][9] = {

	"><<<<<>>",

	">><<<<>>",

	">>><<<>>",

	">>>><<>>",

	">>>>><>>",

	"<<<<<<=E",

	">>>>>E>>",

	"<<<<<<E="

	};

	int theta1_Index=0, theta2_Index=0;//定义运算符1和运算符2的索引

	for (int i = 0; i < (int)strlen(operateChar); i++){

		if (operateChar[i] == theta1)

			theta1_Index = i ;

		if (operateChar[i] == theta2)

			theta2_Index = i ;

	}

	return operate_Table[theta1_Index][theta2_Index];

}

（4）计算表达式，并将结果返回（这里是计算双目的，在这次试验命题公式中只有!是单目运算符所以到时直接在计算表达式时直接计算）

//计算表达式，并将结果返回(双目)

bool Calculate(bool x, char operate, bool y) {

	switch (operate)

	{

	case '+': return (((!x) || y) && (x || (!y))); break;

	case '-': return ((!x) || y); break;

	case '|': return x || y; break;

	case '&': return x && y; break;

	}

	return -1;

}

（5）判断是否是字母（用来将公式中的命题变元提取出来），然后将变元按递增顺序赋值给VarList

　　　　 我就只做了小写字母的，大写字母可以自己改下判断条件

//判断是否是字母(仅小写字母)

bool isAlpha(char ch) {

	if (((int)ch >= 97 && (int)ch <= 122)&&VarList.find(ch)==-1)//若字符的ascii码在97~122中则是字母

		return true;

	else return false;

}
//提取公式字符串中全部命题变元，并按递增顺序存放在VarList中

void createVarList(string source) {

	int indexNum=0;//比较字母用的下标

	for (auto ch:source) {

		if (isAlpha(ch))

			VarList += ch;

	}

	for (int i = 0; i < VarList.length()-1;i++) {

		for (int j = 0; j < VarList.length() - i-1; j++) {

			if ((int)VarList[j] > (int)VarList[j + 1]) {

				char temp = VarList[j];

				VarList[j] = VarList[j + 1];

				VarList[j + 1] = temp;

			}

		}

	}

}

（6）计算表达式

bool InfixValue(string source) {

	OPTR.push('#');

	char item = source[0];

	bool OPNDtop2, OPNDtop1;

	char OPTRtop;

	int i = 1;

	while (item != '#' || OPTR.top() != '#') {

		if (!In(item)) {

			if (item == '0')

				OPND.push(false);

			else

				OPND.push(true);

			item = source[i++];

		}

		else if (OPTR.top() == '!')

		{

			OPTR.pop();

			OPNDtop1 = OPND.top();

			OPND.pop();

			OPND.push(!OPNDtop1);

		}

		else

		{

			switch (Precede(OPTR.top(), item))

			{

			case '<':

				OPTR.push(item);

				item = source[i++];

				break;

			case '>':

				OPTRtop = OPTR.top();

				OPTR.pop();

				OPNDtop1 = OPND.top();

				OPND.pop();

				OPNDtop2 = OPND.top();

				OPND.pop();

				OPND.push(Calculate(OPNDtop2, OPTRtop, OPNDtop1));

				break;

			case '=':

				OPTR.pop();

				item = source[i++];

				break;

			}

		}

	}

	return OPND.top();

}

（7）因为我们要获得变元所有的取值情况，所以可以当成二进制来依次递增

　　　　 比如  变元有 a b c 三个，就是从 000 开始依次取到111

　　　　 这就需要一个对二进制增值的方法

//依次取值的二进制值加1

void IncreaseVarValue(char(&v)[26], int& flag) {

	int m = 1;

	int n = VarList.length();

	for (int j = n - 1; j > -1; j--) {

		int temp;

		temp = int(v[j]) - 48;

		flag = flag + temp;

		if (flag == 2) {

			v[j] = '0'; flag = 1;

		}

		else {

			v[j] = '1'; flag = 0; break;

		}

	}

}

（8）得到真值表

void TruthTable(string expression,bool * &truthTab,string *&expressionValueList,string *&trowList,int &CircleNum) {

	int m = 1;

	int n = VarList.length();

	int flag;

	char trow[26];//表达式中变元的依次取值

	for (int i = 0; i < n; i++) { m *= 2; trow[i] = '0'; }

	string* expressionValueList_IN = new string[m];

	string* trowList_IN = new string[m];

	bool *truthtable_IN=new bool[m];//真值表中的值

	CircleNum = m;

	//转换成用0或1表示的表达式

	for (int i = 0; i < m; i++) {

		string value1 = expression;//因为公式是字符串无法直接计算，所以定义value1，将里面的命题变元变成0或1

		//使表达式的变元用0或1表示

		for (int j = 0; j < n; j++) {

			char x = VarList[j];

			for (int k = 0; k < expression.length(); k++) {

				char a = value1[k];

				if (value1[k] == x)

					value1[k] =trow[j];

			}

		}

		trowList_IN[i] = trow;

		expressionValueList_IN[i] = value1;

		truthtable_IN[i] = InfixValue(value1);//将得出来的值依次给truthtable

		flag = 1;

		IncreaseVarValue(trow,flag);

	}

	truthTab = truthtable_IN;

	expressionValueList = expressionValueList_IN;

	trowList = trowList_IN;

}

（9）最后输出真值表

//输出真值表

void PrintTable(string expression) {

	string* expressionValueList;//用来保存所有的表达式

	string* trowList;//保存变元的所有取值

	bool* truthtab;//保存所有的表达式的值

	int CircleNum;//循环次数

	createVarList(expression);

	TruthTable(expression, truthtab, expressionValueList, trowList,CircleNum);

	//打印真值表

	for (int i = 0; i < VarList.length(); i++) {

		cout << VarList[i] << "\t";

	}

	cout << expression <<"\t" <<"值"<<endl;

	for (int i = 0; i < CircleNum; i++) {

		for (int j = 0; j < VarList.length(); j++) {

			cout << trowList[i][j] << "\t";

		}

		cout << expressionValueList[i] << "\t" << truthtab[i] << endl;;

	}

}

　　

完整的代码：

#include<iostream>

#include<math.h>

#include<string.h>

#include<stack>

using namespace std;

stack<bool> OPND;//操作数或运算结果栈

stack<char> OPTR;//运算符栈

const char operateChar[8] = { '+', '-', '|', '&', '!', '(', ')','#' };//运算符(+:等价、-:蕴涵、|:析取、&:合取、!:否定

string VarList;//保存公式中的变元

//判断字符是否是运算符

bool In(char ch) {

	for (int i = 0; i < (int)strlen(operateChar); i++)

		if (operateChar[i] == ch)

			return true;

	return false;

}

//比较运算符的优先级

char Precede(char theta1, char theta2) {

	//运算符优先级表

	char operate_Table[8][9] = {

	"><<<<<>>",

	">><<<<>>",

	">>><<<>>",

	">>>><<>>",

	">>>>><>>",

	"<<<<<<=E",

	">>>>>E>>",

	"<<<<<<E="

	};

	int theta1_Index=0, theta2_Index=0;//定义运算符1和运算符2的索引

	for (int i = 0; i < (int)strlen(operateChar); i++){

		if (operateChar[i] == theta1)

			theta1_Index = i ;

		if (operateChar[i] == theta2)

			theta2_Index = i ;

	}

	return operate_Table[theta1_Index][theta2_Index];

}

//计算表达式，并将结果返回(双目)

bool Calculate(bool x, char operate, bool y) {

	switch (operate)

	{

	case '+': return (((!x) || y) && (x || (!y))); break;

	case '-': return ((!x) || y); break;

	case '|': return x || y; break;

	case '&': return x && y; break;

	}

	return -1;

}

//判断是否是字母(仅小写字母)

bool isAlpha(char ch) {

	if (((int)ch >= 97 && (int)ch <= 122)&&VarList.find(ch)==-1)//若字符的ascii码在97~122中则是字母

		return true;

	else return false;

}

//提取公式字符串中全部命题变元，并按递增顺序存放在VarList中
//比如  (!a-d)-（c+b)     VarList值就是 "abcd"

void createVarList(string source) {

	int indexNum=0;//比较字母用的下标

	for (auto ch:source) {

		if (isAlpha(ch))

			VarList += ch;

	}

	for (int i = 0; i < VarList.length()-1;i++) {

		for (int j = 0; j < VarList.length() - i-1; j++) {

			if ((int)VarList[j] > (int)VarList[j + 1]) {

				char temp = VarList[j];

				VarList[j] = VarList[j + 1];

				VarList[j + 1] = temp;

			}

		}

	}

}

//计算表达式

bool InfixValue(string source) {

	OPTR.push('#');

	char item = source[0];

	bool OPNDtop2, OPNDtop1;

	char OPTRtop;

	int i = 1;

	while (item != '#' || OPTR.top() != '#') {

		if (!In(item)) {

			if (item == '0')

				OPND.push(false);

			else

				OPND.push(true);

			item = source[i++];

		}

		else if (OPTR.top() == '!')

		{

			OPTR.pop();

			OPNDtop1 = OPND.top();

			OPND.pop();

			OPND.push(!OPNDtop1);

		}

		else

		{

			switch (Precede(OPTR.top(), item))

			{

			case '<':

				OPTR.push(item);

				item = source[i++];

				break;

			case '>':

				OPTRtop = OPTR.top();

				OPTR.pop();

				OPNDtop1 = OPND.top();

				OPND.pop();

				OPNDtop2 = OPND.top();

				OPND.pop();

				OPND.push(Calculate(OPNDtop2, OPTRtop, OPNDtop1));

				break;

			case '=':

				OPTR.pop();

				item = source[i++];

				break;

			}

		}

	}

	return OPND.top();

}

//依次取值的二进制值加1

void IncreaseVarValue(char(&v)[26], int& flag) {

	int m = 1;

	int n = VarList.length();

	for (int j = n - 1; j > -1; j--) {

		int temp;

		temp = int(v[j]) - 48;

		flag = flag + temp;

		if (flag == 2) {

			v[j] = '0'; flag = 1;

		}

		else {

			v[j] = '1'; flag = 0; break;

		}

	}

}

//得到真值表

void TruthTable(string expression,bool * &truthTab,string *&expressionValueList,string *&trowList,int &CircleNum) {

	int m = 1;

	int n = VarList.length();

	int flag;

	char trow[26];//表达式中变元的依次取值

	for (int i = 0; i < n; i++) { m *= 2; trow[i] = '0'; }

	string* expressionValueList_IN = new string[m];

	string* trowList_IN = new string[m];

	bool *truthtable_IN=new bool[m];//真值表中的值

	CircleNum = m;

	//转换成用0或1表示的表达式

	for (int i = 0; i < m; i++) {

		string value1 = expression;//因为公式是字符串无法直接计算，所以定义value1，将里面的命题变元变成0或1

		//使表达式的变元用0或1表示

		for (int j = 0; j < n; j++) {

			char x = VarList[j];

			for (int k = 0; k < expression.length(); k++) {

				char a = value1[k];

				if (value1[k] == x)

					value1[k] =trow[j];

			}

		}

		trowList_IN[i] = trow;

		expressionValueList_IN[i] = value1;

		truthtable_IN[i] = InfixValue(value1);//将得出来的值依次给truthtable

		flag = 1;

		IncreaseVarValue(trow,flag);

	}

	truthTab = truthtable_IN;

	expressionValueList = expressionValueList_IN;

	trowList = trowList_IN;

}

//输出真值表

void PrintTable(string expression) {

	string* expressionValueList;//用来保存所有的表达式

	string* trowList;//保存变元的所有取值

	bool* truthtab;//保存所有的表达式的值

	int CircleNum;//循环次数

	createVarList(expression);

	TruthTable(expression, truthtab, expressionValueList, trowList,CircleNum);

	//打印真值表

	for (int i = 0; i < VarList.length(); i++) {

		cout << VarList[i] << "\t";

	}

	cout << expression <<"\t" <<"值"<<endl;

	for (int i = 0; i < CircleNum; i++) {

		for (int j = 0; j < VarList.length(); j++) {

			cout << trowList[i][j] << "\t";

		}

		cout << expressionValueList[i] << "\t" << truthtab[i] << endl;;

	}

}

void main() {

	system("pause");

	while (true) {

		cout << "*****************************************************" << endl;

		cout << "***		    +表示等价		 	  ***" << endl;

		cout << "***		    -表示蕴涵			  ***" << endl;

		cout << "***		    &表示合取			  ***" << endl;

		cout << "***		    |表示析取			  ***" << endl;

		cout << "***		    注：必须用#结束		  ***" << endl;

		cout << "***		    输入1退出程序	      ***" << endl;

		cout << "*****************************************************" << endl;

		cout << "请输入命题公式：";

		string expression;

		cin >> expression;

		if (expression == "1") {

			break;

		}

		//如果没有#

		if (expression.find('#') != expression.length() - 1)

		{

			cout << "请以#结束！" << endl;;

			system("pause");

			system("cls");

			continue;

		}

		PrintTable(expression);

		system("pause");

		system("cls");

	}

}

最新文章

  1. FineReport关于tomcat集群部署的方案
  2. SQL Server 导入数据失败：无法在只读列“Id”中插入数据
  3. docker进程管理
  4. 动手学servlet(四) cookie和session
  5. .net 调用SAP RFC函数获取数据的两种方式
  6. OpenGL--第一个OpenGL程序
  7. iOS view和viewController的生命周期
  8. 如何使用lxml的XPath功能
  9. Mybatis第一天
  10. 团队作业4——beta冲刺
  11. 在VMware上安装CentOS6 64位操作系统
  12. Linux背背背（3）
  13. SpringMVC-RESTRUL___CRUD知识点总结
  14. 思维导图软件 xMind 基本用法
  15. 注册表项关于start参数的说明
  16. python基础-列表元组字典
  17. angular2 如何使用websocket
  18. R语言barplot绘图函数
  19. dp合集 广场铺砖问题&amp;&amp;硬木地板
  20. numpy生成随机数

热门文章

  1. Jmeter测试工具
  2. docker 搭建私有云仓库
  3. 项目初始化CSS公共样式
  4. 【深入理解JVM】学习笔记——-1、JVM基本结构
  5. 6.Exchanger-交换机
  6. 基于Springboot+Mybatis+Element UI开发的钢贸供应链系统
  7. jstl中ftm标签用法
  8. NX导入DWG失败
  9. Ubuntu中发生git Connection refused
  10. pytorch和tensorflow的爱恨情仇之基本数据类型