Zeroth Order Logic
Zeroth order logic, also known as propositional logic, is one of the many existing logic systems.
Zeroth order logic enables the programmatic representation of knowledge and the mechanization of deductions.
It is a good starting point because it forms a foundation for higher order logics.
Syntactically, zeroth order logic is formed from:
- Constants: true and false
- Atomic propositions: e.g. "the card should break", "the light is red", etc
- Connectives: (e.g.
Propositions can assume two values: true or false. For example "the light is red" is either true or false, and they are typically represented with letters (e.g.
p = "the light is red").
Connectives defines different ways to combine atomic propositions to form new ones, enabling more complicated propositions to be expressed from simpler ones. For example, "red light"
=> "the card should break", or
p => q for short, is a compound proposition formed from a connective (
=>) and two atomic propositions (e.g. "red light" and "the card should break").
There are certain propositions that are always true regardless of interpretation, called tautologies. For example
p or ~p is true regardless of whether
p is interpreted as true or false and, importantly, regardless of what
p represents (e.g. "it is raining or it is not raining" is always true regardless of whether "it is raining" is true or false).
With that, we are able to construct equivalences and implications that enable us to transform propositions mechanically, deriving new ones from existing ones, independently of their evaluation (i.e. valid for all interpretation) and their domain of discourse (e.g. what they represent). For example, knowing
p (e.g. "I am pretty") I can deduce
~~p (e.g. "I am not not-pretty") with a logical transformation called double negation. Or, knowing
p => q (e.g. "If the light is red you should break") and
a (e.g. "the light is red") I can deduce
q (e.g. "you should break") with a logical transformation called modus ponens.
Automated deduction can be constructed by programmatically searching over the space of possible logical transformations that can be applied from a set of given premises to arrive at a desired result. For example, knowing
p => q I can deduce
q by applying double negation to
~~p to deduce
p and use that intermediate result and the original premise
p => q with modus ponens to arrive at
Logical connectives combine a number of propositions to produce a new proposition. Each logical connective is defined by its name, its arity and its interpretation.
For example, take the negation connective: it takes a single proposition
p and turns that into a new proposition
~p with the following interpretation:
Binary connectives, on the other hand, operate on two propositions
q and form a new proposition with the following interpretation:
|p||q||p or q||p and q||p => q||p <=> q||p xor q|
Each connective has a name, a symbol used as convention, an arity and a semantic interpretation:
|negation||~||~ p||not p|
|conjunction||and||p and q||p and q|
|disjunction||or||p or q||p or|
|necessity||=>||p => q||if p then q|
|equivalence||<=>||p <=> q||if and only if p then q|
|sufficiency||<=||p <= q||p if q|
|exclusive disjunction||xor||p xor q||either p or q|
Notably, the application of a connectives turns the proposition into a new proposition, so you can compound them:
|p||q||p or q||~ (p or q)||~ ~ (p or q)||(~ ~ (p or q)) => false|
Tautologies are propositions that are
true in every possible interpretation. For example,
p or ~p is always
true, regardless of the value of
|p||~p||p or ~p|
Contradictions, on the other hand, are propositions that are always
false. For example,
p and ~p is always
false, regardless of the value of
|p||~p||p and ~p|
Contigencies are propositions that are neither tautologies nor contradictions.
p or q can be
false depending on the values of
|p||q||p or q|
q are logically equivalent when
p <=> q is a tautology (i.e. true regardless of the values of
For example, take the double negation tautology:
~~p <=> p is
true regardless of the value of
|p||~p||~~p||~~p <=> p|
Another example is what is known as the commutative tautology:
p or q <=> q or p is
true regardless of the values of
|p||q||p or q||q or p||p or q <=> q or p|
Another example is what is known as the de morgan's tautology:
~ (p or q) <=> ~p and ~q is
true regardless of the values of
|p||q||p or q||~ (p or q)||~p||~q||~p and ~q||~ (p or q) <=> ~p and ~q|
There are an infinite number of equivalences, but here are some of the more known:
|tautology||p or ~ p||true|
|contradiction||p and ~ p||false|
|conjunction domination||p and false||false|
|disjunction domination||p or true||true|
|conjunction identity||p and true||p|
|disjunction identity||p or false||p|
|conjunction idempotency||p and p||p|
|disjunction idempotency||p or p||p|
|double negation||not not p||p|
|commutative||p and/or q||q and/or p|
|associative||p and/or q||q and/or p|
|distributive||p and/or (q and/or r)||(p and/or q) and/or r|
|de morgan||~ (p and/or q)||~ p or/and ~ q|
In zeroth order logic, for each of these equivalences, you can verify their truthness by enumerating all possible values of
Implications are tautologies where you establish a sufficiency
=> but not a necessity
For example, from the following premises:
p => q
We can conclude
That's known as modus ponens and can be thought as
(p and p => q) => q. It becomes clear it is a tautology if you enumerate all possible interpretation of
q and verify that it has to be true in any permutation.
|p||q||p => q||(p and p => q)||(p and p => q) => q|
So, regardless of the values that
q assume, and regardless of their domain of discourse, knowing
p => q lets us assume
q through modus ponens.
Notably, modus ponens is not an equivalence because knowing
q doesn't enable us to deduce that
p => q, so it is a one way street.
Another example of implication is one called conjunction elimination: given
p and q assume
p and q => p).
|p||q||p and q||p and q => p|
Which clearly works one way (
p and q => p), but not the other way (
p and q <= p).
Like equivalences there is an infinite number of implications, but some are more easy to comprehend in discourse then others, making them more commonly used in arguments. Here are some of the most common ones:
|disjunction introduction||p||p or q|
|conjunction introduction||p, q||p and q|
|disjunctive syllogism||p or q, ~p||q|
|conjunction syllogism||p and q||p, q|
|modus ponens||p, p => q||q|
|modus tollens||~ q, p => q||~ p|
|hypothetical syllogism||p => q, q => r||p => r|