Find a logical statement containing 3 variables, where it is only true when any two of the variables are true.

discrete mathematicslogic

I can only use negations and implications.

My first idea was to try out all the possibilities, but that failed. My second idea was to write the solution in a truth table and look for two statements where, when I connect them with an implication, gives the solution. These two statements will be referred to as $S_1$ and $S_2$. The truth table for the solution is based on the wording of the question. And $S_1$ and $S_2$ are based on the behavior of implications. Where I've put "$-$", it can be both true or false.

\begin{array}{|c|c|c|c|c|c|}
A & B & C & S_1 & S_2 &Solution\\
\hline
1 & 1 & 1 & 1 & 0 & 0\\
1 & 1 & 0 & – & – & 1\\
1 & 0 & 1 & – & – & 1\\
1 & 0 & 0 & 1 & 0 & 0\\
0 & 1 & 1 & – & – & 1\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{array}

I have observed that $S_1$ and $S_2$ cannot take the form of $X \implies \neg Y$ when using only one implication. I have tested all other forms: $X \implies Y$; $Y \implies X$; $\neg X \implies Y$; $\neg Y \implies X$; $\neg X \implies \neg Y$; $\neg Y \implies \neg X$;

I did not find a candidate for $S_1$ or $S_2$

Is there a better method I can employ to find this statement?

Thanks

Best Answer

You need to have many more implications.

Note that $p\lor q=(\lnot q\Rightarrow p)$ and so $p\land q=\lnot(q\Rightarrow \lnot p)$ in the Lindenbaum algebra of our Boolean algebra. So I'll leave you to build $((A\land B)\lor (B\land C))\lor (C\land A)$.

Related Question