compound proposition logically equivalent

Question

I can not solve this question Find a compound proposition logically equivalent to $p \to q$ using only the logical operator $\downarrow$.

Answer 1

It's quite simple; let start with :

$\lnot p \equiv p \downarrow p$.

Then :

$p \rightarrow q \equiv ((p \downarrow p) \downarrow q) \downarrow ((p \downarrow p) \downarrow q)$.

In order to check the definition, we have to use the truth-table for $\downarrow$ : it is true only when both $p$ and $q$ are false.

This fact justify the definition of $\lnot p$ as $p \downarrow p$.

For the conditional, we will work by steps:

$((p \downarrow p) \downarrow q)$ is $\lnot p \downarrow q$ [see the definition of $\lnot$ above].

Thus, the complete formula is simply : $\lnot ( \lnot p \downarrow q)$.

Now we may check that the only case when it is false (i.e.$0$) is when $p=1$ and $q=0$.

Note. You can see this paper on Adeqaute set of connectives for a general overview of the topic.

Answer 2

Given propositions $p$ and $q$, the propositon $p \downarrow q$ is given by the following truth table:

$$ \begin{align} p \qquad & q & p \downarrow q \\ T \qquad & T & F \\ T \qquad & F & F \\ F \qquad & T & F \\ F \qquad & F & T \end{align} $$

Thus we have $$ T \downarrow T \equiv F, \ \ \ T \downarrow F \equiv F, \ \ \ F \downarrow T \equiv F, \ \ \ F \downarrow F \equiv T. \tag{0} $$

In fact, we have the logical identity $$ p \lor q \equiv \overline{p \downarrow q}. \tag{1} $$

We further note that $$ p \downarrow p \equiv \overline{p}, \tag{2} $$ because when $p$ is True, we have $T \downarrow T$, which is False, and when $p$ is False, we have $F \downarrow F$, which is true.

And, we also note that $$ \begin{align} p \lor q &\equiv \overline{\overline{p \lor q}} \\ &\equiv \overline{p \downarrow q} \qquad \mbox{[ using (1) above ]}\\ &\equiv \big( p \downarrow q \big) \downarrow \big( p \downarrow q \big). \end{align} $$ Thus we have the logical identity $$ p \lor q \equiv \big( p \downarrow q \big) \downarrow \big( p \downarrow q \big). \tag{3} $$ Now we note that $$ \begin{align} p \rightarrow q &\equiv \overline{p} \lor q \qquad \mbox{[ using the conditional-disjunction equivalence ] } \\ &\equiv \left( \overline{p} \downarrow q \right) \downarrow \left( \overline{p} \downarrow q \right) \qquad \mbox{[ using (3) above with $\overline{p}$ in place of $p$ ]} \\ &\equiv \big( (p \downarrow p) \downarrow q \big) \downarrow \big( (p \downarrow p) \downarrow q \big) \qquad \mbox{[ using (2) above ]}, \end{align} $$ as required.