\part{Propositional logic}

Perhaps the simplest branch of logic, this theory analyzes the relationship between 

\chapter{Propositions}

Proposition
Some statement that can be either 'true' or 'false'


We want to develop a basic sytem to:
- Mathematically represent an 'irreducible proposition' 
- Develop 'operators' so that more complex propositons are expressible
- Evaluate the truth of propositions given the truth of its dependent 'irreducible propositions'


Truth value
Value that relates a proposition to its truth.
The top $\top$ is the truth value relating to 'true'.
The bottom $\bot$ is the truth value relating to 'false'.


Propositional variable
Free variable that can take a _truth value_. It is a type of _atomic formula_; it is an irreducible free variable of truth values.


Valuation
Function mapping a proposition to a truth value. Its mapping is done by a certain setting of the propositional variables.
Combinatorics implies this function has \[2^n\] mappings if there are \[n\] propositional variables involved.



Proposition
Mathematically, it is a statement written in propositional logic that evaluates to either 'true' or 'false'.



Valuation
Assignment of truth values







\chapter{Logical connectives}


One may naturally seek to create propositions that are built from a multitude of propositional variables.
Logical connectives are the operators that allow this to occur.



Logical connective
Operators or functions of propositional variables.


Since logical connectives are operators, one seeks to determine its behaviour by a function mapping truth values to a truth value.

\begin{definition} \emph{Boolean function}
Function mapping a tuple of truth values to a truth value. Its mapping is done through a _formula_.
\[f : \{ \top , \bot \}^n \to \{ \top , \bot \}  \]
\end{definition}

For a visual description, truth tables are a convenient way to describe the mappings of a a Boolean function and hence the behaviour of a logical connective. To demonstrate this, define a binary logical connective $\oplus$ and examine the truth table below.


Using this truth table as a reference, one can understand the way in which the logical connective connects 2 propositions


Zeroary connectives
Verum
\[\top\]
Falsum
\[\bot\]


Unary connectives
Negation (NOT)
\[\neg P \]


Binary connectives
Conjunction (AND)
\[P \land Q\]
Disjunction (OR)
\[P \lor Q\]
\[\neg ( \neg P \land \neg Q)\]
Conditional (IMPLY)
\[P \implies Q \]
\[Q \lor \neg P\]
Biconditional (IFF)
\[P \iff Q \]
\[(P \land Q) \lor \neg (P \lor Q) \]


There exist other binary logical connectives of interest.

Exclusive Disjunction (XOR)
\[ P \oplus Q\]
Nonconjunction (NAND)





\chapter{Formulae}



Formula
Sequence of symbols that are interpreted by some logical system (in our case, propositional logic)

Well formed formula (WFF)
Formula that is 'well formed' with respect to the logical system in question. For proposition logic, such formulae are defined inductively.

Propositional variables are WFF
If P is a WFF, then \[\neg P\] is a WFF
If P,Q are WFF, then \[(P \land Q)\] is a WFF
If P,Q are WFF, then \[(P \lor Q)\] is a WFF
If P,Q are WFF, then \[(P \implies Q)\] is a WFF
If P,Q are WFF, then \[(P \iff Q)\] is a WFF

An interesting type of formula is one that happens to always be true regardless of the outcome of its underlying propositonal variables; these are called tautologies.

Tautology
Formula that yields true for all settings of its propositonal variables.

Here are some simple tautologies.

Law of the Excluded Middle
\[P \lor \neg P\]
Double negation
\[ \neg \neg P \iff P \]
Self implication
\[ P \implies P \]
Self equivalence
\[ P \iff P \]




Satisfiable formula
A formula $\gamma$ is satisfiable if there exists a setting of its propositional variables such that $\varphi (\gamma) = \top$


Satisfiable set of formulae
A set of formulae $\Gamma$ is satisfiable if there exists a setting of its propositional variables such that $\varphi(\gamma)=\top$ for every $\gamma \in \Gamma$ 


Tautological implication
A tautologically implies B if every valuation that satisfies A satisfies B

Tautology equivalence
A is tautologically equivalent to B if the valuations that satisfy A are the only valuations that satisfy B

Semantic Deduction Theorem





### Simple tautological equivalences
Modus ponens
\[((P \implies Q) \land P ) \implies Q\]
Modus tollens
De Morgan's law
\[\neg (P \land Q) \iff ( \neg P \lor \neg Q ) \]
\[\neg (P \lor Q) \iff ( \neg P \land \neg Q ) \]
Law of the syllogism
Contrapositive
\[ (P \implies Q) \iff (\neg Q \implies \neg P)\]
Absorption
Idempotence


Theorem; De Morgan's laws

Theorem; NOT/AND, NOT/OR, NOT/IMPLY are all functionally complete (can form any formula)
\[(P \lor Q) \iff (P \land \neg Q)\]
\[(P \implies Q) \iff (\neg (\neg Q \land P))\]
\[(P \iff Q) \iff (\neg (\neg (Q \land P)\land \neg (\neg Q \land \neg P)))\]









Semantic deduction theorem



Validity

Consistency
A set of propositions is inconsistent iff
\[\bigwedge_{p \in P} p \iff \bot\]



Language
A language is a set of logical connectives

Adequate Language
A set of logical connectives is adequate if under composition, they can represent any Boolean function

Literal
Formula of a predicate variable either under negation or not

\begin{theorem} AND OR NOT IMPLY IFF is an adequate language
\end{theorem}

Disjunctive Normal Form (DNF)
Disjunction of a conjunction of literals, can represent any Boolean function
Conjunctive Normal Form (DNF)
Conjunction of a disjunction of literals



\chapter{Propositional substitution}
