0
$\begingroup$

The biconditional operator $\iff$ of Propositional Logic can be defined by the identity

$p \iff q \equiv (\lnot p \lor q) \land (\lnot q \lor p) \quad (1.1)$

Use the identity $(1.1)$ and identities from the list on page 2, to show algebraically that

$p \iff q \equiv (\lnot p \land \lnot q) \lor (q \land p)$

State which identity you are using at each step.


What does this question mean by asking to "show algebraically"? I have tried referring to my notes and online search but no luck with a definition! These propositions are already algebraic, are they not? Having some issues understanding the wording of the question. This is from a mock university test. I'm assuming it wants me to demonstrate using a truth table?

$\endgroup$
1
  • 1
    $\begingroup$ "To show algebraically" means to demonstrate on the basis of symbolic rules. I encourage you to edit your question adding the identities the problem statement refers to. $\endgroup$
    – Acsor
    Aug 14 '20 at 15:15
0
$\begingroup$

Although you haven't posted any of the logical rules the problem statement refers to, it is reasonable to assume they are similar to those found in many standard logic textbooks. To prove your identity, I will make use of

$$ \begin{align} P \land Q & \equiv Q \land P, &\text{$\land$ commutativity} \\ P \land (Q \lor R) & \equiv (P \land Q) \lor (P \land R), &\text{$\land$ distribution} \\ P \land \lnot P & \equiv \bot &\text {(3)} \\ P \lor \bot &\equiv P, & \text{$\bot$ annihilation} \end{align} $$

where $\bot$ denotes falsehood. With that in mind

$$ \begin{align} p \iff q \equiv & \\ (\lnot p \lor q) \land (\lnot q \lor p) \equiv & & \text{By definition}\\ ((\lnot p \lor q) \land \lnot q) \lor ((\lnot p \lor q) \land p) \equiv & &\text{By distribution of $\land$} \\ (\lnot q \land (\lnot p \lor q)) \lor (p \land (\lnot p \lor q)) \equiv & &\text{By commutativity of $\land$} \\ (\lnot q \land \lnot p \lor \lnot q \land q) \lor (p \land \lnot p \lor p \land q) \equiv & &\text{By distribution of $\land$} \\ (\lnot q \land \lnot p \lor \bot) \lor (\bot \lor p \land q) \equiv & &\text{By $(3)$} \\ (\lnot q \land \lnot p) \lor (p \land q) \equiv & &\text{By $\bot$ annihilation} \\ (\lnot p \land \lnot q) \lor (q \land p) \equiv & &\text{By commutativity of $\land$} \\ & &\square \end{align} $$

I've assumed throughout $\land$ to have higher precedence than $\lor$.

$\endgroup$

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.