(reference only) A. Nerode and R.A. Shore, Logic for Applications, 2nd ed., Springer-Verlag, 1999.
(reference only) J.W. Floyd, Foundations of Logic Programming, 2nd ed., Springer-Verlag, 1987.
(reference only) W.F. Clocksin and C.S. Mellish, Programming in Prolog, 3rd ed., Springer-Verlag, 1987.
(reference only) R. Lalement, Computation as Logic, Prentice-Hall, 1993.
(reference only) David H. D. Warren, Logic Programming and Compiler Writing, Software Practice and Experience, Vol. 10, pp. 97-125, 1980.
(reference only)朱水林, 現代邏輯入門, 九章, 台北, 1997.
(reference only)莫紹奎, 數理邏輯概貌, 亞東, 台北, 1991.
(reference only)Nils J. Nilsson, Logic and artificial intelligence, Vol. 47 (1991) of the journal Artificial Intelligence
Logic is the science of convincing yourself.
邏輯學是一門說清楚、講明白的學問。
Logic speaks the unspoken words.
This course is an introduction to logic for computer science students. There are two purposes in studying logic: firstly, logic teaches us how to think reasonably and efficiently. A reasonable and efficient brain is indispensible in any advanced study as well as in our daily life. Secondly, logic is the foundation of the science of computer programming. This course will prepare the students for future, advanced study in computer sciecnes.
Logic has applications in diverse fields in computer science, from the low-level chip design to the high-level knowledge systems. Logic permeates in all branches of computer sciences, including programming languages, artificial intelligence, expert systems, hardware design, database, formal language theory, etc.
Logic is the study of inference. We have two broad areas in this study: propositional logic and predicate logic. The formal is easier but more confined. The latter is more complicated but applicable to a larger extent.
We will start from our intuition of everyday reasoning to establish the logic formulas and their truth values. Then we will study the tableaux method, the natural deduction method, the sequent calculus, and, finally, the axiomatic approach to propositional logic and resolution. During our study, we will prove several important results of the axiomatic system, namely, the soundness, consistency, and completeness of the system. Important computer applications of the axiomatic approaches, such as the logic gate layout of IC design, the type system for the ML programming language and program correctness proof, will also be presented.
We will also discuss the predicate logic, its axiomatic system, resolution method. If time permits, we will study Godel incompleteness theorem.
The following is the outline of this course:
Homework will be announced during class as well as posted on this web page.
A son and a daughter from each of the A, B, and C families are going to have their weddings together. Of course a bride and her bridegroom should not come from the same family. We only know that the son from family A does not marry the daughter from family B. Now you are asked who and who get married.
甲乙丙丁四人上午輪流在實驗室作實驗﹝每次只有一人在實驗室裡﹞，到了下午老師發現 實驗的器材壞了，於是老師問他們四人發生了甚麼事。
甲說：實驗的器材不是我們弄壞的。
我進實驗室時，乙剛好出來。
當我離開實驗室時，實驗的器材還是好的。
乙說：最後進實驗室的是我。
當我離開實驗室時，實驗的器材還是好的。
丙說：我是第三個進入實驗室的人。
當我離開實驗室時，實驗的器材還是好的。
丁說：我是第二個進入實驗室的人。
當我進入實驗室時，實驗的器材已經損壞了。
老師察言觀色，知道四人的每一句話都是謊言。
那麼到底是誰弄壞了實驗的器材？
答案：甲或是丁弄壞了實驗的器材。
甲乙丙丁四人上午輪流在實驗室作實驗﹝每次只有一人在實驗室裡﹞，到了下午老師發現 實驗的器材壞了，於是老師問他們四人發生了甚麼事。
甲說：實驗的器材不是我們弄壞的。
我進實驗室時，乙剛好出來。
當我離開實驗室時，實驗的器材還是好的。
乙說：最後進實驗室的是我。
當我離開實驗室時，實驗的器材還是好的。
丙說：我是第三個進入實驗室的人。
當我離開實驗室時，實驗的器材已經損壞了。
丁說：我是第二個進入實驗室的人。
當我離開實驗室時，實驗的器材已經損壞了。
老師察言觀色，知道四人的每一句話都是謊言。
那麼到底是誰弄壞了實驗的器材？
答案：This problem is wrong. Can you see why?
Please prove that 1 + 1 = 2.
Two questions that I mentioned in the class.
有五位小姐排成一列 所有的小姐穿的衣服顏色都不一樣 所有的小姐姓也不同 所有的小姐都養不同的寵物,喝不同的飲料,吃不同的水果 錢小姐穿紅色的衣服 翁小姐養了一隻狗 陳小姐喝茶 穿綠衣服的站在穿白衣服的左邊 穿綠衣服的小姐喝咖啡 吃西瓜的小姐養鳥 穿黃衣服的小姐吃柳丁 站在中間的小姐喝牛奶 趙小姐站在最左邊 吃橘子的小姐站在養貓的隔壁 養魚的小姐隔壁吃柳丁 吃蘋果的小姐喝香檳 江小姐吃香蕉 趙小姐站在穿藍衣服的隔壁 只喝開水的小姐站在吃橘子的隔壁請問那位小姐養蛇?
IT IS RECOMMENDED THAT YOU USE CHINESE TO ANSWER QUESTIONS IN THE EXAMS. YOU MAY ALSO USE ENGLISH IF NECESSARY. DO NOT USE ANY OTHER LANGUAGES.
Midterm: April 13, 2004, Tuesday, 10-12.
Final: June 22, 2004, Tuesday, 10-12.
There will be no programming assignments in this course.
There will be two exams (35% each) and paper homework (30%).
