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 can I show that this is a tautology by using a truth table? $(p∨q)∧(¬p∨r)\to(q∨r)$

I know how to do it by logical equivalences, but now I have to use a truth table. Never done it before so I dont even know where to start.

share|improve this question

3 Answers 3

The idea is that you create a truth table for the whole statement. If the "output" column is only "true" values, then it's a tautology (by definition). It helps to build this truth table slowly, adding only one binary operation at a time:

$$\begin{array}{c|c|c||c|c|c|c|c||c} p & q & r& \neg p & (p \lor q) & (\neg p\lor q) & (p \lor q)\land(\neg p\lor q) & (q \lor r) & (p \lor q)\land(\neg p\lor q)\to (q \lor r) \\\hline T & T & T & F & T & T & T & T & T \\\hline T & T & F & F & T & T & T & T & T \\\hline T & F & T & F & T & F & F & T & T \\\hline T & F & F & F & T & F & F & F & T \\\hline \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\\hline F & F & F & T & F & T & F & F & T \end{array}$$

I've left out some rows so there's still some fun for you to have... ;)

share|improve this answer
1  
$\TeX$ing, like a boss. –  Pedro Tamaroff May 2 '13 at 22:44

To make a truth table, you make columns for all the variables and rows for all combinations of truth values of the variables. Then you make as many columns as you want to assess the truth value of the statement in question. If you want to prove something a tautology, it must be true for all values of the truth value of the variables. I'll give some lines of the table:

$$\begin {array}{c|c|c|c|c|c} \\ p&q&r&p \vee q&\lnot p \vee r&q \vee r \\ \hline T&T&T&T&T&T\\T&T&F&T&T&T\\F&F&F&F&T&F \end {array}$$

There are five more lines. Mine would usually be the first, second, and eighth lines in the table. Now add some columns to build up your expression.

share|improve this answer
    
Thanks to both of you! It really helped! –  Maren May 2 '13 at 22:24

"I don't know where to start." Then read the appropriate chapter(s) of some good textbook to get the principle of using truth-tables before asking here (for it is the general technique you need to know).

There are a lot of good books to choose from! I happen to like P*t*r Sm*th's Introduction to Formal Logic. Among freely available treatments, Paul Teller's Modern Formal Logic Primer is now available from his website and is very good.

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.