So, I have the statement
(p ^ q) \/ (p ^ ¬ q) ≡ p
I have to prove the given logical equivalence using Theorems and not constructing a truth table. If anyone has as idea how I prove this I would appreciate an explanation and solution.
cheers
-ipatch
Hello, ipatch!
I don't know the names of the theorems you know.
I hope you can follow my proof.
Prove: .
. . . . . . . . .
. . . . Distributive
. . . . . .
. . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . Distributive
. . . . . . . . . . . . .
. . . . . . . . . . . . . . .
(p ^ q) \/ (p ^ ¬ q) ≡ p
1. (p ^ q) \/ (p ^ ¬ q)-----------------hypotesis
2. (p ^ q)-----------------assume
3. p-----------------2, ^-elim 2
4. (p ^ ¬ q)-----------------assume
5. p-----------------4, ^-elim 2
6. p-----------------1, 2-3 , 4-5, \/-elim
Rules used:
conjunctive elimination ( ^-elim ) if you have A and B the you have A (or B)... simple
disjuntive elimination (\/-elim)... a little more complex... if you have A or B and from A you can deduce C; and from B you can deduce C; then from A or B we can deduce C.....
ipatch:
There two kind of proofs,one in Boolean Algebra and one in propositional calculus.
The proof in Boolean Algebra was shown by other people in the forum.
The proof in propositional calculus is as follows:
First we prove : and then:
.
Proof:
1) .................................................. ............................given
2) .................................................. ..............................................assu mption to start a conditional proof
3) p................................................. .................................................. .....from (2) and using Conjunction Elimination (=C.E)
4) .................................................. ....................................from (2) to (3) and using the rule of conditional proof
5) In the same way we prove:
6) .................................................. ...........................from (4)and(5) and using the rule called proof by cases: .
7) .................................................. .......................................from (1) and (6) and using M.Ponens
8) .................................................. .......................................tautology
9) .................................................. ........................................from (8) and using biconditional elimination
10) p................................................. .................................................. ....from (7) and (9) and using M.Ponens
Now to prove the converse.
Proof:
1)p............................................... .................................................. given
2) .................................................. ........................................assumption to start a conditional proof
3) .................................................. ..........................................from (2) and using De Morgan
4) .................................................. .....................from (3) and using material implication
5) .................................................. .....................................from (1) and (4) and using M.Ponens
6) .................................................. ...........................from (1) and (5) and using Conjunction Introduction
7) .................................................. .......................from (2) to(6) and using the rule of conditional proof
8) .................................................. ........................from (7) and using material implication