Well-formed Formulas (wffs)
A key property of formulas is that they can be uniquely parsed to determine the structure of the formula in terms of its propositional variables and logical connectives. When formulas are written in infix notation, as above, unique readability is ensured through an appropriate use of parentheses in the definition of formulas. Alternatively, formulas can be written in Polish notation or reverse Polish notation, eliminating the need for parentheses altogether.
The inductive definition of infix formulas in the previous section can be converted to a formal grammar in Backus-Naur form:
::= | () | () | () | () | ()
It can be shown that any expression matched by the grammar has a balanced number of left and right parentheses, and any nonempty initial segment of a formula has more left than right parentheses. This fact can be used to give an algorithm for parsing formulas. For example, suppose that an expression x begins with . Starting after the second symbol, match the shortest subexpression y of x that has balanced parentheses. If x is a formula, there is exactly one symbol left after this expression, this symbol is a closing parenthesis, and y itself is a formula. This idea can be used to generate a recursive descent parser for formulas.
Example of parenthesis counting:
This method locates as "1" the principal connective -- the connective under which the overall evaluation of the formula occurs for the outer-most parentheses (which are often omitted). It also locates the inner-most connective where one would begin evaluatation of the formula without the use of a truth table, e.g. at "level 6".
| start | ( | ( | ( | c | & | d | ) | V | ( | p | & | ~ | ( | ( | c | & | ~ | ( | d | ) | ) | ) | ) | ) | = | ( | ( | ( | c | & | d | ) | V | ( | p | & | d | ) | ) | V | ( | p | & | ~ | ( | c | ) | ) | ) | ) | |
| count | 0 | 1 | 2 | 3 | 3 | 3 | 3 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 5 | 5 | 5 | 5 | 6 | 6 | 5 | 4 | 3 | 3 | 1 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 3 | 3 | 4 | 4 | 4 | 4 | 3 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 1 | 0 |
Read more about this topic: Propositional Formula
Famous quotes containing the word formulas:
“You treat world history as a mathematician does mathematics, in which nothing but laws and formulas exist, no reality, no good and evil, no time, no yesterday, no tomorrow, nothing but an eternal, shallow, mathematical present.”
—Hermann Hesse (1877–1962)