Constructing Truth Tables for Formulas with Variable Valuations

Question

I was solving a problem from old exams and got stuck here. I'd appreciate the help.

We have the three variables p, q, and r. There are 8 valuations of the variables. If F is a propositional logic formula containing p, q, and r, and we construct a truth table for F, the table will thus have 8 rows.

Provide a formula F with the variables p, q, and r that is true for the valuations

$${ \lbrace p : F, q : T, r : F \rbrace, \lbrace p : T, q : T, r : F \rbrace, \lbrace p : T, q : F, r : F \rbrace }$$

and is false for all other valuations.

I drew a truth table and got an answer which goes: $((p⋁q⋁r) ⋁ \neg (p⋁q⋁r)) \to ((r \to p) ⋀ r)$

BUT this took a lot of time to the point I started to think is this even how we are supposed to solve this problem. There has gotta be another way than just playing with the truth table given the fact that we have a short time for the exam.

My question: Is there another easier way to solve it? If not, how do I find an easier formula and faster?

Answer 1

One way to do this, assuming the list of cases is interpreted the way I believe it ought to be, is as follows.

The expression is true when:

• either $p = F$ and $q = T$ and $r = F$
• or $p = T$ and $q = T$ and $r = F$
• or $p = T$ and $q = F$ and $r = F$.

We're practically there.

We just express it symbolically as:

$$(\neg p \land q \land \neg r) \lor (p \land q \land \neg r) \lor (p \land \neg q \land \neg r)$$

This is now in disjunctive normal form, and is one of the standard forms in which an arbitrary propositional logical statement can be expressed.

It is possible to simplify it considerably, for example and for a start by factorising $\neg r$ out using distributivity rules.

EDIT: Decided to complete the job, as follows:

Hence we get: $$((\neg p \land q) \lor (p \land q) \lor (p \land \neg q)) \land \neg r$$

Then we notice that: $(\neg p \land q) \lor (p \land q) \lor (p \land \neg q)$ just means "false when both $p$ and $q$ are false.

That is: $(\neg p \land q) \lor (p \land q) \lor (p \land \neg q)$ is the same as $\neg (\neg p \land \neg q)$, which by De Morgan is just $p \lor q$.

Hence what we get at the end is: $$(p \lor q) \land \neg r$$

Edit 2: For clarity, here is the truth table:

$$\begin {array} {|ccc|c|c|c|} \hline p & q & r & p \lor q & \neg r & (p \lor q) \land \neg r \\ \hline F & F & F & F & T & F \\ F & F & T & F & F & F \\ F & T & F & T & T & T \\ F & T & T & T & F & F \\ T & F & F & T & T & T \\ T & F & T & T & F & F \\ T & T & F & T & T & T \\ T & T & T & T & F & F \\ \hline \end {array}$$