Учитывая n булевых переменных, как проверить, истинны ли k или менее из них только с помощью исчисления высказываний?

Question

Во время моих заданий для теоретического 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, который возвращает истину только и только если k или меньше из заданных n верны.

Для примера, если мы допустим, что k = 1, формула соответствует NAND-функции:

(x1, x2) ^{<= 1} = NOT (x1 AND x2)</sup>

(x1, x2, x3) ^{<= 1} = НЕ ((НЕ (x1 И x2)) И x3),,.</sup>

Пока вопрос в том, как формула изменится, если k увеличится ...

Также довольно очевидная связь:

(x1, x2, ..., xn) ^{<= k} = (x1, ..., xn) = k ИЛИ (x1, ..., xn) = k-1 ИЛИ ... ИЛИ (x1, ..., xn) <= 1 </sup></sup>

Answer 1

Простая формула для этого следующая:

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

В вышеприведенном:

• ИЛИ - это повторяющееся логическое ИЛИ всех членов, вычисленных из набора
• S ^ (k + 1) - множество всех (k + 1) -подмножеств S
• И - повторяющееся логическое И всех членов, вычисленных из набора

Идея такова:

Это тот случай, когда k или меньше истинны, если и только если это не тот случай, когда по крайней мере k + 1 верны. По крайней мере, k + 1 истинны тогда и только тогда, когда все подмножества с точно k + 1 верны.