# How can I reduce ((¬p ∧ q) ∧ (q ∧ r))∧ ¬q to a single character using these logical equivalence laws?

Im pretty confused and don't know where to start. These are the laws

Commutative laws: p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p

Associative laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

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

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

Identity laws: p ∧ t ≡ p

p ∨ c ≡ p

Negation laws: p ∨ ∼p ≡ t

p ∧ ∼p ≡ c

Double negative law: ∼(∼p) ≡ p

Idempotent laws: p ∧ p ≡ p

p ∨ p ≡ p

Universal bound laws: p ∨ t ≡ t

p ∧ c ≡ c

De Morgan’s laws: ∼(p ∧ q) ≡ ∼p ∨ ∼q

∼(p ∨ q) ≡ ∼p ∧ ∼q

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

p ∧ (p ∨ q) ≡ p

Negations of t and c: ∼t ≡ c

∼c ≡ t

• You have only to re-arrange it, taking into account that $q \land \lnot q \equiv \text F$. – Mauro ALLEGRANZA Jan 25 '17 at 20:31
• @MauroALLEGRANZA Which means the commutative and associative laws. There is no "only rearrange". – Arthur Jan 25 '17 at 20:31
• @Arthur so i thought it might start with the distributive. Could you elaborate why its the commutative and associative laws? – tanNerd Jan 25 '17 at 20:43
• Since all operators are $\land$, the Distributive Laws do not apply. Use Commutative and Associative Laws to 're-arrange': getting the two $q$'s next to each other allows you to get rid of one by Idempotent laws, get the $q$ and $\neg q$ next to each other to apply a Negation Law, and use the Universal Bound law to reduce it all to $c$. – Bram28 Jan 25 '17 at 20:46

$$((¬p ∧ q) ∧ (q ∧ r))∧ ¬q \equiv ¬p ∧ (q ∧ q) ∧ r ∧ ¬q\tag{associativity}$$

$$\equiv \lnot p \land q \land r \land \lnot q\tag{idempotent}$$

$$\equiv \lnot p \land (q \land \lnot q) \land r\tag{commutativity/assoc}$$

$$\equiv \lnot p \land c\land r \tag{negation laws}$$

$$\equiv \lnot p \land r \land c \tag{commutativity}$$

$$\equiv (\lnot p \land r) \land c \tag{Associativity}$$

$$\equiv c\tag{Universal Bound Laws}$$

Assuming $c$ means contradiction.

If your teacher is a real stickler about the syntactical format of these rules:

$((\neg p ∧ q) ∧ (q ∧ r))∧ \neg q \equiv$ (Associative)

$(\neg p ∧ q) ∧ ((q ∧ r)∧ \neg q) \equiv$ (Commutative)

$(\neg p ∧ q) ∧ ((r ∧ q)∧ \neg q) \equiv$ (Associative)

$(\neg p ∧ q) ∧ (r ∧ (q∧ \neg q)) \equiv$ (Negation)

$(\neg p ∧ q) ∧ (r ∧ c) \equiv$ (Universal Bound)

$(\neg p ∧ q) ∧ c \equiv$ (Universal Bound)

$c$

See how you use Association and Commutation to re-arrange and in particular move those parentheses?