how does complicated truth tables work?

Question

I am discovering logical reasoning and I saw some examples of simple truth tables and I was wondering how do they work when they turned to be a little bit more complicated for propositions such as:

$(\neg p \wedge \neg(p\rightarrow q)$

Answer 1

Truth tables are created "inside out". You start with the least complex formulae and advance to the more complex formulae.

Here is a recipe. First, list all the subformulae of your formula except the propositional variables:

• $(\neg p \wedge \neg(p \rightarrow q))$
• $\neg p$
• $\neg(p \rightarrow q)$
• $(p \rightarrow q)$

Sort them such that if one formula is a subformula of another, it stands earlier in the list, and write them into a table like this:

$$\begin{array}{cc|cccc} p & q & \neg p & (p \rightarrow q) & \neg (p \rightarrow q) & (\neg p \wedge \neg (p \rightarrow q)) \\ \hline T & T & & & & \\ T & F & & & &\\ F & T & & & &\\ F & F & & & &\\ \end{array}$$

The ordering reflects that $(p \rightarrow q)$ is a subformula of $\neg (p \rightarrow q)$, which again is a subformula of $(\neg p \wedge \neg (p \rightarrow q))$. Plus, because $\neg p$ is a subformula of $(\neg p \wedge \neg (p \rightarrow q))$, it's listed earlier. Of course, $\neg p$ could equally well stand as second or third element, too.

Now you can start filling the remaining truth values. Having ordered the formulae, this is easy: You just go from left to right. Begin by inserting the truth tables for negation and conditional:

$$\begin{array}{cc|cccc} p & q & \neg p & (p \rightarrow q) & \neg (p \rightarrow q) & (\neg p \wedge \neg (p \rightarrow q)) \\ \hline T & T & F & T & & \\ T & F & F & F & &\\ F & T & T & T & &\\ F & F & T & T & &\\ \end{array}$$

Next is the negation of a complex formula. Since you have already 'calculated' the truth values for the formula that is negated, you only have to look them up and, in this case, invert them:

$$\begin{array}{cc|cccc} p & q & \neg p & \mathbf{(p \rightarrow q)} & \neg (p \rightarrow q) & (\neg p \wedge \neg (p \rightarrow q)) \\ \hline T & T & F & \mathbf{T} & F & \\ T & F & F & \mathbf{F} & T &\\ F & T & T & \mathbf{T} & F &\\ F & F & T & \mathbf{T} & F &\\ \end{array}$$

Finally, there is a conjunction. I have highlighted the relevant two columns (for the left and right conjunct); just combine them according to the truth table for conjunction (write 'T' into the last column if both highlighted columns at that line have a 'T', or 'F' otherwise).

$$\begin{array}{cc|cccc} p & q & \mathbf{\neg p} & (p \rightarrow q)& \mathbf{\neg (p \rightarrow q)} & (\neg p \wedge \neg (p \rightarrow q)) \\ \hline T & T & \mathbf{F} & T & \mathbf{F} & F \\ T & F & \mathbf{F} & F & \mathbf{T} & F\\ F & T & \mathbf{T} & T & \mathbf{F} & F\\ F & F & \mathbf{T} & T & \mathbf{F} & F\\ \end{array}$$

Fin.