Examples on propositional logic

In the article we will show some formulas and their possible evaluations using the table method.

The first example

Let's try to see when this formula is true: $\phi=(p \wedge q) \vee \neg q$. Let's write down the propositional symbols p and q in the table:

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

Next, let's write down the first part of the formula in the table: (p ∨ q), the negation $\neg q$ and then the whole formula:

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

Now we will calculate the values for the third column, that is the simple conjunction and also for the negation - there we just insert the reversed values than what is in the second column:

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

Finally, we calculate the values in the last column. That's the whole formula. Given our table, we thus calculate the disjunction "between the third and fourth columns". Result:

$$\begin{array}{ccccc} p&q&p \wedge q&\neg q&\phi\\ 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 problem, different formula: $(p \wedge \neg q) \Leftrightarrow (\neg p \Rightarrow q)$. We see that the formula contains the propositional symbols p and q and their negations. So we first create a table with the two symbols and their negations:

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

Next, we add the formulas $\phi=p \wedge \neg q$ and $\neg p \Rightarrow q$, which we can already evaluate easily, since we have both the evaluation of the individual statements and their negations in the table. The table looks like this:

$$\begin{array}{cccccc} p&q&\neg p&\neg q&(p\wedge \neg q)&(\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}$$

The last thing we need to do is to evaluate the whole formula, which is the equivalence between the last two columns:

$$\begin{array}{ccccccc} p&q&\neg p&\neg q&(p\wedge \neg q)&(\neg p\Rightarrow q)&\phi\\ 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}$$

The third example

The third example will be a bit more complicated, we will try three propositional symbols, which will make the table calculation more complex. The formula will look like this: $\phi=(\neg(p\Rightarrow q)) \wedge (r\Leftrightarrow(\neg p \vee q))$.

Since there are three propositional symbols, the total number of variations of the evaluation will be 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}$$

Next, we will proceed as in the previous case, evaluating each column in all eight rows. The whole table will look like this:

$$\begin{array}{ccccccccc} p&q&r&\neg p&(p\Rightarrow q)&(\neg p\vee q)&\neg (p\Rightarrow q)&(r\Leftrightarrow (\neg p\vee q))&\phi\\ 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 example is no longer entered as a simple formula, but as a word problem. Three friends who want to go to a wild party where topless models will be handing out refreshments don't exactly like each other and set conditions on which they will go to the party. Their names are Martin, James and Peter. The rules are as follows:

1. If Martin goes, so does Jakub.

• Peter will go to the party or, if Martin goes, Jakub will not go.
• Peter will come if Martin doesn't come or James doesn't come.

The question is, can everybody come to the party? If not, who can go to the party and not break any rules?

The first thing we need to do is to rewrite the previous verbal statements into propositional symbols and formulas. So let's label the propositional symbols M, J and P (Martin, James, Peter) and it will always denote a statement like "Martin will go to the party". We could rewrite the first rule as $M \Rightarrow J$ - "if M, then J", or "if Martin goes to the party, then James goes to the party".

The second rule could be rewritten as follows. The rule starts with "Peter will come to the party or...", so obviously we need a disjunction. For now, we'll write this down: P∨… The next part of the sentence says, "If Martin is coming, James will not be coming." That's an implication, and we still need to use negation on the right-hand side. "James will not come" = $\neg J$. The whole implication would look like this: $M \Rightarrow \neg J$. We'll add that to the previous disjunction: $P \vee M \Rightarrow \neg J$.

We rewrite the third rule as follows: we start with "Peter will come right then". This implies equivalence: P ⇔ … Next we have "Martin will not come or James will not come", which we rewrite as follows: $\neg M \vee \neg J$. We put together: $(P\Leftrightarrow (\neg M\vee \neg J))$.

Now we put all the formulas into a table and calculate the values:

$$\begin{array}{cccccc} M&J&P&(M\Rightarrow J)&(P\vee (M\Rightarrow \neg J))&(P\Leftrightarrow (\neg M\vee \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 could go to a wild party. The answer can be found in the first row. This gives us the answer to the case where all the boys will go - this is signalled by the three 1s in the first three columns. Are all the conditions met? The first yes (fourth column), the second also (fifth column), but the last no (last column), there is a zero. That means that if all three go, the third condition will not be met.

So we are looking for those rows in which the positions symbolizing the conditions (i.e. the last three columns) are all ones. A one means that the condition is satisfied. We see that this occurs in two cases. If James and Peter go but Martin does not, and then if only Peter goes.

You can also calculate this by adding the formula $\phi$ to the table, which will be the conjunction of all three conditions. So it will look like this: $\phi = ((M\Rightarrow J)\wedge (P\vee (M\Rightarrow \neg J))\wedge (P\Leftrightarrow (\neg M\vee \neg J)))$. This represents what we want - that all formulas (all conditions) are satisfied. The table would then look like this:

$$\begin{array}{ccccccc} M&J&P&(M\Rightarrow J)&(P\vee (M\Rightarrow \neg J))&(P\Leftrightarrow (\neg M\vee \neg J))&\phi\\ 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}$$

Some examples of the table method

Since I have written a program that can automatically build a whole table from a given formula, I need to use it properly, so what follows are a few more solved formulas:

Formula: $((a\wedge \neg b)\vee (b\wedge (b\Rightarrow a)))$. Table:

$$\begin{array}{ccccc} a&b&(a\wedge \neg b)&(b\wedge (b\Rightarrow a))&((a\wedge \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\vee \neg a)\Leftrightarrow (b\wedge \neg b)$. Table:

$$\begin{array}{ccccc} a&b&(a\vee \neg a)&(b\wedge \neg b)&((a\vee \neg a)\Leftrightarrow (b\wedge \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: $\neg (a\vee b)\Leftrightarrow (\neg b\wedge \neg a)$. Table:

$$\begin{array}{ccccc} a&b&\neg (a\vee b)&(\neg b\wedge \neg a)&(\neg (a\vee b)\Leftrightarrow (\neg b\wedge \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: $(\neg p \Leftrightarrow (q \wedge r)) \Rightarrow (p \vee \neg (p \wedge q))$. Table:

$$\begin{array}{cccccccc} p&q&r&(q\wedge r)&\neg (p\wedge q)&(\neg p\Leftrightarrow (q\wedge r))&(p\vee \neg (p\wedge q))&\phi\\ 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: $\neg(p\Leftrightarrow \neg q) \wedge (r \Rightarrow \neg p) \wedge (p \vee r)$. Table:

$$\begin{array}{ccccccc} p&q&r&\neg (p\Leftrightarrow \neg q)&(r\Rightarrow \neg p)&(p\vee r)&\phi\\ 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}$$