Extensions
In extensions of classical propositional logic, the duality still holds (that is, to any logical operator we can always find its dual), since in the presence of the identities governing negation, one may always introduce an operator that is the De Morgan dual of another. This leads to an important property of logics based on classical logic, namely the existence of negation normal forms: any formula is equivalent to another formula where negations only occur applied to the non-logical atoms of the formula. The existence of negation normal forms drives many applications, for example in digital circuit design, where it is used to manipulate the types of logic gates, and in formal logic, where it is a prerequisite for finding the conjunctive normal form and disjunctive normal form of a formula. Computer programmers use them to simplify or properly negate complicated logical conditions. They are also often useful in computations in elementary probability theory.
Let us define the dual of any propositional operator P(p, q, ...) depending on elementary propositions p, q, ... to be the operator defined by
This idea can be generalised to quantifiers, so for example the universal quantifier and existential quantifier are duals:
To relate these quantifier dualities to the De Morgan laws, set up a model with some small number of elements in its domain D, such as
- D = {a, b, c}.
Then
and
But, using De Morgan's laws,
and
verifying the quantifier dualities in the model.
Then, the quantifier dualities can be extended further to modal logic, relating the box ("necessarily") and diamond ("possibly") operators:
In its application to the alethic modalities of possibility and necessity, Aristotle observed this case, and in the case of normal modal logic, the relationship of these modal operators to the quantification can be understood by setting up models using Kripke semantics.
Read more about this topic: De Morgan's Laws
Famous quotes containing the word extensions:
“If we focus exclusively on teaching our children to read, write, spell, and count in their first years of life, we turn our homes into extensions of school and turn bringing up a child into an exercise in curriculum development. We should be parents first and teachers of academic skills second.”
—Neil Kurshan (20th century)
“The psychological umbilical cord is more difficult to cut than the real one. We experience our children as extensions of ourselves, and we feel as though their behavior is an expression of something within us...instead of an expression of something in them. We see in our children our own reflection, and when we don’t like what we see, we feel angry at the reflection.”
—Elaine Heffner (20th century)