Introduction to Logic

Logic has been inherited by us from philosophy through mathematics. Now, it is an important part of computer science, with applications in program verification, the semantics of programming languages, automated theorem proving, logic programming, and the design of artificial intelligence (AI) tools. In this course, the students will be familiarized with the fundamentals of logical reasoning, in particular propositional and predicate logics. Some applications of these logics in computer science and artificial intelligence, such as logic programming, will be discussed.

Propositional Logic. Syntax and Semantics. Connectives and Truth Tables. Disjunctive and Conjunctive Normal Forms. Resolution Calculus. Decision Algorithms. Predicate Logic. Terms, Formulas, and Deductions. First-Order Semantics. Prenex Formulas. Herbrand and Skolem Normal Forms. Predicate Resolution Calculus. Undecidability of General Predicate Logic.

By the end of this course, students should be able to formalize everyday reasoning into a formal language and see if the argument follows logically. They should be able to deduce logical conclusions from any assumptions. The wrong steps in the flawed proofs should be spotted and corrected if possible, and a reason should be demonstrated as to why a repair is not possible.

By the end of this course, students should be able to formalize everyday reasoning in a formal language and determine whether the argument follows logically. Students should be able to deduce logical conclusions from any assumptions. The wrong steps in the flawed proofs should be spotted and corrected if possible, and a reason should be demonstrated as to why a repair is not possible.

• Have learned the vocabulary and rules of Propositional and Predicate Logic | Know/Knowledge Outcome
• Understand mathematical proofs and their formalizations rigorously | Comprehend Outcome
• Prove mathematical and logical theorems by using the Resolution Calculus | Apply Outcome
• Formalize mathematical and everyday reasonings in a formal language | Analysis Outcome
• Spot possible pitfalls of proofs or evaluate their correctness | Evaluate Outcome
• Design logical solutions for existing as well as new problems in the real world | Create/synthesize Outcome

• W. Ertel (2025, 3^rd ed.), Introduction to Artificial Intelligence, Springer.
• U. Schöning (2008), Logic for Computer Scientists, Birkhäuser.

• Mordechai Ben-Ari, “Mathematical Logic for Computer Science,” Springer (2012, 3rd ed.)
• Ivan Bratko, “PROLOG Programming for Artificial Intelligence,” Addison-Wesley (2011, 4th ed.)