Logic I

Alternative textbook exercises (regular): 2.8, 2.10, 2.12, 2.21

Alternative textbook exercises (fast): 2.8, 2.10, 2.12, 2.21

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

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 (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

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

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

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

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.

Fast Lecture 02

Date given: Tuesday 19th January 2016

slides , handout [pdf]

Exercises for this lecture:

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.

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.

∧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

How to Write Proofs (130)

definitions

Describes how to write proofs.

Rules of Proof for Identity (110)

proof

Introduces and illustrates the rules of proof for identity, =Intro and =Elim.

Reading: §2.2

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

→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

→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.

Subproofs with zoxiy (395)

proof proof-example zoxiy ex-proof

Reading: §8.1, §8.2

∨Intro and ∨Elim (222)

proof

States the rules of proof for ∨, ∨Intro and ∨Elim.

Reading: §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

¬, ⊥ (270)

proof

Quick introduction to two connectives, ¬ and ⊥, together with illustration of rules of proof for ⊥.

Reading: §6.3

Fast Lecture 03

Date given: Tuesday 21st January 2014

Exercises for this lecture:

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

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

¬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

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 (quick version) (152)

truth-tables

Whiz through 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

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'.

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

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

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

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.

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

Fast Lecture 04

Date given: Tuesday 2nd February 2016

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

∃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

Quantifer Rules: ∃Elim with zoxiy (554)

proof zoxiy ex-proof

Explains how to do proofs involving quantifier rules with zoxiy. (Where you need to put the name ‘a’ in a box, write ‘[a]’.)

All Squares Are Blue (Fast Version) (504)

quantification

Looks at translating 'All squares and blue' and 'Some squares are blue' into awFOL using quantifiers.

Reading: §9.2, §9.3, §9.5

Alternative textbook exercises (fast): 9.16.10--9.16.15, 9.17.7--9.17.15

What does ∀ mean? (492)

semantics

Explains the meaning of ∀ with an example.

Reading: §9.4

∀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

Summary of Quantifier Rules (575)

proof

Quick recap of the four main quantifier rules.

Reading: §13.1, §13.2

Alternative textbook exercises (fast): 10.20, *10.24--10.7, 10.28--10.29, 13.2--13.3, 13.8--13.9, 13.11, 13.13, 13.15

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

What does ∃ mean? (491)

semantics

Explains the meaning of ∃ with a simple example.

Reading: §9.4

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

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

Fast Lecture 05

Date given: Tuesday 9th February 2016

Exercises for this lecture:

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.

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: 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

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

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)

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

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

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

Fast Lecture 06

Date given: Tuesday 23rd February 2016

Exercises for this lecture:

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

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

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

Two Things Are Broken (470)

quantification semantics

Explains how to translate sentences involving number into awFOL using quantifiers and identity.

Reading: §14.1

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

↔ : truth tables and rules (567)

translation

Mentions the truth-tables and rules of proof for the biconditional, ↔.

Variables (600)

translation syntax

Explains the role of variables in the formal language awFOL. Stresses that translations into English should not mention variables (e.g. 'there is an x such that ...' does *not* count as English for the purposes of this course).

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

∀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

Substitution of Equivalents (250)

meta

Statement of the substitution theorem. Suppose that φ, ψ and χ are sentences of awFOL. Suppose that φ is logically equivalent to ψ. Let χ[φ/ψ] be the result of replacing, in χ, zero or more occurrences of φ with ψ. Then the subsitution theorem says that χ[φ/ψ] is logically equivalent to χ.

Reading: §4.5, §10.3

Alternative textbook exercises (regular): 7.25

Alternative textbook exercises (fast): 4.31, 7.25

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

Fast Lecture 07

Date given: Tuesday 1st March 2016

Exercises for this lecture:

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

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

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

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

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)

More Records Than the KGB (780)

quantification translation

Identifies a problem translating some sentences involving comparisons into our formal language, awFOL.

Reading: §14.1, §14.3

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