The Dayeinu Boolean Function Is Almost Always True!

Doron ZEILBERGER

Dedicated to Hemi and Yael Nae

[Recall, from Logic 101, that for any two statements, X, Y , X ∨ Y means that “either X or Y or both happened”, X ∧ Y means that both X and Y happened, while X̄ means that X did not happen. For typographical clarity, X ∧ Y is often written XY .]

Two nights ago, my wife Jane and I were fortunate to be guests in a wonderful Passover seder at the house of Hemi^{1} and Yael Nae. Soon enough we came to the number-one hit song, Dayeinu, praising God for doing 15 amazing miracles, let’s call them x_{1}, …, x_{15}, where x_{1} stands for “Took us out of Egypt”, and x_{15} stands for “Built us our Temple”. The exact nature of the other 13 miracles (and for that matter the above two ) are irrelevant to this mathematical paper, but can be easily looked-up in any Haggadah (and of course, nowadays, on the internet).

It so happened that what God actually did can be described by the Boolean function (with n = 15)

G_{n}(x_{1}, …, x_{n}) = x_{1} ∧ … ∧ x_{n} = ⋀_{i=1}^{n} x_{i} ,

whose only truth vector is the all-true vector T^{n}, i.e., assuming, that the probability of any one miracle occuring is p (and that they are independent events), has the tiny probability of p^{n}.

But the author of Dayeinu asserts that God was an over-achiever, and we, the children of Israel, should have been content if the following Boolean function would have been satisfied.

D_{n}(x_{1}, …, x_{n}) = ⋁_{i=1}^{n−1} x_{i} \overline{x_{i+1}} .

The following question immediately came to my mind: How many (and which) truth-vectors are satisfied by the Dayeinu function, and what is the probability that God, deciding randomly which miracles to perform and which not to perform, would have satisfied the minimum requirement demanded by the anonymous author of Dayeinu?

Thanks to DeMorgan we have

\overline{D_{n}(x_{1}, …, x_{n})} = ⋀_{i=1}^{n−1} ( \overline{x_{i}} ∨ x_{i+1} ) .

1 Hemi and I were dorm-mates at the Weizmann Institute, way back in the early seventies. His son is also called

Doron, so we call him ‘little Doron’, while I am ‘big Doron’. ‘Litte Doron’ is no longer so little (he is 25-years-old), but Hemi commented that he knows me (‘big Doron’) much longer than he knows ‘little Doron’.

We are now ready for

The Dayeinu Theorem. The full disjunctive normal form of the negation of the Dayeinu Boolean function is given by

\overline{D_{n}(x_{1}, …, x_{n})} = ⋁_{i=1}^{n+1} ( ⋀_{j=1}^{n−i+1} \overline{x_{j}} ⋀_{j=n−i+2}^{n} x_{j} ) ,

or, more concretely:

\overline{D_{n}(x_{1}, …, x_{n})} = \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−1}} \overline{x_{n}} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−1}} x_{n} ∨ … ∨ \overline{x_{1}} x_{2} … x_{n−1} x_{n} ∨ x_{1} x_{2} ⋯ x_{n} .

Proof: By induction on n. It is true when n = 2 (check!). Assume that it is true when n is replaced by n − 1. Note that

\overline{D_{n}(x_{1}, …, x_{n})} = \overline{D_{n−1}(x_{1}, …, x_{n−1})} ∧ (\overline{x_{n−1}} ∨ x_{n})
= \overline{D_{n−1}(x_{1}, …, x_{n−1})} ∧ \overline{x_{n−1}} ∨ \overline{D_{n−1}(x_{1}, …, x_{n−1})} ∧ x_{n} .

By the inducticve hypthesis:

\overline{D_{n−1}(x_{1}, …, x_{n−1})} = \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} x_{n−1} ∨ … ∨ \overline{x_{1}} x_{2} … x_{n−2} x_{n−1} ∨ x_{1} x_{2} ⋯ x_{n−1} .

Regarding \overline{D_{n−1}(x_{1}, …, x_{n−1})} ∧ \overline{x_{n−1}} we have

\overline{D_{n−1}(x_{1}, …, x_{n−1})} ∧ \overline{x_{n−1}}

= \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}}\overline{x_{n−1}} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} x_{n−1}\overline{x_{n−1}}∨ … ∨\overline{x_{1}} x_{2} … x_{n−2} x_{n−1}\overline{x_{n−1}}∨ x_{1} x_{2} ⋯ x_{n−1}\overline{x_{n−1}} .

Since x_{n−1} \overline{x_{n−1}} is FALSE, all the above terms, except the first, vanish, and since \overline{x_{n−1}} \overline{x_{n−1}} = \overline{x_{n−1}}, we have

\overline{D_{n−1}(x_{1}, …, x_{n−1})} ∧ \overline{x_{n−1}} = \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} .

Regarding \overline{D_{n−1}(x_{1}, …, x_{n−1})} ∧ x_{n} we have

\overline{D_{n−1}(x_{1}, …, x_{n−1})} x_{n} =

\overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} x_{n} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} x_{n−1} x_{n}∨ … ∨\overline{x_{1}} x_{2} … x_{n−2} x_{n−1} x_{n}∨ x_{1} x_{2} ⋯ x_{n−1} x_{n} .

Combining, we have

\overline{D_{n}(x_{1}, …, x_{n})} =
\overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}}

∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} x_{n} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} x_{n−1} x_{n} ∨ … ∨ \overline{x_{1}} x_{2} … x_{n−2} x_{n−1} x_{n} ∨ x_{1} x_{2} ⋯ x_{n−1} x_{n} .

Since

\overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} = \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} \overline{x_{n}} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} x_{n} ,

we get

\overline{D_{n}(x_{1}, …, x_{n})} =
\overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} \overline{x_{n}} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} x_{n} ∨

\overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} x_{n} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} x_{n−1} x_{n} ∨ … ∨ \overline{x_{1}} x_{2} … x_{n−2} x_{n−1} x_{n} ∨ x_{1} x_{2} ⋯ x_{n−1} x_{n} .

Since the second and third term above are the same (and X ∨ X = X), we finally get

\overline{D_{n}(x_{1}, …, x_{n})} =

\overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} \overline{x_{n}} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} \overline{x_{n−1}} x_{n} ∨ \overline{x_{1}} \overline{x_{2}} ⋯ \overline{x_{n−2}} x_{n−1} x_{n} ∨ … ∨ \overline{x_{1}} x_{2}·x_{n} ∨ x_{1} x_{2} ⋯ x_{n−1} x_{n} .

Corollary: Assuming that the probability of each miracle is \frac{1}{2}, and that they are done independently, the probability of not meeting the Dayeinu requirement is \frac{n+1}{2^{n}} and hence of meeting it is 1 − \frac{n+1}{2^{n}}, that happens to be, for n = 15, \frac{2047}{2048} = 0.9995117188.

Comments:

1. Surprisingly, what God actually did, performing all the miracles, is not part of the truth-set of the Dayenu Boolean function, since there is always at least one miracle that is not performed.

2. A faster proof, without Boolean logic, for getting the set of true-false vectors not satisfying the Dayenu function D_{n} (and hence proving the above Dayeinu theorem), can be gotten by finding the set of all members of {T, F }^{n} for which an F never (immediately) follows a T. Of course, this set is {F^{n}, F^{n−1}T, …, T^{n}}.

17 Nissan 5777. Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron

Zeilberger , http://www.math.rutgers.edu/~zeilberg/pj.html, and arxiv.org .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .