Math and Logic for Cognitive Science
COGSQ250 §7146, Fall 2011
General Information
Lecture  Monday and Wednesday 9:30am–10:45am, Psychology PY113 
Lab  Friday 9:05am–9:55am, Ballantine Hall BH108 
Webpage  http://cl.indiana.edu/~wren/COGS_Q250_2011F/ 
Instructor  wren ng thornton 
wrnthorn@indiana.edu (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 
jtorre@indiana.edu  
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 selfcontained 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 inclass 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.
Assignments
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.
Exams
There will be three exams, covering, in order, the three major topics of the course:
 discrete mathematics, automata theory, and theory of computation
 logic, reasoning, and proofs
 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.
Grading
 10% Participation and Lab Quizzes
 30% Homework Assignments (3% each, ×10)
 60% Exams (20% each, ×3)
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, hardcopy, 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.16).
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 (8128557578; http://www.indiana.edu/~iubdss/).
Readings
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.
Schedule
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):
Contextfree 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]
Lastlast 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  Sequentstyle 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) [handout] Last year's: practice [answers] 