Let's say I have a truth table like this:
X Y A
t t f
t f t
f t t
f f fNow, 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 fIs there an approach i'm missing here?
$\endgroup$4 Answers
$\begingroup$I believe Karnaugh Maps are useful for this purpose.
$\endgroup$ 0 $\begingroup$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.
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$
$\endgroup$ $\begingroup$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.
$\endgroup$
