Thread: How to prove logical equivalence using Theorems and substitution?

1. How to prove logical equivalence using Theorems and substitution?

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

2. Originally Posted by ipatch
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
Just read it as a sentence:

"p and q" or "p and not q".

It's saying you have to have p but you may or may not have q.

So what it's the same as having? p.

3. I have to prove the given logical equivalence using Theorems and not constructing a truth table
The solution depends on what theorems you have in mind. Every course may have a different set of those.

4. Hello, ipatch!

I don't know the names of the theorems you know.
I hope you can follow my proof.

Prove: .$\displaystyle (p \;\wedge\; q) \;\vee\; (p\; \wedge \sim q) \;\;\equiv \;\; p$

. . . . . . . . . $\displaystyle (p \;\wedge\; q) \;\vee\; (p\; \wedge\; \sim q)$

. . $\displaystyle (p \;\vee\; p) \;\wedge\; (p \;\vee\; \sim q) \;\wedge\; (q \;\vee\; p) \;\wedge\; (q \;\vee\; \sim q)$ . . Distributive

. . . . . . $\displaystyle p\;\wedge\;(p\;\vee\;\sim q)\;\wedge\;(p\;\vee\; q) \;\wedge\; T$

. . . . . . . . . $\displaystyle (p\;\vee\;\sim q)\;\wedge\; (p\;\vee q)$

. . . . . . . . . . . $\displaystyle p\;\vee(\sim q\;\wedge\; q)$ . . . . . . . . . . . . Distributive

. . . . . . . . . . . . . $\displaystyle p\;\vee\;F$

. . . . . . . . . . . . . . . $\displaystyle p$

5. Hello ipatch
Originally Posted by ipatch
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
Using the standard Laws of Boolean Algebra (for instance, just here) we get:
$\displaystyle (p \land q)\lor(p\land\neg q) \equiv p\land(q\lor\neg q)$ (Distributive Law)
$\displaystyle \equiv p\land T$ (Complement Law)

$\displaystyle \equiv p$ (Identity Law)

6. (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

7. Hello again, ipatch!

My first proof was long and clumsy.
(Don't know where my brain was at the time.)

There are two theorems we need. .(I don't know their names.)

. . $\displaystyle \begin{array}{cccc}P \;\vee \sim \!P &\equiv& t & \text{Theorem 1} \\ \\[-3mm] P \wedge \:t &\equiv& P & \text{Theorem 2} \end{array}$

. . . . $\displaystyle \begin{array}{ccc}(p \;\wedge\; q) \;\vee\; (p\; \wedge\; \sim q) & \text{Given} \\ \\ p \;\wedge\; (q \;\vee \sim \!q) & \text{Distr.} \\ \\ p \;\wedge \;t & \text{Theorem 1} \\ \\ p & \text{Theorem 2} \end{array}$

8. Originally Posted by cgafa
(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.....

9. Originally Posted by ipatch
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
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 : $\displaystyle (p\wedge q)\vee (p\wedge\neg q)\Longrightarrow p$ and then:

$\displaystyle p\Longrightarrow (p\wedge q)\vee (p\wedge\neg q)$.

Proof:

1)$\displaystyle (p\wedge q)\vee (p\wedge\neg q)$.................................................. ............................given

2)$\displaystyle (p\wedge q)$.................................................. ..............................................assu mption to start a conditional proof

3) p................................................. .................................................. .....from (2) and using Conjunction Elimination (=C.E)

4)$\displaystyle (p\wedge q)\Longrightarrow p$.................................................. ....................................from (2) to (3) and using the rule of conditional proof

5) In the same way we prove: $\displaystyle (p\wedge\neg q)\Longrightarrow p$

6)$\displaystyle (p\wedge q)\vee (p\wedge\neg q)\Longrightarrow p\vee p$.................................................. ...........................from (4)and(5) and using the rule called proof by cases: $\displaystyle [((A\Longrightarrow B)\wedge (C\Longrightarrow D))\Longrightarrow ((A\vee C)\Longrightarrow (B\vee D))]$.

7) $\displaystyle p\vee p$.................................................. .......................................from (1) and (6) and using M.Ponens

8) $\displaystyle p\vee p\Longleftrightarrow p$.................................................. .......................................tautology

9) $\displaystyle p\vee p\Longrightarrow p$.................................................. ........................................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)$\displaystyle \neg(p\wedge q)$.................................................. ........................................assumption to start a conditional proof

3)$\displaystyle \neg p\vee\neg q$.................................................. ..........................................from (2) and using De Morgan

4)$\displaystyle p\Longrightarrow\neg q$.................................................. .....................from (3) and using material implication

5)$\displaystyle \neg q$.................................................. .....................................from (1) and (4) and using M.Ponens

6)$\displaystyle p\wedge\neg q$.................................................. ...........................from (1) and (5) and using Conjunction Introduction

7)$\displaystyle \neg(p\wedge q)\Longrightarrow(p\wedge\neg q)$.................................................. .......................from (2) to(6) and using the rule of conditional proof

8)$\displaystyle (p\wedge q)\vee (p\wedge\neg q)$.................................................. ........................from (7) and using material implication $\displaystyle (A\Longrightarrow B)\Longleftrightarrow (\neg A\vee B)$