关于计算使逻辑式为真的状态数

zgg___

这个问题已经考虑了很久，论坛的一些帖子使我又联想起它，在这里提出来吧。 对于一个有n个变量的逻辑表达式，它的形式是先乘后加的样子，其中乘法表示and，加法表示or，假设它有m项。 例如：f(a,b,c,d)=ab+bcd+ac，它的n=4，m=3。 所有变量的取值都只能是0或1，当所有变量取遍所有的值时（共有2^n种情况），问其中f==1的情况共有多少次？（这个数定义为T(f)） 例如上面的f，T(f)=7。 可以看到，f对应于一个n*m的01矩阵M={{1,1,0,0},{0,1,1,1},{1,0,1,0}}，所以问题也可以是问对于某个M的T(M)。 那么对于一个n为几百，m为几千的M，有没有可行的算法来计算T(M)。 附：如果M的自同构群对计算有帮助，可以认为是已知的。所谓M的自同构群G(M)就是Sn的一个子群，用Sn的某个元素来置换M的列，如果存在一种行的置换使其恢复原状，那么这个元素就属于G(M)，反之就不属于G(M)。对于上面问题，我们可以认为M和它的转置的G都是已知的。

gxqcn

对于这个问题，我能想到的是德·摩根定律，但似乎与本问题关联性不大，因为没有涉及“非”运算。 看是否可以这样并行运算： 1、因式分解，尽可能将表达式化为乘积形式； 2、将各项独立分拆成单项式，比如原 f 可分拆成：f1(a,b)=ab, f2(b,c,d)=bcd, f3(a,c)=ac，可并行计算 f1, f2, f3 的真值表； 3、整合各单项式的真值表得到多项式的真值表； 4、重复步骤2,3，得到最终原表达式的真值表。

wsc810

将原式化为纯异或表达式（这个不难，有一定的方法），不知对问题的解决有无帮助。我将原式所化的结果为F=AB^AC^ABC^BCD^ABCD,F=1,所对应的向量为ABCD(0,1,1,1),(1,0,1,0),(1,1,0,0),(1,1,0,1)(1,1,1,0)(1,1,1,1)不知缺哪一个？

G-Spider

对于大变量数，比如1000个，从左向右算，首先要列出2^1000种，又如果右表达式只有一个运算ab 这将是一个灾难..............不可取。所以 我将每个变量用一个bit位来表示，这样一个字节可表示8个变量。分项的表达式中若存在该变量，则该位为1，否则为0，这样得到了以下的处理过程(对于极大的变量数，比如1000个需要用到大数来存储，相信不难，只涉及简单的逻辑运算)，以下也是我脑子里模拟计算机的运算过程。不妥之处请指正。 比如下面一个比较典型的例子： f(a,b,c,d,e)=ab+ac+abc++ae+abd+abe+bcd 其中全1的必为真 ;----------------- 1.分析表达示 ab: 11000 ac: 10100 abc: 11100 ae: 10001 abd: 11010 abe: 11001 bcd: 01110 ;----------------- 2.逻辑过滤 比如ab,abc,abd,abe实现只需要ab即可. 经过(n-1)*n/2次与运算，过滤。比如ab&&abc=11000&&11100=11000=ac则abc被过滤掉(清0即可)，依次... 得到最基本的有效组: ab: 11000 ac: 10100 ae: 10001 bcd: 01110 ;----------------- 3.解析出每个基本项的所有有效解(不包括本身和全1(已经得到了)) 比如对于ac:10100得到满足最高位为1和第3位为1的其他所有组合。 处理： 10100取反有01011再压缩1(其实就是1的个数n) =>111=>(取1～(n-1)) =>001,010,011,100,101,110 =>扩展成01011格式有 =>00001,00010,00011,01000,01001,01010 =>与ac:10100进行或运算 =>10101,10110,10111,11100,11101,11110 这就是对于基本项ac的所有扩展解 其他类似...一遍处理完ab,ac,ae,bcd这样得到了所有扩展解，当然可能含有重复项 ;----------------- 4.重复项过滤 再进过(n-1)*n/2次比较运算即可实现重复项的过滤。 完毕. ;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 又如： f(a,b,c,d)=ab+ac+bcd ;----------------- 1.分析表达示 ab: 1100 ac: 1010 bcd: 0111 ;----------------- 2.逻辑过滤 ab: 1100 ac: 1010 bcd: 0111 ;----------------- 3.解析 ab:1100=> 0011=>11=>01,10=>0001,0010=>1101,1110 ac:1010=> 0101=>11=>01,10=>0001,0100=>1011,1110 bcd:0111=> 1000只有一个1，无扩展解 ;----------------- 4.重复项过滤 所有扩展解: 1101 1110 1011 1110 过滤后为： 1101 1110 1011 再加上基本有效组: 1100 1010 0111 再加上全1: 1111 即得到所有有效情形： 1101，1110，1011，1100，1010，0111，1111

zgg___

感谢大家的讨论……呵呵。 题目中的已知条件是一个逻辑表达式f，它是m项的和(or)，每一项都是小于等于n个变量的积(and)，这样，表达式的长度将小于m乘n，这是算法的输入，它可以用一个m乘n的01矩阵来表示；输出是一个数，如果能将f展开成范式，那么这个数就是范式的项数，但是这个数将是2^n量级（虽然比2^n小许多），因此，当n为几百时，无法将f展开成范式，也无法将f等于1的所有情况罗列出来。我想找到一种算法，仅仅是能够计数f等于1的所有情况。

wsc810

If we expand the minimal term of logic function .then we can get all status. Thats the n