3

你怎么能用布尔逻辑表达 Y 中的 X 是真的？像以下 2 条这样的规则必须为真（A、B、C、D、E、F）它是乘法还是集合运算的一种形式？
最终结果是所有排列，如 AB OR AC OR AD，如果你说 3 跟随它就像 ABC、ABD、ABE 等。所以它就像 (A,B,C)^2？

谢谢！

4

7 回答 7

3

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

于 2008-11-12T01:34:21.137 回答
3

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

bool nOf(int n, bool[] bs)
{
    foreach(bool b in bs)
    {
      if((n -= b ? 1 : 0) <= 0) break;
    }
    return n == 0;
}
于 2008-11-12T01:39:59.427 回答
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));
于 2008-11-12T02:27:56.180 回答
2

你有这个想法。要表达“n 中的 k 个”，您将需要列举所有 k 成立的案例。所以，如果我们有变量 ABCDE，并且你想要 3 of 5，你需要

(A  &  B &  C & ~D & ~E) |
(A  &  B & ~C &  D & ~E) |
(A  &  B & ~C & ~D &  E) | ...
(~A & ~B &  C &  D &  E)

其中 & 是“和”，| 是“或”，〜是“不是”。

于 2008-11-12T01:32:24.823 回答
0

假设“A或更多”

你可以通过建造一棵树来做得更好

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;
}
于 2008-11-12T01:33:25.447 回答
0

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

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 (Half-Adder)]找到更多示例和链接

然后你可以将这六个变量分成三对，然后弄清楚如何使用这些输出来更接近答案并自己解决其余的问题。

另一种选择是使用电路来查找弹出计数（横向添加）并检查唯一的位是否与 2 匹配。组装而不是逻辑门的著名示例是 [Hakmem 169][ http://home.pipeline.com /~hbaker1/hakmem/hacks.html#item169 (popcount)]。

于 2008-11-14T21:14:40.827 回答
0

您的意思是“恰好两个必须为真”还是“至少两个必须为真”会有所不同。

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

于 2008-12-13T20:29:17.697 回答