# Prove a tautology without truth tables.

• September 6th 2010, 06:03 PM
lm6485
Prove a tautology without truth tables.
[ negation p and (p or q)] implies q.

I have no idea how to start.
• September 6th 2010, 06:09 PM
undefined
Quote:

Originally Posted by lm6485
[ negation p and (p or q)] implies q.

I have no idea how to start.

"not p and p" is a contradiction. What does this tell you?

Edit: Maybe it will make more intuitive sense if you put statements in.

"It is true that I'm not happy and that: I'm happy or rich (or both)." Do you see why this in all cases implies that "I'm rich"?

Edit 2: Sorry didn't notice the "without truth tables" part.

This might not be quite right, but here's my attempt

not p and (p or q) <-> (not p and p) or (not p and q) <-> not p and q

so we have

not p
q
--------
therefore q

which is a tautology because the conclusion is the same as one of the premises.
• September 6th 2010, 08:29 PM
Soroban
Hello, lm6485!

Use Distributive, Associative, DeMorgan's Law, and these:

. . . . $p \to q \;=\;\sim\!p \vee q$ . . ADI (Alternate Definition of Implication)

. . $\begin{array}{ccccc}p\;\wedge \sim\!p &=& f & [1] \\ \\[-4mm] p \vee f &=& p & [2] \\ \\[-4mm] p\;\vee \sim\!p &=& t & [3] \\ \\[-4mm] p \vee t &=& t & [4] \end{array}$

Quote:

Prove without truth tables: . $\bigg[ \sim p \wedge (p \vee q)\bigg]\;\to\;q$

$\begin{array}{ccccc} \bigg[\sim\!p \wedge (p \vee q)\bigg]\;\to\;q && \text{Given} \\ \bigg[(\sim p \wedge p) \vee (\sim p \wedge q)\bigg] \;\to\;q && \text{Distributive} \\ \bigg[f \vee (\sim p \wedge q)\bigg] \;\to\;q && [1] \\ \\[-3mm] (\sim p \wedge q) \;\to\;q && [2] \\ \\[-3mm] \sim(\sim p \wedge q) \vee q && \text{ADI} \\ \\[-3mm] (p \;\vee \sim\!q) \vee q && \text{DeMorgan} \\ \\[-3mm] p \vee (\sim\!q \vee q) && \text{Associative} \\ \\[-3mm] p \vee t && [3] \\ \\[-3mm] t && [4]\end{array}$
• September 7th 2010, 02:52 AM
emakarov
Quote:

Prove without truth tables: $\bigg[ \sim p \wedge (p \vee q)\bigg]\;\to\;q$.
Just for fun, I'm going to prove this formula from a "programmer's view".

In the programmer's view, propositions like $p$, $q$, etc. are types like $\mathsf{nat}$ for natural numbers, $\mathsf{bool}$ for Booleans and $\mathsf{string}$ for strings of characters. Next, $p\to q$ is a function that accepts $p$ and returns $q$; $p\land q$ is a pair of $p$ and $q$, and $p\lor q$ is a disjoint union of $p$ and $q$.

I will write $F$ for "false". Then $\neg p$ is equivalent to $p\to F$. Also, $F\to q$ is a tautology for any $q$. Thus, $\neg p$ is a type such that, given $p$, one can produce a value of any type.

Now, towards the proof of the formula, assume we are given $\neg p\land(p\lor q)$. This is a pair of, first, $\neg p$ and, second, either $p$ or $q$. We need to produce $q$. If the second given element is $q$, then we are done. If it is $p$, then, using the first element $\neg p$, we can manufacture any type, including $q$.
• September 7th 2010, 06:37 AM
Plato
Quote:

Originally Posted by lm6485
[ negation p and (p or q)] implies q.
I have no idea how to start.

Frankly, I am puzzled by this question.
This is merely a statement of Disjunctive Syllogism, (D.S.).
That is a standard rule of inference.