Logic - 3
Semantic Consequence
Suppose $\Gamma$ is a finite set of formulas and $P$ is a formula. Then $P$ follows from $\Gamma$ (is a semantic consequence of $\Gamma$) if the following implication holds for every interpretation $I$:
\[\text{If } I(Q)=1\text{ for all } Q\in \Gamma,\text{then } I(P)=1\]This is denoted by:
\[\Gamma \models P\]Logical Puzzles
An island has two kinds of inhabitants, knights, who always tell the truth, and knaves, who always lie.
You go to the island and meet $A$ and $B$.
- $A$ says, “$B$ is a knight.”
- $B$ says, “The two of us are opposite types.”
What are $A$ and $B$?
We can prove this in a proof by cases or, as the two people have a binary type you can model this question as below.
$p$: “$A$ is a knight”; and $q$: “$B$ is a knight”
Options for $A$
- $p$ is true $p\Rightarrow q$
- $p$ is false $\neg p\Rightarrow \neg q$
Options for $B$
- $q$ is true $q\Rightarrow \neg p$
- $q$ is false $\neg q\Rightarrow \neg p$
Here we are summarising the two statements as logical propositions.
Truth Table
| $p$ | $q$ | $\neg p$ | $\neg q$ | $p\Rightarrow q$ | $\neg p\Rightarrow \neg q$ | $q\Rightarrow \neg p$ | $\neg q\Rightarrow \neg p$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
$\wedge$-ing together all the answers shows that the correct answer is $p=0,q=0$. This means that $A$ is a knave and $B$ is a knave.
Say that the implications in the truth table are numbered, $\{1,2,3,4\}$. We can then rewrite this table as the following statement:
\[\{1,2,3,4\}\models \neg p \wedge \neg q\]Examples
-
Show $\{(p_1\wedge p_2)\}\models (p_1\vee p_2)$.
$p_1$ $p_2$ $(p_1\wedge p_2)$ $(p_1\vee p_2)$ 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 The top line represents $(p_1\vee p_2)$ which we can see as $p_1=1, p_2=1$. As the proposition and the result hold true in this case then the statement is correct.
-
Show $\{p_1\}\not\models p_2$
$p_1$ $p_2$ 1 1 1 0 0 1 0 0 From this table we can see that the statement is correct as when $p_1=1, p_2=0$.
Logic and Proof Principles
Modus Ponens
Direct proof corresponds to the following semantic consequence:
\[\{P,(P\Rightarrow Q)\}\models Q\]Reducto ad Absurdum
Proof by contradiction corresponds to:
\[\{(\neg P\Rightarrow\bot)\}\models P\]where $\bot$ is a special proposition, which is false under ever interpretation. $\bot=a\wedge\neg a$.
Modus Tollens
Another look at proof by contradiction:
\[\{(P\Rightarrow Q),\neg Q\}\models\neg P\]Case Analysis
\[\{(P\Rightarrow Q),(R\Rightarrow Q),(P\vee R)\}\models Q\]Proof Theory
We have studies proof as carefully reasoned arguments to convince a sceptical listener that a given statement is true. These are called social proofs.
Proof theory is a branch of mathematical logic dealing with proofs as a mathematical objects:
- Strings of symbols.
- Rules for manipulation.
- Mathematics becomes a game played with strings of symbols.
- Can be read and interpreted by computers.
This is to say that in prof theory we make statements that computers are able to solve by putting them in a very structured language. This language can then be solved by Boolean logic.