= Solution
Simultaneous <propositional substitution> gives
$$
\varphi S=((X\land Y)\to\neg(X\lor Y))\lor(\neg Y\land\neg(X\land Y)).
$$
Let $K=\neg(X\land Y)$. The first disjunct equals $K\lor\neg(X\lor Y)$. By <De Morgan's laws>, $\neg(X\lor Y)=\neg X\land\neg Y$ implies $K=\neg X\lor\neg Y$, so absorption reduces that first disjunct to $K$. The second disjunct is $\neg Y\land K$ and is also absorbed by $K$. Therefore
$$
\boxed{\varphi S\equiv\neg(X\land Y)\equiv\neg X\lor\neg Y.}
$$
The resulting <Boolean function> is false only when both $X$ and $Y$ are true, providing a four-row <truth table> check.
Back to article page
