1. Complete sets of connectives, truth-functions and substitutions

Complete Sets of Connectives

Complete Set of Connectives

A set of connectives is called complete (or adequete) if every propositional logic formula is equivalent to a formula using only connectives from this set.

Examples:

• Since every formula has a DNF, the set $\{\neg ,\wedge ,\vee \}$ is complete.
• From De Morgan’s laws we have that: $$\begin{array}{rl}P\vee Q& \equiv \neg (\neg P\wedge \neg Q)\\ P\wedge Q& \equiv \neg (\neg P\vee \neg Q)\end{array}$$ Therefore both sets of connectives $\{\wedge ,\neg \}$ and $\{\vee ,\neg \}$ are complete.

To show a given set of connectives is complete, we need to express it in terms of a known complete set of connectives.

• The set $\{\neg ,\to \}$ is complete because $P\to Q\equiv \neg P\vee Q$, hence the set $\{\neg ,\to \}$ can be expressed in terms of the complete set $\{\neg ,\vee \}$.
• No singleton set from the standard set of connectives is complete.

Link to original

Truth-functions

Truth-function

A truth-function is a function whose arguments take true ($1$) or false ($0$) and return either true or false as their output.

• Formally, a truth-function $f$ is a function $f:\{0,1{\}}^n\to \{0,1\}$.
• Any well-formed formulae defines a truth-function and vice-versa.
• 2. Disjunctive Normal Form > Truth Table to DNF can be used to build the function.

title: Example
Let $f$ be the truth-function as defined:
$$
	f(P,Q,R) = 1 \iff \text{either } P = Q = 0 \text{ or } Q = R = 1
$$
 
Hence $f$ is equal to $1$ in these four exact cases:
$$
	f(0,0,0), f(0,0,1), f(0,1,1), f(1,1,1)
$$

Link to original

Substitutions

Uniform substitution of formulae

Universal substitution of formula for propositional variables:

• Let $W,H_1,...,H_n$ be formulae.
• Let $P_1,...,P_n$ be propositional variables. ? The expression $W(P_1/H_1,...,P_n/H_n)$ denotes the formula obtained by simultaneously replacing all occurences of $P_1$ in $W$ by the formula $H_1$, $P_2$ by $H_2$ and so forth.
• We say that the formula $W(../...)$ is a substitution instance of the original formula.

title: Example 1
Let $W$ be $P \rightarrow (Q \rightarrow P)$.
Hence $W(P/\neg P \lor R, Q/\neg P)$ is the formula $\neg P \lor R \rightarrow (\neg P \rightarrow \neg P \lor R)$.
 
In this case, both $W$ and $W(...)$ are both tautologies as $W(...)$ follows from the logic of $W$.

title: Example 2
The formula $(\neg P \lor R \rightarrow \neg P) \rightarrow \neg P \lor R$ is not a subsitution instance of $P \rightarrow (Q \rightarrow P)$.
- Both have a different structure from each other.
If we replace $P$ by $(\neg P \lor R \rightarrow \neg P)$ then we would have to replace $Q$ by $\neg P \lor R$ but we would "miss the consequent of $Q \rightarrow P$".

Link to original

Substitution Properties

From $F\equiv G$, we can assume that $F(P_1/H_1,...,P_n/H_n)\equiv G(P_1/H_1,...,P_n/H_n)$.

We can obtain a new equivalence as a substitution instance of the De Morgan law, take the logical equivalence $\neg (P\vee Q)=\neg P\wedge \neg Q$:

• $\neg (\underline{(P\to R)}\vee \underline{(R⟺Q)})\equiv \neg \underline{(P\to Q)}\wedge \neg \underline{(R⟺Q)}$
• This new equivalence is also a tautology. $\neg (\underline{(P\to R)}\vee \underline{(R⟺Q)})⟺\neg \underline{(P\to Q)}\wedge \neg \underline{(R⟺Q)}$