Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

obviously $a\equiv\neg (p \rightarrow q)=p\land\neg q$. But, I was wondering what is the simplest\shortest sentence (other than $a$ of course), which contains 1 or more implication connectives (Constructed with p and q as basic sentences of course) Tautologically Equivalent to the above?

$c\equiv(\neg p \rightarrow q)\land(\neg p \rightarrow \neg q)\land(p \rightarrow\neg q)$ is one answer.

Is there a proposition $d$ with `$\rightarrow$` symbols as the main/outermost of operators?

meaning, if we look at $d$ as the ordered symbol tuple $d=(d_1,d_2,...d_n)$, and define the function $f: \mathbb \{0\}\cup \mathbb N_{\leq{n}} \rightarrow \{z \in \mathbb Z| \ |z|\leqslant n \}$, such that: $f(0)=0$. and for every $k \in \mathbb N_{\leq{n}} \ $: $f(k)=f(k-1)+ \left\{ \begin{array}{ll} 1 & \quad d_k=`(` \\ 0 & \quad d_k \notin \{`(`,`)`\} \\ -1 & \quad d_k=`)` \end{array} \right.$

Then, for all $i \in \mathbb N_{\leq{n}}$ such that $d_i=`\rightarrow`$: $f(i)=0$ should be true.

For example $c=a=b\equiv\neg(\neg q \rightarrow \neg p)$ and $c_4=c_{11}=c_{18}=a_4=b_5=`\rightarrow`$, but $f(c_4)=f(c_{11})=f(c_{18})=f(a_4)==f(b_5)=1$. And therefore $a,b,c$ do not qualify.

Anyone has an idea? :)

share|cite|improve this question
Welcome to Math.SE. Thank you for your question. Please read it carefully, as it seems you have some inconsistent letters. It will also help us to answer it if you give more contest for the question, as well as what ideas you've tried already. – vadim123 Apr 28 '13 at 23:41
Sorry for the inconsistent letters and not using latex in the heading.. Was about to fix it, but my internet decided to disconnect at the same instant. – Dror Apr 28 '13 at 23:45
Please clarify what you're asking for. Every statement $B$ is of the form $\neg A$, for the statement $A=\neg B$. – vadim123 Apr 28 '13 at 23:47
Well, admittedly, I tried out to find it my self for more then 1 hour.. (Which is a lot by any standard). If I keep at it' I'll find it eventually. Though, I though this forum could save some time :) – Dror Apr 28 '13 at 23:48
Could you provide some motivation for this question? Why do you want to find the shortest sentence equivalent to a given sentence, containing a given connective, and not equal to a given sentence? – Trevor Wilson Apr 29 '13 at 0:30

$\neg(\neg q\rightarrow \neg p)$ looks to be about as short as possible.

share|cite|improve this answer
Heh' Obviously. That's exactly why I originally didn't want it to be of the form $\neg A$ when $A$ is some sentence.. – Dror Apr 29 '13 at 0:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.