Academic year 2013-14
Computational Logic
| Degree: | Code: | Type: |
| Bachelor's Degree in Computer Science | 21422 | Compulsory subject, 2nd year |
| Bachelor's Degree in Telematics Engineering | 22606 | Optional subject |
| Bachelor's Degree in Audiovisual Systems Engineering | 22672 | Optional subject |
| ECTS credits: | 4 | Workload: | 100 hours | Trimester: | 3rd |
| Department: | Dept. of Information and Communication Technologies |
| Coordinator: | Héctor Palacios |
| Teaching staff: | Theory: Héctor Palacios Practice: Héctor Palacios Seminar: Héctor Palacios, Filippos Kominis |
| Language: | Readings: English, Spanish Theory: Héctor Palacios (Spanish) Practice: Héctor Palacios (Spanish) Seminar: Héctor Palacios (Spanish), Filippos Kominis (Spanish/English) |
| Timetable: | |
| Building: | Communication campus - Poblenou |
Computational Logic is a compulsory subject offered in the degree in computer engineering as part of the second course. The course covers deductive and algorithmic aspects of both propositional logic and predicate logic, as well as their computational problems. The subject has a theoretical and practical component. Within the theoretical component the emphasis is on understanding the concepts on an intuitive level and the use of mathematical language.
The course consists of three main activities: lectures, seminars and laboratories. In theory classes we introduce the formal concepts and provides examples of its application. In seminars students solve small problems. Each problem corresponds to the concepts introduced in class theory. In laboratories are problems of greater complexity and more computational so the students have the opportunity to put into practice the concepts learned.
Objectives
The aim of the course is to understand deductive and algorithmic aspects of propositional and predicate logic, as well as their computational problems. Also, students should develop skills to understand the differences between the various types of logic and identify the best formalism to specify different problems and to solve them computationally.
The background for the pursuit of the subject are certain concepts acquired basic math in secondary compulsory during the first three courses of studies. In particular
prior knowledge required for the course are:
• basic algebraic notions: functions, sets and operations elementary on sets, equivalence ratios.
• mathematical logic basics: relations, logical connectives.
• Basic arithmetic.
• Ability to understand and write basic math to elementary expressions.
The main objective of the course is to provide students with the fundamental ideas related to deductive and algorithmic aspects of propositional and predicate logic.
|
Transversal skills | Specific skills |
|---|---|
|
Instrumental 1. Ability to reason at an abstract level 2. Cognitive Skills 3. Common sense Interpersonal 4. Communication Competence Systemic. 5. Ability to identify the best methodology to solve a problem. 6. Ability to solve such problems by combining nontrivial new and known elements. 7. Ability to generate other ideas
|
1. Ability to understand on an intuitive and formal level various aspects of the propositional and predicate logic: syntax, semantics and its application to different computer problems. 2. Ability to apply the knowledge |
The continuous assessment takes into account each of the three activities that constitute the subject: lectures, labs and seminars:
T: evaluation of the theory through a final exam
L: laboratory evaluation by programming practices.
S: evaluation of the seminars
In the continuous assessment, you must pass the laboratory and also approve the sum of the evaluation of the seminars plus the final exam. That is,
L must be approved.
T + S has to be approved.
Final Grade = 0.6 * t + 0.2 * L + 0.2 * S
The theory exam will evaluate the topics developed in theory and seminars class. It is an individual written exam that assesses all the skills developed throughout the course.
In laboratories, do a series of practices that test the ability of students to apply the theory in the form of computer programs. The practices are made as a couple, so that the students have to cooperate and communicating to solve problems.
Before each seminar will present problems for students to solve them before the session, as a preparation. These problems correspond to concepts or knowledge of theory covered in class. Students will be asked to present their solutions to the blackboard or in writing. As part of the evaluation will be two quizzes, and two writing tasks to deliver.
Failure to pass the course, the student is entitled to a call in July, but only if they had approved the laboratory (L). The note of this call will be obtained on a test.
Note July = 1.0 * T +0 +0 * L * S (if had approved L)
1. Logic: What is it?, history, uses in computing. Notion of formal derivation. Examples of mathematics.
2. Propositional logic.
1. Formal language, formulas.
2. Modeling.
3. Proof Theory: natural deduction system for the logic propositional. Proof, derivability.
4. Semantics: truth tables and valuations. Satisfiability and Logical entailment. Tautologies.
5. Normal Forms. Resolution. Horn Clauses. SAT and SAT solvers.
3. Predicate logic.
1. Motivation. Formal language, formulas.
2. Modeling.
3. Proff theory for predicate logic: natural deduction. Testing, derivability.
4. Semantic interpretations of formulas of predicate logic.
5. Satisfiability and Logical Consequence. Resolution y predicate logic.
The usual process of learning begins with a theory session where you have certain theoretical and practical foundations. This activity is done with the entire group of students. The student will need to supplement this activity with a reading of his own notes and materials additional teacher has provided. For example, a theory session of two hours will require additional work outside the classroom than 1 hour from the student.
Later there will be some exercise sessions in which the student uses the concepts and techniques presented at the meeting of theory,
by solving small problems. For the first exercise session solutions can be provided, but otherwise no. The aim is to consolidate
the basics so that later can solve problems more complexity. This activity takes place in
four small groups of students.
The next step in the learning process is the practice session. It proposes some bigger problems that require the integration of different concepts and techniques. This activity is done in pairs, in groups of about 20 students, and it is assumed that continues outside the classroom.
Theory are planned 18h, 12h seminar, and 6h in classroom practice, although it continues outside the classroom.
Sources of information for learning. Bibliography (paper and electronic support)
Logic in Computer Science
Michael R.A. Huth, Mark D Ryan
Cambridge University Press. 2nd edition, 2004.
We cover the first part, pp. 1-131. Except for Section 1.6, that we will make
differently (using the DPLL method).
Sources of information for learning. Further reading (paper and electronic support)
Mathematical Logic for Computer Science
Mordechai Ben-Ari
Springer (2003).
Logic and its Applications
Edmund Burke, Eric Foxley
Prentice Hall (1996)
Sources of information for learning.
Bibliography of reinforcement (paper and electronic support)
Web of subject
Notes. Collection of exercises (with solutions)
Practices Statements
Teaching resources. Materials and tools to support
http://www.diveintopython.org
http://www.swi-prolog.org/