Math and Logic for Cognitive Science
COGS-Q250 §7146, Fall 2011

General Information

Lecture Monday and Wednesday 9:30am–10:45am, Psychology PY113
Lab Friday 9:05am–9:55am, Ballantine Hall BH108
Instructor wren ng thornton
Email (be sure to include "Q250" in the subject line)
Office Hours MTWR 11:10am–noon, F 10:10am–noon, Eigenmann EG807
(Do note that Eigenmann 8th floor is locked noon–1:00pm)
Or by appointment
Teaching Intern (UTI) James Torre
Office Hours By Appointment
Study Sessions Wednesday 7:00pm–, Wells Library West Tower

Course Description

Cognitive science aims to provide rigorous explanations of the processes that underlie intelligent behavior. To this end, cognitive scientists employ a wide variety of tools and concepts from logic and various branches of mathematics. In this course, we explore a range of topics in math and logic that are particularly important for cognitive science: propositional and predicate logic, automata theory, and probability theory.

For each topic, our goal is twofold: first, to understand the basic mathematical and conceptual underpinnings; second, to understand the relevance for cognitive science. To address the latter, we consider each mathematical topic as it fits within a certain area of cognitive science. Thus, we consider logic and automata theory as they relate to computational models of the mind, and probability theory in the context of Bayesian modeling. Ideally, then, students will come away from this course with two things: (1) a skill set of basic mathematical tools and (2) appreciation and enthusiasm for how these tools can be used to model and understand the mind. The material for the course is self-contained and no prerequisites beyond a sound high school mathematics background are needed.

Class Policies

Participation and Labs

All students are expected to attend every class and lab section. Tardiness and unexcused absences will decrease the lab participation grade.

Labs will begin with an opportunity for students to ask questions related to material covered in the preceding week. Then, there will be a short in-class quiz related to that week's material. Each student's lowest quiz grade will be dropped. The rest of the lab will then be devoted to presentation and discussion of materials designed to supplement that week's lectures, including computer demonstrations, additional problems that we can work through together, etc.


There will be ten homework assignments, given approximately weekly. Homeworks will be assigned in class on Wednesday and will be due at the beginning of class on the following Monday, correction, Wednesday. The assignments are mandatory. For each homework assignment not handed in, the final course grade will be reduced by a full letter grade. Do not skip the assignments.

Assignments shall be emailed to both the instructor and the UTI, with "Q250" in the subject line, as a PDF file named q250_hwN_lastname.pdf where N is the assignment number and lastname is your last name. If you cannot create the mathematical symbols for a PDF, then scans of handwritten documents may be accepted; however, PDFs are preferred. Only these file types will be accepted. Do note that this means I will not accept Word, RTF (rich text format), or HTML files, because they are often garbled in transit between different machines and different operating systems.

Late Work

To reiterate, assignments will not be accepted late for any reason. Please note that as a result of this policy, there is no reason to come to me with excuses for late assignments, however valid, unless you are asking for, and believe you qualify for, an Incomplete.


There will be three exams, covering, in order, the three major topics of the course:

  1. discrete mathematics, automata theory, and theory of computation
  2. logic, reasoning, and proofs
  3. probability theory, and Bayesian models

The exams will be distributed more or less evenly throughout the semester, meaning that there will be an exam once every month or so. The third exam will be administered during the final exam period, but will be the same length as the other two exams.


Note that for each homework assignment not handed in, the final grade will be reduced by a full letter grade (after performing the above calculation). Do not skip the assignments.

Academic Misconduct

Academic misconduct is not allowed in this course. The Indiana University Code of Student Rights, Responsibilities, and Conduct defines academic misconduct as "any activity that tends to undermine the academic integrity of the institution . . . Academic misconduct may involve human, hard-copy, or electronic resources . . . Academic misconduct includes, but is not limited to . . . cheating, fabrication, plagiarism, interference, violation of course rules, and facilitating academic misconduct" (II. G.1-6).

Students with Disabilities

Students who need an accommodation based on the impact of a disability should contact me to arrange an appointment as soon as possible to discuss the course format, to anticipate needs, and to explore potential accommodations.

I rely on Disability Services for Students for assistance in verifying the need for accommodations and developing accommodation strategies. Students who have not previously contacted Disability Services are encouraged to do so (812-855-7578;


Select readings will be given throughout the semester. These are given to provide a deeper or alternative description of the topics of the course.

Critchlow and Eck, Foundations of Computation (version 2.3.1)

This is a free textbook available online. The first chapter is on logic and proofs, which is what we'll be reading from. The remaining chapters cover set theory and automata theory, but since they are presented in a different order than we will be covering them and for a computer science audience, they may not be easy to read through. Sections which I think may be especially hard are optional, though you should try reading them anyways (and should definitely skim them).

James Hein, Discrete Structures, Logic, and Computability (Second or third editions)

This is an alternative textbook. It's fairly expensive, but it covers everything in great enough depth to spend a semester (or more) on each of the three major topics of the course. Perhaps more importantly, the Student Study Guide is freely available online. This is the book I learned from and it is very clearly written, unlike many other textbooks covering the same topics. I will not be assigning readings from this book, but I can provide suggestions on request.

Frank Pfenning, Automated Theorem Proving (draft of Spring 2004)

These are class notes from the ATP class at Carnegie Mellon University. As mentioned on the title page, it is just a draft and should not be cited or distributed. However, it gives a good and thorough introduction to natural deduction and sequent calculus.

Charles M. Grinstead & J. Laurie Snell, Introduction to Probability (AMS published version)

This is one of many introductions to probability theory. The AMS published version has since been made available for download. A more recent version has been made and is freely redistributable; but I haven't had a change to update the pages and section numbers for the new version yet.


I'll try to upload slides before class; and will definitely upload them by after class. The readings in parentheses are optional but recommended. Reading the answers to the homeworks is mandatory.

Disclaimer: This syllabus is subject to change. All important changes will be made here in writing and mentioned in class, with ample time for adjustment.

Date Topic Readings/Assignments/Notes
Week 1: Sets and Relations
M 29 Aug Course introduction
Sets and set operations
Relations (part I): Introduction
(Read FOC §2.1)
W 31 Aug Relations (part II): Equivalences and orderings Read FOC §§2.4, 2.7
HW 1 given
F 2 Sep Equational reasoning
Graph theory
Read Introduction to Graphs
Week 2: Functions / Graph theory
M 5 Sep No Class: Labor Day  
W 7 Sep Functions (Relations, part III)
Graphs: Introduction
HW 1 due [answers]
HW 2 given
F 9 Sep Practice with functions  
Week 3: Automata theory
M 12 Sep Formal languages
Regular languages
HW 2 due [answers]
Read FOC §§3.1–3.6
W 14 Sep Finite state machines HW 3 given
F 16 Sep Practice with regular expressions wren away for ICFP
Week 4: Automata theory / Theory of computation
M 19 Sep Guest Lecture (Alex Rudnick):
Context-free languages / PDAs
wren away for ICFP
(Read FOC §§3.7, 4.1)
W 21 Sep Guest Lecture (Robert Rose):
Turing machines
Church–Turing hypothesis
The Halting problem, and decidability
wren away for ICFP
Read FOC §§5.1–5.3
F 23 Sep ... wren away for ICFP
Week 5: Automata theory
M 26 Sep Review HW 3 due [answers, updated 5 Oct]
W 28 Sep Review  
F 30 Sep First Exam [answers]
Last-last year's: review, exam [answers]
Last year's: practice [answers], exam [answers]
And don't forget Jim Hein's study guide
Week 6: Introductory logic
M 3 Oct No Class: wren unexpectedly sick  
W 5 Oct No Class: wren unexpectedly sick  
F 7 Oct (Classical) propositional logic Read FOC §§1.1
HW 4 given
Week 7: Boolean algebra, and some lambda calculus
M 10 Oct (Classical) propositional logic, continued.
Normal forms
Boolean algebras
Read FOC §1.2, 2.2
W 12 Oct Untyped lambda calculus (LC)
Simply typed lambda calculus (STLC)
slides written up after the fact
HW 4 due [answers]
A LC tutorial
Another LC tutorial
Alligator Eggs (a game version of LC)
Wikipedia on STLC
HW 5 given
F 14 Oct Practice with propositional logic
Practice with lambda calculus
Week 8: Intuitionism, constructivism, and type theory / Predicates and quantifiers
M 17 Oct Giving types for terms, terms for types
Russell's paradox
[Another LC and STLC tutorial, ch.1–2]
W 19 Oct Curry–Howard correspondence
The Barendregt cube

Predicates and quantifiers
Read FOC §1.4
Tarski's World Applet
HW 5 due [answers]
HW 6 given
F 21 Oct Practice with predicates and quantifiers  
Week 9: Proof theory
M 24 Oct (naive) Natural deduction [Examples] Read ATP, chapter 2
Read FOC §§1.5–1.7
W 26 Oct Sequent-style natural deduction HW 6 due [answers]
HW 7 given
F 28 Oct Practice with proofs  
Week 10: Induction/recursion
M 31 Oct Recursive types (Peano numbers, lists, trees)
Recursive functions
Read FOC §1.8
W 2 Nov Inductive proofs Read FOC §§1.9–1.10
HW 7 due [answers]
HW 8 given
F 4 Nov Practice with inductive proofs  
Week 11: More Proofs
M 7 Nov Review, explanation of HW 8  
W 9 Nov Review, lambda calculus HW 8 due [answers]
F 11 Nov Second Exam [answers] [handout]
Last year's: practice [answers], exam [answers]
Week 12: Probability theory
M 14 Nov Probability spaces, events, random variables Read ITP §§1.1–1.2
W 16 Nov Conditional probability Read ITP §§4.1, 4.3
F 18 Nov The Monty Hall problem HW 9 given
Week 13: Probability theory and independence
M 21 Nov Discussion of the second exam Read Helping doctors and patients
make sense of health statistics
W 23 Nov No Class: Thanksgiving Recess  
F 25 Nov No Class: Thanksgiving Recess  
Week 14: Independence and graphical models
M 28 Nov Combinatorics Read Bayesian Models of Cognition
Read ITP §§3.1–3.2
W 30 Nov Conditional independence
Graphical models [example]
HW 9 due [answers]
Read ITP §§6.1–6.2
(Read Murphy's GM introduction)
F 2 Dec Optional Early Second Exam Redux
Review for the second exam redux
HW 10 given
Week 15: Dead Week
M 5 Dec HW 10 discussion
Review for the second exam redux
W 7 Dec Review for the final HW 10 due [answers]
F 9 Dec Second Exam Redux [answers]
[handout 1] [handout 2]
Week 16: Final Exam
W 14 Dec Final Exam
(The exam slot is 8:00am–10:00am; however, we will meet 9:05am–9:55am)
Last year's: practice [answers]