Propositional logic examples

In this article we look at a few formulae and their possible assignments using the truth table method.

First example

Let’s find out when this formula is true: ϕ = (p ∧ q) ∨ ¬q. We write the propositional variables p and q in a table:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Next we add the first part of the formula to the table: (p ∧ q), then the negation ¬q, and then the whole formula:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Now we work out the values for the third column, which is a simple conjunction, and also for the negation – there we just put the opposite of the values in the second column:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Finally we work out the values in the last column. This is the whole formula. In terms of our table, we are calculating the disjunction “between the third and fourth columns”. The result:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Second example

Same task, different formula: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). We can see that the formula contains the propositional variables p and q and their negations. So first we create a table with the two variables and their negations:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Next we add the formulae p ∧ ¬q and ¬p ⇒ q, which we can now evaluate easily, because the table contains both the assignments of the individual statements and of their negations. The table looks like this:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Last, we need to evaluate the whole formula, which is the biconditional between the last two columns:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Third example

The third example is a little harder: we will try three propositional variables, which makes the table more complicated to fill in. The formula is: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Because there are three propositional variables, the total number of possible assignments is eight:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

From here on we proceed as in the previous case and fill in each column in all eight rows. The whole table looks like this:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Fourth example

This time we won’t give an ordinary formula but a word problem. Three friends who want to go to a wild party, where topless models will be handing out refreshments, don’t quite like each other and set conditions under which they will go to the party. Their names are Max, Jack and Paul. The rules are as follows:

1. If Max goes, then Jack will go too.
2. Paul will come to the party or, if Max comes, Jack won’t come.
3. Paul will come if and only if Max doesn’t come or Jack doesn’t come.

The question is: can all of them come to the party? If not, who can go to the party without breaking any of the rules?

First we need to rewrite the statements above using propositional variables and formulae. Let’s denote the propositional variables M, J and P (Max, Jack, Paul); each always stands for a statement such as “Max will go to the party”. We could rewrite the first rule like this: M ⇒ J – “if M, then J”, or “if Max goes to the party, then Jack will go to the party”.

We would rewrite the second rule like this. The rule begins with the sentence “Paul will come to the party or…”, so we clearly need a disjunction. For now we write: P ∨ … The next part of the sentence says: “if Max comes, Jack won’t come”. That is an implication, and on the right-hand side we also need a negation: “Jack won’t come” = ¬J. The whole implication would look like this: M ⇒ ¬J. We attach it to the earlier disjunction: P ∨ (M ⇒ ¬J).

We rewrite the third rule like this: we start with “Paul will come if and only if”. That means a biconditional: P ⇔ … Next we have “Max doesn’t come or Jack doesn’t come”, which we rewrite as ¬M ∨ ¬J. Putting it together: (P ⇔ (¬M ∨ ¬J)).

Now we put all the formulae into a table and work out the values:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

The question was whether all three boys can go to the wild party. We find the answer in the first row. It covers the case where all the boys go – this is shown by the three ones in the first three columns. Are all the conditions met? The first is met (fourth column), so is the second (fifth column), but the last is not (last column), where there is a zero. This means that if all three go, the third condition will not be met.

So we look for the rows in which the positions representing the conditions (that is, the last three columns) are all ones. A one means that the condition is met. We can see that this happens in two cases: when Jack and Paul go but Max doesn’t, and when only Paul goes.

You can also work it out by adding to the table a formula ϕ, which will be the conjunction of all three conditions. It looks like this: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). This represents what we want – for all the formulae (all the conditions) to be satisfied. The table would then look like this:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

A few more examples of the truth table method

Because I wrote a program that can automatically build the whole table from a given formula, I have to make good use of it, so here are a few more solved formulae:

Formula: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Table:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formula: (a ∨ ¬a) ⇔ (b ∧ ¬b). Table:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formula: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Table:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formula: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Table:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formula: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Table:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$