布尔表达式

Question

你如何用布尔逻辑表达X中的Y是真实的？例如，规则“以下2个必须为真（A、B、C、D、E、F）”，这是一种乘法还是集合操作？最终结果是所有排列组合，如AB或AC或AD。如果你说要选3个，则是ABC、ABD、ABE等，所以是（A，B，C）^2吗？

谢谢！

- Enigmae

Answer 1

在布尔逻辑中（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。

- Pax Diablo

Answer 2

假设使用C#或其他bool != int的语言：

bool nOf(int n, bool[] bs)
{
    foreach(bool b in bs)
    {
      if((n -= b ? 1 : 0) <= 0) break;
    }
    return n == 0;
}

- Patrick

Answer 3

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));

- Peter

Answer 4

你的想法是正确的。要表达“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)

&表示“与”，|表示“或”，~表示“非”。

- Seneca the Younger

Answer 5

我会数它们。 但是如果你必须仅使用布尔运算来生成谓词，那么你可以将输入视为位进入加法器系统。

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）]。

- waynecolvin

Answer 6

假设“一个或多个”

通过构建树，您可以做得更好

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;
}

- BCS

Answer 7

区分“必须有两个是真的”和“至少有两个是真的”是有区别的。

对于变量集合{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的集合，由具有真值的变量组成的子集恰好有两个元素。（使用<=而不是“=”来表达您问题的另一种解释。）

- joel.neely