7
$\begingroup$

How can I solve for $x$ in terms of A, B and C given the truth table below?

$$\begin{array}{ccc|c} A & B & C & x ⇔ A\\ \hline 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0 \end{array}$$

The main way I tried to solve this was by simplifying the truth table into its ANF and then seeing if I could move things around.

So from $(A \land \lnot B \land C) \lor (\lnot A \land B \land C)$ to $(A \land C) \oplus (B \land C)$ but then I got stuck because I didn't know how to get A onto its own in the formula.

The way that I eventually managed to solve it was intuitively but it took forever and it was a lot of guesswork: $$ (((\lnot A \lor \lnot B) \land (A \lor B) \land \lnot C) ⇔ B) ⇔ A $$ $$ \therefore x = (((\lnot A \lor \lnot B) \land (A \lor B) \land \lnot C) ⇔ B) $$

If this question doesn't obey some stylistic convention, I'm happy to edit it. I'm sure it's not professional but I am a hobbyist not a mathematician.

$\endgroup$
  • 1
    $\begingroup$ It might be worth using the symbol $\leftrightarrow$ rather than $\iff$, since the latter is often taken to denote logical equivalence, rather than material equivalence. $\endgroup$ – dwolfeu Jul 15 at 18:54
  • $\begingroup$ @dwolfeu: Alternative binary symbol for the equivalence connective is "⇔" (LaTeX \Leftrightarrow). The longer one (LaTeX \iff) is indeed meant for meta-level equivalence, hence the different spacing. $\endgroup$ – user21820 Jul 16 at 5:14
6
$\begingroup$

By comparing corresponding truth values for $A$ and $(x{\iff}A)$, you can infer the corresponding truth values for $x$:

    If $(x{\iff}A)=1$, then $x=A$, else $x=A'$.

Hence we can extend the truth table to include a column for $x$: $$\begin{array}{ccc|c|c} A & B & C & x{\iff}A&x\\ \hline 0 & 0 & 0 & 0&1\\ 0 & 0 & 1 & 0&1\\ 0 & 1 & 0 & 0&1\\ 0 & 1 & 1 & 1&0\\ 1 & 0 & 0 & 0&0\\ 1 & 0 & 1 & 1&1\\ 1 & 1 & 0 & 0&0\\ 1 & 1 & 1 & 0&0\\ \hline \end{array}$$ which allows us to write $$ x=A'B'C'+A'B'C+A'BC'+AB'C $$ with one term for each of the $4$ rows for which $x=1$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

As a footnote to @quasi's answer, which gives a natural and principled way of getting an answer, it is perhaps worth also noting that $x$ won't be unique.

Find one solution $x$, and any wff tautologically equivalent to $x$ will do as well. For example, $(x \land T) \leftrightarrow A$ has the same truth-table as $x \leftrightarrow A$ for any tautology $T$ at all.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Give the last column a name, say $Y$.
So, you are given $$Y = (x \iff A)$$ which is same as $$Y = (x = A)$$ so $$Y = \lnot(x \ne A)$$ Unequality of boolean values is their exclusive or: $$(p\oplus q) \equiv ((p \land\lnot q)\lor(\lnot p\land q))$$ so: $$Y = \lnot(x \oplus A)$$ hence $$\lnot Y = x \oplus A$$ and $$x = \lnot Y \oplus A$$

From the table $$Y=(A\oplus B)\land C$$ so $$x = \lnot ((A\oplus B)\land C) \oplus A$$

This expands and then contracts as $$\begin{align}x & = \lnot ((\lnot AB\lor A\lnot B)\land C) \oplus A \\ & = \lnot (\lnot ABC\lor A\lnot BC) \oplus A \\ & = ((A\lor\lnot B\lor\lnot C)\land (\lnot A\lor B\lor\lnot C)) \oplus A \\ & = \lnot((A\lor\lnot B\lor\lnot C)\land (\lnot A\lor B\lor\lnot C)) \land A \lor ((A\lor\lnot B\lor\lnot C)\land (\lnot A\lor B\lor\lnot C)) \land \lnot A\\ & = (\lnot ABC\lor A\lnot BC) \land A \lor ((A\lor\lnot B\lor\lnot C)\land (\lnot A\lor B\lor\lnot C)) \land \lnot A\\ & = (\lnot ABCA\lor A\lnot BCA) \lor ((A\lor\lnot B\lor\lnot C)\land \lnot A\\ & = (A\lnot BC) \lor (\lnot A\lnot B\lor\lnot A\lnot C)\\ & = A\lnot BC \lor \lnot A(\lnot B\lor\lnot C)\\ \end{align} $$

where missing operators are $\land$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.