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.

I need to find the Boolean expression for the truth table below where $P$, $Q$, $R$ are inputs, and $S$ is the output. Does anyone have a cool easy way of solving such problems please? Your help will be appreciated.

$$\begin{array}{c|c|c||c} P & Q & R & S\\ \hline 1 & 1 & 1 & 1\\ \hline 1 & 1 & 0 & 0\\ \hline 1 & 0 & 1 & 1\\ \hline 1 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 1\\ \hline 0 & 1 & 0 & 1\\ \hline 0 & 0 & 1 & 0\\ \hline 0 & 0 & 0 & 0 \end{array}$$

share|improve this question
    
I'm sorry, but how is what you gave meant to be interpreted? I would have guessed that each xxx y is meant to be that the row corresponding the the assigments xxx has y as the output, but you have four variables (P, Q, R, and S), and only three inputs. –  Arturo Magidin May 10 '11 at 21:20
    
Thanks @Quanta. @Arturo, yes, I have 3 inputs and 1 output, S –  user10695 May 10 '11 at 21:26
    
While boolean algebra and discrete mathematics would fit, logic is really the proper tag. Mathematical physics? Not at all... –  Asaf Karagila May 10 '11 at 21:54
    
Karnaugh map (en.wikipedia.org/wiki/Karnaugh_map) is the simplest way to go. –  Brandon Carter May 10 '11 at 22:14
add comment

2 Answers

up vote 4 down vote accepted

A mechanical way of getting an expression that has a desired truth table is to take the disjunction of the formulas that determine the rows you want with 1s.

For example, for a truth table on P, Q, and R that has $$\begin{array}{c|c|c||c} P & Q & R & \text{Table}\\ \hline 1 & 1 & 1 & 1\\ \hline 1 & 1 & 0 & 0\\ \hline 1 & 0 & 1 & 1\\ \hline 1 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 1\\ \hline 0 & 1 & 0 & 1\\ \hline 0 & 0 & 1 & 0\\ \hline 0 & 0 & 0 & 0 \end{array}$$ we note that the rows corresponding to $1$s are: $P\land Q\land R$, $P\land \neg Q\land R$, $\neg P\land Q\land R$, and $\neg P\land Q\land\neg R$. So a formula that has the desired truth table is $$(P\land Q\land R)\lor (P\land\neg Q\land R)\lor (\neg P\land Q\land R) \lor (\neg P\land Q\land \neg R).$$ This is, of course, unlikely to be the simplest formula that works, and may be simplified later.

share|improve this answer
    
Awesome!! thanks! –  user10695 May 10 '11 at 21:33
    
This can by easily simplified, for example the $$(P \land Q \land R)$$ and $$(P \land \neg Q \land R)$$ clauses only differ by the $$Q$$ and $$\neg Q$$ so they can be condensed to a single $$(P \land R)$$. This is the type of simplification that the Karnaugh map does for you. –  tolomea May 10 '11 at 23:19
    
Note: this is also a very convenient way to write a formula in disjunctive normal form. –  amWhy May 11 '11 at 20:22
add comment

You can just render the thing as a bunch of OR-ed together clauses, one checking for each case where the output is 1. If you want a simpler expression, you can use a Karnaugh map.

share|improve this answer
    
If you do the Karnaugh map the resulting expression is $$(P \land R) \lor (\neg P \land Q)$$ –  tolomea May 10 '11 at 23:15
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.