[ negation p and (p or q)] implies q.

I have no idea how to start.

Printable View

- Sep 6th 2010, 06:03 PMlm6485Prove 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 PMundefined
"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 PMSoroban
Hello, lm6485!

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

. . . . . . ADI (Alternate Definition of Implication)

. .

Quote:

Prove without truth tables: .

- Sep 7th 2010, 02:52 AMemakarovQuote:

Prove without truth tables: .

In the programmer's view, propositions like , , etc. are types like for natural numbers, for Booleans and for strings of characters. Next, is a function that accepts and returns ; is a pair of and , and is a disjoint union of and .

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

Now, towards the proof of the formula, assume we are given . This is a pair of, first, and, second, either or . We need to produce . If the second given element is , then we are done. If it is , then, using the first element , we can manufacture any type, including . - Sep 7th 2010, 06:37 AMPlato