1、离散数学主析取范式主合取范式实验二实验题目:生成主析取范式和主合取范式实验目的:1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算;通过实验提高学生编写实验报告、总结实验结果的能力;使学生具备程序设计的思想,能够独立完成简单的算法设计和分析。2.掌握命题逻辑中的联接词、真值表、主范式等,进一步能用它们来解决实际问题。实验内容:利用计算机构造真值表来建立主析取范式和主合取范式实验原理:1.合取:二元命题联结词。将两个命题P、Q联结起来,构成一个新的命题PQ。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P 为真, Q为真时方可PQ为真, 而P、Q只要有一为假则
2、PQ 为假。2.析取:二元命题联结词。将两个命题P、Q联结起来,构成一个新的命题PQ。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P为假, Q为假时方可PQ为假, 而P、Q只要有一为真则PQ为真.3.真值表:表征逻辑事件输入和输出之间全部可能状态的表格.列出命题公式真假值的表。通常以1表示真,0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定,命题联结词的真值表给出了真假值的算法. 真值表是在逻辑中使用的一类数学表,用来确定一个表达式是否为真或有效。4。主析取范式:在含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,而两者之一出现
3、一次且仅出现一次,称该简单合取式为小项。由若干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的。5。主合取范式:在含有n个命题变元的简单析取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项。由若干个不同的大项组成的合取式称为主合取范式;与A等价的主合取范式称为A的主合取范式.任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式,并且是惟一的。实验结果与分析: 实验结果: 实验分析: 参考前面实验的代码,生成真值表,然后找出所有值为1时
4、,各变元的取值,从而生成相应的小项,最终得到主析取范式。找出值为0时各个变元的取值,从而生成相应的大项,最终得到主合取范式。附:程序源代码:htmlscript language=javascriptfunction getTrueTable() var text=document.getElementById(text).value; alert(”输入的公式:”+text); var varList=”; var i=0; var n=text.length; var value=; var code=0; var addList=”; var decList=”; for(i=0;in;
5、i+)/取出公式中的字母 code=text.charCodeAt(i); if((code=97)(code123)) x=text.substr(i,1); if(varList。indexOf(x)0) if(varList.length=0) varList=x; else varList+=,+x; alert(公式中字母列表:+varList); var arrList=varList。split(”,); var n=arrList。length; var table=”table border=1 align=center id=tableMain”; var t=”; for
6、(i=0;in;i+)/输入第一行 t+=+arrListi+/td; t+=td”+text+; t+=td真值/td”; t+=/tr”; table+=t; var m=1; var trow=new Array(n+1); for(i=0;in;i+) m*=2; trowi=0; var j=0; var flag=0; var k=0; var s=; for(i=0;im;i+) t=tr”; value=text; for(j=0;jn;j+) x=arrListj; for(k=0;kvalue。length;k+) if(value。substr(k,1)=x) value
7、=value。substr(0,k)+trowj+value.substr(k+1); t+=td+trowj+”; t+=”td+value+/td”; t+=”td+calcValue(value)+; t+=”/tr; table+=t; if(calcValue(value)=1) s=”; for(j=0;jn;j+) x=arrListj; if(trowj=1) if(s=”) s=x; else s+=”+x; else if(s=”) s=!”+x; else s+=+”!+x; if(addList=) addList=(”+s+); else addList+=+”+”(
8、+s+”); else s=”; for(j=0;j-1;j-) flag=flag+trowj; if(flag=2) trowj=0; flag=1; else trowj=1; break; table+=; table+=br主析取范式是:+addList; table+=br主合取范式是:+decList; document.getElementById(disp)。innerHTML=table;function calcValue(Value) /计算真值表的值 /方法: /第一:计算括号内的值 / 1.从左到右遍历,记录新找到的左括号(的位置 / 2.若新出现的字符是右括号),
9、则说明这对括号是最内层括号, / 将这对括号的内容发送给计算函数,求出其值,再将该括号内换成新值 / 3.再从原来左括号(起,向右寻找。)var nlp=Value.indexOf(”();var i=nlp+1;var nrp=Value.length;var x=”;/第k个字符var v=”;/某个中间公式的值while (nlp=0) x=Value.substr(i,1); if (x=(”) /如果是左括号则将其记下来 nlp=i; i=i+1;/考虑下一个字符 else /如果不是左括号,则判断是否为右括号 if (x=) /第一个右括号之前的最后一个左括号的内容应该没有括号了
10、/调用无括号的计算函数calcValueNoP()计算其值 nrp=i; /alert(去括号前:”+Value); v=calcValueNoP(Value.substr(nlp+1,nrpnlp1)); /起止范围的公式 Value=(nlp0?Value。substr(0,nlp):”)+v+ (nrp+1)=Value.length) /超出字符串的长度 nlp=Value。indexOf((); /测出左括号的起位 i=nlp+1; /经过这轮循环后,应该没有左右括号return calcValueNoP(Value);function calcValueNoP(Value) /先算
11、否定 var nnot=Value.indexOf(!); /第一个合取符号的位置 while (nnot=0) /这个符号可能在第0个位置 /!符号后一个是运算数, /alert(”否定以前的值:+Value); Value=(nnot0?Value。substr(0,nnot):)+ caclNot(Value.substr(nnot+1,1)+ ((nnot+2)=Value。length?Value.substr(nnot+2):”); /alert(”否定以后的值:”+Value); nnot=Value.indexOf(”!”); /先算合取 var nand=Value。inde
12、xOf(); /第一个合取符号的位置 while (nand0) /这个符号不可能在第0个位置,肯定大于0 /符号前一个是运算数, /alert(”合取前的值:+Value); Value=((nand-1)0?Value.substr(0,nand-1):”)+ caclAnd(Value。substr(nand1,1),Value。substr(nand+1,1))+ (nand+2)0?Value。substr(0,nOr1):”)+ caclOr(Value.substr(nOr1,1),Value。substr(nOr+1,1))+ ((nOr+2)bodyh1 align=”center生成一个公式主析取、主合取范式/h1基本方法:生成一个公式的真值表,并且将各变元的值保留下来br公式一:/div/body/html