FORMAL LOGIC

LOGIC LECTURE 1:

What we will be doing this term:

- Sentential logic: language, symbolization, and semantics
- 2 Sentential logic: derivations (Part 1)
- 3 Sentential logic: derivations (Part 2)
- 4 Sentential logic: metatheory (Part 1)
- 5 Sentential logic: metatheory (Part 2)
- 6 ReadingWeek
- 7 Predicate logic: language and symbolization
- 8 Predicate logic: derivations (Part 1)
- 9 Predicate logic: derivations (Part 2)
- 10 Predicate logic: semantics and metatheory
- 11 Review

Object language and metalanguage

- Object language- a language that is treated an OBJECT of study
- Metalanguage- a language that is USED to study another language
- Sentential Logic and Predicate Logic are objective language- our metalanguage is
English
Disjunction: use and mention
- Quotation marks allows us to talk about an expression rather than use it to refer to its
meaning e.g John has four letters vs John has four letters.
- A metavariable is a symbol in the metalanguage which is used to refer generically to
expressions of the object language.
- We use boldface letters for metavariables: P, Q, R, ... range over expressions of SL
and PL.

The symbols of Sentential Logic:

- Sentence letters= A,B,C,D,E
Sentential connectives= (logical symbols)
- one-place (unary): ~
- two-place (binary): & , V, ⊃, ≡
- Parenthesis ( , )

Formulation rules:
 - (Basic rule) Sentence letters of SL are sentences of SL.
- (~-rule) If P is a sentence of SL, then ~P is a sentence of SL.- negation rule does not
require parentheses
- (& -rule) If P and Q are sentences of SL, then (P & Q) is a sentence
- of SL.
- (V -rule) If P and Q are sentences of SL, then (P V Q) is a sentence of
- SL.
- (⊃-rule) If P and Q are sentences of SL, then (P ⊃ Q) is a sentence of
- SL.
- (≡-rule) If P and Q are sentences of SL, then (P ≡ Q) is a sentence of
- SL.
- Nothing else is a sentence of SL.
Formulation rules- how to use them:
- By the Basic rule, sentence letters (i.e. A, B, C, D, E ...) are sentences of SL by
default. They are also called atomic sentences.
- More complex sentences of SL are constructed using the other Rules. They are called
compound sentences.

- First one- A is
sentence and B is a sentence- get the OR rule- procedures that allow you to form
more and more compound sentences in tree like manner. Just breaking down
compound sentences into single letters.
More examples:
Main connective is the connective that has been introduced at the last stage of the
construction tree- the connective that’s introduced last

Main connective and immediate subformulas

- (Basic rule) Sentence letters A, B, C,... are sentences of SL. They have no main
- connective and they have no immediate subformulas.
- (~-rule) If P is a letter of SL, then ~P is a sentence of SL. Its main connective
- is ~ and its only immediate subformula is P.
- (& -rule) If P and Q are sentences of SL, then (P & Q) is a sentence of SL. Its
- main connective is & and its immediate subformulas are P and Q.
- (V -rule) If P and Q are sentences of SL, then (P V Q) is a sentence of SL. Its
- main connenctive is V and its immediate subformulas are P and Q.
- (⊃-rule) If P and Q are sentences of SL, then (P ⊃ Q) is a sentence of SL. Its
- main connenctive is ⊃ and its immediate subformulas are P and Q.
- ((≡-rule) If P and Q are sentences of SL, then (P (≡ Q) is a sentence of SL.

Translations

- Translation comes with translation key

- A translation key provides a translation for the sentence letters, i.e. the atomic
sentences of SL. E.g A: Albert received a scholarship B: Bertrand impressed his
coach
Translating negations:
- Example. Albert did not receive a scholarship.
- This can be rephrased as: It is not the case that Albert received a scholarship.
- A: Albert received a scholarship. ~A
- Example. Bertrand failed to impress his coach.
- It is not the case that Bertrand impressed his coach.
- B: Bertrand impressed his coach. ~ B
Translating conjunctions:
- Example: Albert received a scholarship and Bertrand impressed his coach.
- (A & B) (with the same key as above)
Translating disjunctions:
- Example. Juventus will be eliminated or Napoli will be eliminated.
- J: Juventus will be eliminated.
- N: Napoli will be eliminated.
- (J v N)
- Example. Annie, Bonnie, or Connie will be late.
- A: Annie will be late.
- B: Bonnie will be late.
- C: Connie will be late.
- ((A v B) v C) correct
- (A v (B v C)) correct
- (A v B v C) incorrect
Translating material conditionals:
- Example. If everything goes well, Tony will graduate next semester.
- E: everything goes well.
 - G: Tony will graduate next semester.
- (E ⊃ G)
- Example. If Annie and Bonnie show up, Connie will show up too.
- A: Annie will show up.
- B: Bonnie will show up.
- C: Connie will show up.
- ((A & B) ⊃ C) correct
- (A & (B ⊃ C)) incorrect
- (A & B ⊃ C) incorrect
Material conditionals continued:
- Example. Amelia wins the final provided that she is the fastest runner.
- W: Amelia wins the final.
- F: Amelia is the fastest runner.
- (F ⊃ W)
- Amelia wins the final if she is the fastest runner.
- Example. Amelia wins the final only if she is the fastest runner.
- (W ⊃ F)
- If Amelia wins the final then she is the fastest runner.

Semantics

- Semantics= formal study of meaning

- Logic is formal.
- Validity turns on the form of an argument, not its content.
- SL attempts to express/capture the logical form of a significant portion of natural
language.
- Logical form: the structure of a sentence. This is what matters for correct deductive
reasoning and, more generally, for the analysis of logical relations (entailment,
consistency, etc.).
- Building a language that gives us the tools to represent the features of the
sentences from natural language that explain their logical properties/behaviour-
for this to succeed there are two principle that need to be upheld:
Two guiding principles:
1. If the SL-translation of an argument is valid, then the argument itself is valid.
2. If the SL-translation of an argument is invalid, then argument itself
is invalid- if an argument is valid, then its SL- translations is valid.

When are sentences of SL true?- connection between truths and semantics

- Recall: we construct every sentence of SL from its atomic components (sentence
letters) in accordance with the definition of sentence in SL (slide 11) .
- The key property of the semantics is compositionality.
- Compositionality- The “meaning” of a sentence of SL (i.e. its truth value) is
completely determined by the “meanings” its atomic components (i.e. their truth
values) and the “meaning” of the connectives used to build the sentence (i.e. the truth
tables).

Truth tables for the sentential connectives :

Truth value assignment:

- A truth-value assignment is a function from the sentence letters of SL to the truth
values T and F.

Displaying the calculation:

Another example:

Semantic notions

Logical truth, logical falsehood, logical

indeterminacy:
- Logical truth- A sentence is logically true
(tautology) if it is impossible for it to be false.
- Logical falsehood- A sentence is logically false
(contradiction) iff it is impossible for it to be true.
- Logical indeterminate- A sentence is logically
indeterminate iff it is not a logical truth and it is not
a logical falsehood, i.e. it is possible for it to be false
and it is possible for it to be true
Notions made precise:
- Truth functional truth- A sentence P of SL is truth-
functionally true iff it is impossible for P to be false,
i.e, P is true on every truth-value assignment.
- Truth-functional falsehood- A sentence P of SL is
truth-functionally false iff is impossible for P to be
true, i.e. P is false on every truth-value assignment.
- Truth-functional indeterminacy- A sentence P of SL is truth-functionally
indeterminate iff P could be true and P could be false, i.e. there is a truth-value
assignment on which P is true and there is a truth-value assignment on which P is
false.
Now want to define:
- truth-functional equivalence
- truth-functional consistency (and inconsistency);
- truth-functional entailment and validity.

Notation: sets of sentences

- Sets are collections of objects that have members or elements.
- We can specify a finite set by listing its members, separated by commas, within curly
brackets.
- We call empty set the set that contains no members,
and denote it by Ø
- We will use variable such as Γ (gamma) and Δ (delta),
with or without a subscript, to range over sets of sentences of SL

Truth-function equivalence:
- Logical equivalence=informal notion- Two sentences are logically equivalent iff it is
impossible for one to be true while the other is false
- Truth-functional equivalence- Two sentences of SL are truth-functionally equivalent
if and only if they have the same truth-value on every assignment, i.e. they have the
same truth table.

Truth-functional consistency:
- Logical consistency- A set Γ of sentences is consistent iff it is possible for all the
members of Γ to be true together.
- Truth-functional consistency- A set Γ of sentences of SL is truth-functionally
consistent iff there is an assignment on which each member of Γ is true.
- Check if there’s a row on truth table where every set is true
Truth-functional entailment:
- A set Γ of sentences of SL truth-functionally entails a sentence P of SL iff there is no
truth-value assignment on which all the members of Γ are true and P is false
Notation for truth-functional entailment:

- An invalidating row would be- T, T, F (false being the conclu) e.g of when
gamma does not truth functionally entail (C)

Validity:
- Validity- A deductive argument is valid iff it is impossible for the premises to be true
while the conclusion is false.
- Truth- functional validity- A deductive argument in SL is truth-functionally valid iff
the set of premises truth-functionally entails the conclusion.
 - A deductive argument in SL is truth-functionally valid iff the set of premises truth-
functionally entails the conclusion, i.e. there is no assignment on which all the
premises are true and the conclusion is false.
- Invalidity- A deductive argument is invalid iff it is possible for the premises to be true
while the conclusion is false.
- Truth- functional invalidity- A deductive argument in SL is truth-fucntionally invalid
iff the set of premises does not truth-functionally entail the conclusion, i.e. there is an
assignment on which all the premises are true and the conclusion is false.

Interesting facts about entailment and validity:

- Correcponding conditional- Suppose that an argument has premises P1…. Pn and
conclusion C.
- Then the argument’s corresponding conditional is
- Theorem- An argument with a finite number of
premises is truth-functionally valid iff its corresponding conditional is a truth-
functional truth. If we want to check if argument is truth functionally valid we
might check instead whether corresponding conditional is a truth functional
truth.
E.g
 LOGIC LECTURE 2:- DERIVATIONS IN SENTENTIAL LOGIC

The basic semantic notion of entailment ⊨ (logical consequence)

- how we define every other notion we have introduced in terms of entailment

- First row- inconsistency= there is a contradiction

- Second- falsity- if its truth-functionally entails a contradiction-. From left to
right- if we assume p is truth-functionally false there is no row in which P is true
and the contradiction is false therefore the truth functional entailment holds.
- A sentence P is truth-functionally true if and only if the empty set truth
functionally entails P.
- Two sentences P and Q are truth-functionally equivalent if and only if the empty
set truth functionally entails that they are equivalent.

The basic proof-theoretic notion: ⊢ (provability, derivability)

- SINGLE TURNSTILE IS SYMBOL FOR PROOF
- The notion of derivations aims to capture our informal notion of proof, i.e gap free,
correct reasoning from a set of assumptions to a conclusion.
Provability (derivability, deducibility)
- Let Γ be a set of sentences and P any sentence.
- Γ ⊢ P means that P is provable/derivable/deducible from Γ .
Entailment and provability:
- We have some assumptions. Which conclusions follow from them?
- Answer 1 (⊨): Any conclusion that is entailed by the assumptions.
- Answer 2 (⊢): Any conclusion we can arrive at by reasoning correctly from these
assumptions- proofs

N.B DERIVATION= NATURAL DEDUCTION

Proof: basic idea

- A proof (derivation) is a sequence of sentences such that each step is either an
assumption or is obtained by previous sentences using an inference rule.
 AUXILIARY NOTIONS EXAMPLE:
Auxiliary notions:
- Scope line- verticle lines- first one
on left is always present
- Primary assumption- the assumptions
that are listed at beginning- correspond
to sentences your given- line
underneath to show the primary
assumption are done.
- Auxiliary assumption- assumptions
you make later- need to be discharged
or given up before reaching conclusion
- Subderivation- a derivation within a
derivation e.g from 3 to 6 is a
subderivation
- Accessibility- essential for the rule
of Reiteration- e.g is B accessible at line 6- YES because not B lies either above or to
the left of the scope of line 6.
Is A available at lime 7- NO because the scope line at line 7 lies to left of the scope
line of line 3.
Something is accessible if it is in same scope line (above it) or if it is to the left of
the scope line. If something is to the right of it its not accessible because whatever
is to the right is something that can only be attained from assumptions that are
no longer in place.
 Reiteration

- Only rule that has nothing to do with the connectives- special rule
- If we have established P we can just re assert P
- Reiteration can only be applied if P is accessible at line M+N- if you have
established P under some assumptions that are no longer in place- as long as we
are operating below or to right of P we can reiterate.

AND

INTRODUCTION:
Rules for &: introduction:
Example:
- Mary will graduate in 2021 (M)
- Bonnie will graduate in 2021 (B)
- Conclu- Mary will graduate in 2021 AND Bonnie will graduate in 2021
 - M and B both need to be accessible at n+m otherwise wouldn’t be able to
conclude M&B

ELIMINATION:
Example:
- Conclu- Mary will graduate in 2021 AND Bonnie will graduate in 2021
- Mary will graduate in 2021
- Bonnie will graduate in 2021

- with elimination can only conclude either P or Q

Precise formulation:

Examples:
 - in first brackets are primary assumptions
- put line underneath assumptions!!!
Negation

Introduction
- Assume that P. If the assumption leads to contradiction, then it must be false. So, you
may conclude ~P

Elimination
- Assume that~ P. If the assumption leads to contradiction, then it must be false. So you
may conclude that P.

Precise formulation:
 - Dash at last step
Examples of negation:

- How to prove without assumption given- assumption will have to be given up at

end of proof
- Assume who’s negation we want to prove- without negation

Conditional

Rules for conditional elimination:

E.g
- If the murder weapon was a knife, then the butcher was the murderer
- The murder weapon was a knife (K)
- The butcher was the murderer (B)

Rules for conditional introduction:

- Let’s provisionally assume that P. If that
assumption leads to
- Q, then we may conclude that P⊃Q.
Precise formulation:

- - Note- you cannot put Q before

P in an elimination!! Have to assume P first.

Examples:

OR

Rules for V: introduction

Example:
- Mary will graduate in 2021 (M)
- ...
 - Whatever you like is good here (W)
- Mary will graduate in 2021 or whatever you like is good here

Rules for V: elimination

Example:
- We have established that either A (Annie will graduate in 2021) or B (Bobbie will
graduate in 2021). If each assumption independently leads to C (Connie will be
looking fora roommate in 2021). Then we may conclude C directly from A or B.

- Citing on last step is important here- think know this already?

Precise formulation:

Examples: (disjunctive syllogism)

 Biconditional

Rules for ≡: introduction

- Idea. If assuming P leads to Q and assuming Q leads to P, then P ≡ Q.

Rules for ≡: elimination

- Idea. Suppose that P≡ Q. Then, if we establish P, we may conclude Q.
 - (Analogously, if we establish Q, we may conclude P.)

Precise form:

Examples:
- Assume left hand side to prove right
- Then assume right hand side to prove left

Logical notions

Derivation (proof)
- A derivation is a sequence of sentences of SL such that each sentence in the sequence
is either an assumption or is obtained by previous sentences using introduction or
elimination rules or reiteration.

(Deductive) inconsistency
- A set of sentences Γ is (deductively) inconsistent if and only if, for some sentence P, Γ
⊢P& ~P

(Deductive) validity
- An argument whose premises form the set Γ and whose conclusion is P is
(deductively) valid if and only if Γ ⊢ P.

Theorem
- A sentence P of SL is a theorem if and only if ∅ ⊢ P
 (Deductive) Equivalence
- Two sentences of SL, P and Q, are (deductively) equivalent if and only if ∅ ⊢ P ≡ Q

Toolbox
Classical logic:

Ex falso:
Few tricks about ⊃:

Flip the
conditional and
add or remove
negation.
 LOGIC LECTURE 3: Metatheory

Introduction:
Study the system from the outside- called metatheory- branch of logics
that’s takes proofs systems as objects of study and find interesting features
of the system.
How are ⊨ (entailment) and ⊢ (provability) related?

We have two basic notions:

How are they related?

- Whenever we can prove P from gamma and P is a truth functional

consequence of the members of gamma- this means relation of
probability is sound.
- Next question is if we have truth functional entailment do we also
have provability- when conclusion is truth functionally entailed from
some premises can we derive the conclusion of the premises- if yes
then the proof system is said to be complete.
- Summary- two questions 1) Relation of probability is sound? 2)
Relation of probability is complete?

The big results:

- Gamma might be an infinite set- meaning provability might be from

a finite subset of gamma- namely the members of gamma that you
use as your assumptions in your proof

Soundness:
 - Important as it gives us a way to show P is not provable from
gamma- if you can prove P is not truth functionally entailed by
gamma the logical equivalent formulation tells you P is not provable
from gamma.
- If you can show there is a failure of truth functional entailment then
you know there is no proof.
Completeness:

- Useful because if your struggling with proof- if there is truth

functional entailment then there is a proof- can know proof exists
- If something is not provable from some assumptions it does not entail
these assumptions.
- The logically equivalent formula is not very useful- top one more
useful as allows you to decide whether something is provable.

How to use the Soundness and the Completeness theorems:

LOOK AT PP FOR EXAMPLES
Completeness example
 - You build a truth table and look for a row where there is a true
premise and a false conclusion (look at main connective)- if no such
row then we have truth functional entailment.
- Once determined there is truth functional entailment question to ask
is can we prove conclusion from premise- YES- completeness
theorem tells us that- If P truth functionally follows from gamma
then P can be proved from gamma.
- Can conclude because there is truth functional entailment there is
also provability- from completeness theorem.
- Can then use a derivation- to prove it.
- Completeness theorem gives us very useful information- tells us there
must be a derivation so we just need to keep trying until we find one.
- COMPLETENESS= TRUTH TABLE- IF NO INVALIDATING
ROW CAN PROVE IT- CAN USE DERIVATION TO PROVE
- If there is an invalidating row there is no truth-functional entailment
- If no truth-functional entailment can appeal to the logically
equivalent soundness theorem to go from lack of truth functional
entailment to lack of truth functional provability. Means we cannot
prove it- there is no derivation of whatever you can prove from the
assumptions therefore no point spending time trying to find a derivation-
very useful info.
Soundness example:
- If can prove the derivation- does that mean its entailed by those
assumptions- answer is yes- soundness theorem tells us if we can
prove a claim from some assumptions, the claim also truth
functionally entails those assumptions.
- Can build truth table to verify the claim and show there is no
invalidating row.
- SOUNDNESS= USE DERIVATION TO SHOW CAN PROVE IT-
THIS MEANS ITS ENTAILED- CAN USE TRUTH TABLE TO
SHOW THIS

Summary:
The Soundness and Completeness theorems help us answer this
question:
- Given a set of sentences Γ and a sentence P, can we derive P from Γ?
To answer the question, you can use the Soundness and Completeness
theorems as follows:
Use the truth-table method to check if Γ ⊨ P.
- If Γ ⊨ P, then there is a derivation: Γ ⊢ P (by the Completeness theorem).
- If Γ P (no truth functional entailment), then there is no derivation: Γ
(no proof) P (by the Soundness theorem).
 Mathematical induction
- Important technique proving the soundness theorem
The principle of mathematical induction:
- The proof of Soundness makes essential use of a key principle in
mathematics: the principle of mathematical induction.
- The proof is a proof by induction.

Mathematical induction: motivation:

- Suppose I want to check whether a universal statement is true:

- That V means everything

- If the domain of quantification is finite, I can establish this by checking
all objects in the domain. - verifying all of them are F
- What if the domain is infinite? How do we show in an infinite domain
that everything is F?
- Mathematical induction helps with this question.

Mathematical induction: the idea:

 - When proving a universal statement using mathematical induction we need to carry
out 2 tasks 1) prove the base case 2) prove the inductive case

First formulation:
Weak induction:
Suppose you can show that
1) Base case: F is true of 0;
2) Inductive Case:
If F is true of n, then F is true of n+1
Then you can assert

(showing everything is F)
- Note: step 2 is a conditional. We show that IF F is true of n, THEN it is
also true of n+1
- Note- not weak- v strong principle

Second formulation:
Strong induction:
Suppose you can show that
1) Base Case: F is true of 0;
2) Inductive Case;
If F is true of m for every m<n, then F is true of n- assuming that every
number smaller than the mystery number is F so we show that n is F.
Then you can assert

Note: step 2 is a conditional. We show that IF F is true of m for every m<n,

then F is also true of n.

Mathematical induction: variant

- If want to start induction not at 0 but at a later point- you can do that
and everything is the same.
- These principles can also be used to show that every natural number from
k onwards has a certain feature:
 - Every natural number from K has a certain feature.
- Essentially, we replace 0 with k and consider only numbers from K
onwards.

Weak induction:
Suppose you can show that:
1) Base Case: F is true of K;
2) Inductive case:
If F is true of n with k<n, then F is true of n+1
Then you can assert:

- If F is true of anything bigger or equal to K then the next number is also F- so

anything bigger or equal to K is F (every natural number)

Strong induction:
Suppose you can show that:
1) Base Case: F is true of K;
2) Inductive case:
If F is true of m with k<m, then F is true of n
Then you can assert:

- If want to start from K- assuming that our starting point is K and we assume
that everything before N is F and want to show F is also true of N.
- So every number bigger or equal to K is F.

Proofs by induction- examples on PP

- Base case- need to show F is true of 0- need to verify that 0 is less
than 1 which is true- F applies to 0
- Inductive case- assume that F is true of n, that is n+1 is greater than
0. Need to show F is also true of n+1. By inductive hypothesis n+1 is
greater than 0. But n+1 is less than (n+1)+1- by adding one we get
something bigger.

Example 2:
- Trying to prove- if we take a number from 1 onwards and double it
we get something that’s different from 0
- NOTE- this starts from something other than 0- so might use variant-
one based on arbitrary number. The starting point in this case is 1
- Show base case is strong first- F is true of 1, that is, 2x1 (not zero)
- Proving inductive step:

Simplifying

- Last step before proving soundness theorem

 Truth-functional completeness:

- Only using not and and- they are both truth functionally complete-
using these two connective can express any truth table
 - If want to express disjunction can say not negation of the
conjunction- so can change an or to not (not P and not Q)
- Conditional- changes to not (P and not Q)

Simplifying the proof system:

- Without loss of generality, we can avoid the rule of reiteration.
- To get rid of reiteration of P for example. Do P&P and then next line
take the P- conjunction elimination- without using reiteration.

We can “recover” the rules for v, ⊃, and ≡ using those for ˜ and &.

Upshot:
- Without loss of generality, we can work in a system in which every step
in a derivation is either an assumption or is obtained by one of the
following four rules:

LOGIC LECTURE 4: Metatheory (Part 2)

- N.B mathematical induction is a technique needed to prove the
theorems

Soundness theorem:
 - Second formulation- Allows us to prove something is not provable
from a certain claim- can look at truth tables and see if a proof does
not exist thanks to the theorem
- Reason they are equivalent 1) formulation is like A ⊃B 2
formulation) is ˜B ⊃ ˜A- these are equivalent

Preliminary notions

Initial segments of proofs are proofs:

- We can see any initial segment of a proof as another (shorter) proof.
- At each step of a proof, we have proved something from something else.
- More specifically, we have proved the last sentence of that proof segment
from the open assumptions at that point.

Examples:

- Cut the proof off after line 5

- In first 5 steps we have proved not B from A ⊃B, not B, A.
- Would then write it as:
- A⊃B
- ˜B
- A
- B
- ˜B
 - Line 4 and 5 is the justification
- What we have seen is that a segmnent of a proof e.g the segment 1-5
is itself a proof.

- Cut proof at line 6- what has been proved?- proved not A. Open
assumptions are A then B and not B.- not including A because A has
been discharged- been given up at line 6- not longer active

Notation:
- Take a proof and let n be a line in the proof.
Let us write

- to indicate what has been proved at line n.

- So Γn is the set of open assumptions at line n and Pn is the sentence at
line n.
 - Just showing each step of a proof can be seen as proof itself

Proof of soundness

Induction (Cont.)

- For every natural number greater or equal to 1- that’s what

beginning bit says
 - if we assume soundness theorem is true for every proof of length less
than n then also must be true for every proof of length n- will be
relying on strong induction.
Induction:

- base case- every proof of length one is such that the assumptions of
that proof truth functionally entail the conclusion.
- Inductive case- assume that for every proof of length Kappa where
Kappa is strictly less than n then the assumptions of the proof truth
functionally entail the conclusion.
- Then we show on the basis on that assumption that that must also be
true for the next length- n. Assumptions at length n truth functionally
entail its conclusion.
- Conclusion we can derive from base and inductive case- for any
proof of P from gamma that has length X or axis greater or equal to
1 then gamma truth functionally entails P.
Notation:

- Conditional with line underneath means is a member of- also means

is a subset or is equal to?
- In example- every member of gamma 1 is a member of gamma 2 so
can use the symbol for is a member of.
- Can also say gamma 1 is a subset of gamma 1- because obviously
every member of gamma 1 is also a member of gamma 1.
- Also will use the plus symbol to show we have a superset

Notation (cont.)
 - Notation for union is indicated by a cap (U)
- Note C is not repeated- set ignores repetition- repeating an element of
the set does not change the set- no need to repeat.
- Use fork to represent membership.
- Line through fork if its not a member

Facts:

- Fact 1- is P is a member of gamma then gamma truth functionally

entails P. (If P is one of your assumptions then your assumptions
entail P.)
 - Fact 2- If gamma truth functionally entails P then any superset of
gamma truth functionally entails P. (If your assumptions entail a
sentence then adding assumptions will not change it) By adding
assumptions P is still truth functionally entailed by our assumptions.
- Fact 3- if I have assumptions gamma which truth functionally entail
P and they also truth functionally entail Q then my assumptions
truth functionally entails P&Q. (if your assumptions entail P and
entail Q then obviously they entail P&Q).
- Fact 4- if a gamma truth functionally entails a conjunction then
gamma truth functionally entails each conjunct. E.g if it entails P&Q
then it entails P.
- Fact 5- if gamma together with additional assumption P entails Q,
and gamma together with that assumption also truth functionally
entails not Q- then gamma must entail not P.
- Fact 6- if gamma truth functionally entails not not P then gamma
truth functionally entails P.

Proof: base case

- Soundness theorem holds for proofs of length 1

Proof: induction step

Proof: induction step (assumption)

Proof: induction step (&-introduction)

- Because Q is accessible at line n and J is accessible at line n, our

assumptions in-between have not decreased if anything has
expanded.
- If gamma n proves a conjunction then gamma n truth functionally
entails that conjunction.
- If the step n is obtained by &introduction then the soundness
theorem is satisfied.

Proof: induction step (&-elimination)

Proof: induction step (~ introduction)

Proof: induction step (~ elimination)

Proof: induction step completed

- For any proof of length greater of equal to 1 then soundness theorem
holds.

LOGIC LECTURE 5- completeness theorem

- Truth functional entailment implies pro. M l,vability

 Notation and useful facts

Useful notation:

- Fact 7- if gamma proves Q and not Q then gamma will also prove A
and not A and B and not B and so on.
- Fact 8- biconditional- proof of this claim- gamma cannot be truth
functionally consistent-left to right- assuming gamma entails a
contradiction and proving its truth-functionally inconsistent- if it
were a contradiction would have to be true on a line of the truth table
and that would be impossible- so we conclude that gamma is not
 truth-functionally consistent hence it is truth functionally
inconsistent. From right to left- assuming gamma is truth
functionally inconsistence and proving gamma entails a
contradiction- suppose gamma did not truth functionally entail a
contradiction would have to be row in truth table that invalidates this
claim, an invalidating row where all members of set are true and
contradiction is false. If gamma doesn’t truth functionally entail P
that means there is a row in truth table where all members of gamma
are true therefore gamma is not truth functionally inconsistent
against the assumption.
- ASSUME GAMMA IS TRUTH FUNCTIONALLY
INCONSISTENT THEN ASSUMING GAMMA DOES NOT
TRUTH FUNCTIONALLY ENTAIL A CONTRADICTION AND
THIS LEADS TO CONTRADICTION THUS GAMMA TRUTH
FUNCTIONALLY ENTAILS A CONTRADICTION ON THE
ASSUMPTION THAT GAMMA IS TRUTH FUNCTIONALLY
CONSISTENT.
-
- would have to be line in truth table where gamma is true and
contradiction is false- an invalidating row.
- You start from your assumption, assume negation of what you want
to show, there’s a contradiction and then assume what you want to
show- that gamma truth functionally entails a contradiction.
- Fact 9- if gamma has a superset gamma plus and gamma plus does
not truth functionally entail a contradiction then gamma also does
not truth functionally entail a contradiction.
- If a superset is truth functionally consistent then a subset is truth
functionally consistent- suppose gamma is A,B and C and gamma
plus is A,B,C,D- if gamma plus is consistent- theres a row in truth
table where A,B,C and D is true
- Fact 8 useful for fact 9- if superset has row in truth table where all
members are true then subset will also have a row in truth table
where all members are true.

- If A if and only if B then not A if and only if not B- they are logically
equivalent-fact 8- Gamma does not truth- functionally entail a
contradiction if and only if gamma is truth functionally consistent- 9
says if have set of assumption sand you expand it and if the expanded
set does not truth functionally entail a contradiction, that is gamma
plus is truth functionally consistent then gamma does not entail a
contradiction, it is truth functionally consistent.
 - Thanks to fact 8 able to replace the claim about not truth
functionally entailing a contradiction with the claim about
consistency.

- Gamma is a,b and c and gamma plus is a,b,c and d- if gamma plus is
consistent- row in truth table where a,b,c,d are true and also going to
be row where a,b and c is true

Proving Completeness

The proof strategy:

- Step 1 and step 3 are simple

- The real work is in proving step 2.
- Need intermediary steps- first show if gamma truth functionally
entails p then gamma union the negation of P truth functionally
entails a contradiction.

STEP 1:

- Assume antecedent and derive consequent

- If gamma truth functionally entails P there is no truth-value assignement where
every member of gamma is truth and P is false.
- Appealing to fact 8 in the process.
Step 3

- Assuming gamma union not P proves a contradiction.

- Gamma proves P on the assumption that gamma union not P proves a
contradiction.

Step 2
 - Easier to prove the logically equivalent formulation
- Any set of sentences is the triangle symbol- if a set of sentences do not prove a
contradiction then they do not truth functionally entail a contradiction.

Key Lemma

- If delta does not prove a contradiction then delta does not truth functionally
entail a contradiction- the way we will prove it= using intermediary steps
- Fact 9 told us that if we have a set and superset- if superset does not truth
functionally entail a contradiction then initial step doesn’t either.
- First thing to do is build delta plus.

Maximally consistent sets of sentences: making delta plus

 - To make delta plus- the expansion consists in making delta maximally consistent
- Number 2= If P does not belong to the set then adding it to the set allows me to
prove a contradiction
- In order words a set of sentences is maximally consistent if its consistent (doesn’t
prove a contradiction) and is maximal in the sense that if I add anything else to
the set I will be able to prove a contradiction.

Maximal Consistency Lemma:

- Here is the first move in the proof of the Key Lemma.

- Take delta- add sentences while keeping it consistent and stop when you can no
longer add something before delta becomes inconsistent.
- Way in which we prove this is by laying out a procedure to expand delta.
- If by adding a sentence I don’t prove a contradiction then I add that sentence
otherwise we leave the set as is and move on to the next sentence.

- Consistent- cannot prove a contradiction from any finite subset of delta plus
- Maximal- something is not in the set that adding it to the set will prove a
contradiction
Maximal consistency and truth-functional consistency:
- Showing maximal consistency implies truth-functional consistency.

- If delta plus is maximally consistent then delta plus does not entail a
contradiction- how this can be shown- assume antecedent and assume
consequent- need to show delta plus does not truth functionally entail a
contradiction.
- Can show that delta plus is truth functionally consistent
 - Conclusion is that delta plus does not truth functionally entail a contradiction-
why?- assumed that delta plus is maximally consistent then built an assignment,
A that makes true all and only the members of delta true. If there is an
assignment where all members of delta plus are true then delta plus is truth
functionally consistent then by fact 8 this means delta plus does not truth
functionally entail a contradiction.

Putting our results together

- If delta does not prove a contradiction then delta does not truth functionally
entail a contradiction
Process of key lemma:
- 1) start with your assumption
- 2) built a maximally consistent set of sentences, delta plus
- 3) through the consistency lemma we concluded that if delta plus is maximally
consistent we can build an assignment A where all its members are true which
means that delta plus does not truth functionally entail a contradiction
- 4) By fact 9 can conclude that delta does not truth functionally entail a
contradiction.

Completeness theorem
Proof strategy:
Starting from assumption that gamma truth functionally entails P
Step 1- by adding not p to gamma the result is. A set that truth functionally entails a
contradiction
Step 2- Then shown key lemma- if delta is consistent then delta does not truth functionally
entail a contradiction so that any set that does truth functionally entail a contradiction can
prove a contradiction.

LOGIC LECTURE 6- Predicate Logic: Language and

Symbolization

The Limits of SL

Why is SL inadequate?

- - Limited language- first

example- premises do not truth functionally entail the conclusion- through
soundness theorem can say doesn’t prove- argument that’s valid but logical
system doesn’t do justice to this validity.
 - Example 2- premise does not truth functionally entail the conclusion thus doesn’t
prove conclusion-

The language of PL

The symbols:
Individual terms (with or without numerical subscripts)
- Individual constants: a, b, c, ...
- Individual variables: x, y, z, w, ...
- Subscripts is like a1, a2, a3…

Predicates with numerical superscripts (with or without numerical subscripts)

- One-place: A1, B1, ... P1, Q1, ...
- Two-place: A2, B2, ..., P2, Q2, ...
- ….
- n-place: An, Bn, ..., Pn, Qn, ...
- superscripts are mandatory and subscripts are optional
- A special two-place relation, identity: =.
- Quantifiers: Universal: ∀ (means for all) Existential: ∃ (means exists)
- Sentential connectives: ~, &, v, ⊃, ≡
- Parentheses ( , )
- No other symbol is part of PL.

The meaning of the new logical symbols

- Predicate logic is also known as predicate calculus or first-order logic

- Anyone is also backwards E

How to use PL symbols
Terms:
- Individual constants are names for objects (i.e. people, things, etc.),
- analogous to proper names in English.
- Individual variables function (to some extent) like pronouns in English: ‘he’, ‘she’,
‘them’, it’.
Predicates (one place):
- Predicates translate English predicates, i.e., expressions that indicate properties of
individuals.
- One-place predicates translate expressions that indicate properties of one individual.
- They are called one-place because all they need to
yield a statement is one expression referring to
one individual, e.g. an individual constant. - need
one term to produce a statement

Predicates (two-place):
- Two-place predicates translate expressions that indicate relations between two
individuals, e.g., ‘loves’, ‘likes’, ‘is taller than’, ‘plays with’ ...
- Requires two expressions on either side

Well-formed formulas in PL

The grammar of PL: defining well-formed formulas (wffs)

 - Parenthesis are not allowed with negations- no parentheses are used for second
one
- Last one is free variables minus v.

Examples of wffs- basic rule:atomic formulas

Using the formation rules: construction trees

- By the Basic rule, an n-place predicate followed by n terms is a wff.
- More complex wffs are constructed using the other rules.
 - Blue indicates x is a free variable
- No longer free when quantifier is added
- Can you have two existential qualifiers- answer is YES

Some terminology

Sentence
- a sentence is a wff without free variables

- Second ones are wff that are not free variables

Main connective and immediate sub

formulas
- Familiar..
 - use tree to see main connective
- immediate sub formula is one next after main connective

Scope
- The scope of a quantifier is (are) its immediate subformula(s).

- Third example- question is what is the scope of the y quantifier- would be B2xy
as that’s the immediate subformula after. Scope for first quantifier would be Ey
- Do tree to work it out- tree makes notion v clear

Binding
- A quantifier (∃v) or (∀v) binds every free occurrence of v within its immediate sub
formulas. The variable v is also said to be a bound variable.
 - First one- vx binds all variables marked as red

Universe of discourse (domain of quantification)

- Quantifiers can be implicitly restricted to the individuals belonging to certain
Universe of Discourse (UD)
- Examples of UDs: people, the natural numbers
- E.g if I invite people to party and at party I say is everyone here- I only mean
people I’ve invited not everyone in the world- the set of people ive invited is the
universe of discourse.

Practice

Everybody likes someone:

Symbolizing in PL: practice
In the following, let us eliminate the superscripts that declare the number of arguments of
each predicate. We give instead the following key:
 LOGIC LECTURE 7- Derivations in Predicate Logic
The derivation rules of PD include:
- all the rules of SD (now applied to sentences of PL- when main connective is &, V
etc. );
- rules for the quantifiers;
- rules for =;

Substitution: motivation
Every human is mortal
Socrates is human
Socrates is mortal
- We want to find a way of connecting the first premise with the second, so that the
conclusion “Socrates is mortal” is justified.
- That is, we want to instantiate the universal quantifier “every human” to the particular
case of Socrates.
- We introduced the notions of free and bound variables.

Substitution instances:
An easy rule: ∀- elimination

- Main connective has to be universal quantifier

∀- introduction- harder rule?

 - Two conditions have been met 1) A does not occur at any open
assumption at step 4 2) doesn’t occur in universally quantified
statement you want to prove.

Why the restrictions on ∀-I?

(i) A does not occur in any assumption that’s open at n+m

 (ii) A does not appear in (∀x)P.

∃- introduction- easy rule

∃-elimination
Why the restrictions on ∃- E?

(i) A does not occur in any assumption that is open at n+m+k+j

Provided that:
(ii) A does not appear in (∃x)P
 (iii) A does not appear in Q

LOGIC LECTURE 8- Derivations in Predicate Logic (Part 2)

Replacing constants

= Introduction
 - line 3- incorrect application of universal introduction- 2nd condition is that a does
not occur in the universal statement that we are deducing- would have had to say
y=y instead of a=y.

= Elimination
Identity is symmetric
Identity is transitive

Toolbox

Proof toolbox: a couple of tricks about ∀ and ∃

 LOGIC LECTURE 9- Predicate logic: Semantics
Interpretations

What ⊢ cannot do
- By defining the notion of derivation in PL (i.e. first-order logic), we have
defined a key logical relation:

- This relation captures one central aspect of logical consequence.

- But knowing what can be proved does not tell us what cannot be proved:
Interpretation:
- An interpretation (or model) of the language of PL is given by 2
components:
1) a domain (or universe) of discourse;
2) a function interpreting the non-logical vocabulary.
- The domain of discourse is a set of objects, the range of quantifiers
- Intuitively, the function interpreting the non-logical vocabulary gives us
the meaning of that vocabulary.

- A bit more precisely, the function interpreting the non-logical vocabulary

tells us:
a) which object is denoted by each constant;
b) of which objects in the domain each unary predicate is true;
c) of which pairs of objects in the domain each binary relation is true.
d) ...
e) of which n-tuples in the domain each n-place relation is true
f) ...

Notation: Sets
- Sets are collections of objects that have members or elements.
- We can specify a finite set by listing its members, separated by commas,
within curly brackets.
- Examples: (1; 2; 3) {John, Milly, Debby, Karim} {A V B}, {(A&B),A}
- We will use sets to interpret the universe of discourse and also to interpret
unary predicates.
- We will also use Venn diagrams to help us picture the relations

Notation: infinite sets

- Notation for sets:
- we can write e.g. {1, 2, 3} ... but also {n : n > 0&n < 4}
- The second notation is particularly useful when we wish to refer to
infinite sets. For example, {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ….}
- can be more economically and more precisely written as {n : n is even}-
means going to include every entity n, such that n is even.

Notation: n-tuples
- The order of the members of a set does not matter:
- {1, 2, 3} = {2, 3, 1} = {3, 1, 2}matters what’s in the set not the order
- What really matters is which members belong to a set.
- But sometimes we are interested in ordered collections. So we introduce
n-tuples.
 - An n-tuple is an ordered set with n members. - ordered sequences of
entities
- We denote n-tuples by using “<” and “>” in place of “” and “”.
Examples of n-tuples:
- < Annie, Bonnie > is a pair. Annie comes first Bonnie comes second
- < 1, 2, 3 > is a triple etc. has to be in this order
- Note that < 1, 2, 3 > is different from < 2, 3, 1 > and < 3, 1, 2 >, etc.
- Two n-tuples will be identical if and only if they contain the same
objects arranged in the same way
- We can also have pairs of the form < 2, 2 > or < Mary, Mary > and triples
of the form < 1, 1, 1 >, etc.
Why do we need n-tuples?:
- We can use n-tuples to represent relation.
- In particular, a binary predicate like love can be represented as a set of
pairs.
- Suppose John loves Mary and Mary loves Mary (herself). Then we can
represent love as: {< John, Mary >,< Mary, Mary >}
- This set is the extension of the predicate love.

Interpretation (again) (informal)

- An interpretation (or model) of the language of PL is given by
1) a domain (or universe) of discourse (UD);
2) a function interpreting the non-logical vocabulary.
- More precisely, an interpretation I for PL:
- specifies a (non-empty) set as UD;
- and assigns:
 a member of the UD to each individual constant of PL;
 set of n-tuples of members of the UD to each n-place predicate of PL.

Examples
- domain is represented as a box- I1 is domain
- use symbol for entailment

- this interpretation (I2) is false

- first conjunct is false as not everything is false- the dot outside circle- therefore
conjunction as a whole is false
- first conjunct also made false by another object- dot lies in G and not F
- second conjunct by dot outside G as well
- A single outlier makes sentence false
- So say I2 not truth functionally entail the conjunction
- Has 5 objects
- Relation of love is represented by arrows
- Does I3 make the sentence true? Need to check whether everyone loves someone-
it is true- every entity in the domain loves someone.
- Interpretation I3 makes the sentence true.

- Same sentence different interpretation- is it true everyone loves someone- entity

at top does not love anything
- So summarise our findings by saying our interpretation, I4 does not make the
sentence true.
- love is represented by arrow
- Lax means there is someone A loves- true because there is arrow departing it and
hitting a different object.

- Is it true that A is F- yes- A remains in circle F

- A is in G- still true
- Second conjunct- that A loves someone- this is false as there is no arrow going
from A to another entity
- This interpretation does not satisfy for make true that A is F and A is G and A
loves someone.

Practice
- Can pick how many objects in it
- There are many possible solutions to this problem
- This interpretation makes the sentence true

- Trying to show everything F is G but not true that everything G is F.

- Need to check both conjuncts
- Is it true is a is F then a is G- true
- Second conjunct- the negated sentence
- Built an interpretation where every F is G but not true that every G
is F.
- Want to prove a model which makes a sentence false
- If everyone loves someone then someone loves everyone
- Trying to show conditional is false- one way can do this- if has true
antecedent and a false consequent.
- Showing everyone loves something- every dot has arrow from it
- Showing not true that something loves everything – dot on left at
bottom does not love everything.
- This interpretation makes conditional false as antecedent is true but
consequent is false.

Describing interpretations- Example

- Need a way to describe interpretations in a more rigorous way.

- UD is just all the dots

- De
pe
nd
in
g on what resources are available you can give alternative
descriptions
 Semantic notions

Quantificational entailment:

Failure of quantificational entailment:

Example:
- Gamma is the first conjunct and Q is second
- Trying to show gamma does not truth functionally entail Q.
- Trying to show conclusion – that something loves everything is false- easy to
verify- can go through objects and show none of them loves everything

- Trying to show gamma is

true and Q is false (gamma is
ex vy lxy) Q is second
conjunct
- Want to make true that
something loves everything-
seen through dot that loves
itself and three other objects
in model
- Now want to show I10 does
not satisfy Q. says everything
loves something- dot at
bottom doesn’t love
anything.
- Gamma does not quantificationally entail Q
-Gamma now contains two
sentences
- Trying to show that
gamma is true and Q is
false
- First part- if something
that’s either F or G- dot is
in G so true
- Second part of first
conjunct- nothing that’s
both f and g- nothing in
intersection so true
- Need to then show its false
that there is something
that’s neither F nor G. Only one object that’s in G so false.
 - Trying to show gamma
containing the
conditional does not
quantificationally entail
that every F is G.
- Antecedent of
conditional- false so full
conditional is true
- Trying to show not true
that every F is G.

More semantic notions:

- Quantificational truth= Q is quantificationally true iff Q is true on every

interpretation
- Quantificational falsehood= Q is quantificationally false iff Q is false on
every interpretation
- Quantificational indeterminacy= Q is quantificationally indeterminate iff
Q is neither quantificationally true nor quantificationally false.
- Quantificational equivalence= Q and P are quantificationally equivalent
iff there is no interpretation on which Q and P have different truth values.
- Quantificational consistency= Γ is quantificationally consistent iff there is
an interpretation on which all members of Γ are true.
- Quantificational inconsistency= Γ is quantificationally inconsistent iff
there is no interpretation on which all members of Γ are true.
Reduction of semantic notions:
- The semantic notions defined so far can be expressed by means of
quantificational entailment. This is no different than what we saw in the
case of SL.
- Quantificational truth= Q is quantificationally true iff ∅ ⊨ Q
- Quantificational falsehood= Q is quantificationally false iff ∅ ⊨ -Q (a
negation)
- Quantificational equivalent= Q and P are quantificationally equivalent iff
∅ ⊨ (Q = P) (biconditional symbol)
- Quantificational consistency= Γ is quantificationally consistent iff there is
no P such that Γ ⊨ (P& -P) (a contradiction)
- Quantificational inconsistency= Γ is quantificationally inconsistent iff for
some P, Γ ⊨ (P& -P)
- So we can take ⊨ to be our basic semantic notion

Rigorous formulation

Definitions- rigorous formulation:

- Interpretation (model)- An interpretation I is a pair (d, i) where d (the domain or UD)
is a set and i is an interpretation function for the non-logical terminology of PL.

Variable assignment
 - Let I= (d, i) be an interpretation. A variable assignment v1 is a function that assigns a
member of d to each variable of PL.

Variant of a variable assignment:

Definitions:
Let Q be a formula of SL, and let I and V1 be an interpretation and a variable assignment,
respectively.

Lecture 10- more semantics and metatheory

More on semantics
 Metatheory

The main metatheoretic results continue to hold in first-order logic.

So, we have:
- A soundness theorem
- A completeness theorem
And there is more….

Soundness theorem

- If P is provable form gamma, then gamma quantificationally entails P.

Soundness theorem (logically equivalent formulation):

 - If gamma does not quantificationally entail P, then P is not provable from
gamma.

Completeness theorem

- If gamma quantificationally entails P, then P is provable from gamma

Completeness theorem (logically equivalent formulation):

- If P is not provable from gamma, then gamma does not quantificationally

entail P.

Compactness theorem

- If gamma quantificationally entails P, then P is quantificationally entailed

by a finite subset of gamma.

Upward Löwenheim-Skolem theorem

Theory:
- A theory in PL is a set of sentences of PL

Notation:
 Glimpses beyond

Important difference between SL and PL:

- With SL mechanical procedure is truth tables don’t have this for PL-
if we want to know if P is provable from gamma we have a
mechanical way of answering the question in SL- doesn’t hold for
PL- not mechanical procedure to decide whether P is
quantificationally entailed by gamma.
Incompleteness theorems

Second-order logic

Second- order logic allows quantification into predicate position:

Modal logic
 Exam

Basic list of topics that will be covered:

- What is the language of SL? What is a sentence of SL?
- What is a truth-value assignment? When is a sentence true/false on a
given truth-value assignment?
- Practice truth tables.
- Translation of natural language sentences into SL.
Master definitions of the following notions:
- P is truth-functionally true/false/indeterminate;
- P and Q are truth-functionally equivalent;
- Gamma is truth-functionally consistent/inconsistent;
-

- Introduction and elimination rules for negation, and, V, backwards C and

equal sign
- Constructing a derivation in SL
- The excercises on SL derviations will ask you to establish whether for
some gamma and P, gamma proves P or gamma does not prove P. Here
you need to: (1) use truth tables to check if there is entailment; (2) say if
there is a derivation or not; (3) explain if you use the soundness or the
completeness theorem to reach your conclusion; (4) if there is a
derivation, you need write one down.
- Proofs by induction
- Proofs of soundness and completeness theorems for SL.
 - What is the language of first-order logic (= PL)? What is a well-formed
formula of PL?- through a syntactic tree
- What are a sentence/free variable/bound variable/scope of a quantifier?
When does a quantifier bind a given variable?- can get this from
construction tree?
- Translation of natural language sentences into PL.
- Introduction and elimination rules for backwards E, universal and equals
sign
- Construct derivation in PL
- For PL typical questions will ask you to establish whether gamma proves
P or gamma does not prove P.
- Soundness and completeness theorems for first-order logic: what do they
say? How do they help us determine whether or not a derivation exists?
- What is an interpretation of first-order logic
- When is a sentence true/false on an interpretation.
Master definitions of the following notions:
- P is quantificationally true/false/indeterminate;
- P and Q are quantificationally equivalent;
- Gamma is quantificationally consistent/inconsistent;