# Math Help - Tautologies

1. ## Tautologies

Heres what I know, I know what a tautology is, I know what it looks like from looking at a truth table. Heres what i need help with, how do i prove these are tautologies, just truth tables alone?(also how would i set these up in a truth table) or are there other methods i could use. I only got a little past using truth tables in my book so id probably feel more comfortable using those.
a) ¬q ^ p -> q -> ¬p
b) p V q ^ ¬p -> q
( ^ is supposed to be the upside down V)

2. ## Re: Tautologies

To start, could you clarify the syntactic conventions? It is usually assumed that implication associates to the right, i.e., ¬q /\ p -> q -> ¬p is ¬q /\ p -> (q -> ¬p). I also assume that /\ binds stronger than \/, i.e., p \/ q /\ ¬p -> q is p \/ (q /\ ¬p) -> q.

Originally Posted by KellyFay
how do i prove these are tautologies, just truth tables alone?
Yes, or some modification of the truth table method.

Originally Posted by KellyFay
(also how would i set these up in a truth table)
If you know how to construct truth tables, then you should be able to do this for these formulas. Otherwise, what exactly is your question about truth tables?

Originally Posted by KellyFay
are there other methods i could use.
It is sometimes easier to try to find a falsifying assignment (valuation, interpretation). For example, if ¬q /\ p -> (q -> ¬p) is false, then ¬q /\ p is true and (q -> ¬p) is false, which means that q is true and ¬p is false. From the last two facts, both p and q are true, but then ¬q /\ p is not true. Since there is no falsifying assignment, the formula is a tautology.

There is a falsifying assignment for p \/ (q /\ ¬p) -> q, but not for (p \/ q) /\ ¬p -> q.

3. ## Re: Tautologies

Hello, KellyFay!

Could you replace the parentheses?
I'm sure that the problems weren't give to you this way . . .

$(a)\;\sim q \wedge p \to q \to \;\sim p$

$(b)\;p \vee q \:\wedge \sim p \to q$

$\sim\!q \wedge p \to q \to \;\sim\!p$ can be interpreted in a number of ways:

. . $\big[(\sim\!q \wedge p) \to q\big] \to\; \sim\!p$

. . $(\sim\!q \wedge p) \to (q\to\; \sim\!p)$

. . $\big[\sim\!q \wedge (p \to q)\big] \to \sim\!p$

. . $\sim\!q \wedge \big[(p\to q) \to\; \sim\!p\big]$

. . $\sim q \wedge \big[p \to (q \to\; \sim\!p)\big]$

. . $\sim\big[(q \wedge p) \to (q \to \sim\!p)\big]$

. . . . . . . . .etc.

4. ## Re: Tautologies

Since KellyFay has not returned, I guessed what her problems were.

$(a)\;(\sim\!q \wedge p) \to (q \to \:\sim\!p)$

$\begin{array}{|c|c||c|c|c|c|c|c|c|} p&q&(\sim\!q & \wedge & p) & \to & (q & \to & \sim\!p) \\ \hline T&T& F&F&T& {\color{red}T} & F&F&F \\ T&F & T&T&T & {\color{red}T} & F&T&T \\ F&T & F&F&F & {\color{red}T} & T&T&T \\ F&F & T&F&F & {\color{red}T} & F&T&T \\ \hline && 1 & 2 & 1 & 3 & 1 & 2 & 1 \\ \hline \end{array}$

$(b)\;\big[(p \vee q) \:\wedge \sim\!p \big] \to q$

$\begin{array}{|c|c||c|c|c|c|c|c|c|} p&q & [(p & \vee & q) & \wedge & \sim\!p] & \to & q \\ \hline T&T & T&T&T& F & F & {\color{red}T} & T \\ T&F & T&T&F & F & F & {\color{red}T} & F \\ F&T & F&T&T& T & T & {\color{red}T} & T \\ F&F & F&F&F & F & T & {\color{red}T} & T \\ \hline &&1&2&1&3&1&4&1 \\ \hline \end{array}$

5. ## Re: Tautologies

That's a lot of work!
Thanks (I like the numbering scheme on the bottom row - is that a standard practice?)
It doesn't change the tautology, but I think there are two incorrect entries in the top diagram. (They look like transcription errors, because you then produced a correct result based not on what's showing, but on what should be showing - if I'm following you correctly.)
Top diagram, top row, 3rd column from the right (under the "q"): I think it should be a T.
Top diagram, 2nd row, rightmost column (under the "~p"): I think it should be an F.
Oh - and I think I see one more:
Bottom diagram, bottom row, rightmost column(under the "q"): I think it should be an F .