IIT Bombay | MS/PhD Admission Test Dec. 2024 | Question: 122

Question

A student wishes to build circuits representing propositional logic formulas. However, she doesn't have the usual "$\mathrm{AND}$", "$\mathrm{OR}$", "$\mathrm{NOT}$" gates available for this purpose. Instead, she has the following ternary (i.e. three-input) "gates" available to her.

• $\mathrm{AE}$ (or "All Equal"): Evaluates to true iff all its three inputs have the same truth value. Thus, $\mathrm{AE}(0,0,0)=\mathrm{AE}(1,1,1)=1$, and $\mathrm{AE}(p, q, r)=$ 0 for all other values of $p, q, r$.
• $\mathrm{EO}$ (or "Exactly One"): Evaluates to true iff exactly one of its inputs is true. Thus, $\mathrm{EO}(1,0,0)=\mathrm{EO}(0,1,0)=\mathrm{EO}(0,0,1)=1$, but $\mathrm{EO}(p, q, r)=0$ for all other values of $p, q, r$.
• $\operatorname{MAJ}$ (or "Majority"): Evaluates to the same truth value as the majority of its inputs. Thus, $\operatorname{MAJ}(0,1,1)=\operatorname{MAJ}(1,1,0)=\operatorname{MAJ}(1,0,1)= \operatorname{MAJ}(1,1,1)=1$ and $\operatorname{MAJ}(1,0,0)=\operatorname{MAJ}(0,0,1)=\operatorname{MAJ}(0,1,0)= \operatorname{MAJ}(0,0,0)=0$.
• $\mathrm{ONE}$: Always evaluates to true, regardless of its inputs.

Which of the following statements is/are true (choose all that apply).

1. Every propositional logic formula can be represented using only $\mathrm{EO}$ and $\mathrm{ONE}$.
2. There exists at least one propositional logic formula that cannot be represented using only $\mathrm{AE}$ and $\mathrm{MAJ}$.
3. Every propositional logic formula can be represented using only $\mathrm{MAJ}$ and $\mathrm{ONE}$.