logical equivalence of ¬((q∨¬p)∧¬r)

Question

I have just started the course of logic and still not familiar with applying different formula to obtain logically equivalent statement. ¬((q∨¬p)∧¬r)should be (¬q∧p)∨ r, and it asks me to find a equivalent statement without using and/or/negation. I want to know who to get there. Then in second part, the question is to find equivalent formula for (p∨ ¬q)∨ (p∧(q∧ ¬r)). I can list the truth table for these but I don't know the tech of finding logical equivalent formula.

Answer 1

Starting from the formula : $¬((q \lor ¬p) \land ¬r)$, we have to use the tautological equivalence : $\lnot (\alpha \land \beta) \equiv (\alpha \to \lnot \beta)$ to get : $(q \lor ¬p) \to r$, and then use Material Implication :

$(p \to q) \to r$.

---

Same approach for the second one : $(p \lor ¬q) \lor (p \land (q \land ¬r))$.

We have to replace $(p \lor ¬q)$ with $q \to p$.

Regarding $p \land (q \land ¬r)$ we have : $p \land \lnot (q \to r) \equiv \lnot [p \to (q \to r)]$.

In conclusion, the complete formula will be equivalent to :

$(q \to p) \lor \lnot [p \to (q \to r)] \equiv (p \to (q \to r)) \to (q \to p)$.

Answer 2

Are you familiar with the NAND operator? Let's denote it by $\uparrow$. You can express any logical operator with NAND. Indeed, negation is given by

$$\neg p \equiv p\mathbin{\uparrow}p,$$

conjunction is given by $$p\land q \equiv (p\mathbin{\uparrow} q) \mathbin{\uparrow} (p\mathbin{\uparrow} q),$$

and disjunction is given by

$$p\lor q \equiv (p\mathbin{\uparrow} p) \mathbin{\uparrow} (q\mathbin{\uparrow} q).$$

I don't know how you could express a logical formula without any of and/or/not unless you use something like this.