4

I made an attempt on this question. Please guide me if its wrong.

Consider the following boolean fuctions: $\sim p$ ,$\sim\sim\sim\sim\sim p$ , and $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p$ . Which of these are equal?

$\sim p$ and $\sim\sim\sim\sim\sim p$ are equal since if we write $\sim\sim p$, then this can be simplified to give $p$ as double negation canceled out or we can say $\sim\sim p=p$. Thus, in $\sim\sim\sim\sim\sim p$, there are $2$ pairs of double negation ($\sim$) which cancel out leaving the answer to $\sim p$. If we compare $\sim p$ and $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p$, then we can say that they are not equal since $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p$ has $6$ pairs of double negations ($\sim$) which cancel out leaving the answer as only $p$. If we compare $\sim p$ and $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p$, then we again say that they are not equal, as shown above $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p=p$. Thus, $\sim p$ is not equal to $p$.

  • Yeah it looks right but notice that $ \neg^{(2k)}p = p \ & ~ \neg^{(2k + 1)}p = \neg p, \ \ k \in \mathbb N$. This can be proven by induction. This can probably save you a lot of writing. – user222031 Apr 17 '15 at 22:41
  • 3
    Yes, your answer is correct. – MJD Apr 17 '15 at 22:41
  • Roneel: I just tried to clean up your question a bit. Did you type it on a phone or something? It looked very disorganized as it was inserted. Maybe this tutorial will help more in the future if you have not seen it already. Cheers. – Daniel W. Farlow Apr 17 '15 at 22:52

1 Answers1

2

We have the following (this is the clearest way to see it IMO):

  • $\sim p\equiv\,\sim p$
  • $\sim\sim\sim\sim\sim p\equiv\,\sim(\sim\sim(\sim\sim p))\equiv\,\sim p$
  • $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p\equiv (\sim\sim(\sim\sim(\sim\sim(\sim\sim(\sim\sim (\sim\sim p))))))\equiv p$

Hence, the first two are equal. Your answer is correct, as MJD has pointed out in a comment. The above is largely provided to give increased clarity.