Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
Great answer as always Brian Scott, I always know to look for answers by you! I just started my first graduate logic course and was intimidated by the abstract notation at first (S-interpretations and all that jazz) but after reading through this I see that the abstraction for a similar question is just as easy as the more specific undergrad version of the question! Thank you for always formulating such comprehensive answers. –  Clark Zinzow Sep 30 '13 at 19:05
    
@Clark: You’re welcome, and thank you. –  Brian M. Scott Sep 30 '13 at 19:10
    
Scott, Thanks for your through explanation . This really resolved my doubts regarding "Logical Equivalence" and "Logical Consequence". Thank you. –  user98322 Oct 2 '13 at 22:53
    
@Vijay: You’re welcome; I’m glad that it was so helpful. –  Brian M. Scott Oct 3 '13 at 5:29

Logical equivalence goes in both directions; consequence goes one way only.

For example, in the elementary theory of groups, we can let $F_1$ be $\forall x:x*x=e$ and $F_2$ be $\forall x:x*x*x*x=e$.

Then $F_2$ is a consequence of $F_1$, because every group that satisfies $F_1$ also satisfies $F_2$. But they are not equivalent because there are groups where $F_2$ is true but $F_1$ isn't -- such as the cyclic group of order 4.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.