Proving some property of a Formal Logic Language [duplicate]

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,\phi' \in \mathscr{L}$, $\psi,\psi'\in\Sigma^\ast$ and $@\in\{\lor,\land,\rightarrow,\leftrightarrow\}$, If $(\phi @\psi)=(\phi' @\psi')$ Then it must be the case that $\phi = \phi'$ and $\psi = \psi'$.

---

I tried to prove it using structural induction and ordinary induction, but I wasn't able to prove it.

What we need to show is that the @ in the strings $(\phi @\psi)$ and $(\phi' @\psi')$ lies at the same index position, and then we will get immediately that $\phi = \phi'$ and $\psi = \psi'$ by definition of string equality.

Thanks for any help.

Answer 1

Let us assign value $1$ to '$($' and '$@$', and assign $-2$ to '$)$', and $0$ to any other characters, we firstly show that if $\phi\in \mathscr{L}$ then $\sum_{i=1}^{j}v(\phi_i)< 0$ and $\sum_{i=1}^{n}v(\phi_i)=0$ where $j<n=\mathrm{len}(\phi)$.(this is a trivial job...)

Now suppose $\phi\not=\phi'$, then one must have $\phi\subset \phi'$ or $\phi'\subset\phi$ (where $A\subset B$ means that A is a prefix of B), but if it is any of the cases, we will find an index $j$ make $\sum_{i=1}^{j}v(\phi_i)=0$(resp. $\phi'$), a contradiction.