Main definitions (in swedish) overhead

Goals of the course

The goal of this course is first to present some basic mathematical concepts that are common to mathematics and computer science: basic set theory, theory of relations, inductive definitions and proofs. We then analyse more in details two mathematical theories, which have important applications

• propositional calculus, and boolean algebras

• finite automata

For computer science, the tools presented in this course have the following applications (among others)

• routing and connectivity: graph theory

• compilers: regular expressions, automata, and formal languages

• speech understanding: formal languages

• circuit design: propositional logic and boolean algebra

• databases: relational algebra

For mathematics, this course can be seen as an introduction to mathematical logic, and provides tools helpful in most part of mathematics (universal algebra, algebra, topology, functional analysis,...)

Contents of the course

I will follow chapters 1,2,3 and 4 (first part of the course)

Then I will present proposition calculus (chapter 6) and boolean algebra (section 10.2) and, if time allows, either some part of section 10.5 or more about the problems of simplifying boolean formulae (Quine-McCluskey Procedure)

I will finish with chapter 11 (Regular Languages and Finite Automata)

Exercises

• March 28-31: ps;
• April 4-7: ps;
• April 11-14: ps;
• April 27-28: ps;
• May 2-5: ps;
• May 9-12: ps;
• May 16-19: ps;
• May 23-26: ps;
• May 29-30: ps;

Homeworks

• First Homework (the deadline is Friday, May 12): ps

Text book

• James L. Hein, Discrete Structures, Logic, and Computability. Boston: Jones and Bartlett, 1995. (866 pages)

  Errata (list of typos) for Discrete Structures, Logic, and Computability

What has been covered in the courses

• week 1
• week 2
• week 3
• week 4
• week 5
• week 6
• week 7
• week 8
• week 9

Additional reading

• Regular Expressions and Automata using Haskell

• Computation and Formal Systems

  One can find lecture notes on Relations, Graphs, Finite Automata, Propositional Logic, with computer science oriented motivations

• Course on Software verification

  One can find lecture notes on Floyd-Hoare Logic

• The Programming Logic Group
• The Formal Methods Group home page
• On the historical background of Propositional Calculus: ARISTOTLE'S SYLLOGISM: LOGIC TAKES FORM, by Jordana Wiener.

Latest exams

• exam (1999): ps and correction: ps
• testexam: ps

Communications