离散数学主析取范式主合取范式.doc

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