Right now I am studying logic, and a bit confused on how to prove that some formula is not a well-formed formula. Here is my (or my course's) definition of well formed formula:
Suppose that $P$ is a set of proposition, and suppose that alphabet of the string is $P \cup C \cup D$ where $D=\{'(', ')'\}$ is the set containing close parentheses and open parentheses symbols. where $C := \{\neg, \vee, \wedge\}$ . The formula is well-formed if it is in the "smallest" set (i.e. intersections over every WFF which are subset of the universe / set of the every possible strings) of closed sets (i.e. closed under conjunction, negation, disjunction) which are constructed as follows:
- P $\subset WFF$
- If $\phi, \psi$ is WFF then $(\phi \vee \psi) \in WFF$
- If $\phi, \psi$ is WFF then $(\phi \wedge \psi) \in WFF$
- If $\phi \in WFF$ then $(\neg\phi) \in WFF$
Based on this definition, I want to prove that empty string, and invalid formulas like $p\neg$ are not WFF. How could I formally prove this although intuitively it is so correct. Thank you in advance!!
For your first question.
The empty string, $\lambda \notin P$
Every element of P has length of at least 1.
All other WFF's are constructed from elements of P or combinations of P, C or D, or other WFF's. These combinations adds length to the WFF. The length of every WFF is at least 1.
However, $\lambda$ has length zero and therefore not a WFF.
If you need something more formal, the next step up would be a proof by recursive or structural induction. This is a variation of natural induction, but applies to recursively defined sets.
For the second example, either $p\neg$ or $(p\neg )$, try something similar, except you may need to exhaust all the possibilities of length 1, 2, 3 or 4.