$\begingroup$

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

$\endgroup$

3 Answers

$\begingroup$

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.

$\endgroup$ $\begingroup$

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)

$F$

$\endgroup$ $\begingroup$

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

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

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

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

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

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

𝑞 ∧ TRUE ≡ 𝑞

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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