Logic I
Introduction to Symbolic Logic
--- by s.butterfill@warwick.ac.uk
A course at the University of Warwick about logical validity, truth, quantification and natural deduction.
Handouts & Slides
There are three versions of these lectures:
Exercises & Past Exams
Exercises are set for subtopics of each lecture (links below). You can also find a summary of all exercises set on zoxiy:
Past exams with sample answers:
Other:
Practical Info
For timings, past exam papers, permission to the take module as an unusual option and everything else, please see:
Slides and Handouts for Regular Lectures
You can find slides and handouts below, together with an outline of each lecture.
Please note that these may be revised even after lectures have occurred.
Lecture 01
Date given: Tuesday 12th January 2016
Exercises for this lecture:
The Pigs of Logic (01)
definitions
Explains the notion of a logically valid argument with an illustration involving two pigs. Previews key ideas coming later.
Reading: §1.1, §1.2, §2.1
Why Logic? (011)
definitions
Provides two reasons for studing logic, one abstract the other practical.
zoxiy (016)
zoxiy
There are logic exercises associated with each lecture. This is how to complete them ...
Quick Intro to awFOL (02)
definitions
Gives some examples of the formal language awFOL and explains their relation to ordinary English. Also explains terms like 'name' and 'predicate'.
Reading: §1.1, §1.2, §1.3
Alternative textbook exercises (regular): 1.1--1.5, *1.6, 1.8--1.10
zoxiy: Creating Possible Situations (026)
zoxiy ex-create
Describes how to create possible situations in logic-ex.
Logically Valid Arguments (03)
definitions
Explains the notion of logically valid argument. This is the central notion for this course.
Reading: §2.1
Alternative textbook exercises (regular): 2.3, 2.4
Lecture 02
Date given: Thursday 14th January 2016
Exercises for this lecture:
Learning Objectives (013)
Graphical depiction of learning objectives for this course.
Counterexamples (04)
definitions zoxiy ex-create
Explains the notion of a counterexample. Discusses a counterexample to a simple argument. Demonstrates using zoxiy to construct a counterexample involving shape and size properties.
Reading: §2.5
Alternative textbook exercises (regular): 2.8, 2.10, 2.12, 2.21
Alternative textbook exercises (fast): 2.8, 2.10, 2.12, 2.21
Soundness (041)
definitions
Explains the notion of a sound argument.
Identity (06)
definitions zoxiy ex-create
Introduces the notion of identity used in studying first-order logic. Includes example argument and the two principles. Also demonstrates how to assign names in zoxiy, and using zoxiy to make identity statements true and false.
Reading: §2.2
Alternative textbook exercises (regular): 2.5, 2.6
Formalizing Arguments (135)
translation
Illustrates how for formalise simple arguments with the 'pigs' illustration.
Reading: §3.7
Sentence Letters (012)
definitions
Explains what sentence letters are and why we use them.
Truth Tables (071)
definitions
Introduces truth tables for conjunction, disjunction and negation. Truth tables give the meanings of connectives in our formal language awFOL.
Reading: §3.1, §3.2, §3.3
Alternative textbook exercises (regular): 3.1, 3.2, 3.5, 3.7
Alternative textbook exercises (fast): 3.1, 3.3, 3.5, 3.7
Complex Truth Tables (60)
truth-tables
Illustrates how to construct complex truth tables with an example, not(P and Q).
Contradictions, Logical Truths and Logical Possibilities (065)
definitions zoxiy ex-tt
Illustrates and defines the terms ‘contradiction’, ‘logical truth’ and ‘logical possibility’. Describes how to recognise these from truth tables. Demonstrates using zoxiy to construct truth-tables and answer questions about contradictions, logical truths and logical possibilities.
Reading: §2.2
Alternative textbook exercises (regular): 2.5, 2.6
Lecture 03
Date given: Tuesday 19th January 2016
Exercises for this lecture:
Logical Validity and Truth Tables (14)
truth-tables
Illustrates the use of truth tables to determine logical validity.
Reading: §4.3
Alternative textbook exercises (regular): 5.1-5.4
Formal Proof (211)
proof
Marks the transition from truth-tables, in which the notion of truth plays a central role, to fitch proofs which are purely formal entities.
Translating a Simple Argument (213)
translation
Illustrates how to translate an argument from English into our formal language awFOL.
Reading: §3.2
Formal Proof: ∧Elim and ∧Intro (21)
proof zoxiy ex-proof
Introduces and illustrates the use of rules of proof for conjunction. Explains how to create proofs using logic-ex.
Reading: §5.1, §6.1
Alternative textbook exercises (regular): 6.1
Alternative textbook exercises (fast): 5.3--5.6
Symbols and Words (022)
proof zoxiy ex-proof ex-trans
When you use zoxiy you can type words instead of using symbols. But which words stand for which symbols? Here’s a list.
Truth Tables Are Stipulations (073)
truth-tables semantics
Sometimes people think that one or other of the truth tables for a connective is wrong. These thoughts are always mistaken. The truth tables for the connectives are stipulations about their meanings.
Rules of Proof for Identity (110)
proof
Introduces and illustrates the rules of proof for identity, =Intro and =Elim.
Reading: §2.2
How to Write Proofs (130)
definitions
Describes how to write proofs.
Complex Truth Tables (09)
truth-tables
Illustrates how to construct complex truth-tables with an example, the truth-table for (P and Q) or R. Also describes how to order the reference columns.
Reading: §3.3, §3.5
Alternative textbook exercises (regular): 3.12, 3.13, 4.4-4.7, 4.12-14
Alternative textbook exercises (fast): 3.14, 3.15
Logic Makes Me Die Inside (161)
definition
Is the definition of logical validity flawed?
Reading: §2.1
Contradictions, Logical Truths and Logical Validity (160)
truth-tables
Continues exploring the use of truth-tables to establish whether sentences are contradictions or logical truths, and to demonstrate logical validity. Notes that logical validity is not what you think it is.
Reading: §4.1, §4.2, §5.4
Alternative textbook exercises (regular): 4.1, 4.2
Alternative textbook exercises (fast): 4.1, 4.2, 4.12--4.16
Lecture 04
Date given: Thursday 21st January 2016
Exercises for this lecture:
∨Intro (225)
proof
Introduces the rule of proof ∨Intro with some examples.
∧Intro and ∨Intro: Compare and Contrast (212)
proof
Contrasts two rules of proof and explores how their differences are related to truth-tables.
Reading: §6.1
Truth-functional Connectives (072)
truth-tables semantics
Explains the notion of a truth-functional connective. Discussion of why 'because' could not have a truth table.
Reading: §7.0 (the text before §7.1)
Alternative textbook exercises (regular): 7.9
Alternative textbook exercises (fast): 7.9
The Storm Clouds on the Horizon Were Getting Nearly Directly Overhead (162)
truth-tables
Illustrates and defines the terms 'tautology' and 'contradiction' with some quotes from George Bush.
A ∧ B ∨ C (151)
proof syntax
Distinguishes lexical from structural ambiguity. Asks how we can know there is no structural ambiguity in our formal language awFOL.
Reading: §3.5
Alternative textbook exercises (regular): 3.20, 3.21, 3.22
A ∧ B ∨ C: the Truth-tables (153)
truth-tables
Illustrates how to construct complex truth tables for (A ∧ B) ∨ C and A ∧ (B ∨ C).
A ∧ B ∨ C: They Are Different (154)
truth-tables
Uses two arguments to show that (A ∧ B) ∨ C and A ∧ (B ∨ C) really are different.
Alternative textbook exercises (regular): 3.14, 3.15
Alternative textbook exercises (fast): 3.14, 3.15, 7.2, 7.5, 7.6
Lecture 05
Date given: Tuesday 26th January 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
¬, ⊥ (270)
proof
Quick introduction to two connectives, ¬ and ⊥, together with illustration of rules of proof for ⊥.
Reading: §6.3
→Intro, →Elim (390)
proof proof-example
Introduction to the rules of proof for →, →Intro and →Elim. This is the first time subproofs are used. Also illustrates a proof without any premises. The proof is from premises P→Q and Q→R to conclusion P→R.
Reading: §8.1, §8.2
Alternative textbook exercises (fast): 8.20--8.25
Subproofs with zoxiy (395)
proof proof-example zoxiy ex-proof
Introduction to the rules of proof for →, →Intro and →Elim. This is the first time subproofs are used. Also illustrates a proof without any premises. The proof is from premises P→Q and Q→R to conclusion P→R.
Reading: §8.1, §8.2
Ambiguity: Recap (170)
syntax
What is the source of ambiguity in natural languages?
I Shot an Elephant in My Pyjamas (171)
syntax
What is the source of ambiguity in natural languages? Depicts two structures for Groucho Marx' utterance 'I shot an elephant in my pyjamas'.
Lecture 06
Date given: Thursday 28th January 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
∨Intro and ∨Elim (222)
proof
States the rules of proof for ∨, ∨Intro and ∨Elim.
Reading: §6.2
∨Elim and Soundness (226)
proof
Introduces the rule of proof ∨Elim and links it to the truth table for ∨.
Reading: §5.2, §6.2
∨Elim: An Example (221)
proof proof-example
Illustrates the use of ∨Elim, a rule of proof. Uses the inference from A∨B to B∨A as an example.
Reading: §5.2, §6.2
Alternative textbook exercises (regular): 5.1--5.6, 6.2--6.6
Not Or (603)
translation
Negating disjunctions is tricky. This contrasts ¬(A ∨ B) with ¬A ∨ ¬B.
Reading: §3.7
Alternative textbook exercises (regular): 3.19, 5.18
→Intro: An Example (391)
proof proof-example
Discusses (but does not complete) a relatively hard proof involving the rule →Intro. The proof is from premise A∨B to conclusion ¬B→A.
¬Elim (280)
proof
Introduces the rule of proof ¬Elim with an illustration. Relates the rule to the truth table for ¬.
Reading: §6.3
¬Intro (281)
proof proof-example
Introduction to the rule of proof ¬Intro with an illustration. Discusses the proof from premise A∧B to conclusion ¬(¬A∨¬B).
Reading: §5.3, §6.3
Alternative textbook exercises (regular): 6.7--6.10, *6.11--6.12
Alternative textbook exercises (fast): 6.7--6.12, 6.18--6.20, 6.24--6.27, *6.40--6.42
¬Intro continued (282)
proof
Completes the proof used to illustrate ¬Intro.
∨Elim: Recap (223)
proof
Repeats an earlier illustration of the use of ∨Elim, a rule of proof. Uses the inference from A∨B to B∨A.
Subproofs Are Tricky (224)
proof
Offers what appears to be a proof of an argument that is not logically valid in order to illustrate a restriction on the use of subproofs.
Lecture 07
Date given: Tuesday 2nd February 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
Recap: Structural Ambiguity in Natural Languages (231)
syntax
Reminder about the sources of structural ambiguity in natural language.
The Syntax of awFOL (230)
syntax
States the rules of syntax for awFOL. Illustrates these with tree diagrams. Links to truth tables.
Reading: §9.3
¬P ∨ ¬Q compared with ¬(P ∨ Q) (232)
syntax
Explains how the brackets make a different to the meanings of sentences. Illustrates by comparing ¬P ∨ ¬Q with ¬(P ∨ Q).
Reading: §3.5
Logically Entails (239)
definitions
One sentence logically entails another just if there’s no possible situation where the first is true and the second false.
Subproofs Are Tricky: The Answer (227)
proof
Explains that in doing a proof, it is not allowed to cite lines from a closed subproof, thereby answering a question asked earlier.
¬Intro Proof Example (283)
proof proof-example
Discusses an intermediate proof involving ¬Intro, from premises P→Q and ¬Q to conclusion ¬P.
Reading: §5.3, §6.3
Alternative textbook exercises (regular): 6.24--6.26
DeMorgan: ¬(A ∧ B) ⫤⊨ ¬A ∨ ¬B (235)
truth-tables
Introduces DeMorgan's Laws relating ¬, ∧ and ∨. The laws can be stated as A ∧ B ⫤⊨ ¬(¬A ∨ ¬B) and A ∨ B ⫤⊨ ¬(¬A ∧ ¬B). Also mentions that A → B ⫤⊨ ¬A ∨ B.
Reading: §3.6, §4.2
Alternative textbook exercises (regular): 3.19, 4.15--18, 7.1--7.2, *7.3--7.6
Alternative textbook exercises (fast): 3.19, 4.31
Get Some Quantifiers: Don't Economise (473)
quantification
We're going to be using quantifiers a lot. We understand them thanks to Frege and Taski. It's important to get a pair you like.
Reading: §9.1
Everything Is Broken (471)
quantification
Quantifiers are for talking about things without naming them.
Reading: §9.1, §9.2
Alternative textbook exercises (regular): 9.1 odd numbers only, 9.2 even numbers only
Alternative textbook exercises (fast): 9.8–-9.10
Lecture 08
Date given: Thursday 4th February 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
Get Some Quantifiers: Don't Economise (473)
quantification
We're going to be using quantifiers a lot. We understand them thanks to Frege and Taski. It's important to get a pair you like.
Reading: §9.1
Everything Is Broken (471)
quantification
Quantifiers are for talking about things without naming them.
Reading: §9.1, §9.2
Alternative textbook exercises (regular): 9.1 odd numbers only, 9.2 even numbers only
Alternative textbook exercises (fast): 9.8–-9.10
All Squares Are Blue (503)
quantification revision
Explains how to translate 'All squares and blue' and 'Some squares are blue' into awFOL using quantifiers.
Reading: §9.2, §9.3, §9.5
Alternative textbook exercises (regular): 9.4--9.5, 9.8--9.10
What does ∀ mean? (492)
semantics
Explains the meaning of ∀ with an example.
Reading: §9.4
Vegetarians Are Evil (502)
quantification
Practices translating an English argument involving quantifers into awFOL.
Reading: §9.2, §9.3, §9.5
Counterexamples with Quantifiers (502b)
quantification
Illustrates giving a counterexample to an argument involving quantifiers.
We knew that it was invalid ... (163)
definition
Some arguments are logically valid even though the conclusion is unrelated to the premises.
DeMorgan: ¬(A ∧ B) ⫤⊨ ¬A ∨ ¬B (235)
truth-tables
Introduces DeMorgan's Laws relating ¬, ∧ and ∨. The laws can be stated as A ∧ B ⫤⊨ ¬(¬A ∨ ¬B) and A ∨ B ⫤⊨ ¬(¬A ∧ ¬B). Also mentions that A → B ⫤⊨ ¬A ∨ B.
Reading: §3.6, §4.2
Alternative textbook exercises (regular): 3.19, 4.15--18, 7.1--7.2, *7.3--7.6
Alternative textbook exercises (fast): 3.19, 4.31
Lecture 09
Date given: Tuesday 9th February 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
Scope: A Mistaken Application of ¬Elim (291)
definition syntax
Describes a mistaken application of the rule ¬Elim. Asks why this application is mistaken.
Alternative textbook exercises (regular): 6.8
Scope (290)
definition syntax
Defines the notion of scope using trees; explains its application in constructing proofs and truth-tables.
Reading: §3.5
Alternative textbook exercises (regular): 3.14, 3.15
Scope and Negation (320)
semantics
Explores differences between the negation of a disjunction and a disjunction of negations. That is, between ¬(A∨B) and (¬A∨¬B)
Reading: §3.5, §3.6
Proof Example: ¬(P∨Q) therefore ¬P∧¬Q (821)
proof revision proof-example
Describes how to prove ¬(P∨Q) therefore ¬P∧¬Q.
Alternative textbook exercises (regular): 6.24--6.27
I Met a Philosopher (501)
quantification
Explains how to express propositions like 'I met a philosopher' by using the existential quantifier together with conjunction.
Reading: §9.2, §9.3, §9.5
Alternative textbook exercises (regular): 9.1 odd numbers only, 9.2 even numbers only, 9.4, 9.5, 9.8, 9.9, 9.10, 9.12
Alternative textbook exercises (fast): 9.8, 9.9, 9.10, 9.12, 9.13
Scope and Quantifiers (710)
semantics
Explores differences between ∃x(Square(x) ∧ Blue(x)), some squares are blue, and ∃x Square(x) ∧ ∃x Blue(x), something is square and something is blue.
Reading: §9.5, §9.6
Proof Example: ¬P∨R therefore P→R (820)
proof revision proof-example
Describes how to prove ¬P∨R therefore P→R.
∀Elim (800)
quantification proof
Explains the rule of proof ∀Elim with an example.
Reading: §13.1
Lecture 10
Date given: Thursday 11th February 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
∃Intro (801)
quantification proof
Explains the rule of proof ∃Intro.
Reading: §13.2
What does ‘→’ mean? (700)
semantics
Shows how to derive a truth table for → from the rules of proof for →, →Intro and →Elim.
Reading: §7.1
Alternative textbook exercises (regular): 7.1--7.6, 8.1 (yes/no answers are ok)
Alternative textbook exercises (fast): 7.2, 7.5, 7.6
Not If (604)
translation
Negating sentences whose main connective is the arrow is tricky. This contrasts ¬(A → B) with A → ¬B.
↔ : truth tables and rules (567)
translation
Mentions the truth-tables and rules of proof for the biconditional, ↔.
Fubar Rules (340)
meta
Introduces a fake rule of proof, ∧Fubar. The challenge is to explain what is wrong with ∧Fubar.
Reading: §8.3
What does ∃ mean? (491)
semantics
Explains the meaning of ∃ with a simple example.
Reading: §9.4
There Does Not Exist (605)
translation quantification
How can we translate sentences involving quantifiers and negation from English into our formal language awFOL? Discusses translating 'Something is not dead' and 'Nothing is dead'; also 'Everything is not broken' and 'Not everything is broken'. New: now includes discussion of first-order counterexamples.
Alternative textbook exercises (regular): 9.12
Alternative textbook exercises (fast): 9.18--9.19
Quantifier Equivalences: ¬∀x Created(x) ⫤⊨ ∃x ¬Created(x) (764)
translation quantifiers semantics
Introduces the logical equivalence that allows us to turn ∀ into ∃, and conversely. Explains how to prove informally that the equivalence holds using the truth-conditions for quantified statements.
Reading: §10.1, §10.3, §10.4
Lecture 11
Date given: Tuesday 23rd February 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
Revision: ∀Elim, ∃Intro (551)
proof
Summary of two rules of proof, ∀Elim and ∃Intro.
Reading: §12.1, §13.1, §13.2
∃Elim (550)
proof
Introduces the rule of proof ∃Elim with an example. The example proof is from premise ∃x( Blue(x) ∧ Square(x) ) to conclusion ∃x Blue(x).
Reading: §12.2, §13.2
Translation with Quantifiers (507)
translation
Discusses how to translate 'Some persuasive arguments are not valid' and 'All quadrumanous discordians weep and wail except Gillian Deleude' into first-order logic.
Reading: §9.5, §9.6
Alternative textbook exercises (regular): 9.4–-9.5, 9.8–-9.9
Alternative textbook exercises (fast): 9.12-–9.13
Don't use ∃ with → (245)
translation
Stresses that ∀ works with → by examining sentences with ∀ and ∧, and ∃ with →.
Alternative textbook exercises (regular): 9.10, 9.15--9.17, *9.18--9
Alternative textbook exercises (fast): 9.10
Watch Out, Here Come Multiple Quantifiers (744)
revision quantification semantics translation
Preliminary to discussion of multiple quantifiers.
Reading: §11.1
Something Is Above Something (740)
quantification semantics
Introduces a simple sentence involving multiple quantifiers. Illustrates how to apply the procedure for determining the truth of sentences involving quantifiers to sentences containing multiple quantifiers.
Reading: §11.1
Alternative textbook exercises (fast): 11.2, 11.4
Multiple Quantifiers: Something Makes Someone Want to Die Inside (741)
quantification semantics translation
Introduces translation from English to awFOL using multiple existential quantifiers with an example.
Reading: §11.1
Multiple Quantifiers: Everyone Likes Puffins (742)
quantification semantics translation
Introduces translation from English to awFOL using multiple universal quantifiers with an example.
Reading: §11.1
Alternative textbook exercises (regular): 11.2
Quantifiers Bind Variables (711)
semantics
Illustrates how quantifiers bind variables (but does not define this). Contrast ∀x(Square(x) → Blue(x)), all squares are blue, with ∀x Square(x) → ∀x Blue(x), if everything is square then everything is blue.
Reading: §9.3
Summary of Quantifier Rules So Far (571)
proof
Summary of ∀Elim, ∃Intro and ∃Elim.
Reading: §12.1, §12.2, §12.3, §13.1, §13.2
∀Intro (570)
proof proof-example
Introduces the rule of proof ∀Intro with an example. The example proof is from premise ∀x(Square(x) → Blue(x)) to conclusion ∀x Square(x) → ∀x Blue(x).
Reading: §12.1, §12.3, §13.1
Alternative textbook exercises (regular): 12.4--12.5, *12.6--12.7, 12.9--12.10
∀Intro: An Incorrect Proof (572)
proof
Discussion of an incorrect proof which appears to apply ∀Intro to prove this invalid argument: (∀x Square(x)) → (∀x Blue(x)) therefore ∀x(Square(x) → Blue(x)).
Reading: §13.1, §13.2
Lecture 12
Date given: Thursday 25th February 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
Relations: Reflexive, Symmetric (120)
quantification relations counterexamples
Explains what it is for a relation to be reflexive, and what it is for a relation to be symmetric.
Reading: §15.1, §15.6
Relations: Transitivity (125)
quantification relations counterexamples
Explains what it is for a relation to be transitive. Describes how to show, using counterexamples, that the relation NotAdjacent (which holds between two objects just when the first is not adjacent to the second) is not transitive. Also describes how to express the counterexample formally.
Reading: §15.1, §15.6
Relations: Some Examples (128)
quantification relations
Practices identifying whether a given relation is reflexive, symmetric or transitive. Also practices finding relations with some given set of features (e.g. find a relation that is reflexive and symmetric but not transitive).
Reading: §15.1, §15.6
Defining Relations Using Dot-Arrow Diagrams (129)
relations
Describes how to use dot-arrow diagrams to define relations.
Expressing Relations with Quantifiers (581)
quantification relations
Describes how quantifiers can be used to express the claim that a particular relation is reflexive, symmetric or transitive. Also introduces dot-arrow diagrams to describe relations.
Reading: §15.1, §15.6
Alternative textbook exercises (regular): 15.33--15.40 (second edition)
Alternative textbook exercises (fast): 15.33, 15.37--15.39 (second edition)
Negating Identity (323)
semantics
Sometimes people think that ¬a=b and ¬(a=b) mean something different. They don't.
There Does Not Exist (605)
translation quantification
How can we translate sentences involving quantifiers and negation from English into our formal language awFOL? Discusses translating 'Something is not dead' and 'Nothing is dead'; also 'Everything is not broken' and 'Not everything is broken'. New: now includes discussion of first-order counterexamples.
Alternative textbook exercises (regular): 9.12
Alternative textbook exercises (fast): 9.18--9.19
Expressing Counterexamples Formally (583)
counterexamples relations
Describes how quantifiers can be used to express the claim that a particular relation is reflexive, symmetric or transitive.
Reading: §15.1, §15.6
Summary of Relations (126)
relations
Quick summary definition of reflexive, symmetric and transitive.
Proof Example: A∧B therefore ¬(¬A∨¬B). (822)
proof revision proof-example
Describes how to prove A∧B therefore ¬(¬A∨¬B)..
Proof Example: P therefore ¬¬P. (823)
proof revision proof-example
Describes how to prove P therefore ¬¬P.
Proof Example: S∨(Q∧R) therefore S∨Q. (824)
proof revision proof-example
Describes how to prove S∨(Q∧R) therefore S∨Q.
Lecture 13
Date given: Tuesday 1st March 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
There Is a Store for Everything (560)
quantification semantics translation
Explains how to translate English sentences involving a combination of universal and existential quantifiers into awFOL with an example.
Reading: §11.2, §11.3
Alternative textbook exercises (regular): 11.3, 11.4, 11.8, 11.9, 11.11, 11.13, *11.10
Alternative textbook exercises (fast): 11.8, 11.9, *11.11
How Big Is a Truth-Table? (431)
meta truth-tables
Explains how to determine how many rows a truth table for a sentence containing 2, 3 or 369 sentence letters would be.
Truth-functional completeness (430)
meta truth-tables
Explains what it is for a set of connectives to be truth-functionally complete. Proves that {¬, ∧, ∨} is truth-functionally complete. ‘A set of truth-functors is said to be expressively adequate (or sometimes functionally complete) iff, for every truth function whatever, there is a formula containing only those truthcfunctors which express that truthcfunction, i.e. which has as its truthctable the truthctable specifying that function.’ (Bostock, Intermediate Logic p. 45).
Reading: §7.4
Alternative textbook exercises (regular): 7.25, 7.26, *7.28, 7.29
Alternative textbook exercises (fast): 7.25, 7.26, *7.28, 7.29
Lecture 14
Date given: Thursday 3rd March 2016
slides , handout [pdf], recording [warwick only]
Exercises for this lecture:
Two Things Are Broken (470)
quantification semantics
Explains how to translate sentences involving number into awFOL using quantifiers and identity.
Reading: §14.1
Loving and Being Loved (755)
quantifiers translation
Discusses translating English sentences about loving and being loved in order to illuminate the difference between ∃y∀x Loves(x,y) and ∃y∀x Loves(y,x).
Reading: §11.2, §11.3
Somebody Is Not Dead (607)
translation quantification
Continues discussion of how to translate sentences involving quantifiers and negation from English into our formal language awFOL? Discusses translating 'Some person is not dead' and 'No person is dead'; also 'Every person is not dead' and 'Not every person is dead'.
Quantifier Equivalences: ∀x(Square(x) → Broken(x)) ⫤⊨ ∀x(¬Broken(x) → ¬Square(x)) (760)
translation quantifiers
Describes how we can use knowledge of equivalences among propositional sentences to get quantifier equivalences with an example. The example is the inference from this: A → B ⫤⊨ ¬B → ¬A, to this: ∀x(Square(x) → Broken(x)) ⫤⊨ ∀x(¬Broken(x) → ¬Square(x)).
Reading: §10.3
Alternative textbook exercises (regular): 10.20, 10.22
Quantifier Equivalences: ∀x(Square(x) → Broken(x)) ⫤⊨ ∀x(¬Square(x) ∨ Broken(x)) (762)
translation quantifiers
A further example of how we can use knowledge of equivalences among propositional sentences to get quantifier equivalences.
Reading: §10.3
More Dead Horse (565)
quantification semantics translation
Continues the discussion of how to translate English sentences involving a combination of universal and existential quantifiers into awFOL with an example, 'There is a store for everything.' Also discusses structural ambiguities related to quantifier scope and how to use awFOL to pin down this sort of ambiguity.
Reading: §11.4, §11.5
Lecture 15
Date given: Tuesday 8th March 2016
Exercises for this lecture:
Soundness and Completeness: Statement of the Theorems (400)
meta
Explains what it is for a system of proof, such as Fitch, to be sound; and what it is for a system of proof to be complete.
Reading: §8.3, §13.4
The Soundness Property and the Fubar Rules (fast) (346)
meta
Identifies a property of the rules of proof in Fitch: no rule allows us to go from truths to a falsehood. Illustrates by contrasting ∧Elim with ∧Fubar.
Reading: §8.3
Alternative textbook exercises (regular): 7.32
Alternative textbook exercises (fast): 7.32
Proof of the Soundness Theorem (410)
meta
Sketches a proof of the soundness theorem for the propositional part of our formal system of proof, Fitch.
Reading: §8.3
Translation from awFOL to English (951)
translation quantification revision
Revises translation from awFOL to English by considering some questions from an exam paper.
Alternative textbook exercises (regular): 14.1--14.3, (*14.4--14.5)
Numerical Quantifiers (620)
quantification translation
Explains how to translate sentences involving number, such as exactly two things are broken, into awFOL using quantifiers and identity.
Reading: §14.1
Alternative textbook exercises (fast): 14.2--14.3, 14.4--14.5, 14.10--14.11
Lecture 16
Date given: Thursday 10th March 2016
Exercises for this lecture:
There Is Exactly One (625)
translation
Mentions several ways of expressing the idea that there is exactly one creator in our formal language, awFOL.
Alternative textbook exercises (regular): 14.10--14.12, *14.13
Alternative textbook exercises (fast): 11.10, 11.13, 14.2
Every Time I Go to the Dentist Someone Dies (750)
quantifiers translation
Discusses translating English sentences involving obscured quantifiers into awFOL with an example.
Reading: §11.2
Could There Be Nothing? (805)
quantification proof
Our system of proof, Fitch, allows us to prove that something exists from no premises. So if Fitch is sound, there must not be a possible situation in which nothing exists. Here we look at what three proofs that somehing exists which indicate how Fitch would need to be restricted so that it does not allow us to prove that something exists from no premises.
Reading: §13.2
Proofs about Proofs (440)
meta
Explains how to prove proofs about proofs. Examples include: (i) if A ⊢ B then ⊢ A → B, (ii) if A ⊢ B then A ⊢ ¬¬B
Does ‘if’ mean what ‘→’ means? (640)
semantics quirk
Argues that ‘if’ must mean what ‘→’ means, and that it cannot.
Reading: §7.3
Lecture 17
Date given: Tuesday 15th March 2016
Exercises for this lecture:
Revison: Definitions (972)
definitions
Discusses the first part of many exam questions.
Revison: Truth tables (975)
quantification translation
Discusses an exam question.
Revison: Proofs (propositional) (977)
proof proof-example
Discusses an exam question.
Revison: Proofs (with quantifiers) (979)
proof proof-example
Discusses an exam question.
Revison: Translation from English to awFOL (971)
quantification translation
Discusses an exam question.
Proof Example: ∃x Dead(x) ⊢ ¬∀x¬ Dead(x). (825)
proof revision proof-example
Describes how to prove that not everything is not dead given that something is dead.
Alternative textbook exercises (fast): 13.43--13.45
Proof Example: ¬∀x Dead(x) ⊢ ∃x¬ Dead(x). (826)
proof revision proof-example
Describes how to prove that something is not dead from the premise that not everything is dead.
Alternative textbook exercises (fast): 13.49--13.50
The End Is Near (790)
quantification translation
Extremely brief introduction to definite descriptions. Hints at how sentences such as 'The winner is hungry' might be translated into awFOL.
Reading: §14.3
Alternative textbook exercises (regular): 14.26, 14.28
Alternative textbook exercises (fast): 14.2, 14.4, 14.5, 14.10, 14.11, 14.26, 14.28
Lecture 18
Date given: Thursday 13th March 2014
Exercises for this lecture:
Proofs about Proofs (440)
meta
Explains how to prove proofs about proofs. Examples include: (i) if A ⊢ B then ⊢ A → B, (ii) if A ⊢ B then A ⊢ ¬¬B
A ⊨ ⊥ (467)
meta
Explains what A ⊨ ⊥ means. (A ⊨ ⊥, i.e. the argument with premises A and conclusion ⊥ is logicallly valid.)
If (A ⊬ ⊥ entails A ⊭TT ⊥) then (A ⊨TT B entails A ⊢ B) (469)
meta
This is a step towards our proof of the completeness theorem. The completeness theorem says A ⊨TT B entails A ⊢ B. Here we prove that we can show this by showing that A ⊬ ⊥ entails A ⊭TT ⊥.
The Essence of the Completeness Theorem (450)
meta
Outlines how the completeness theorem for the propositional part of our formal proof system, Fitch, will work.
Reading: §8.3
Lemma for the Completeness Theorem (453)
meta
Proves the following claim, where Γ is a set of sentences of awFOL: if for every sentence letter P, either Γ⊢P or Γ⊢¬P, then for every sentence of awFOL φ, either Γ⊢φ or Γ⊢¬φ.
Reading: §8.3
Proof of the Completeness Theorem (455)
meta
Sketches a proof of the completeness theorem.
Reading: §8.3, §17.1, §17.2
Proof of Proposition 4 for the Completeness Theorem (465)
quantification relations
Describes how quantifiers can be used to express the claim that a particular relation is reflexive, symmetric or transitive. Also introduces dot-arrow diagrams to describe relations.
Reading: §15.1, §15.6
Alternative textbook exercises (regular): 15.33--15.40 (second edition)
Alternative textbook exercises (fast): 15.33, 15.37--15.39 (second edition)