2

given some truth value, how can we indeed deduce what the form is like? For example,

P Q R X

T T T T

T T F F

T F T T

T F F T

F T T T

F T F F

F F T F

F F F T

Here, given the truth value of X, can you deduce the form of X in term of P,Q,R?? I think if time are given one can guess the formula but if the case become more complicated, it seem very inefficient to guess. Is there any more general technique or algorithm?

john
  • 43
  • You would use Karnaugh-maps to do this. have a look at http://math.stackexchange.com/questions/10392/how-to-find-the-logical-formula-for-a-given-truth-table?rq=1 – Ahmed Masud May 21 '13 at 05:45

1 Answers1

6

For any truth table, there are many logical expressions that have that truth table. We give a simple mechanical method for producing such an expression. The main disadvantage is that in general, the expression so obtained is quite a bit longer than necessary.

Look at all the entries that give truth value $T$. The first one is $TTT$. Write down $P\land Q\land R$.

The next one is $TFT$. Write down $P\land \lnot Q\land R$.

The next one is $TFF$. Write down $P\land \lnot Q\land \lnot R$.

Continue, one for every combination of truth values that yields $T$. The remaining two are $FTT$ and $FFF$. Write down the appropriate conjunctions.

Put $\lor$'s between all the things you wrote down. We get the expression $$(P\land Q\land R)\lor (P\land \lnot Q\land R)\lor (P\land \lnot Q\land \lnot R) \lor (\lnot P\land Q\land R)\lor (\lnot P\land \lnot Q\land \lnot R) .$$

A little thinking shows why this gives the right truth table. It certainly gives $T$ at the right places. And at the places where the truth table yielded $F$, everyone of the conjunctions that were $\lor$-ed is false.

The above procedure gives us what is called the full disjunctive normal form (DNF). This form may be quite inefficient. There are good algorithms for simplifying a DNF to use a much smaller number of connectives. This minimization process is an important part of circuit design.

We can also do some hand-optimization. For example, note that there are only $3$ combinations that give the value $F$, as against $5$ that give the value $T$. So write down the disjunctive normal form we would get if the $F$ and $T$ in the last column had been switched, put an $\lnot$ in front. and use De Morgan's Laws to simplify. We will get a conjunctive normal form that is simpler than the DNF we got. There are many other tricks/methods.

André Nicolas
  • 507,029