Person in charge:  () 
Others:  () 
Credits  Dept. 

7.5 (6.0 ECTS)  CS 
Person in charge:  () 
Others:  () 
This course will deepen into the general subjects of logic as a basic tool for computing.
Additionally, we will develop abilities in some application areas that will allow the student to quickly create systems for solving very diverse practical problems.
Special attention will be dedicated to logical programming and logical programming with constraints.
Estimated time (hours):
T  P  L  Alt  Ext. L  Stu  A. time 
Theory  Problems  Laboratory  Other activities  External Laboratory  Study  Additional time 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

9,0  0  6,0  0  6,0  8,0  0  29,0  
Review of propositional logic.
Algorithms: Resolution, DavisPutnamLogemannLoveland, DBB"s. Tools: Prolog, Chaff, DDB packages. Programming using translation into a SAT (satisfiability formula) and use of associated tools. Examples of applications: timetabling problems, etc.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

12,0  0  8,0  0  4,0  6,0  0  30,0  
Review of first order logic.
Algorithms: Resolution and constraints, automatic deduction. Resolutionbased methods: Logic programming, deductive databases.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

6,0  0  4,0  0  8,0  10,0  0  28,0  
Foundations: SLD resolution.
Optimisations: predefined data types, inputoutput. Designing declarative programmes. Advanced data structures in logic programming.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

9,0  0  6,0  0  6,0  9,0  0  30,0  
How to obtain flexibility and speed in expressing characteristic problems of logic programming, and efficiently using specialised resolvers for integers, real numbers, finite domains, etc.
CLP(X) and domains. Ways of reducing the search space. Logic problems with domain constraints. Example: resource allocation, schedules. Search for optimum solutions in CLP (Constraint Logic Programming). CLP(X) and domains, ways of reducing the search space. Logic problems with domain constraints. Example: schedules (revisited). Search for optimum solutions in CLP (Constraint Logic Programming).


T  P  L  Alt  Ext. L  Stu  A. time  Total  

4,0  0  4,0  0  4,0  4,0  0  16,0  
Some problems that can be represented in propositional logic and in First Order Logic.
Verification of circuits. Verification of cryptographic protocols. Representation of finite state systems.

Total per kind  T  P  L  Alt  Ext. L  Stu  A. time  Total 
42,0  0  28,0  0  28,0  37,0  0  135,0  
Avaluation additional hours  4,0  
Total work hours for student  139,0 
On average, 3 hours a week will be spent on theory and/or problems. The actual number of hours in any one week will not be fixed since this would render class schedules too inflexible. The same applies to classes of problems.
Students are encouraged to work on their own. The teacher will be present in the 2 hours of weekly lab classes. His or she will work in a consulting role and evaluate students" work as they tackle the exercises.
The theory grade will be based on the written exam and carry a weight of 60%.
The lab grade (40%) will be based on assessment of the successive submissions on lab class exercises. Four such assignments are envisaged. However, an optional one may also be set at the end of the term to give students the opportunity to improve their marks or to make up for a fail mark.
The course is fairly selfcontained and requires little in the way of previous knowledge.
Basic knowledge of logic is required at the level of the IL course. However, it should be noted that LI provides a broad review of these contents, albeit with a stronger orientation towards computing applications. It is desirable  though not essential  that students also have some knowledge of data structures and basic algorithms (Pred).