Proving a property of a Logic Formal Language

Question

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.

Answer 1

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.

Answer 2

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.