CS 375 Logic and Theory of Computing

University of Kentucky
Department of Computer Science
CS 375 Logic and Theory of Computing
1.  Course Number/Name:  CS375, Logic and Theory of Computing
2.  Credits and Contact Hours:  3 credits, 3 contact hours
3.  Instructor:  assigned by the department
4.  Textbook:  Discrete Structures, Logic, and Computability, (4th Edition) J. L. Hein.
                a. Lecture notes.
5.   a.   Catalog Description: Topics in logic and discrete math aimed at applications in Computer Science.
             Propositional calculus: truth tables, logical relations, proofs, tautologies, soundness. Predicate
             calculus: variables, quantifiers, equivalencies. Models of computation: logic circuits, finite
             automata, Turing machines.
 b.   Prerequisites:  MA 113, CS 215, CS 275 and engineering standing.
 c.   Required course: Required 
6.  a.   Outcomes of Instruction:  The students will develop knowledge of a variety of  mathematical tools for the design and 
            analysis of algorithms and computer  programs. They will learn basic concepts of logic, proof construction, and reasoning
            with variables and quantifiers. They will learn about basic models of computation based on finite automata, grammars and
            Turing machines.
      Specifically students will have:
1.     an ability to reason with propositional theories;
2.     an ability to write predicate logic formulas, understand their precise formal meaning, and use them as problem specifications;
3.     a fluency in the elements of automata theory, regular grammars and regular expressions, and their uses;
4.     understanding of the relationship between formal models of computation and modern computers;
5.     understanding of the relevance of logic and theory of computation to the computer science curriculum;
6.     an ability to apply knowledge of computing and mathematics appropriate to the discipline;
7.     an ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices.
b.   Contributions to Student Outcomes (ABET Criterion 3  for Computer Science)













CS  375












3- Strongly supported   2 – Supported   1 – Minimally supported
 7.   List of Topics Covered:

1.     Preliminaries: set algebra, relations, functions
2.     Propositional logic
3.     Predicate logic
4.     Computing with Logic  
5.     Algebraic structures
6.     Regular languages, finite automata
7.     Context-free languages, pushdown automata
8.      Turing Machines