[前へ戻る]
   

 授業科目
 Course Title
数理論理特論
Mathematical Logic 
 担当者
 Instructor
教授   阿部 吉弘  後学期 水曜日2時限
 単 位
 Credit
2

関連するディプロマポリシー Related Diploma Policy
時代の課題と社会の要請に応えた専門的知識と技能/Expert knowledge and skills to address the issues of the age and the demands of society
 
到達目標 Target to be Reached
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 attain 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.


 
授業内容 Course Content
 We survey the basic facts in the computer science relating to Mathematical Logic.
Specificcaly, we treate the following items:
  1.Boolean algebra
  2.Automata
  3.formal grammar
  4.recursive function
  5.Turing machine
Every subject is restricted in the elementary level and the main purpose is to offer the students the basis for further study.
 
授業計画 Course Planning
 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.
1.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

2.Partially ordered set; partial order, upper bound, lower bound, order isomorphism

3.Axiom System of Boolean Algebra; distributive laws, complement, duality principle

4.Boolean Functions and Combinational Circuits; Boolean variables, AND・OR・NOT circuit

5.Boolean Logical Expressions and Reduction; primary disjunctive normal form, primary conjunctive normal form, Karnauge map

6.The Representation Theorem for Boolean Algebras; atom, power set, Boolean isomorphism

7.State Transitions of Automata; alphabet, state transition function, the initial state, acceptance conditions

8.Accepted language of Automata; state transition diagram, analysis and composite of automata

9.Formal Grammar; regular grammar, context sensitive grammar, context free grammar

10.Recursive Functions; primitive recursive functions, regularity condition

11.the Calculation of Recursive Functions; double induction

12.the Action of Turing Machines; instantaneous description, transition function, halting, divergence, resolution, the number of computation steps

13.Basic Turing Machines; composite, diagram

14.the Classes of Computational Complexity; Turing computable functions, time complexity, polynomial time, P and NP

 
授業運営 Course Management
 The student on duty explains the content of the text. The teacher in charge ask questions suitably to check his understanding. It is hoped that other students ask questions as well so that every student make deeper understanding. Students not in duty should have read the text.
 
評価方法 Evaluation Method
 Assessment will be based on the performance of the lecture in charge (80 %) and homework (20 %).
 
オフィスアワー Office Hour (s)
 After class or appointment.
 
使用書 Textbook (s)
Tanaka, Hisao『Introduction to Computational Logic』The fifth edition[shokabo]2008


 
 
 
[前へ戻る]