Discrete mathematics: logical foundations of computing science [ LINGI1101 ]

> https://icampus.uclouvain.be/claroline/course/index.php?cid=ingi1101

Within SINF1BA : LSINF1250

Within FSA1BA : LFSAB1101, LFSAB1102, LFSAB1401, (LFSAB1301, LFSAB1201, LFSAB1202)

The prerequisite(s) for this Teaching Unit (Unité d’enseignement – UE) for the programmes/courses that offer this Teaching Unit are specified at the end of this sheet.

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 Internet-based 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 real-life 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 real-world 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”.

• short test during the semester
• written exam

• 2h of lecture / week
• 2h of exercise sessions / week

• Preliminaries: sets, relations, and functions; formal systems.
• Mathematical logic:
  • proposition calculus -- syntax, semantics, proof theory;
  • first-order predicate calculus -- syntax, semantics, proof theory, resolution and refutation;
  • first-order 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.

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,

Background :

• Elementary discrete mathematics (functions, sets, ...)
• Use of different techniques of mathematical proof