谢谢!
在布尔逻辑中(v表示OR,谓词后面的'表示NOT):
A B C'D'E'F' v
A B'C'D'E'F v
A'B C'D'E'F' v
: : : : : :
<absolute bucketload of boolean expressions>
: : : : : :
A'B'C'D'E F
使用排列组合时,你需要编写许多子表达式。
当然,如果这是一个编程问题,你可以将布尔值转换为0或1,将它们加起来并确保结果为2。
bool nOf(int n, bool[] bs)
{
foreach(bool b in bs)
{
if((n -= b ? 1 : 0) <= 0) break;
}
return n == 0;
}
Python:
expressions = [A, B, C, D, E, F, G ]
numTrue = len(filter(None, expressions)
PHP:
$expressions = array(A, B, C, D, E, F, G);
$numTrue = count(array_filter($expressions));
你的想法是正确的。要表达“k of n holds”,你需要枚举所有k成立的情况。因此,如果我们有变量A B C D E,并且您想要5个中的3个,您将需要:
(A & B & C & ~D & ~E) |
(A & B & ~C & D & ~E) |
(A & B & ~C & ~D & E) | ...
(~A & ~B & C & D & E)
&表示“与”,|表示“或”,~表示“非”。
我会数它们。 但是如果你必须仅使用布尔运算来生成谓词,那么你可以将输入视为位进入加法器系统。
Basic Half-Adder
A, B : 1st 2nd bits
O, C : unit output and carry to next unit
O := A xor B;
C := A and B;
您可以在[Wikipedia][http://en.wikipedia.org/wiki/Half_adder(半加器)]中找到更多的例子和链接。
然后,您可以将这六个变量分成三对,然后想出如何使用这些输出来接近答案并自己解决其余部分。
另一个选择是使用电路查找pop count(侧向加法),并检查是否仅有的位匹配为2。汇编中著名的例子不是逻辑门,而是[Hakmem 169][http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169(popcount)]。
假设“一个或多个”
通过构建树,您可以做得更好
2 : a&(b|c|d|e|f) | b&(c|d|e|f) | c&(d|e|f) | d&(e|f) | e*f
3 : a&(b&(c|d|e|f) | c&(d|e|f) | d&(e|f) | e*f) | b&(c&(d|e|f) | d&(e|f) | e*f) | c&(d&(e|f) | e*f) | d&e&f
或者作为代码
bool AofB(int n, bool[] bs)
{
if(bs.length == 0) return false;
if(n == 0) return true;
foreach(int i, bool b; b[0..$-n])
if(b && AofB(n-1,b[i+1..$]) return true;
return false;
}
更好的是
bool AofB(int n, bool[] bs)
{
foreach(bool b; bs) if(b && --n == 0) return true;
return false;
}
区分“必须有两个是真的”和“至少有两个是真的”是有区别的。
对于变量集合{A..F},Pax和Charlie Martin的回答涵盖了“恰好两个”的情况(两个为真,其余为假),而你问题中的表达似乎处理的是“至少两个”的情况:
(A && B) || (A && C) || ... || (D && E) || (D && F) || (E && F)
是一个表达式,当A和B为真且其余变量为任何值(真或假)时,该表达式为真。
如果您要求的是类似于集合论的表达式来描述上述情况,则可以表达为以下形式:
#{x | x <- {A, B, C, D, E, F} | x} = 2
符号的使用方式如下:
#{...}
表示封闭集的大小和集合本身:
{x | x <- {A, B, C, D, E, F} | x}
读作“集合x
,其中x
是从A
到F
中的一个,并且x
为真”。换句话说,给定变量A
到F
的集合,由具有真值的变量组成的子集恰好有两个元素。(使用<=
而不是“=”来表达您问题的另一种解释。)