Proving logical equivalence using laws of propositional logic

1k Views Asked by At

Honestly I have no idea where to start and It'd be so nice if someone provided me with a step by step explanation , Thank you !

1) $\neg q \rightarrow \neg p \equiv p \rightarrow q$

2) $p \lor (p \land q) \equiv p$

3) $(p \lor q) \land \neg p = \neg p \land q$

2

There are 2 best solutions below

0
On

Make truth tables for each of them:

e.g. #1

|~q → ~p ≡ p → q| →  |~q → ~p ≡ p → q|
|++-+-++-+-+-+-+| →  |++-+-++-+-+-+-+|
| F    F   F   F| →  |TF T TF T F T F|
| F    T   T   F| →  |TF F FT T T F F|
| T    F   F   T| →  |FT T TF T F T T|
| T    T   T   T| →  |FT T FT T T T T|

Because the equivalent function is true in ALL of the four cases, the two statements are equivalent. You can continue this method with the other two pieces.

All of the equivalents must be true for the two statements to be equivalent, otherwise, they are not equivalent.

0
On

There are many ways in which you can prove the equivalences you have to prove ... and it is not clear what method you have to use when you say 'using laws of propositional logic'. Here are some possibilities though:

If you are allowed to (or have to) create a truth-table, see Logan's answer.

If you have to use logical equivalences, then it depends on exactly what equivalences you are allowed to use. But, interestingly, all 3 equivalences you have to prove are usually used as such basic equivalences:

1) is called Contraposition

2) is called Absorption

3) is called Reduction

Finally, if you have to prove the equivalences using a formal proof (or formal derivation), we would have to know exactly what rules are allowed to work with in order for us to help you.