2

在我的理论 CS 作业中，我偶然发现了布尔函数的外观问题，即测试 n 个给定的布尔变量、x1 到 xn、k 或更少的变量是否为真。

在 Java 中，这将相当简单：

public boolean k_or_less_true(boolean[] x , int k) {

   int num_true = 0;
   int n = boolean.size;
   for(int i = 0; i < n-1; i++){
       if(x[i]){num_true++;}
   }

   return num_true <= k;
}

现在的问题是通过依赖于 n 和 k 的命题演算找到一个公式，该公式仅在给定的 n 中的 k 或更少为真时才返回真。

举个例子，如果我们让 k = 1，则公式对应于 NAND 函数：

(x1 , x2) <=1 = NOT(x1 AND x2)

(x1 , x2 , x3) <=1 = NOT( (NOT(x1 AND x2)) AND x3)
。
.
.

到目前为止的问题是，如果 k 增加，公式将如何变化......

还有一个非常明显的联系是：

(x1, x2, ..., xn) <=k = (x1, ..., xn) =k OR (x1, ..., xn) =k-1 OR ... OR (x1, ... ., xn) <=1

4

1 回答 1

1

一个简单的公式如下：

f(S) = not [ OR(for T in S^(k+1)) [ AND(for t in T) t ] ]

在上面：

  • OR 是从一组计算的所有项的重复逻辑 OR
  • S^(k+1) 是 S 的所有 (k+1)-子集的集合
  • AND 是从一组计算的所有项的重复逻辑与

这个想法是这样的：

当且仅当至少 k+1 不为真时，k 或更少为真。当且仅当恰好 k+1 的某个子集全部为真时，至少 k+1 为真。

于 2019-06-17T12:39:30.507 回答