| Teachers | KAMIDE, Norihiro | |
|---|---|---|
| Grade, Semester | Year 1 1st semest [Department of Information and Electronic Engineering, Faculty of Science and Engineering] | |
| Category | Basic Major Subjects | |
| Elective, Credits | Requisites 2credit | |
| Syllabus Number | 3A111 | |
The contents of the lectures are summarized as follows:
(1) proof system and semantics for propositional classical logic (formulas, tautology, sequent calculus, valuation semantics, soundness theorem, completeness theorem, etc.),
(2) proof system and semantics for first-order classical logic (quantifiers, valid formulas, soundness theorem, completeness theorem, etc.),
(3) how to construct normal forms of formulas in propositional and first-order classical logics (conjunction normal form, disjunction normal form, prenex normal form, etc.),
(4) sets and functions (set, function, injection, surjection, bijection, etc.),
(5) ordered sets and lattices (pre-ordered set, linearly ordered set, lattices, etc.), and
(6) Boolean algebras (Boolean algebra, relationship between Boolean algebras and propositional classical logic, etc.).
The aim of this course is to understand the following items:
(1) proof system and semantics for propositional classical logic,
(2) proof system and semantics for first-order classical logic,
(3) normal forms of formulas in propositional and first-order classical logics,
(4) sets and functions,
(5) ordered sets and lattices, and
(6) Boolean algebras.
Students are evaluated by a term examination, some midterm examinations, and some quizzes.
| Kind | Title | Author | Publisher |
|---|---|---|---|
| Textbook | No textbook. The original slides and video contents are used. | ||
| References | No reference. The original slides and video contents are used. |
The slides of the lecture should be read. The video contents of the lecture should be viewed.
LMS is used in this course.
| 1 | Introduction: Outline of this course. Basic concepts of logic. |
| 2 | Propositional classical logic (1): Propositions. Formulas. Truth table. Valuation semantics. Tautology. |
| 3 | Propositional classical logic (2): Equivalent formulas. Conjunction normal form. Disjunction normal form. |
| 4 | Propositional classical logic (3): Sequent calculus. Proofs by sequent calculus. |
| 5 | Propositional classical logic (4): Soundness theorem. Completeness theorem. Cut-elimination theorem. |
| 6 | First-order classical logic (1): Quantifiers. Formulas of first-order classical logic. |
| 7 | First-order classical logic (2): Semantics. Valid formulas. Prenex normal form. Sequent calculus. |
| 8 | First-order classical logic (3): Godel's completeness theorem. Compactness theorem. Midterm examination. |
| 9 | Sets and functions (1): Sets. Cardinality. Operations on sets. |
| 10 | Sets and functions (2): Functions. Surjection. Injection. Bijection. |
| 11 | Sets and functions (3): Infinite sets. Countable sets. Uncountable sets. Diagonalisation argument. |
| 12 | Relations: Relation. Equivalence relation. Order. |
| 13 | Ordered sets and latices: Partially ordered sets. Totally ordered sets. Lattices. Boolean algebras. |
| 14 | History of logic and the origin of computer: Godel's incompleteness theorem. Church-Turing thesis. |
| 15 | Advanced topics: Non-classical logics and their applications to computer science. Term examination. |
