Find logic expression for given truth table

3.9k Views Asked by At

So I was given this truth table and I need to find a logical expression for the formula to give such a result (where there can be two or three 2-place connective expressions (e.g. $A \lor B$ counts as one but $\neg A$ does not count since only one variable is within it). Can anyone help me? I have been thinking for ages and I am not getting anywhere near the answer!

P Q R (Formula)

T T T F

T T F T

T F T F

T F F T

F T T T

F T F F

F F T F

F F F F

2

There are 2 best solutions below

0
On

One easy solution is $$(P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R)$$

The above statement is the disjunctive normal form of the searched statement. You get it by looking at all cases, where the final statement should be true. Then you concatenate each input ($A$ if the variable $A$ is true in this case and $\neg A$ if $A$ is false in this case) with $\land$. All these statements are afterwards concatenated with $\lor$.

1
On

Look at each row in which $T$ is in the right-most column.

Then "and" all the truth-value assignments that yield that row true, and do the same for the remaining rows which evaluate to true:

P Q R (Formula)

T T T F

T T F T $\leftarrow$

T F T F

T F F T $\leftarrow$

F T T T $\leftarrow$

F T F F

F F T F

F F F F


What we get is the proposition in normal disjunctive form:

$$(P\land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P \land Q \land R)\tag{1}$$

Each of the disjuncts above represents a different row of the truth table (each one yielding true in the right-most column): Note that there are three possible truth-value assignments to the variables that make the expression true; we use "or" between the three clauses since all it takes is one of those clauses to be true in order for the proposition to be true.

$(1)$ no doubt can be simplified; I'll leave that to you. Give it a go, and follow up below if you get stuck.

Edit: $$\begin{align}(P\land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P \land Q \land R) &\equiv [(P \land \lnot R)\land(Q\lor \lnot Q)] \lor (\lnot P \land Q \land R)\\ \\ &\equiv (P\land \lnot R) \lor (\lnot P \land Q \land R) \end{align}$$