Home / Computer science / 3-satisfiability (3SAT) / Explore / Case 2: Two literals
Proof
By truth tables, with
\begin{equation*} c' = (c'_1 \land c'_2), \end{equation*}we have
\begin{align*} \begin{array}{ccc|cccc} \ell_1 & \ell_2 & y & c & c'_1 & c'_2 & c' \\[1ex] 0 & 0 & 0 & \boxed{0} & 0 & 1 & \boxed{0} \\[0.25ex] 0 & 0 & 1 & \boxed{0} & 1 & 0 & \boxed{0} \\[0.25ex] 0 & 1 & 0 & \boxed{1} & 1 & 1 & \boxed{1} \\[0.25ex] 0 & 1 & 1 & \boxed{1} & 1 & 1 & \boxed{1} \\[0.25ex] 1 & 0 & 0 & \boxed{1} & 1 & 1 & \boxed{1} \\[0.25ex] 1 & 0 & 1 & \boxed{1} & 1 & 1 & \boxed{1} \\[0.25ex] 1 & 1 & 0 & \boxed{1} & 1 & 1 & \boxed{1} \\[0.25ex] 1 & 1 & 1 & \boxed{1} & 1 & 1 & \boxed{1} \\[0.25ex] \end{array} \> \> . \end{align*}\(\blacksquare\)