proving something is not a well formed formula

4,003

The problem is that the concep of well formed formula depends on the language you are working with.

A language has a syntax, i.e. rules that allows you to "build" terms (i.e."names") and expressions (i.e."sentences").

If I assume that you are working in formalized arithmetic, usualy variable like "x" are terms standing for numbers; so, the expression $x > y$ is well formed. But, in this case $x$ and $y$ are not wff.

If instead we are working with the language of propositional logic, where the variables ($x$ and $y$) are called sentential variables, the expression $x > y$ is not well formed.

Again, we need to know what language are you handling.

About concatenation:

but the comment about concatenation of two wffs not being allowed is really the crux of my issue.

If I work with propositional logic, the language is made by sentential variables, like $p, q, r, ...$ and truth-functional connectives, $\lnot$ (negation, unary), $\land$ (conjunction, binary), $\lor$ (disjunction, binary), $\rightarrow$ (conditional, binary).

The rules available to build expressions are (tipically) :

(i) every sentential variable is a wff

(ii) if $A$ ia a wff, then $\lnot A$ is a wff

(iii) if $A$ and $B$ are wffs, then $A \lor B$, $A \land B$ and $A \rightarrow B$ are wffs

(iv) nothing else is a wff.

Reviewing the above rules, you can see that there are no rules allowing you to juxtapose two wff without interposing a connective; e.g. :

$AB$ and $\lor A$ are not wffs.

If you are working in first-order number theory, you have individual variables, like $x$ and $y$, you have the above connectives, you have the equality symbol and the quantifiers, (for simplicity, we assume that also $>$ is a primitive symbol).

The following are examples of wffs :

$\forall x (x > 0)$ and $x = 0$

Again, you have rules like the above, that do not allow you to "build" an expression like :

$(x = 0) \forall x (x > 0)$

But there are languages ($\lambda$-calculus) where concatenation is allowed; and then there are programming languages ...

Share:
4,003

Related videos on Youtube

Sandie H.
Author by

Sandie H.

Updated on August 11, 2022

Comments

  • Sandie H.
    Sandie H. about 1 year

    Prove if $W$ is well formed formula (wff) them $W$ cannot be written as $W_1W_2$ where $W_1$ and $W_2$ are wffs

    $$\text{wff} :=\begin{cases} (A_i)\\ (\sim x)&\text{if } x \text{ is a wff}\\ (x>y)&\text{if }x, y \text{ are wffs}\end{cases}$$

    I apologize if I am not expressing myself well, but the comment about concatenation of 2 wffs not being allowed is really the crux of my issue. Why isn't this allowed? By the laws of a legal parenthesis string (lps) this is acceptable as long as what ever is inside of the two parentheses are lps themselves. Isn't a wff an lps in it's own right? Again, I am sorry, I'm sure this is probably simple but I always get caught up in the semantics of thing and want to make sure I am seeing things correctly.

    • Dustan Levenstein
      Dustan Levenstein almost 10 years
      This depends heavily on the particular definition of well-formed formula.
    • Mauro ALLEGRANZA
      Mauro ALLEGRANZA almost 10 years
      I rephrase the comment by Dunstan : if you want a satisfying answer, please ask an understandable question. If you are working in propositional logic, a plausible reading of your statement has a definite answer; something like : the operation of concatenation of formulas is not allowed; between two wffs you must interpose a binary connective, like : $\lor$, $\land$ or $\rightarrow$.
    • Hagen von Eitzen
      Hagen von Eitzen almost 10 years
      I tried to format the question towards legibility, but I'm not sure what to make of the last part. Also, what can be said about the $A_i$?