2

During my assignments for theoretical CS I stumbled over the questions how a boolean function would look, that tests if of n given boolean vars, x1 to xn, k or less variables are true.

In Java this would be fairly simple : 

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

The problem now is to find a formula by means of propositional calculus dependent on n and k, that returns true only and only if k or less of the n given are true.

To give an example, if we let k = 1, the formula corresponds to the NAND-function :

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

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

So far the question is, how the formula changes if k increases...

Also a pretty obvious connection is :

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

Lennart F
  • 21
  • 2
  • I'm voting to close this question as off-topic because it's a mathematics question, not a computer programming question. You already have the computer program. – Raymond Chen Jun 16 '19 at 14:54

1 Answers1

1

A straightforward formula for this is the following:

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

In the above:

  • OR is a repeated logical OR of all terms computed from a set
  • S^(k+1) is the set of all (k+1)-subsets of S
  • AND is a repeated logical AND of all terms computed from a set

The idea is this:

It is the case that k or fewer are true if and only if it is not the case that at least k+1 are true. At least k+1 are true if and only if some subset of exactly k+1 are all true.

Patrick87
  • 27,682
  • 3
  • 38
  • 73