The majority vote among three

The majority vote among three

Our purpose is to prove the equivalence of

(0) $\left( {{X}{\Lambda }Y}\right) \vee \left( {{Y}{\Lambda }Z}\right) \vee \left( {{Z}_{\Lambda }X}\right)$ and (1) $(X \vee Y) \wedge (Y \vee Z) \wedge (Z \vee X)$

To save work, $\left( {?!,!}\right)$ is a permutation of(v,w); note that these operators satisfy

(2) $[X?Y \equiv X \equiv Y \equiv X!Y]$

We observe for any $A,B,C$

$$ \begin{array}{l} A? B? C \ = {2) \mathrm {w i t h} X, Y := A, (B? C) } \ A \equiv B? C \equiv A! (B? C) \ = {(2) \mathrm {w i t h} X, Y := B, C } \ A \equiv B \equiv C \equiv B! C \equiv A! (B \equiv C \equiv B! C) \ = {\mid d i s t r i b u t e s o v e r \equiv \equiv } \ A \equiv B \equiv C \equiv A! B \equiv B! C \equiv C! A \equiv A! B! C! \ \end{array} $$

Applying the equivalence of first and last line with $A,B,C = X!Y,Y!Z,Z!X$ we find

(3) $[ (X!Y)? (Y!Z)? (Z!X) \equiv$

$$ X! Y \equiv Y! Z \equiv Z! X ] $$

as the idempotence of ! reduces the four last terms of the last line all to $X!Y!Z$

We now observe

$$ \begin{array}{l} (X \wedge Y) \vee (Y \wedge Z) \vee (Z \wedge X) \ = {3) w i t h!, ? := \wedge , \vee } \ X \wedge Y \equiv Y \wedge Z \equiv Z \wedge X \ = {G o l d e n R u l e t h r i c e a n d [ X \equiv Y \equiv Y \equiv Z \equiv Z \equiv X ] } \ X _ {v} Y \equiv Y _ {v} Z \equiv Z _ {v} X \ = {3) w i t h!, ? := v, \wedge } \ (X \vee Y) \wedge (Y \vee Z) \wedge (Z \vee X) \ \end{array} $$

In passing we found two other expressions for the majority vote among three, viz. the continued equivalence of the pairwise disjunctions or of the pairwise conjunctions.

Austin, 4 March 1991

prof.dr.Edsger W.Dykgsta

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712 - 1188

USA