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

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