14
$\begingroup$

Let's say I have a truth table like this:

X  Y   A
t  t  f
t  f  t
f  t  t
f  f  f

Now, I have to find the formula for A. This case is rather easy because I can immediately see that this looks like the inverted values of X~B, thus ¬(X~B). Now, for a more complicated problem I do not know the method.

X  Y  Z  A
t  t  t  f
t  t  f  f
t  f  t  t
t  f  f  f
f  t  t  f
f  t  f  f
f  f  t  t
f  f  f  f

Is there an approach i'm missing here?

4 Answers 4

1

Solve first the problem of finding the formula for truth tables which have exactly one T on the rightmost table. Then go to the general case.

13

I believe Karnaugh Maps are useful for this purpose.

10

Expanding on Mariano's answer: to get a formula for a truth table that has exactly one t and the rest of the lines are f, look at the line and write down the values of the variables in that line. For instance, if you wanted a formula for a truth table with three variables as in your second example which has a t in the third line (corresponding to $X$ and $Z$ true, and $Y$ false) and f in all the other ones, then since that line is "$X$ is true, $Y$ is false, and $Z$ is true", then you use the formula $X \wedge (\neg Y)\wedge Z$.

Now, suppose you have a formula with t's in two rows and fs everywhere else. Say, three variables, a t in row three, a t in row five, and f's everywhere else. A formula that has a t in just row three is, as before, $X\wedge (\neg Y)\wedge Z$. A formula that has a t in just row five is $(\neg X)\wedge (\neg Y)\wedge Z$. So a formula that as a t in just row three or row five is: $$\Bigl( X\wedge (\neg Y)\wedge Z\Bigr) \vee \Bigl((\neg X)\wedge (\neg Y)\wedge Z\Bigr).$$

For an arbitrary number of t's, just take the disjunction of enough formulas, each of which corresponds to a table with just one t.

  • 3
    The general point here is that the lines that end in "T" can be used to produce a formula in disjunctive normal form that will give you back the same truth table. But the formulas obtained in this way may have redundancy, for example the displayed formula in this answer is equivalent to $(\lnot Y) \land Z$. The method of Karnaugh maps, mentioned by Moron in another answer, is useful because it can produce shorter, more "optimized", formulas.2010-11-15
  • 0
    @Carl: Quite right; I meant to mention that this will lead to *a* formula, but not necessarily a short (or best) one. One need only consider the table of $X\vee Y$ to see this...2010-11-15
3

Pick out the rows where a t appears in the rightmost column, and write down a disjunctive normal form. In your example, there are only two rows with a t and your expression will have two terms:

$ (X \cdot \bar{Y} \cdot Z) + (\bar{X} \cdot \bar{Y} \cdot Z) $

Now you have a logical formula for your truth table. You can stop there, or you can use the laws of boolean algebra to get a simpler expression. In this case, you can use the distributive law:

$ (X \cdot \bar{Y} \cdot Z) + (\bar{X} \cdot \bar{Y} \cdot Z) = (X + \bar{X})\cdot (\bar{Y} \cdot Z) = 1 \cdot (\bar{Y} \cdot Z) = \bar{Y} \cdot Z$