Proving NOR is logically complete confusion

propositional-calculus

In this question I am very confused in part iii:

  1. Consider the connective ↓ (called the Pierce arrow or NOR), and defined
    by the truth-table below:
P Q P ↓ Q
1 1 0
1 0 0
0 1 0
0 0 1

As you can see, the formula P ↓ Q is true when both P and Q are false,
and it is false otherwise.

(i) Show that P ↓ Q is logically equivalent to ¬(P ∨ Q).

(ii) Show that P ↓ P is logically equivalent to ¬P.

(iii) Show that the connective ↓ is adequate for propositional logic (in other
words, show that the set of logical connectives consisting only of the
connective ↓ is functionally complete).

The answer to part (iii) is:

To show that a given set of connective is complete all we need to do
is to express a known complete set of connectives in terms of the
given set (as per Lecture 3.1).

We know that the set {¬, ∨} is complete (Lecture 3.1). In addition,

$$¬P ≡ P ↓ P$$
$$¬(P ∨ Q) ≡ (P ↓ Q) =⇒ P ∨ Q ≡ ¬(P ↓ Q) ≡ (P ↓ Q) ↓ (P ↓ Q)$$

Thus, the each of connectives ¬ and ∨ can be expressed in terms of the
connective ↓ only

Why I am confused:

  1. firstly why are we only checking ¬ and V can be expressed in terms of ↓? Why aren't we checking for the all the connectives aka conjunction, implication, biimplication, exclusive OR etc. Surely if ↓ is logically complete then all connectives should be able to be expressed in terms of ↓ only not just negation and V.

  2. How is ¬(P↓Q) equivalent to (P↓Q)↓(P↓Q)? What inference rule was used here?

  3. We have already proven in parts (i) and (ii) that V and negation are logically complete why do we have to show it again in part (iii)?

  4. When we have questions like (iii) do we have to check that it is logically complete for each connective in the set separately or can we do it combined because in (i) we showed P ↓ Q is logically equivalent to ~(P V Q) but in (iii) they negated both sides to get the connective V on its own

Best Answer

In part (i), you can use their truth tables to show that $A \downarrow B$ and $\lnot (A \lor B)$ are logically equivalent. They are true and false under the same conditions.

In part (ii), you can likewise write truth tables for $ P \downarrow P$ and $\lnot P$ and show that they are logically equivalent.

In part (iii), if you know already that $\{\lnot , \lor\}$ is complete, then all you have to do is check those two. You don't have to check $\land$, for example, because you already know that $\land$ can be written in terms of $\{\lnot , \lor\}$, and then you write those in terms of $\downarrow$, and you're done. You CAN check them all individually, but you don't need to.

For your second question, they literally just used part (ii). You know that $\lnot A$ is equivalent to $A \downarrow A$. Plug in $P \downarrow Q$ for $A$ and you get the result immediately.

For your third question, that's not what the question said. You already know that $\{\lnot , \lor\}$ is complete, and you showed in (i) and (ii) that each of those can be written in terms of $\downarrow$, so putting those together you can conclude that $\downarrow$ is complete, which you didn't know before proving the pieces.

For your fourth question, you are allowed to negate both sides. If $P \Leftarrow \Rightarrow Q$ then you can conclude that $\lnot P \Leftarrow \Rightarrow \lnot Q$.

Related Question