# Prove a tautology without truth tables.

• Sep 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.
• Sep 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.
• Sep 6th 2010, 08:29 PM
Soroban
Hello, lm6485!

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

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

. . $\displaystyle \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: .$\displaystyle \bigg[ \sim p \wedge (p \vee q)\bigg]\;\to\;q$

$\displaystyle \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}$
• Sep 7th 2010, 02:52 AM
emakarov
Quote:

Prove without truth tables: $\displaystyle \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 $\displaystyle p$, $\displaystyle q$, etc. are types like $\displaystyle \mathsf{nat}$ for natural numbers, $\displaystyle \mathsf{bool}$ for Booleans and $\displaystyle \mathsf{string}$ for strings of characters. Next, $\displaystyle p\to q$ is a function that accepts $\displaystyle p$ and returns $\displaystyle q$; $\displaystyle p\land q$ is a pair of $\displaystyle p$ and $\displaystyle q$, and $\displaystyle p\lor q$ is a disjoint union of $\displaystyle p$ and $\displaystyle q$.

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

Now, towards the proof of the formula, assume we are given $\displaystyle \neg p\land(p\lor q)$. This is a pair of, first, $\displaystyle \neg p$ and, second, either $\displaystyle p$ or $\displaystyle q$. We need to produce $\displaystyle q$. If the second given element is $\displaystyle q$, then we are done. If it is $\displaystyle p$, then, using the first element $\displaystyle \neg p$, we can manufacture any type, including $\displaystyle q$.
• Sep 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.