1
$\begingroup$

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.

$\endgroup$
6
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 12:55

2 Answers 2

Reset to default
2
$\begingroup$

Hint

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.

$\endgroup$
11
  • $\begingroup$ How do you prove formally that if $\sigma \in X$, then $\neg\sigma \in X$ ? $\endgroup$
    – J.-E. Pin
    Mar 21, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 13:35
1
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2015 at 14:26
  • $\begingroup$ Yes: I have expanded the answer a bit. $\endgroup$
    – Rob Arthan
    Mar 21, 2015 at 15:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .