Number of implementations of a boolean function taking into account necessary, sufficient, and necessary and sufficient conditions.

Question

Suppose we wanted to implement a boolean function, such as isRectangle, by making note of its necessary, sufficient, and necessary and sufficient conditions and combining them in different ways. How many unique implementations can we make?

For the example of isRectangle, we have

Let $P = $ "shape $s$ is a rectangle"

$N$: Necessary condition of $P$ (i.e. $P \rightarrow N$)

• $N_1 = $ shape $s$ has four sides
• $N_2 = $ shape $s$ has four angles

$S$: Sufficient condition for $P$ (i.e. $S \rightarrow P$)

• $S_1 = $ shape $s$ is a square

$T$: Necessary and sufficient conditions (i.e. $P \leftrightarrow T$)

• $T_1 = $ shape $s$ has four angles and they are all right angles

One implementation of isRectangle would be:

def isRectangle(s):
  if not N1: return False
  if not N2: return False
  if S1: return True
  return T1

but this is just one of many. A second could be:

def isRectangle(s):
  if S1: return True
  if not N2: return False
  return T1

And yet a third could be

def isRectangle(s):
  return T1

---

In general, how many implementations are there of a boolean function, when taking into account necessary conditions, sufficient conditions, and necessary and sufficient conditions?

Answer 1

---

In general, for a given proposition $P$,

• Let $N$ be the set of necessary, but not sufficient, conditions of $P$, that is, $N = \{C\ |\ P \rightarrow C\ \wedge\ C \not\rightarrow P\}$.
• Let $S$ be the set of sufficient, but not necessary, conditions for $P$, that is $S = \{C\ |\ C \rightarrow P\ \wedge\ P \not\rightarrow C \}$.
• Let $T$ be the set of necessary and sufficient conditions for $P$, that is, $T = \{C\ |\ P \leftrightarrow C\}$.

Necessary and Sufficient conditions allow us to do early returns

• Early return False: if any $N$ condition is false, then $P$ is false.
• Early return True: if any $S$ condition is true, the $P$ is true.

We can implement $P$ as any of the following

def isP(input):
  NS_early_return*
  T_return

where

NS_early_return := N_early_return | S_early_return
N_early_return := "if not n: return False"
S_early_return := "if s: return True"
T_return := return t

where n $\in N$, s $\in S$, and t $\in T$.

Now, to count the number of implementations of this boolean function,

• Let $|N|$ be the count of necessary, but not sufficient, conditions
• Let $|S|$ be the count of sufficient, but not necessary, conditions
• Let $|T|$ be the count of necessary and sufficient conditions

Then any $r$-permutation of $N$ and $S$ conditions (with $r$ ranging from $0$ to $|N| + |S|$) followed by a $T$ condition form an implementation.

The total number of implementations, then$^1$, is $\bigg\lfloor e \cdot \big(|N|+|S|\big)! \bigg\rfloor\ \cdot |T|$

---

$^1$: See How to compute $\sum_{r=0}^N \frac{N!}{(N-r)!}$? This quantity is the count of $r$-permutations of $N$ items (for $r$ ranging from $0$ to $N$).

---

Why check a necessary condition or a sufficient condition when all we need to do is check a necessary and sufficient condition? A: In some cases, a $N$ (necessary) condition) or a $S$ (sufficient) condition is easy(ier) to check than a $T$ (necessary and sufficient) condition and if the $N$ condition fails, we can return False early, or if the $S$ condition succeeds, we can return True early w/o having to check a more expensive $T$ condition.