I missed a couple of lectures in college where we where learning how to simplify propositions e.g

Use the laws of logic to show that ¬(𝑞 → 𝑝) ∨ (𝑝 ∧ 𝑞) simplifies to q

I searched online for a tutorial on how to do them however there isnt really any decent tutorial on the ineternet that gives you a step instruction of what to do and why each step that was carried out was done.

It would really help if someone can simplify the following two propositions and explain how and why for each step. I know the basics of logic I just dont know how to, when, where and why to apply the laws of logic to simplify a proposition.

Here are the following laws of logic we need to know and the two questions are below.

Equivalence law p ↔ q ≡ (p→q) ∧ (q →p)

Implication law p → q ≡ ¬p ∨ q

Double negation law ¬¬p ≡ p

Commutative laws p ∨ q ≡ q ∨ p / p ∧ q ≡ q ∧ p

Associative laws p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r / p ∨ ( q ∨ r) ≡ ( p ∨ q ) ∨ r

Idempotent laws p ∧ p ≡ p p ∨ p ≡ p

Distributive laws p ∧ (q ∨ r) ≡ (p ∧ q)∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q)∧ (p ∨ r)

De Morgan’s laws ¬(p ∧ q) ≡ ¬p ∨ ¬q / ¬(p ∨ q) ≡ ¬p ∧ ¬q

Identity laws p ∧ T ≡ p / p ∨ F ≡ p

Annihilation laws p ∧ F ≡ F / p ∨ T ≡ T

Inverse laws p ∧ ¬p ≡ F / p ∨ ¬p ≡ T

Absorption laws p ∧ (p ∨ q) ≡ p / p ∨ (p ∧ q) ≡ p

  1. Show using the laws of logic that ¬[𝑝 ∨ ¬(𝑝 ∧ 𝑞)] is a contradiction

  2. Use the laws of logic to show that [¬(𝑝 → 𝑞) ∨ (𝑝 ∧ 𝑞)] → (𝑝 ∨ 𝑞) is a tautology. Verify your answer using a truth table


HINT: I’d start by getting rid of the implication:

$$\begin{align*} \neg(q\to p)\lor(p\land q)&\equiv\neg(\neg q\lor p)\lor(p\land q)\\ &\equiv\big(\neg(\neg q)\land\neg p\big)\lor(p\land q)\\ &=(q\land\neg p)\lor(p\land q) \end{align*}$$

So far I’ve used implication, De Morgan, and double negation. Now see if you can use a commutative law, a distributive law, an inverse law, and an identity law to finish it off.


For 1:

$\neg [p \lor \neg(p \land q)] \equiv$ (De Morgan's Laws)

$\neg p \land \neg \neg(p \land q) \equiv$ (Double negation law)

$\neg p \land (p \land q) \equiv$ (Associative Law)

$(\neg p \land p) \land q \equiv$ (Commutative Law)

$(p \land \neg p) \land q \equiv$ (Inverse Law)

$F \land q \equiv$ (Annihilation Law)



¬(𝑞 → 𝑝) ∨ (𝑝 ∧ 𝑞) given

≡ ¬(¬𝑞 ∨ 𝑝) ∨ (𝑝 ∧ 𝑞) definition of if then

≡ (𝑞 ∧ ¬𝑝) ∨ (𝑝 ∧ 𝑞) de morgan's law

≡ (𝑞 ∧ ¬𝑝) ∨ (𝑞 ∧ 𝑝) just rearranged (communicative ?)

≡ 𝑞 ∧ ( (¬𝑝) ∨ (𝑝) ) distributive prop.

( (¬𝑝) ∨ (𝑝) ) is a tautology

𝑞 ∧ TRUE ≡ 𝑞

  • $\begingroup$ the first step simply gets rid of the if then. The second step is just simplification. I did the third step to make the fourth more obvious, at step three I notice you can factor 𝑞 ∧ and all you have left is a tautology on one side. $\endgroup$ – Dunkas Dec 9 '16 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.