Discrete mathematics: logical foundations of computing science [ LINGI1101A ]

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

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 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 .

• 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