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)}$

Link to original

3. Logical consequence

Logical consequence

Argument

An argument is a sequence of [[Proposition|propositions]].

$$\begin{array}{rlrl}& \underline{\begin{array}{l}{p}_1\\ p_2\\ ..\\ p_n\end{array}\}}& & n\text{ premises}\\ \therefore & q& & \text{one conclusion}\end{array}$$

You can read ”$p_1,p_2,...,p_n$, therefore $q$”.

Link to original

Logical consequence

In a valid argument, we can informally say that conclusion $B$ “follows” from a set of premises $A_1,...,A_n$.

Formally, we say that formula $B$ is a logical consequence of the set of formulae $\{A_1,...,A_n\}$, if the following implication holds for every interpretation $v$: $$ \text{If } v(A_i) = 1, \text{ for all } 1 \le i \le n, \text{ then } v(B) = 1. $$

Alternative terminologies include:

• $B$ is a logical consequence of $A_1,...,A_n$.
• $A_1,...,A_n\models B$.
• The argument $A_1,...,A_n\models B$ is valid.
• $B$ is semantically entailed (or implied) by $A_1,...,A_n$
• $B$ is a valid consequence of $A_1,...,A_n$

Link to original

Alternate definition of Model

Let the symbol $\mathcal{I}$ denote the set of all interpretations. Let $\mathcal{S}=\{A_1,...,A_n\}$. We have that

$$\mathcal{S}\models B⟺\mathrm{mod}(\mathcal{S})\subseteq \mathrm{mod}(B)$$

Notice that $\mathrm{mod}(\neg B)=\mathcal{I}-\mathrm{mod}(B)$ hence:

$$\mathrm{mod}(B)\cap \mathrm{mod}(\neg B)=\varnothing$$

Therefore, if $\mathcal{S}\models B$, then $\mathrm{mod}(\mathcal{S})\cap \mathrm{mod}(\neg B)=\varnothing$.

title: Example
Show that $P, P \rightarrow Q \models Q$.
 
| *interpretation* | $p$ | $q$ | $p \rightarrow q$ | $p \land (p \rightarrow q)$ | $q$ |              $\models$              |
|:----------------:|:---:|:---:|:-----------------:|:---------------------------:|:---:|:-----------------------------------:|
|     $v_{0}$      |  0  |  0  |         1         |              0              |  0  |        ✅ **premises false**        | 
|     $v_{1}$      |  0  |  1  |         1         |              0              |  1  |        ✅ **premises false**        |
|     $v_{2}$      |  1  |  0  |         0         |              0              |  0  |        ✅ **premises false**        |
|     $v_{3}$      |  1  |  1  |         1         |              1              |  1  | ✅ **premises and conclusion true** |
 
The statement follows because in every row in which the columns for $P$ and $P \rightarrow Q$ contain $1$ (the premises), so does the column for $Q$ (the conclusion).
 
$$
	\bmod (\{ P, P \rightarrow Q \}) = \{ v_3 \} \subseteq \, \bmod(\{ Q \}) = \{ v_1, v_3 \}
$$
 
This type of derivation is called [[Modus ponens]].

Special case: unsatisfiable premises

Take the following scenario:

• If Jack takes a holiday, then Jill will be happy and she will not cry.
• Jack will take a holiday and if Jill is happy she will cry.
• Therefore Jack will take a holiday.

We define this formally using:

• Let $J$ stand for ‘Jack will take a holiday’
• Let $H$ stand for ‘Jill will be happy’
• Let $C$ stand for ‘Jill will cry’

In this case, the argument $J\to (H\wedge \neg C),J\wedge (H\to C)\models J$ is valid. This is because $\mathrm{mod}(\mathcal{S})=\varnothing \subseteq \mathrm{mod}(B)$. In general, any conclusion follows from an unsatisfiable set of premises.

Special case: tautological conclusions

Tautologies are always true, so if $A$ is a tautology, then $\mathrm{mod}(A)=\mathcal{I}$.

This has two effects:

1. A tautology is a logical consequence of any set of formulae.
2. A tautology also follows from ‘nothing’. Any interpretation satisfies all of the formulae in the empty set, hence $\mathrm{mod}(\varnothing )=\mathcal{I}$. However, if $A$ is a tautology, then $\mathrm{mod}(A)=\mathcal{I}$ hence $\mathrm{mod}(\varnothing )=\mathcal{I}\subseteq \mathrm{mod}(A)=\mathcal{I}$.

Invalid argument

Invalid argument

An argument that is not valid is said to be invalid.

By the definition of logical consequence, $A_1,...,A_n/\models B$ if there exists an interpretation $v$ such that:

$$v(A_i)=1\text{ for all }1\le i\le n,\text{ but }v(B)=0$$

Hence, in order to show a conclusion does not follow from a set of premises, we must find an interpretation that makes all of the premises true, but under which the conclusion is false.

Link to original

title: Example 1
Show that $P \not\models Q$ where $P$ and $Q$ are atoms.
 
**Solution**: Take the interpretation $v$ with $v(P) = 1$ and $v(Q) = 0$.

title: Example 2
Show that $P \rightarrow Q \not\models Q$ where $P$ and $Q$ are atoms.
 
**Solution**: Take the interpretation $v$ with $v(P) = 0$ and $v(Q) = 0$.
When $P$ and $Q$ are $0$, it makes $P \rightarrow Q$ true but $Q$ is still false.

Link to original