How to prove logical equivalence using Theorems and substitution?

**ipatch** · January 26th 2010, 05:30 PM

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

**Prove It** · January 26th 2010, 07:48 PM

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.

**emakarov** · January 27th 2010, 04:20 AM

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.

**Soroban** · January 27th 2010, 07:33 AM

Hello, ipatch!

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

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

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

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

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

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

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

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

. . . . . . . . . . . . . . . $p$

**Grandad** · January 27th 2010, 08:16 AM

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:

$(p \land q)\lor(p\land\neg q) \equiv p\land(q\lor\neg q)$ (Distributive Law)

$\equiv p\land T$ (Complement Law)

$\equiv p$ (Identity Law)

Grandad

**cgafa** · February 10th 2010, 12:43 PM

(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

**Soroban** · February 10th 2010, 01:05 PM

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.)

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

. . . . $\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}$

**cgafa** · February 10th 2010, 01:19 PM

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

**xalk** · February 11th 2010, 02:17 PM

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 : $(p\wedge q)\vee (p\wedge\neg q)\Longrightarrow p$ and then:

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

Proof:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

LinkBack

Thread Tools

Display

How to prove logical equivalence using Theorems and substitution?

Similar Math Help Forum Discussions

Logical equivalence

Logical Equivalence

Prove/disprove using logical using logical arguments

Logical Equivalence Help

Logical Equivalence

Search Tags