Proofs for Predicate Logic

Propositional calculus (Propositional logic)

Translation

Circuits

Equivalences

Boolean Algebra

Canonical Forms

Predicate Logic

Proofs for Propositional Logic

English Proofs

Set theory

Modular arithmetic

Primes

Greatest Common Divisor (GCD)

Euclidian Algorithm

Modular Equations

Modular Exponentiation

Induction

Strong Induction

Recursively Defined Functions

Recursively Defined Sets

Set (mathematics)

Structural Induction

Relation (mathematics)

Nondeterministic Finite Automata (NFA)

More Structural Induction

Directed Graphs

Relating DFAs, NFAs, and REs

Regular expression

Finite State Machine (FSM)

Limitations of DFAs, NFAs, and REs

Context-Free Grammar (CFG)

FSM Minimization

CSE 311 Foundations of Computing I University of Washington Autumn 2021 CSE 311 introduces theoretical computer science, the theory background necessary for other CSE courses, and how to construct rigorous, formal arguments. Topics include logic, set theory, modular arithmetic, induction, regular expression, and relations.  1. Teach you the theory background needed for other CSE courses
    – only topics used in many areas of CSE
1. Teach you how to make and communicate rigorous and formal arguments
    – want to know for certain that systems work
1. Introduce you to theoretical CS
    – may be the only theory course you take  There is no required text for the course. For the first 6-7 weeks of the course, the following textbook can be useful: Rosen, Discrete Mathematics and Its Applications, McGraw-Hill. (Course materials will reference problem numbers from the 6th edition, but more recent versions include the same material.) It should be available through the bookstore and on short-term loan from the Engineering Library.

On occasion, there may be required readings during the course when there is insufficient time to fully cover the material during lecture. If this occurs, the readings will be posted on the web site and students will be notified of the reading via email or the message board.

CSE 311 Foundations of Computing I

Mathematical Foundations

Theoretical Computer Science

Proofs for Predicate Logic

1 courses cover this concept

CSE 311 Foundations of Computing I