I am stuck at this problem:

Let $\Sigma = \{\lnot,\lor,\land,\rightarrow,\leftrightarrow,(,),P_1,...,P_n\}$ be an alphabet.

Now let's define the set of logical expressions $\mathscr{L} \subseteq \Sigma^\ast$ recursively as follows:

Rule #1: For each $i\in\{1,2,...,n\}$, $P_i\in \mathscr{L}$

Rule #2: For each $\phi \in \mathscr{L}$, $\lnot \phi \in \mathscr{L}$

Rule #3: For each $\phi,\psi \in \mathscr{L}$ and $@\in\{\lor,\land,\rightarrow,\leftrightarrow\}$, $(\phi @ \psi)\in\mathscr{L}$

No strings other than those derived from Rules #1, #2 and #3 are in $\mathscr{L}$.

Prove that for all $\phi \in \mathscr{L}$ and $\psi\in\Sigma^\ast$, If $(\phi\land\psi)\in\mathscr{L}$ Then it must be the case that $\psi\in\mathscr{L}$.

I tried to prove it using structural induction, contradiction and several other ways but I wasn't able to prove it.

Thanks for any help.

  • $\begingroup$ The problem you might have had with contradiction is that if you suppose $\psi\notin\mathcal{L}$, then by rule #3, it might still be the case that $(\phi\land\psi)\in\mathcal{L}$. The important thing to remember is No strings other than those derived from Rules #1, #2 and #3 are in L. $\endgroup$ – Demosthene Mar 21 '15 at 11:14
  • $\begingroup$ @Demosthene, Thanks for the reply. Of course by the recursive nature of the language $\mathscr{L}$, $\psi$ must be in $\mathscr{L}$ but I don't get how to prove it rigorously, I've tried structural induction but I got stuck. $\endgroup$ – MathNerd Mar 21 '15 at 11:32
  • $\begingroup$ @Demosthene, I showed that we can find $\phi,\psi\in\Sigma^\ast$ such that $(\phi\land\psi)\in\mathscr{L}$ but $\phi,\psi\notin\mathscr{L}$, Indeed we can take $\phi=P_1\land(P_1$ and $\psi=P_1)$ and so $(\phi\land\psi)=(P_1\land(P_1\land P_1))$ which is in $\mathscr{L}$. $\endgroup$ – MathNerd Mar 21 '15 at 11:49
  • $\begingroup$ Hint. The right way to prove this is given by the flag "context-free grammar". $\endgroup$ – J.-E. Pin Mar 21 '15 at 12:19
  • $\begingroup$ @Saita - in your "example" with $\phi=P_1∧(P_1$ and $\psi=P_1)$ we are satisfying the rule 3 in a "vacuous" way. The "trick" is the "closure" condition: $P_1) \notin \mathscr L$ because we cannot "produce" it with the three rules : starting with $P_1$, there is no rules that allows us to "throw it" into $\mathscr L$. $\endgroup$ – Mauro ALLEGRANZA Mar 21 '15 at 12:55


We have to take into account the difference between the set $\mathscr L$ of logical expressions (the well-formed formulae) and the set $\Sigma^*$ of strings.

The string $P_1 \to P_2$ is a logical expression, while the string $\land P_1$ is not.

The "closure" condition following the three rules guarantees that only strings built-up from the $P_i$ following the three rules is a logical expressions.

It can be equivalently expressed as :

the set $\mathscr L$ is the smallest set $X$ of strings satisfying the rules 1,2,3.

Thus, the approach "by contradiction" is the right one; we will assume that :

$\phi, (\phi \land \psi) \in \mathscr L$ and that $\psi \notin \mathscr L$.

Consider the set $X = \mathscr L − \{ (\phi \land \psi) \}$; we have that $P_i \in X$ and that if $\sigma \in X$, then $\lnot \sigma \in X$; thus, rules 1 and 2 are satisfied by $X$.

Consider now $\sigma_1, \sigma_2 \in X$; then $\sigma_1, \sigma_2 \in \mathscr L$ and thus, by rule 3 : $(\sigma_1 \land \sigma_2) \in \mathscr L$.

But the string $(\sigma_1 \land \sigma_2)$ is different from the string $(\phi \land \psi)$; it is enough to compare them and we have to conclude that the only way they can be equal (as strings) is when $\sigma_1 = \phi$ and $\sigma_2 = \psi$, and this is not possible, because $\sigma_2 \in \mathscr L$ and we have assumed that $\psi \notin \mathscr L$.

Thus, $(\sigma_1 \land \sigma_2) \in X$ and also rule 3 is satisfied by $X$.

But then $X$ satisfy rules 1,2,3 and this contradicts the "closure" condition, i.e. the fact that $\mathscr L$ is the smallest set of strings on the alphabet that satisfy the rules.

| cite | improve this answer | |
  • $\begingroup$ How do you prove formally that if $\sigma \in X$, then $\neg\sigma \in X$ ? $\endgroup$ – J.-E. Pin Mar 21 '15 at 12:18
  • $\begingroup$ @Saita - you are welcome :) To be "perfect" it needs the proof of the "Lemma" regarding the equality of strings ... $\endgroup$ – Mauro ALLEGRANZA Mar 21 '15 at 12:18
  • $\begingroup$ @J.-E.Pin - because $X$ is $\mathscr L$ "minus" $(\phi \land \psi)$ and $\mathscr L$ satisfy rule 2. Again "by inspection", the "deleted" formula is not $\lnot \sigma$, for some $\sigma$, and thus we have no impact on the rule 2. $\endgroup$ – Mauro ALLEGRANZA Mar 21 '15 at 12:21
  • $\begingroup$ @Saita - see Herbert Enderton, A Mathematical Introduction to Logic (2nd ed - 2001), page 4 : "If two sequences are equal $\langle x_1,\ldots,x_n \rangle = \langle y_1,\ldots,y_n \rangle$, then it is easy to see that $x_i=y_i$ for $1≤i≤n$. (The proof uses induction on $n$)." $\endgroup$ – Mauro ALLEGRANZA Mar 21 '15 at 13:22
  • $\begingroup$ Sorry, but I do not really get why $(\sigma_1\land\sigma_2)=(\phi\land\psi)$ must imply that $\sigma_1=\phi$ (which will then imply that $\sigma_2=\psi$). There can be as many $\land$ characters as we want in the strings. The string $\phi$ may be for example a proper substring of $\sigma_1$ (or even a substring of $\sigma_1\land\{\text{some substring of $\sigma_2$}\}$). How do we overcome this difficulty and prove that it must be the case that $\phi=\sigma_1$. $\endgroup$ – MathNerd Mar 21 '15 at 13:35

Hint: The rules require you to put brackets around expressions formed with binary operators. Because brackets aren't used for any other purpose in the language the brackets have to balance. This means that if $\phi, \phi' \in {\cal L}$ and $(\phi \land \psi)$ is the same string of alphabet symbols as $(\phi' \land \psi')$ and is in $\cal L$, then $\phi$ and $\phi'$ are the same. To see this, show (by structural induction) that $\phi$ and $\phi'$ must both comprise zero or more $\lnot$ symbols followed either by $P_i$ for some $i$ or by a string of symbols beginning with a left bracket and ending with a matching right bracket (and in which brackets occur in balanced pairs). Since $\phi$ and $\phi'$ are the same, the two $\land$ symbols must be in the same position in the strings, hence you must have that $\psi$ and $\psi'$ are the same.

| cite | improve this answer | |
  • $\begingroup$ Do you mean to prove by structural induction that, for all $\phi,\phi'\in\mathscr{L}$ and $\psi,\psi'\in\Sigma^\ast$, If $(\phi\land\psi)=(\phi'\land\psi')\in\mathscr{L}$ then $\phi=\phi'$ and $\psi=\psi'$ ? $\endgroup$ – MathNerd Mar 21 '15 at 14:26
  • $\begingroup$ Yes: I have expanded the answer a bit. $\endgroup$ – Rob Arthan Mar 21 '15 at 15:53

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.