We start off with two statements:
True - \(T\) or \(\top\)
False - \(F\) or \(\bot\)
We can represent \(T\) or \(F\) using a symbol:
\(\theta\)
A unary operator takes one input and returns another.
Only negation, \(\neg\) is of interest.
The following statements are equivalent:
\(T\)
\(\neg F\)
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\)
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 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\)
A well-formed formula is one which can be given a truth value.
The following is not a well-formed formula:
\(\theta \land\)
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\).
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.
A formula is a tautology if it is true in all interpretations.
Examples of tautologies include:
\(\theta \lor \neg \theta\)
We can have logic with more than two states.
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\).
If \(A\vDash B\) and \(B\vDash A\) we say that \(A\) and \(B\) are logically equivalent.
This is shown as \(A \Leftrightarrow B\).
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\).
There are two unique \(0\)-ary operators. One always returns \(T\) and the other always returns \(F\). These are already described.
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.
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.
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\)
\(\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.
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\)
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)\)