simplification of a propositional statement

Question

Write the formula which is equivalent to the formula

$$\neg (p\leftrightarrow(q\to(r \lor p)))$$

and contains the connectives AND ( $\land$ ) and NEGATION ( $\neg$ ) only.

Answer 1

Use that $x \lor y$ can be written as $\lnot(( \lnot x) \land (\lnot y)),$ i.e. DeMorgan's law, to get rid of or's anywhere. Also use that $x \to y$ can be written as $\lnot (x \land (\lnot y)),$ and finally that $x \leftrightarrow y$ can be written as $(x \land y) \lor ((\lnot x) \land (\lnot y)).$ There may be a "simplest" way to do this for your example, involing the fewest steps.

Added: Another way to do this type of problem is using truth tables. Each truth table row is equivalent to a statement using only and, not. For example if the usual setup is used starting with $TTT$ for the first row as values of $p,q,r,$ next row $TTF$ and so on, then the third row down is $TFT$ which would be $(p \land (\lnot q) \land r).$

Once your truth table is made, for each line which comes out false you include the negation of the formula for that line. Then put all those negations together with $\land$'s in between them. For your example as I recall there were five false lines (it may have been three, I'm not at my notepad scratchings now). Anyway this method does not involve anything "clever" other than the routine construction of the initial truth table.

Answer 2

Hint: $$\begin{align} A\to B \quad & \equiv\quad \neg A \lor B & \text{implication equivalence} \\ & \equiv \quad \neg(A\land \neg B) \\[2ex] A \leftrightarrow B \quad & \equiv \quad (A\lor \neg B) \land(\neg A\lor B) & \text{biconditional equivalence} \\ & \equiv \quad \neg(\neg A\land B)\land \neg (A\land\neg B) \\[2ex] A \lor B \quad & \equiv \quad \neg (\neg A\land \neg B) & \text{DeMorgan's Law} \end{align}$$