Propositional formula: Difference between revisions

Content deleted Content added

Inline

Revision as of 18:24, 31 October 2007

In propositional logic, a propositional formula is a particular type of syntactic expression. A propositional formulas may also be called a propositional expression, a well formed formula, a wff, a sentence, or a sentential formula. In order to be a propositional formula, an expression must be structured so that a unique truth value for the formula can be deduced from truth values of the propositional variables it contains.

In contexts of discussion that involve little risk of confusion, a propositional formula may be more briefly referred to as a "proposition", but the distinction between a proposition, a formal object under discussion, and a propositional formula, a formal expression that denotes it, is often of importance.

Propositional variables

The simplest type of propositional formula is a propositional variable. These are atomic, symbolic expressions often denoted by A, B, etc. A propositional variable in intended to represent an atomic proposition, such as "It is Saturday" or "I only go to the movies on Monday".

More complex formulas

Arbitrary propositional formulas are built from propositional variables and other propositional formulas using propositional connectives. Examples of connectives include:

The unary negation connective. If $\alpha$ is a formula, then $\lnot \alpha$ is a formula.
The classical binary connectives $\land ,\lor ,\to ,\leftrightarrow$ . Thus, for example, if $\alpha$ and $\beta$ are formulas, so is $(\alpha \to \beta )$ .
Other binary connectives, such as NAND, NOR, and XOR
Constant 0-ary connectives $\top$ and $\bot$

Connectives that take more than two arguments are also studied.

Inductive definition

The classical presentation of propositional logic (see Enderton 2002) uses the connectives $\lnot ,\land ,\lor ,\to ,\leftrightarrow$ . 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,
$(\lnot \alpha )$ is a formula whenever $\alpha$ is, and
$(\alpha \,\Box \,\beta )$ is a formula whenever $\alpha$ and $\beta$ are formulas and $\Box$ is one of the binary connectives $\land ,\lor ,\to ,\leftrightarrow$ .

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 X_V 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 XX_V to XX_V:

Given a string z, the operation ${\mathcal {E}}_{\lnot }(z)$ returns $(\lnot z)$ .
Given strings y and z, the operation ${\mathcal {E}}_{\land }(y,z)$ returns $(y\land x)$ . There are similar operations ${\mathcal {E}}_{\lor }$ , ${\mathcal {E}}_{\to }$ , and ${\mathcal {E}}_{\leftrightarrow }$ corresponding to the other binary connectives.

The set of formulas over V is defined to be the smallest subset of XX_V containing V and closed under all the formula building operations.

Parsing formulas

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:

<formula> := <propositional variable>

| ( $\lnot$ <formula> )

| ( <formula> $\land$ <formula>)

| ( <formula> $\lor$ <formula> )

| ( <formula> $\to$ <formula> )

| ( <formula> $\leftrightarrow$ <formula> )

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 (Enderton 2002). This fact can be used to give an algorithm for parsing formulas. For example, suppose that an expression x begins with $(\lnot$ . 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.

Reduced sets of connectives

A set of logical connectives is called complete if every propositional formula is tautologically equivalent to a formula with just the connectives in that set. There are many complete sets of connectives, including $\{\land ,\lnot \}$ , $\{\lor ,\lnot \}$ , and $\{\to ,\bot \}$ . There are two binary connectives that are complete on their own, corresponding to NAND and NOR, respectively.

Normal forms

An arbitrary propositional formula may have a very complicated structure. It is often convenient to work with formulas that have simpler forms, known as normal forms. Some common normal forms include conjunctive normal form and disjunctive normal form.

Impredicative propositions

Consider the following proposition expressing a definition: "A proposition (sentence, assertion) is either simple or compound but not both; a compound sentence is two or more simple sentences linked by a connective such as AND (BUT, semicolon ; ), OR, IF ..., THEN..., and NEITHER ... NOR ... ".

So given this definition, what does one make of the following:

(1) "This sentence is simple." (2) "This sentence is not simple; it is complex, and it is conjoined by AND."

Define "compound" = "not simple". Then assign the variable "s" to the left-most sentence "This sentence is simple", "c" to "This sentence is compound", and "j" by "It [this sentence] is cojoined by AND". Substitute the words "NOT simple" for "compound". the second sentence can be expressed as:

( NOT(s) AND c AND j )

If truth values are to be placed on the sentences s, c and j per the definitions, then all are clearly FALSEHOODS: e.g. "This sentence is complex" is a FALSEHOOD (it is simple, by definition). So their conjuction (AND) is a falsehood. But when taken in its assembed form, the sentence a TRUTH.

This is an example of the paradoxes that result from an impredicative definition -- that is, when an object m has a property P, but the object m is defined in terms of property P. ^[1] The best advice for a rhetorician or one involved in deductive analysis is avoid impredicative definitions but at the same time be aware of them when they appear. Engineers, on the other hand, put them to work in the form of propositional formulas with feedback.

Propositional formula with "feedback"

The simplest case is when the output of OR feeds back into one of its inputs. Begin with (p V a) = q, then let p = q. Observe that q's "definition" in terms of the OR depends on itself as well as "a"; this definition of q is thus impredicative.

No stipulation within the theory (either the axiomatic or truth-table systems of objects and relations) forbids this from happening. The following illustrates what happens when a formula derives one of its inputs e.g. “p” from its output e.g. “q”.

Example: ( ( c & d ) V ( p & ( ~( d ) & ~( c ) ) ) ) = q, but now let p = q

( ( c & d ) V ( q & ( ~( d ) & ~( c ) ) ) ) = q

Either of two conditions can result^[2]: (1) oscillation, (2) memory:

(1) Oscillation: Without the notion of “delay”, this condition presents itself as undecidability; neither { T, F }, (or { ON, OFF }, { 1, 0 }, etc) can be determined. With delay the condition presents itself as alternating values e.g. TFTFTFTF...TF, or 1010101010..., ad infinitum.

(2) Memory: Without delay inconsitencies must be eliminated from a truth table analysis. With the notion of “delay”, this condition presents itself as a momentary inconsistency between the fed-back output variable q is acting as an input (e.g. p = q). But the overall formula remains consitent.

Analysis: A truth table can reveal the rows where inconsistencies occur between q at the input and q at the output. The analysis proceeds in the conventional manner after "breaking the line" (cf Mcklusky p. 194-5). In every row the output q is compared to the now-independent input p and any inconsistencies between p and q are noted (i.e. p = 0 and q = 1, p = 1 and q = 0; when the "line" is "remade" both are rendered impossible by the Law of contradiction ~(p & ~p)). Rows revealing inconsistences are either considered transient states (McCluskey) or just eliminated as inconsistent and hence "impossible".

	motor ON	door closed	clock active							motor ON
	picnic	nice day	noon							picnic
							s			q			q1	r~				r	d~
row	q	d	c	(	(	c	&	d	)	V	(	q	&	~	(	(	c	&	~	(	d	)	)	)	)	)	Description
0	0	0	0			0	0	0		0		0	0	1			0	0	1		0						0.00: RESET: c is inactive and d inactive but flip-flop is reset
1	0	0	1			1	0	0		0		0	0	0			1	1	1		0						0.1: RESET: c is active but not d, flip-flop remains reset)
2	0	1	0			0	0	1		0		0	0	1			0	0	0		1						0.2: RESET: d is active but not c, flip-flop remains reset)
3	0	1	1			1	1	1		1		0	0	1			1	0	0		1
4	1	0	0			0	0	0		1		1	1	1			0	0	1		0						1.00: SET: c is inactive & d is inactive, flip-flop is no longer being set
5	1	0	1			1	0	0		0		1	0	0			1	1	1		0
6	1	1	0			0	0	1		1		1	1	1			0	0	0		1						1.01: SET: c is inactive & d is active, flip-flop is no longer being set
7	1	1	1			1	1	1		1		1	1	1			1	0	0		1						1.11: SET: c is active & d is active, flip-flop is being set

When input p is considered to be the same as ouput q and when c=0 and d=0, the output q can be either 1 or 0. Without knowledge of what is going on “inside” the formula, this represents a condition of [randomness]. That is, sometimes when we look at q we see 0 and other times 1. To avoid this problem one has to know the state (condition) of the "hidden" variable p (i.e. q fed back). When this is known the apparent inconsistency goes away.

To understand [predict] the behavior of formulas with feedback requires the more sophisticated analysis of sequential circuits. One discovers that propositional formulas with feedback lead, in their simplest form, to state machines; they also lead to memories in the form of Turing tapes and counter-machine counters. From combinations of these elements one can build any sort of bounded computational model (e.g. Turing machines, counter machines, register machines, Macintosh computers, etc).

Footnotes

^ This definition is given by Stephen Kleene. Both Kurt Gödel and Kleene believed that the classical paradoxes are uniformly examples of this sort of definition. But Kleene went on to assert that the problem has not been solved satisfactorily and impredicative definitions can be found in analysis. He gives as example the definition of the least upper bound (l.u.b) u of M. Given a Dedekind cut of the number line C and the two parts into which the number line is cut, i.e. M and (C - M), l.u.b. = u is defined in terms of the notion M, whereas M is defined in terms of C. Thus the definition of u, an element of C, is defined in terms of the totality C and this makes its definition impredicative. Kleene asserts that attempts to argue this away can be used to uphold the impredicative definitions in the paradoxes.(Kleene 1952:43).
^ More precisely, given enough "loop gain", either oscillation or memory will occur. In idealized mathematical systems adequate loop gain is not a problem.

References

Enderton, H. B. (2002). A Mathematical Introduction to Logic. Harcourt/Academic Press. ISBN 0-12-238452-0

[1] This definition is given by Stephen Kleene. Both Kurt Gödel and Kleene believed that the classical paradoxes are uniformly examples of this sort of definition. But Kleene went on to assert that the problem has not been solved satisfactorily and impredicative definitions can be found in analysis. He gives as example the definition of the least upper bound (l.u.b) u of M. Given a Dedekind cut of the number line C and the two parts into which the number line is cut, i.e. M and (C - M), l.u.b. = u is defined in terms of the notion M, whereas M is defined in terms of C. Thus the definition of u, an element of C, is defined in terms of the totality C and this makes its definition impredicative. Kleene asserts that attempts to argue this away can be used to uphold the impredicative definitions in the paradoxes.(Kleene 1952:43).

[2] More precisely, given enough "loop gain", either oscillation or memory will occur. In idealized mathematical systems adequate loop gain is not a problem.

[1]

[2]