1

I am just beginning with Propositional Logic, and trying to understand few concepts: Well-built formula.

If $3 + 2 = x$ , $\sqrt{5} − 3 > 2$, $x^2 + 2x − 1 = 0$ are atoms, then:

$$((3 + 2 = x) \land (x^2+ 2x − 1 = 0)) ⇒(\sqrt{5} − 3 > 2)$$ is a well-built formula

How ?

gpuguy
  • 631

2 Answers2

2

You have to review the inductive cluses defining the set of well-formed formulae.

Tipically, we define the set of atomic formulae, like your : $3 + 2 = x$, and then we say that we can use them to build-up more "complex" ones by way of connectives.

Thus, if $\alpha, \beta$ are formulae, then also :

$(\lnot \alpha)$, $(\alpha \land \beta)$, $(\alpha \rightarrow \beta)$

are fomulae.

See Herbert Enderton, A Mathematical Introduction to Logic (2ed - 2001), page 16 :

[We have an alphabet with] the five symbols

$¬, ∧, ∨, →, ↔$

called sentential connective symbols.

We have included infinitely many sentence symbols $A_i$.

We want to define the well-formed formulas (wffs) to be the “grammatically correct” expressions.

The definition will have the following consequences:

(a) Every sentence symbol is a wff.

(b) If $\alpha$ and $\beta$ are wffs, then so are $(¬α), (α∧β), (α∨β), (α→β)$, and $(α↔β)$.

(c) No expression is a wff unless it is compelled to be one by (a) and (b).

2

"Well built" is defined by rules like: if $\varphi$ is well-built, then so too is $\neg \varphi$; if $\varphi$ and $\psi$ are well-built, then so too is $\varphi \wedge \psi,$ etc. Furthermore, we stipulate that only the formulae that can be constructed according to these rules are well-built. This means that meaningless formulae like $\varphi \wedge (\neg)$ are not well-built.

Okay, but why bother?

We use the concept of a well-built formula to prevent "junk theorems." For example, one inference rule might read: "If $\varphi$ is written down, then we may write $\varphi \vee \psi$." Using this rule willy-nilly, we can deduce silly things. For example, perhaps $x=x$ is written down. Then we can deduce $(x=x) \vee (=x= x\neg).$ Such "junk theorems" are avoided by restricting the use of inference rules to well-built formulae.

goblin GONE
  • 67,744