逻辑代数的化简
程序代码：<html>
<head>
<meta charset=utf-8>
</head>
<body>
</body>
<script>
Array.prototype.P=function(){//全排列
var r=[];
var that=this;
!function(n){
for(var i=n;i<that.length;i++){
[that[i],that[n]]=[that[n],that[i]];
if(n+1<that.length-1) arguments.callee(n+1);
else{
r.push(that.slice(0));
};
[that[i],that[n]]=[that[n],that[i]];
}
}(0);
return r;
};
String.prototype.padStart=function(n,s){//补0
var a=n-this.length;
return s.repeat(a)+this;
};
String.prototype.set=function(){//字符串转集合
if(/[2-9]/.test(this)){//判断是否为十进制表示
var a=this.split(',').map(x=>parseInt(x)).set();//得到一个十进制整数集合
}else{
var a=[];
var a1=this.split(',');
n=a1[0].length;
var len1=a1.length;
for(var i=0;i<len1;i++){
a=a.S_u(FJ(a1[i]));
};
};
return a.sort((a,b)=>a-b);
};
Array.prototype.set=function(){//数组唯一化
var r=[];
for(var i=0;i<this.length;i++){
if(this.indexOf(this[i])==i) r.push(this[i]);
};
return r.sort();
};
Array.prototype.toB=function(n){//十进制数组转换为二进制字符串数组
var r=[];
var len=this.length;
for(var i=0;i<len;i++){
r.push(this[i].toString(2).padStart(n,'0'));
};
return r;
};
Array.prototype.S_d=function(a){//差集
var b=this.slice().set();
var a=a.set();
return b.filter(v => !a.includes(v));
};
Array.prototype.S_u=function(a){//并集
var b=this.slice();
return b.concat(a).set();
};
Array.prototype.S_n=function(a){//交集
var b=this.slice().set();
var a=a.set();
b.filter(v => a.includes(v));
return b;
};
Array.prototype.S_in=function(a){//属于
var a=a.set();
var b=this.slice().set();
var c=b.S_u(a);
return a.length==c.length;
};
FJ=function(A){//把带*号的二进制字符串分解成十进制集合
var len=A.length;
var num=0;
for(var i=0;i<len;i++){
if(A[i]=='*'){
num++;
};
};
if(!num){
return [parseInt(A,2)];
};
var NN=2**num;
var D=[];
for(var k=0;k<NN;k++){
var x=k.toString(2).padStart(num,'0');
var n=0;
var t='';
for(var i=0;i<len;i++){
if(A[i]=='*'){
t+=x[n];
n++;
}else{
t+=A[i];
};
};
D.push(parseInt(t,2));
};
return D;
};
String.prototype.HJ=function(M){//化简
var comp=function(a,b){//对比两个二进制数:如果只有一位不同,返回合并;如果多位不同返回0
var t='';
var n=0;
var len=a.length;
for(var i=0;i<len;i++){
if(a[i]!=b[i]){
n++
if(n>1){
return 0;
};
t+='*';
}else{
t+=a[i];
};
};
return t;
};
var union=function(M,s,b){//M的所有元素去除M[s]的元素的集合+b集合
var r=(b||[]).slice();
var len=M.length;
for(var i=0;i<len;i++){
if(i!=s){
r=r.S_u(FJ(M[i]));
};
};
return r;
};
var N=function(n){//生成1到n的自然序列
var r=[];
for(var i=0;i<n;i++){
r.push(i);
};
return r;
};
var ZZ=function(A,b){//获取所有可能的最小覆盖(A是质蕴含集合,b是不定项的具体集合)
var N=[];//必要蕴含项************
var U=[];//互有元蕴含
var len=A.length;
for(var i=0;i<len;i++){
if(!(FJ(A[i]).S_in(union(A,i,b)))){
N.push(A[i]);
}else{
U.push(A[i]);
};
};
var V=union(A).S_d(union(N));//必要蕴含项的补集
if(V.length){
var W=U.P();//互有蕴含的全排列
len=W.length;
var R=[];//所有可能的互有蕴含集合
var len1=W[0].length;
for(var i=0;i<len;i++){//必要蕴含的补集对互有蕴含连续做差集,直到差集为空集
var S=V.slice();
var r=[];
for(var j=0;j<len1;j++){
S=S.S_d(FJ(W[i][j]));
r.push(W[i][j]);//保存参与做差集的互有蕴含
if(!S.length){
break;
};
};
R.push(r);
};
R.sort(function(a,b){return a.length-b.length});//按照互有蕴含个数从小到大排列
var RR=[];
RR.push(R[0].sort().toString());
var len2=R[0].length;
for(var i=1;i<len;i++){
if(R[i].length==len2){//获取最小互有蕴含个数的集合
RR.push(R[i].sort().toString());
}else{
break;
};
};
RR=RR.set();//唯一化选出的互有蕴含
len=RR.length;
var TR=[];
for(var i=0;i<len;i++){
TR=TR.S_u(RR[i].split(','));
};
var lenT=TR.length;
var TTR=[];
var flag=true;
for(var i=0;i<lenT;i++){//选出互有蕴含中重复的项目
flag=true;
for(var j=0;j<len;j++){
if(RR[j].indexOf(TR[i])==-1){
flag=false;
break;
};
};
if(flag){
TTR.push(TR[i]);//保存重复项目
};
};
for(var i=0;i<len;i++){
RR[i]=RR[i].split(',').S_d(TTR);
};
N=N.concat(TTR);
return '{'+N.toString()+'},[{'+RR.join('},{')+'}]';
}else{
return '{'+N.toString()+'}';
};
};
var a=this.set();
var b=(M||[]).set();
var n=(~~Math.log2(Math.max(...(a.S_u(b)))))+1;//获取最大十进制数对应的二进制位数(二进制的宽度)
var A=[];//全体质蕴含项(二进制字符串表示)的集合
!function(m){//生成全体质蕴含项(qm法的第2步)
var index=[];//保存参与合并的基础项下标
var B=[];//合并后的字符串
var xxx=0;
var len=m.length;
for(var i=0;i<len;i++){
var rr=[];//临时保存合并后的字符串
for(var j=i+1;j<len;j++){
xxx=comp(m[i],m[j]);//对比生成合并项目
if(xxx){
rr.push(xxx);
index.push(i,j);
};
};
if(rr.length){//如果生成了合并项目,则并到B中
B=B.S_u(rr);
};
};
index=index.set();//唯一化
var time=N(len).S_d(index);//获得没有参与合并的基础项下标
var len1=time.length;
for(var i=0;i<len1;i++){//把没有参与合并的基础项放到A中
A.push(m[time[i]]);
};
if(B.length){//如果B中还有待处理的项目,则把B作为参数递归一次
arguments.callee(B);
};
}(a.toB(n));
return ZZ(A,b);//得到必要蕴含和所有可能的非必要蕴含最小集合
};
</script>
</html>
