Propositional logic

Introduction

True and False

We start off with two statements:

  • True - \(T\) or \(\top \)

  • False - \(F\) or \(\bot \)

Propositional variables

We can represent \(T\) or \(F\) using a symbol:

\(\theta \)

Operators

Unary operators

A unary operator takes one input and returns another.

Only negation, \(\neg \) is of interest.

The following statements are equivalent:

  • \(T\)

  • \(\neg F\)

Binary operators

A binary operator takes an additional input.

  • If then - \(\theta \rightarrow \gamma \)

  • Then if - \(\theta \leftarrow \gamma \)

  • Iff - \(\theta \leftrightarrow \gamma \)

  • And / Conjunction - \(\theta \land \gamma \)

  • Or / Disjunction - \(\theta \lor \gamma \)

Truth tables

Brackets

Operators can be shown together, with brackets. For example:

\((\alpha \lor \beta )\land \gamma \)

Is not the same as:

\(\alpha \lor (\beta \land \gamma )\)

Atomic formulae

Atomic formulae are those without operators taking more than one input.

Literals, and negative literals, are types of atomic formula.

A literal is a formula with no operators.

\(\theta \)

These are also known as positive literals.

Negative literals are the negation of a literal.

\(\neg \theta \)

Well-formed formulae

A well-formed formula is one which can be given a truth value.

The following is not a well-formed formula:

\(\theta \land \)

Interpretations

An interpretation assigns meaning to propositional variables in a formula.

For example an interpretation of the formula \(\theta \lor \gamma \) assigns values to each of \(\theta \) and \(\gamma \).

Satifisable

A formula is satisfisable if there is some interpretation where it is true.

For example \(\theta \) is satisfisable but \(\theta \land \neg \theta \) is not.

Tautology

A formula is a tautology if it is true in all interpretations.

Examples of tautologies include:

  • \(\theta \lor \neg \theta \)

Multi-valued logic

Multi-valued logic

We can have logic with more than two states.

Semantic consequence

Semantic consequence

A formula, \(A\), semantically implies another, \(B\), if for every interpretation of \(A\), \(B\) is true.

We show this with:

\(A\vDash B\)

Formula \(B\) is satisfisable if there is some \(A\) where this is true.

For example: \(A\land B \vDash A\)

Formula \(B\) is a tautology if this is true for any \(A\). We can also write this as \(\vDash B\).

Logical equivalence

If \(A\vDash B\) and \(B\vDash A\) we say that \(A\) and \(B\) are logically equivalent.

This is shown as \(A \Leftrightarrow B\).

How many unique operators are there?

An arbitrary operator takes \(n\) inputs are returns \(T\) or \(F\).

With \(0\) inputs there is one posible permutation. For every additional input the number of possible permutations doubles. Therefore there are \(2^n\) possible permutations.

For the operator with one permutation there are two operators. For every additional permutation the number of operator doubles. Therefore there are \(2^{(2^n)}\) possible operations.

With \(0\) inputs, we need \(2\) different operators to cover all outputs. For \(1\) input we need \(4\) and for \(2\) inputs we need \(16\).

We don’t need \(0\)-ary operators

There are two unique \(0\)-ary operators. One always returns \(T\) and the other always returns \(F\). These are already described.

We need one unary operator

For the operators with \(1\) input we have:

  • one which always returns \(T\)

  • one which always returns \(F\)

  • one which always returns the same as the input

  • one which returns the opposite of the input

It is this last one, negation, shown as \(\neg \) and is of most interest.

We can use a subset of binary operators

The full list of binary operators are included below.

Of these, the first two are \(0\)-ary operators, and so are not needed. The next four are unary operators, and so are not needed.

The non-implications can be rewritten using negation.

Brackets replace the need for n-ary operators

N-ary operators contain \(3\) or more inputs.

N-ary operators can be defined in terms of binary operators.

As an example if we want an operator to return positive if all inputs are true, we can use:

\((\theta \land \gamma )\land \beta \)

De Morgan’s Laws

  • \(\neg (A\lor B)\Leftrightarrow (\neg A\land \neg B)\)

  • \(\neg (A\land B)\Leftrightarrow (\neg A\lor \neg B)\)

This expresses the duality of normal form.

Duality is the principle that binary operators have inverses, and when they are swapped with their inverse, the truth value of the statement is unaffected.

Normal form

This is where a formula is shown using only:

  • And / Conjunction- \(\land \)

  • Or / Disjunction - \(\lor \)

  • Negation - \(\neg \)

The conjunctive normal form (CNF) is where a formula is converted to a normal form with the following layout:

\(a \land b \land c \land d\)

These letters can represent complex sub-formulae, in normal form.

Statements in this form are easier to evaluate, as each subformula can be evaluated separately. The statement is true only if all formulaes within are also true.

The disjunctive normal form (DNF) is similar for \(\lor \).

\(a \lor b \lor c \lor d\)

Properties of the normal form

The normal binary operators are commutitive - \(A\land B\Leftrightarrow B\land A\) and \(A\lor B\Leftrightarrow B\lor A\)

Both binary operators are associative - \((A\land B)\land C\Leftrightarrow A\land (B\land C)\) and \((A\lor B)\lor C\Leftrightarrow A\lor (B\lor C)\)

Negation is complementary.

\(A\land \neg A\Leftrightarrow F \)

\(A\lor \neg A\Leftrightarrow T\)

Normal binary operators are absorbative.

\(A\land (A\lor B)\Leftrightarrow A\) \(A\lor (A\land B)\Leftrightarrow A\)

Identity.

\(A\land T\Leftrightarrow A\)

\(A\lor F \Leftrightarrow A\)

Distributivity.

\(A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)\)

\(A\lor (B\land C)\Leftrightarrow (A\lor B)\land(A\lor C)\)