Propositional Calculus – How to Prove Logical Consequence

propositional-calculus

How do you guys prove for logical consequence? My teacher said a truth table can be done. But I don't understand how to infer from truth tables to establish logical consequences.

The definition in my course book says:

Let F1 and F2 be two formulae.
F2 is a logical consequence of F1, we write F1 ⊧ F2 iff all models of
F1 are models of F2.

I don't understand what it is being by "all models of F1 are models of F2", i keep thinking about logical equivalence for this statement, I can't discern between the two – logical equivalence and logical consequence. Hence, I have no idea on how to use the truth table to answer questions regarding logical consequence.

Can you guys help to shed light on this issue? Thank you.

Best Answer

In the context of propositional logic, a model is simply an assignment of truth values to the basic propositional variables. The statement $p\land q$ is true in any model that satisfies both $p$ and $q$, i.e., in which $p$ and $q$ are both true; the statement $p\lor q$, on the other hand, is true in any model that satisfies at least one of $p$ and $q$. This information is precisely what you’re collecting when you write out a truth table.

To see whether a formula $F_2$ is a logical consequence of a formula $F_1$, write out their joint truth table. Find the rows in which $F_1$ is true; those are essentially the models that satisfy $F_1$. Check to see whether $F_2$ is also true in all of those rows/models; if it is, then every model that satisfies $F_1$ automatically satisfies $F_2$, and $F_2$ is therefore a logical consequence of $F_1$. Here’s an example.

$$\begin{align*} &F_1:\quad\big(p\to(q\lor r)\big)\land\lnot r\\ &F_2:\quad p\to q \end{align*}$$

Here’s the combined truth table:

$$\begin{array}{c|c} p&q&r&q\lor r&p\to(q\lor r)&\lnot r&p\to(q\lor r)\big)\land\lnot r&p\to q\\ \hline T&T&T&T&T&F&F&\color{blue}{T}\\ \color{green}{T}&\color{green}{T}&\color{green}{F}&T&T&T&\color{red}{T}&\color{blue}{T}\\ T&F&T&T&T&F&F&F\\ T&F&F&F&F&T&F&F\\ F&T&T&T&T&F&F&\color{blue}{T}\\ \color{green}{F}&\color{green}{T}&\color{green}{F}&T&T&T&\color{red}{T}&\color{blue}{T}\\ F&F&T&T&T&F&F&\color{blue}{T}\\ \color{green}{F}&\color{green}{F}&\color{green}{F}&F&T&T&\color{red}{T}&\color{blue}{T} \end{array}$$

The $T$’s for $F_1$ are in red, and those for $F_2$ are in blue. As you can see, in every row in which $F_1$ is true, $F_2$ is also true; the truth values of $p,q$, and $r$ in those rows are in green. $F_1$ holds in precisely those models in which $p$ and $q$ are true and $r$ is false, or $q$ is true and $p$ and $r$ are false, or all three are false. And in all such models $F_2$ holds as well, so $F_2$ is a logical consequence of $F_1$.

Note, though, that $F_2$ holds in some models in which $F_1$ does not hold, e.g., those in which $p,q$, and $r$ are all true. Thus, $F_1$ is not a logical consequence of $F_2$, and therefore $F_1$ and $F_2$ are not logically equivalent.

Related Question