Overview

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. and, or, =>, etc)

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 and 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 q.

Connectives

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:

p	~p
F	T
T	F

Binary connectives, on the other hand, operate on two propositions p and 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
F	F	F	F	T	T	F
F	T	T	F	T	F	T
T	F	T	F	F	F	T
T	T	T	T	T	T	F

Each connective has a name, a symbol used as convention, an arity and a semantic interpretation:

name	symbol	usage	example
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
F	F	F	T	F	T
F	T	T	F	T	F
T	F	T	F	T	F
T	T	T	F	T	F

Tautologies

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	p or ~p
F	T	T
T	F	T

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	p and ~p
F	T	F
T	F	F

Contigencies are propositions that are neither tautologies nor contradictions.

For example, p or q can be true or false depending on the values of p and q.

p	q	p or q
F	F	F
F	T	T
T	F	T
T	T	T

Equivalences

Two propositions p and q are logically equivalent when p <=> q is a tautology (i.e. true regardless of the values of p and q).

For example, take the double negation tautology: ~~p <=> p is true regardless of the value of p:

p	~p	~~p	~~p <=> p
F	T	F	T
T	F	T	T

Another example is what is known as the commutative tautology: p or q <=> q or p is true regardless of the values of p and q:

p	q	p or q	q or p	p or q <=> q or p
F	F	F	F	T
F	T	T	T	T
T	F	T	T	T
T	T	T	T	T

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 and q:

p	q	p or q	~ (p or q)	~p	~q	~p and ~q	~ (p or q) <=> ~p and ~q
F	F	F	T	T	T	T	T
F	T	T	F	T	F	F	T
T	F	T	F	F	T	F	T
T	T	T	F	F	F	F	T

There are an infinite number of equivalences, but here are some of the more known:

Name	Proposition	Equivalence
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 p and q.

Implications

Implications are tautologies where you establish a sufficiency => but not a necessity <=.

For example, from the following premises:

• p and
• p => q

We can conclude q.

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 p and 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
F	F	T	F	T
F	T	T	F	T
T	F	F	F	T
T	T	T	T	T

So, regardless of the values that p and q assume, and regardless of their domain of discourse, knowing p and 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 and p => q, so it is a one way street.

Another example of implication is one called conjunction elimination: given p and q assume p (or p and q => p).

p	q	p and q	p and q => p
F	F	F	T
F	T	F	T
T	F	F	T
T	T	T	T

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:

Name	Proposition	Implication
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

Deduction