This class aims to provide students with the basic knowledge of the logical aspects of computer science such as Boolean algebra, automata and formal grammar, recursive functions, and Turing machine.
It is hoped that students will be familiar with the Boolean operation and be able to find a standard form of a given Boolean expression as well as to make it more simple one.
They will atain a comprehensive understanding of formal grammar and recursive functions as well as the action of automata and Turing amchine deep enough to design automata and Turing machine for given purpose.
We will read the text by turns. A tentative schedule and topics is given below. The actual topics covered may vary from week to week.
１．Guidance and Course Introduction; Preview and Overview of Course Content and Main Topics
Explanation of course goals, classroom management and methods of evaluation; introduction to and outline of course content and reading schedule
２．Partially ordered set; partial order, upper bound, lower bound, order isomorphism
３．Axiom System of Boolean Algebra; distributive laws, complement, duality principle
４．Boolean Functions and Combinational Circuits; Boolean variables, AND・OR・NOT circuit
５．Boolean Logical Expressions and Reduction; primary disjunctive normal form, primary conjunctive normal form, Karnauge map
６．The Representation Theorem for Boolean Algebras; atom, power set, Boolean isomorphism
７．State Transitions of Automata; alphabet, state transition function, the initial state, acceptance conditions
８．Accepted language of Automata; state transition diagram, analysis and composite of automata
９．Formal Grammar; regular grammar, context sensitive grammar, context free grammar
１０．Formal Grammar and Automata; finite automata, non-deterministic automata, pump principle
１１．Recursive Functions; primitive recursive functions, regularity condition
１２．the Calculation of Recursive Functions; double induction
１３．the Action of Turing Machines; instantaneous description, transition function, halting, divergence, resolution, the number of computation steps
１４．Basic Turing Machines; composite, diagram
１５．the Classes of Computational Complexity; Turing computable functions, time complexity, polynomial time, P and NP