Well-Formed Formulas | Readstall

Well-Formed Formulas

02-02-19 Himaja G 0 comment

 Well-Formed Formulae(WFF)

In discrete mathematics, well-formed formula is defined as a statement formula is an expression which is a string consisting of variables (capital letters with subscripts or without subscripts), parenthesis, and connective symbols. Not every string of these symbols is a formula, We shall now give a recursive definition of a statement formula, often called a well-formed formula (WFF). A well-formed formula can be generated by the following rules

  1. A statement variable standing alone is a well-formed formula.
  2. If A is a Well-Formed Formula, then ~A is a well-formed formula.
  3. If A and B are well-formed formulas, then (A∧B), (A∨B), (AB), and (AB) are well formed formulas.
  4. A string of symbols containing the statement variables, connective and parenthesis is a well formed formulas if and only if it can be obtained by finitely many applications of the rules 1, 2 and 3.

The following are well formed formulas:

~(P∧Q),  ~(P∨Q),  (P (Q∨R)),  (P(QR))

The following are not well-formed formulas:

1.~PQ, In this obviously P and Q are well formed formulas A well formed formula would be either (~PQ) or ~(PQ).

2.(PQ) (∧Q), this is not a well formed formula because ∧Q is not.

3.(P∧Q. here note that (P∧Q) is a well formed formula.

In this we shall not discuss these conventions here. It is possible to introduce some conventions so that the number of parentheses used can be reduced.


Leave a reply