Within SINF1BA : LSINF1250
Within FSA1BA : LFSAB1101, LFSAB1102, LFSAB1401, (LFSAB1301, LFSAB1201, LFSAB1202)
Part I: Propositional logic and predicate logic
 Propositional logic (syntax, semantics, proofs)
 Predicate logic (quantifiers, bound and free variables, proofs) and application to algorithm analysis
 Set theory and application to formal system specification (Z notation)
 Relations and applications in computer science (relational databases, overriding, binary relations, ')
 Functions and lambda calculus
Part II: Discrete structures
 Graphs (basic concepts, paths and connectivity)
 Applications of graphs, e.g., to model social networks (ties, homophily, closure)
 Graphs and properties of graphs used to model Internetbased networks
 Introduction to game theory
Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
 AA1.1, AA1.2
 AA2.4
Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
 S1.I1, S1.G1
 S2.2
Students completing this course successfully will be able to
 convert ordinary language statements into logical expressions using the syntax and semantics of propositional or predicate logic
 use rules of inference to construct proofs in propositional or predicate logic
 describe how symbolic logic can model reallife situations , such as those encountered in the context of computing ( eg analysis algorithms )
 identify and define precisely the basic concepts of graphs and trees providing contextualized examples that highlight these concepts
 explain various methods of graph paths
 model various realworld problems encountered in computer using the appropriate forms of graphs and trees, such as social networks and the Web
 explain the key concepts of the theory of games ( game type, the type of policy agents ) using appropriate examples
Students will have developed skills and operational methodology. In particular, they have developed their ability to
 define and interpret concepts with rigor and precision
 avoid misinterpretation and detect errors in reasoning .
The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
 Preliminaries: sets, relations, and functions; formal systems.

Mathematical logic:
 proposition calculus  syntax, semantics, proof theory;
 firstorder predicate calculus  syntax, semantics, proof theory, resolution and refutation;
 firstorder theories models, consistency, inclusion, extension, etc.
 Equational theories: equality, partial orders, lattices, groups.
 Discrete structures on the Internet: graphs and graph properties, giant components, strong and weak links, triadic closure, structural balance, balance theorem, structure of the Web, PageRank, power laws, the long tail.
Applications to various domains : program verification, specification of abstract data types, automated reasoning, expert systems, robotics, databases, parsing, etc.
 2h of lecture / week
 2h of exercise sessions / week
 short test during the semester
 written exam
Background :
 Elementary discrete mathematics (functions, sets, ...)
 Use of different techniques of mathematical proof
Slides on icampus
Books :
 Introductory Logic and Sets for Computer Scientists by Nimal Nissanke
 Networks, Crowds and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg,