# Propositional Logic

# 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 |