Inductive Definition
The classical presentation of propositional logic (see Enderton 2002) uses the connectives . The set of formulas over a given set of propositional variables is inductively defined to be the smallest set of expressions such that:
- Each propositional variable in the set is a formula,
- is a formula whenever is, and
- is a formula whenever and are formulas and is one of the binary connectives .
This inductive definition can be easily extended to cover additional connectives.
The inductive definition can also be rephrased in terms of a closure operation (Enderton 2002). Let V denote a set of propositional variables and let XV denote the set of all strings from an alphabet including symbols in V, left and right parentheses, and all the logical connectives under consideration. Each logical connective corresponds to a formula building operation, a function from XXV to XXV:
- Given a string z, the operation returns .
- Given strings y and z, the operation returns . There are similar operations, and corresponding to the other binary connectives.
The set of formulas over V is defined to be the smallest subset of XXV containing V and closed under all the formula building operations.
Read more about this topic: Propositional Formula
Famous quotes containing the word definition:
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)