Virtual Completeness As An Operator
Implication alone is not functionally complete as a logical operator because one cannot form all other two-valued truth functions from it. However, if one has a propositional formula which is known to be false and uses that as if it were a nullary connective for falsity, then one can define all other truth functions. So implication is virtually complete as an operator. If P,Q, and F are propositions and F is known to be false, then:
- ¬P is equivalent to P → F
- P ∧ Q is equivalent to (P → (Q → F)) → F
- P ∨ Q is equivalent to (P → Q) → Q
- P ↔ Q is equivalent to ((P → Q) → ((Q → P) → F)) → F
More generally, since the above operators are known to be functionally complete, it follows that any truth function can be expressed in terms of "→" and "F", if we have a proposition F which is known to be false.
It is worth noting that F is not definable from → and arbitrary sentence variables: any formula constructed from → and propositional variables must receive the value true when all of its variables are evaluated to true. It follows as a corollary that {→} is not functionally complete. It cannot, for example, be used to define the two-place truth function that always returns false.
Read more about this topic: Implicational Propositional Calculus
Famous quotes containing the words virtual and/or completeness:
“Neither dead nor alive, the hostage is suspended by an incalculable outcome. It is not his destiny that awaits for him, nor his own death, but anonymous chance, which can only seem to him something absolutely arbitrary.... He is in a state of radical emergency, of virtual extermination.”
—Jean Baudrillard (b. 1929)
“Poetry presents indivisible wholes of human consciousness, modified and ordered by the stringent requirements of form. Prose, aiming at a definite and concrete goal, generally suppresses everything inessential to its purpose; poetry, existing only to exhibit itself as an aesthetic object, aims only at completeness and perfection of form.”
—Richard Harter Fogle, U.S. critic, educator. The Imagery of Keats and Shelley, ch. 1, University of North Carolina Press (1949)