Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

5 Answers

up vote 6 down vote accepted

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.

share|improve this answer
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. –  Carl Mummert Nov 15 '10 at 18:06
    
@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... –  Arturo Magidin Nov 15 '10 at 18:07
add comment

I believe Karnaugh Maps are useful for this purpose.

share|improve this answer
    
+1,this is exactly the precise approach. –  Quixotic Nov 15 '10 at 18:18
add comment

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.

share|improve this answer
add comment

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$

share|improve this answer
add comment

You can also use disjunctive normal form or conjunctive Normal Form(no link because of spam prevention mechanism) for finding the right formula. So for the first answe

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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