Press the right key for the next slide (or swipe left)

also ...

Press the left key to go backwards (or swipe right)

Press n to toggle whether notes are shown (no equivalent if you don't have a keyboard)

Press m or double tap to see a menu of slides

\title {Logic I \\ Fast Lecture 07}
 
\maketitle
 

Logic I

Fast Lecture 07

\def \ititle {Logic I}
\def \isubtitle {Fast Lecture 07}
\begin{center}
{\Large
\textbf{\ititle}: \isubtitle
}
 
\iemail %
\end{center}
Readings refer to sections of the course textbook, \emph{Language, Proof and Logic}.
 
\section{Every Time I Go to the Dentist Someone Dies}
\emph{Reading:} §11.2
 
\section{Every Time I Go to the Dentist Someone Dies}
∀t (
\hspace{5mm} ( Time(t) ∧ ToDentist(a,t) )
\hspace{5mm} →
\hspace{5mm} ∃x ( Person(x) ∧ TimeOfDeath(x,t) )
)
 

Truth-functional completeness

 
\section{Truth-functional completeness}
\emph{Reading:} §7.4
 
\section{Truth-functional completeness}
‘A set of truth-functors is said to be \emph{expressively adequate} (or sometimes \emph{functionally complete}) iff, for every truth-function whatever, there is a formula containing only those truth-functors which express that truth-function, i.e. which has as its truth-table the truth-table specifying that function.’ (Bostock, \emph{Intermediate Logic} p. 45)
Illustration of the proof that $\{$¬, ∧, ∨$\}$ is truth-functionally complete:
\emph{Exercise} assuming $\{$¬,∨,∧$\}$ is truth-functionally complete, show that $\{$¬,∨$\}$ is.
7.25, 7.26, *7.28, 7.29
7.25, 7.26, *7.28, 7.29
 

Proofs about Proofs

 
\section{Proofs about Proofs}
 
\section{Proofs about Proofs}

let’s get meta

\begin{minipage}{\columnwidth}
\textbf{If A ⊢ B then ⊢ A→B}
Proof Given a proof for A ⊢ B …
… we can turn it into a proof for ⊢ A→B:
\end{minipage}
\textbf{If ⊢ A→B then A ⊢ B}
\begin{minipage}{\columnwidth}
\textbf{If A ⊢ B then A ⊢ ¬¬B}
Proof:
\end{minipage}
\textbf{If A ⊢ C then A ⊢ B→C}
\textbf{If A ⊢ B and A ⊢ ¬C then A ⊢ ¬(B→C)}
 

The Soundness Property and the Fubar Rules (fast)

 
\section{The Soundness Property and the Fubar Rules (fast)}
\emph{Reading:} §8.3
 
\section{The Soundness Property and the Fubar Rules (fast)}
7.32
7.32
 

Proof of the Soundness Theorem

 
\section{Proof of the Soundness Theorem}
\emph{Reading:} §8.3
 
\section{Proof of the Soundness Theorem}
\begin{minipage}{\columnwidth}
\textbf{Illustration of soundness proof: ∨Intro}
\end{minipage}
\emph{Useful Observation about any argument that ends with ∨Intro.} Suppose this argument is not valid, i.e. the premises are true and the conclusion false. Then Z must be false. So the argument from the premises to Z (line n) is not a valid argument. So there is a shorter proof which is not valid.
\emph{Stipulation}: when I say that \emph{a proof is not valid}, I mean that the last step of the proof is not a logical consequence of the premises (including premises of any open subproofs).
\begin{minipage}{\columnwidth}
\textbf{Illustration of soundness proof: ¬Intro}
\end{minipage}
\begin{minipage}{\columnwidth}
\textbf{How to prove soundness? Outline}
Step 1: show that each rule has this property:
\hspace{5mm} Where the last step in a proof involves that rule, if proof is not valid then there is a shorter proof which is not valid.
Step 2: Suppose (for a contradiction) that some Fitch proofs are not valid. Select one of the shortest invalid proofs. The last step must involve one of the Fitch rules. Whichever rule it involves, we know that there must be a shorter proof which is not valid. This contradicts the fact that the selected proof is a shortest invalid proof.
\end{minipage}
 

The Essence of the Completeness Theorem

 
\section{The Essence of the Completeness Theorem}
\emph{Reading:} §8.3
 
\section{The Essence of the Completeness Theorem}
 

Lemma for the Completeness Theorem

 
\section{Lemma for the Completeness Theorem}
\emph{Reading:} §8.3
 
\section{Lemma for the Completeness Theorem}
If for every sentence letter, P, either A ⊢ P or A ⊢ ¬P, then for every formula, X, either A ⊢ X or A ⊢ ¬X.
Proof
\textbf{Step a.} Suppose (for a contradiction) that there are formulae, X, such that A ⊬ X and A ⊬ ¬X. Take a shortest such formula, call it Y.
\textbf{Step b.} This formula, Y, must have one of the following forms: ¬P, P∨Q, P∧Q, P→Q, P↔Q, ⊥
\textbf{Step c.} We can show that whichever form X has, either A ⊢ Y and A ⊢ ¬Y.
Case 1: X is P→Q. Then since P and Q are shorter than X, either:
\hspace{5mm} (i) A ⊢ P and A ⊢ ¬Q
\hspace{5mm} or
\hspace{5mm} (ii) A ⊢ ¬P
\hspace{5mm} or
\hspace{5mm} (iii) A ⊢ Q
\hspace{5mm} If (i), A ⊢ ¬(P→Q), that is, A ⊢ ¬X.
\hspace{5mm} If (ii), A ⊢ P→Q, that is, A ⊢ ¬X.
\hspace{5mm} If (iii), A ⊢ P→Q, that is, A ⊢ ¬X.
\hspace{5mm} (Here we use the last two Proofs about Proofs, see earlier)
Case 2: X is ¬P.
\hspace{5mm} Then since P is shorter, A ⊢ P or A ⊢ ¬P.
\hspace{5mm} If A ⊢ P then A ⊢ ¬¬P so A ⊢ ¬X which would contradict our assumption. This is shown in the proofs about proofs above.
\hspace{5mm} If A ⊢ ¬P then A ⊢ X (because X is ¬P), which would contradict our assumption.
Case 3: …
\textbf{Step d.} The demonstration in Step c contradicts our assumption, so we can conclude that it is false. That is, either A ⊢ X and A ⊢ ¬X for every formula X.
 

Proof of the Completeness Theorem

 
\section{Proof of the Completeness Theorem}
\emph{Reading:} §8.3, §17.1, §17.2
 
\section{Proof of the Completeness Theorem}
 

Proof of Proposition 4 for the Completeness Theorem

 
\section{Proof of Proposition 4 for the Completeness Theorem}
\emph{Reading:} §15.1, §15.6
 
\section{Proof of Proposition 4 for the Completeness Theorem}
This is a proof of Proposition 4 in §17.2 of the textbook LPL.

Define a structure, h, so that:

h(P)=T when P is in A*

h(P)=F when ¬P is in A*

Claim: h(X)=T for every X such that A* ⊢ X

We want to provide this slightly stronger claim (because we're going to do induction)

Proposition: for every X, h(X)=T iff A* ⊢ X

Suppose not. Then take the shortest sentence, Y, such that the Proposition is false.

Either: h(Y)=T and A* ⊬ Y

Or: h(Y)=F and A* ⊢ Y

We know that Y cannot be a sentence letter or its negation from the assumption about how h() was defined

Also, Y has the form (A→B) or (A∧B) or ...

Let's consider a case.

h(Y)=T

So h(A∧B)=T

So h(A)=T and h(B)=T

But A and B are shorter than Y

So, by assumption, A* ⊢ A and A* ⊢ B

Then A* ⊢ A∧B

i.e A* ⊢ Y

This contradicts our assumption

A* ⊢ Y i.e. A* ⊢ A→B

h(Y)=F i.e. h(A→B)=F

So h(A)=T and h(B)=F

But A and B are shorter than Y.

So, by assumption, A* ⊢ A and A* ⊬ B

But for all X, A* ⊢ X or A* ⊢ ¬X

So A* ⊢ ¬B

So A* ⊢ ¬(A→B) (proofs about proofs)

So A* ⊢ ⊥ (proofs about proofs), which contradicts our assumption.

15.33--15.40 (second edition)
15.33, 15.37--15.39 (second edition)
 

More Records Than the KGB

 
\section{More Records Than the KGB}
\emph{Reading:} §14.1, §14.3
 
\section{More Records Than the KGB}
 
\section{The End Is Near}
\emph{Reading:} §14.3
 
\section{The End Is Near}
‘The’ can be a quantifier, e.g. ‘the square is broken’. How to formalise it?
The square is broken \\ ⫤⊨ There is exactly one square and it is broken
Recall that we can translate `There is exactly one square' as:
\hspace{5mm} ∃x ( Square(x) ∧ ∀y ( Square(y) → x=y ) )
So `There is exactly one square and it's broken':
\hspace{5mm} ∃x ( Sqr(x) ∧ ∀y ( Sqr(y) → x=y ) ∧ Broken(x) )

There is an end, and all ends are this end, and it is near.

∃x ( End(x) ∧ ∀y ( End(y) → x=y ) ∧ Near(x) )

14.26, 14.28
14.2
14.4, 14.5
14.10, 14.11
14.26, 14.28
13.51–2, 14.13 %proofs
For each of the following sentences of FOL, give a logically equivalent sentence of idiomatic English using the specified interpretation. Your English sentences should be as concise as possible.
Domain : people and actions
D(x) : x is desirable
V(x) : x is virtuous
A(x) : x is an action
H(x) : x is a person
P(x,y) : x performed y
i. ∀x (( D(x) → V(x) )
ii. ∀x ( (A(x)∧ D(x) ) → V(x) ) )
iii. ∃x ( A(x) ∧ ¬( D(x) → V(x) ) )
*iv. ∃x(H(x)∧∀y((A(y)∧P(x,y))→V(y)))
**v. ¬∃x (∃y (H(x) ∧ P(x,y) ∧ A(y) ∧ ¬V(y)) ∧ ¬∃z[P(x,z) ∧ A(z) ∧ V(z)))