摘要： 目前人工智能的发展已经非常迅速，而且会越来越普及到我们的生活中。人工智能的发展离不开数理逻辑，命题逻辑是数理逻" />
免费阅读期刊
论文发表、论文指导
周一至周五
9：00&22：00
命题公式主析范式的自动生成系统
2013年30期目录
&&&&&&本期共收录文章20篇
　　摘要： 目前人工智能的发展已经非常迅速，而且会越来越普及到我们的生活中。人工智能的发展离不开数理逻辑，命题逻辑是数理逻辑中重要部分，本文介绍了命题公式主析取范式及主合取范式的自动生成系统的开发、设计与实现过程。 中国论文网 /7/view-4427712.htm　　Abstract： Nowadays the development of artificial intelligence has been very rapid， and is becoming increasingly popular in our life. The development of artificial intelligence can not be separated without mathematical logic. Propositional logic is a significant part of mathematical logical. This paper describes the design and implementation process of the propositional formulas， disjunctive paradigm and conjunctive paradigm of automatic generation of system development. 　　关键词： 命题公式；主析取范式；主合取范式；自动生成 　　Key words： propositional formula；principal disjunctive normal form；principal conjunctive normal form； automatic generation 　　中图分类号：G250.76 文献标识码：A 文章编号：（1-02 　　1 选题背景 　　逻辑学是研究思维和论证的科学，也就是研究关于人类推理的学问。在20世纪的下半个世纪，伴随着计算机科学技术的迅猛发展，新的逻辑学分支——数理逻辑也发展起来。数理逻辑也称为符号逻辑，是一门运用数学的方法来研究推理的形式结构和推理规律的边缘性学科。其内容相当广泛，包括逻辑演算（命题演算与谓词演算）、公理集合论、证明论、递归函数论等，其中逻辑演算是其它各部分的基础。它在逻辑电路、自动控制、人工智能、程序设计、数据库理论以及计算机科学的其它领域有着广泛的应用。人工智能是研究使计算机来模拟人的某些思维过程和智能行为，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能涉及的计算机科学、心理学、哲学和语言学等学科。但最主要的依然是计算机科学的范畴，人工智能对于逻辑的计算十分依赖，尤其是进行推理的时候，在这方面对命题逻辑的研究就有着十分重要的贡献，它是人工智能所能发挥的作用有多大，所能覆盖的范畴有多广的决定性因素之一，所以求一个给定的命题公式的主析取范式或主合取范式是命题逻辑中一类很重要的工作，它是命题分解和进一步进行机器处理的基础。通过这个系统，用户可以更加方便的得出命题公式主范式，有助于对命题逻辑的学习和研究。 　　2 研究内容 　　本文主要介绍了命题公式主范式的自动生成方法。首先，给出了主范式的基础定义及相关定理，并对其中定义给出解释，定理做出解释；探讨出主范式的求法——真值表求法，并对设计过程加以描述，包括了命题公式识别，命题公式转译以及命题公式真值表生成三个部分，可以实现命题公式的合法性判断，大小项的生成，命题公式的真值以及命题公式主范式的生成。 　　3 概念描述 　　3.1 大项与小项 小项：n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 　　大项：n个命题变元的析取式，称作布尔析取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 　　3.2 主析取范式及主合取范式 主析取范式：对于给定的命题公式，如果有一个等价公式仅由小项的析取所组成，则该等价式称作原式的主析取范式。 　　主合取范式：对于给定的命题公式，如果有一个等价公式仅由大项的合取所组成，则该等价式称作原式的主合取范式。 　　3.3 主析取范式及主合取范式的求取方法 主析取范式及主合取范式的求取方法有真值表法、等价变换法等，本系统采用真值表法求取主析取范式及主合取范式，故只对这种方法加以描述，其他方法在这里概不描述。 　　在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。 　　在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。 　　4 模块设计 　　由于无法保证用户输入一定准确无误，而主范式求取的算法默认所得到的命题公式是正确的，所以一旦命题公式输入出错，则有可能输出错误的结果，甚至引起本系统的崩溃，所以为了确保程序能正常进行，在进行主范式生成运算前必须验证命题公式是否正确。 　　由于计算机的计算速度和存取速度十分快速，而真值表法求取主析取范式及主合取范式实现起来比较简单，所以选用了真值表法。这就需要模拟出一个可以填入和修改真值的真值表，最终利用真值表得出命题公式大小项进而得出主范式。 　　因此主范式生成包括公式识别、真值表生成以及主范式生成三大模块。其中公式识别分为公式格式化、公式转译、公式化简并判断。真值表生成分为真值表初始化，真值表填入。模块图如图1所示。 　　5 系统实现 　　首先给出主范式生成的流程图。如图2所示。 　　5.1 命题公式的识别 命题公式识别算法采用递归思想对字符串进行重复简化直到变成一个命题变元，如果不能则判断该字符串不是命题公式。
　　我们知道，命题公式需要遵循四个规定： 　　（1）单个命题变元是一个合式公式； 　　（2）如果A是合式公式，则□A是合式公式； 　　（3）如果A和B是合式公式，那么（A∧B），（A∨B），（A→B）和（A□B）都是合式公式； 　　（4）当且仅当能够有限次地应用（1），（2），（3）所得到的包含命题变元，连接词和括号的符号串是合式公式。 　　由于该公式的定义是由递归的形式给出的，那么我们依然可以应用递归思想去对公式进行判断。 　　为方便系统识别，我们首先定义以下标准： 　　1）所有的字母使用字符“*”代替； 　　2）除 “□”符与括号之外的所有符号均使用“@”代替。 　　当传入字符串之后，首先去掉空括号与连续的两个“□”符，之后运用上述标准做字符替换。由于我们的工作是判断该字符串是否是一个合法的命题公式，在判断的最后只需要返回一个true值或者false值。也就是说A与（A∧B）的返回值是一样的。 　　在这里我们编写了一个剪掉算法，该算法可以剪掉字符串中的任意字符或者代替字符串中的任意字符。 　　这样的话，我们就可以将A∧B，□A，（A）全部替换为A，使用循环直到字符串的长度不再发生变化时循环结束，判断其是否为一个单一命题变元。若是则返回TRUE值；若不是则返回FALSE值。 　　5.2 真值表生成 当我们人为的在纸上构造真值表时，只需要先列出原始命题变元及拆分出的命题公式，通过自己的计算依次填入真值即可，问题是如何在计算机上实现这一系列过程真值表前N列是N个原始的命题变元，我们为了得到整个公式的，需要一点点将其化简，即将类似“□P”，“PVQ”，“（P）”之类的命题公式化简成为“P”，同时应用公式中的符号和命题变元，首先识别符号让计算机知道这个公式是做合取，析取，取反，条件还是双条件，再根据公式中的命题变元计算出该公式对应的真值存入真值表，记录为一个新的命题变元而非公式，如此反复，直到最终整个原始公式只剩下一个命题变元，这个命题变元即为所求公式的真值。 　　本系统为了节省硬盘空间，以及提高效率，直接使用了arraylist数组代替在数据库中建表实现真值表的生成，我将arraylist定义成boolean型数组类型，这样每个arraylist中的一个元素其实都是真值表中的一列，而且可以任意添加，有效控制数量和空间复杂程度，这个类就是对真值表的初始化，运行后的结果就如同画好了真值表表格并已填入初始的单一命题变元的初始真值，为随后的主范式计算做准备。 　　5.3 大小项的生成 在计算出了真值之后，利用真值即可得出大项与小项，只要提取出前面定义的arraylist的最后一组，那一组里存的正是命题公式的真值，在得出大小项后可以生主范式。在web上只需要写上一个调用getString（）方法的语句即可打印出来。 　　这里的原理类似于公式识别，也是将命题公式想办法化简，不同的是，每化简一次都要修改真值表，也就是说在原先的arraylist数组后面再加一个元素，如此一来最后得到的元素必定存储着命题公式的真值，大小项随即得出。 　　5.4 主范式生成 在有了大小项之后，根据真值表法即可得出主合取范式以及主析取范式，由于在计算过程中，使用的符号都是计算机中的符号而非离散数学专业符号，但是给用户的答案必须是专业的，所以在生成主范式的同时，也要对符号进行标准化转化。 　　参考文献： 　　[1]左孝凌，刘永才等 著.离散数学[M].上海科学技术文献出版社，2009年7月. 　　[2]李涛著.数理逻辑引论[M].哈尔滨工业大学出版社，2011年11月. 　　[3]李庆宏.关于命题公式的主范式[J].阜阳师范学院学报（自然科学版））：9-11. 　　[4]张会凌.命题公式真值表的生成与公式类型的机械判定[J].甘肃联合大学学报（自然科学版），）：25-27.
转载请注明来源。原文地址：
【xzbu】郑重声明：本网站资源、信息来源于网络，完全免费共享，仅供学习和研究使用，版权和著作权归原作者所有，如有不愿意被转载的情况，请通知我们删除已转载的信息。
xzbu发布此信息目的在于传播更多信息，与本网站立场无关。xzbu不保证该信息（包括但不限于文字、数据及图表）准确性、真实性、完整性等。Vc++编程求主范式，这个我目前还没有用到，不过相信这是挺有用的，注释比较多：
求命题逻辑公式的主析取和主合取范式。逻辑连接词有析取、合取、取非、蕴含、等价。
#输入格式：
1、必须将自然命题公式中的命题变项按字典顺序转换成大写字母A~Z，如：
出现在命题公式变元依次为q、p、q、r则应转化为B、A、B、C输入；
可见，本程序最多只能接受26变元公式。不过最好不要这么做，因为计算量过大了（呈2^n增长）。
2、析取、合取、取非、蕴含、等价运算符分别用字符：+、*、!、c、e代替书写。
3、输入应注意语法正确。本程序只提供括号匹配检验、字符检验。另外不能省略运算符。举例：
&&可检验，非法
&&可检验，非法
③若变项数n=3，输入C+D
&&可检验，非法
&&不可检验，非法
&&不可检验，非法
4、不能输入常量，如1*B。
综上，可输入字符有A-Z，+，*，!，c，e及(，)（英文括号）
逻辑运算符优先级顺序为：非(!) & 合取(*) & 析取(+) & 蕴含(c) & 等价(e)
命题变项数目：3
输入命题公式：!((A*!B+B*!C)*!(A*B))
!((A*!B+B*!C)*!(A*B)) = &m(0,1,3,6,7)
!((A*!B+B*!C)*!(A*B)) = &M(2,4,5)
命题变项数目：5
输入命题公式：A*!A
A*!A = &m()
A*!A = &M(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31)
命题变项数目：3
输入命题公式：(AeB)cC
(AeB)cC = &m(1,2,3,4,5,7)
(AeB)cC = &M(0,6)
命题变项数目：3
输入命题公式：(AcC)*(Bc!C)*((A*!B)+(!A*B))
(AcC)*(Bc!C)*((A*!B)+(!A*B)) = &m(2,5)
(AcC)*(Bc!C)*((A*!B)+(!A*B)) = &M(0,1,3,4,6,7)
#include &iostream&
#include &cmath&
#include &stack&
const int expLength = 100; //输入命题公式字符容量
const int OP_NUMBER = 8; //包括括号、#在内的操作符数目
//操作符列表，#表示表达式开始与结束
const char opList[OP_NUMBER] = {'!', '+', '*', 'c', 'e', '(', ')', '#'};
/*优先级列表（行与列比较）：
*1表示大于，计算；
*0表示等于，将从操作符栈中去除；
*-1表示小于，压栈
*2表示不可能相遇
const char opPriority[OP_NUMBER][OP_NUMBER] =
/* ! */ {-1, 1, 1, 1, 1,-1, 1, 1},
/* + */ {-1, 1,-1, 1, 1,-1, 1, 1},
/* * */ {-1, 1, 1, 1, 1,-1, 1, 1},
/* c */ {-1,-1,-1, 1, 1,-1, 1, 1},
/* e */ {-1,-1,-1, 1, 1,-1, 1, 1},
/* ( */ {-1,-1,-1,-1,-1,-1, 0, 2},
/* ) */ { 1, 1, 1, 1, 1, 2, 1, 1},
/* # */ {-1,-1,-1,-1,-1,-1, 2, 0}
bool boolExpCompute(char* exp, bool* value);//对每个赋值求公式真假
/********辅助函数**********/
bool isOperator(char c);
//判断是否是操作符
int getOpPosition(char c);
//返回操作符在opList的位置
int getPriority(char op1, char op2);//返回op1,op2的优先顺序
void printResult(char* exp, int num);//打印范式
void binIncrease(bool* digit, int length);//赋值数组自增1
bool calculate(bool value1, char op, bool value2);//计算v1 op v2的值
/*******表达式合法性检验******/
bool operandCheck(char* exp, int n);//输入字符是否合法
bool bracketMatch(char* exp);
//括号是否匹配
int main()
char exp[expLength];
while(true)
cout && &输入以下信息(输入之时按'q'键结束程序)：\n&;
cout && &命题变项数目：&;
if(!(cin && len))//如果输入非整型
cin.clear();
while(cin.get() != '\n');
cin.get(); //输入len值合法时清除回车符
cout && &输入命题公式：&;
cin.get(exp,expLength).get();
if(exp[0] == 'q' && exp[1] == '\0')//如果exp = &q&
//exp结尾加#
for(int i = 0;i& expL i++)
if(exp[i] == '\0')
exp[i] = '#';
exp[i+1] = '\0';
printResult(exp,len);
cout && &键入任何符号，关闭窗口...&;
cin.get();
void binIncrease(bool* digit, int length)
bool isCarry =
for(int i = length -1; i&= 0;i--)
if(digit[i] && isCarry)//如果有进位，且这一位为1
digit[i] =
else if(!digit[i] && isCarry)//如果有进位，且这一位为0
digit[i] =
//没有进位，保持原数
bool boolExpCompute(char* exp, bool* value)
//多数循环计数器
bool temp1,temp2;
char tempOp;
stack&char& //操作符栈
stack&bool& //布尔值栈
optr.push('#');
//表达式开始标志
while(exp[i] != '\0')
//如果是&非&操作符，加入某一布尔值，将&非&转换成二元操作符
if(exp[i] == '!')opnd.push(true);
if(!isOperator(exp[i]))
{ //将字母转换成布尔值
opnd.push(value[exp[i] - 'A']);
switch(getPriority(optr.top(),exp[i]))
case -1://栈顶操作符优先级小于下一操作符
optr.push(exp[i]);
case 0://优先级相等（'('和')'或'#'和'#'相遇）,去括号
optr.pop();
case 1://栈顶操作符优先级大于于下一操作符,计算，结果压栈
tempOp = optr.top();optr.pop();
temp2 = opnd.top();opnd.pop();
temp1 = opnd.top();opnd.pop();
opnd.push(calculate(temp1,tempOp,temp2));
return opnd.top();
bool isOperator(char c)
for(int i = 0; i& OP_NUMBER; i++)
if(c == opList[i])
int getOpPosition(char c)
for(int i = 0; i& OP_NUMBER; i++)
if(c == opList[i])
int getPriority(char op1, char op2)
int op1_pos = getOpPosition(op1);
int op2_pos = getOpPosition(op2);
return opPriority[op1_pos][op2_pos];
bool calculate(bool value1, char op, bool value2)
switch(op)
case '+':return value1 || value2;
case '*':return value1 && value2;
case '!':return !value2;
case 'c':return (!value1 || value2);
case 'e':return (value1 == value2);
bool bracketMatch(char* str)
int i, tempCh;
stack&char&
while((ch = str[i]) != '\0')
if(ch == '(' || ch == ')' )
switch(ch)
s.push(ch);
if(s.size() == 0)
tempCh = s.top();
if(tempCh == '(')s.pop();
return s.empty();
bool operandCheck(char* exp, int n)
for(int i = 0; exp[i] != '\0'; i++)
if(exp[i] &= 'A' && exp[i] &= 'Z')
if(exp[i] & 'A' + n - 1)
else if(!isOperator(exp[i]))
void printResult(char* exp, int len)
int i = 0;
wchar_t wch[3] = L&&&&;
int maxIndex = (int)pow(2.0,len);
//index下标值是极小或极大项下标，true表示对应下标是极小项的，否则为极大项
bool* index = new bool[maxIndex];
bool* value = new bool[len];
wcout.imbue( locale(&chs&));//支持打印宽位字符
for(i = 0; i& i++)
value[i] =
for(i = 0; i& maxI i++)
index[i] =
if(!bracketMatch(exp))
cout && &括号不匹配，重来& && endl &&
else if(!operandCheck(exp,len))
cout && &含非法字符，重来& && endl &&
for(i = 0; i& maxI i++)
index[i] = boolExpCompute(exp,value);
binIncrease(value, len);
//除去exp尾部#，便于打印结果
for(i = 0; exp[i] != '\0'; i++);
exp[i - 1] = '\0';
//主析取范式打印
cout && exp && & = &;
wcout && wch[0] ;cout && &m(&;
for(i = 0; i& maxI i++)
if(index[i]){ cout && }
for(int j = i + 1; j& maxI j++)
if(index[j])cout && &,& &&
cout && &)\n&;
//主析取范式打印
cout && exp && & = &;
wcout && wch[1] ;cout && &M(&;
for(i = 0; i& maxI i++)
if(!index[i]){ cout && }
for(int j = i + 1; j& maxI j++)
if(!index[j])cout && &,& &&
cout && &)\n\n&;
delete [] index,
本类推荐文章
本类最新更新
最新源码下载第一章数理逻辑 命题演算_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
第一章数理逻辑 命题演算
上传于||文档简介
&&淮​海​工​学​院​ ​ ​计​算​机​科​学​与​技​术​ ​ ​教​学​P​P​T
大小：362.50KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢离散数学复习_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
离散数学复习
上传于||暂无简介
大小：265.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
离散数学复习资料 试卷 习题与答案_全案.doc71页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
文档加载中...广告还剩秒
需要金币：250 &&
离散数学复习资料 试卷 习题与答案_全案
你可能关注的文档：
··········
··········
离散数学总复习资料
一、鸽笼原理与容斥原理
1．求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于。
证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于。#
2．对一列个不同整数，任意排列，证明一定存在长为的上升子序列或下降子序列。
证：设此序列为：，从开始上升子序列最长的长度为，下降子序列最长的长度为，每一个都对应了。若不存在长为的上升子序列或下降子序列，那么，形如的不同点对至多有个，而有个，则由鸽笼原理知，必有同时对应，由于，若，则至少比大1，若，则至少比大1，这均与矛盾。故原命题成立。#
3．求中不被3、4、5整除的个数。
解： 设表示中被3整除的数的集合，表示中被4整除的数的集合，表示中被5整除的数的集合，则
， ，进而有
即中不被3、4、5整除的个数为40。#
4．有100个学生，其中60个爱看小说，30个爱下棋，10个既爱看小说，又爱下棋，5个既爱看小说，又爱跳舞，没有既爱下棋，又爱跳舞的，三种活动都不爱的有10个，问有几个学生爱跳舞？
解：设全体学生的集合为，爱看小说的学生集合为，爱下棋的学生集合为，爱跳舞的学生集合为，则依题意有， ，，从而，。另一方面，根据容斥原理，我们有，即有，故，即有15个学生爱跳舞。#
二、数理逻辑
5．求的主析取、主合取范式。
解：取真为： 1,1 ， 0,0 ， 0,1 ；故的主析取范式为；取假为： 1,0 ；故的主合取范式为：。
6．求的主析取、主合取范式。
解：取真为： 1,1,1 ， 0,0,1 ， 0,1,1 ， 1,0,0 ， 1,0,1 ；故的主析取范式为
； 取假为： 1,1,0 , 0,1,0 , 0,0,0 ；
故的主合取范式
正在加载中，请稍后...