Foundations of Semantic Technologies: Recommended reading

[EM] Elliot Mendelson "Introduction to Mathematical Logic", 4th edition, published by Chapman & Hall, 1997.

[MBA] Mordechai Ben-Ari Mathematical Logic For Computer Science, corrected 3rd edition, Springer 2008. Available in the library on reserve, for short term loan.

[RS] Raymond Smullyan ``First-Order Logic'', Dover Publications, 1995.

[SC] Stephen Cook CSC 438F/2404F: Computability and Logic (University of Toronto), Lecture Notes, Fall 2008.

[SS] Stephen Simpson Lecture Notes on Mathematical Logic for MATH557. MATH 557 is an introductory course on mathematical logic at Penn State University (USA).

[TG] Timothy Gowers (Editor) The Princeton Companion to Mathematics, Part 1 "Introduction", Section I.2: The Language and Grammar of Mathematics, pages 8-16, Princeton University Press, 2008.

1. January 12, 2011: Introduction and Overview. You might wish to read slides prepared by Ian Horrocks and Alan Rector for the CS646 course (at University of Manchester, UK) named The Semantic Web: Ontologies and OWL. In addition, it might help to read these slides prepared by Grigoris Antoniou and Frank van Harmelen for Chapter 1 of their book A Semantic Web Primer (2nd edition, MIT Press, 2008: this book is available on reserve for short term loan).
   The W3C provides plenty of information about Semantic Web. Explore this Web page if you would like to learn more, but this is not required.
   Propositional logic: You can find all definitions, theorems and many examples in Stephen Simpson's lecture notes: Read Chapter 1, pages 3-9. Also, [SC] Propositional calculus: pages 2 and 3 only.


2. January 19, 2011. Propositional logic: [RS] Chapter 1 and [MBA] Chapter 2. [SC] Propositional calculus: pages 4-6 only. Also, in [SS], you can read Chapter 1, pages 9-12. Semantic Tableau: construction. [MBA]: Chapter 2.


3. January 26, 2011. Propositional Logic: Soundness and Completeness of semantic tableau. [MBA]: Chapter 2. A brief summary is provided in S.Simpson's lecture notes [SS]: pages 18-22. (Koenig's Lemma, Compactness). You can also read [RS]: Chapters 2 and 3. In-class presentation: Introduction to XML, XML Schema and Namespaces. Selected Slides (a PDF file) are taken from the book "A Semantic Web Primer". The purchase order example is available in XML Schema Primer, Section 2.1 at the W3C Web pages.


4. February 2, 2011. Introduction to first order logic (FOL). Basic Semantic Definition (BSD). You can find an excellent introduction to FOL in [EM]: Sections 2.1 and 2.2. Semantics of FOL: satisfiability, logical consequence, validity. Logical equivalence: examples. [SC] Predicate Calculus, pages 18-24. You can also read S.Simpson's lecture notes Sections 2.1, 2.2 and 2.4: pages 25-30 and pages 37-40. Substitution in terms and in formulas, a term freely substitutable for a variable in a formula, substitution theorem. [SC] Predicate Calculus, pages 25 - 27. You might wish to read also Chapter 5 and Chapter 6 (pages 23-39) from Stefan Bilaniuk's A Problem Course in Mathematical Logic (LaTeX source is available too). There are several related articles in Stanford Encyclopedia of Philosophy, e.g., read Section 4 on Semantics in the entry on classical logic (by Stewart Shapiro) and Section 1: First-order languages and structures in the entry First-order Model Theory (by Wilfrid Hodges).


5. February 9, 2011. Proofs in FOL. Semantic tableau: examples, Gamma-rules, Delta-rules, systematic construction of semantic tableau, soundness and completeness. Godel completeness theorem for FOL. Read [MBA], Section 5.5. Also, consult Dr. D.Delic's handouts about semantic tableau that he prepared for his undegraduate Ryerson course MTH714 (Logic and Computability): read Section 2.6 (tableau in propositional logic) and read Section 5.5 (tableau in FOL); you may skip other sections. Undecidability of the satisfiability problem for FOL formulas when vocabulary includes at least one binary predicate in addition to equality. Compactness of FOL. Finitely axiomatizable theories, incomplete and complete theories, non-standard models of theories. [SC] Lecture Notes: pages 49 - 52.


6. February 16, 2011. Read in the textbook Chapter 2 (Simple Ontologies in RDF and RDF Schema) and Sections 3.1 and 3.2. Describing Web Resources in RDF: slides to Chapter 3 of the textbook "Semantic Web Primer". Michael Zakharyaschev's slides (slides 36 - 60) on RDF, RDF Schema and RDF/S semantics prepared for his Semantic Web course at University of London. Pascal Hitzler's slides on RDF Schema and on RDF Semantics. (The latter slides are prepared for the course Knowledge Representation for the Semantic Web at Wright State University, Ohio, USA.). Note that there is overlap between slides: you can pay attention only to those slides which we covered in class.
   The following links are optional: you are not required to read documents at W3C linked here. RDF and RDF Schema. In January 2011, W3C started a new RDF Working Group chartered to update the 2004 version of the Resource Description Framework (RDF) Recommendation.


7. March 2, 2011. Introduction to Description Logics (DL). Slides (Part 1) of the tutotial Description Logic: a Formal Foundation for Languages and Tools presented by Ian Horrocks. Tutorial at the Semantic Technology Conference (SemTech) held in San Francisco, California, USA, June 22-27, 2010. A readable introduction to DL is provided in Sections 3.1, 3.2, 3.3.1 and 3.7 (pages 1-10 and 31-33) from the Chapter 3 "Description Logics" written by F. Baader, I. Horrocks, and U. Sattler and published in Handbook of Knowledge Representation, pages 135-179, Elsevier, 2007. Read Sections 5.1.1 and 5.1.2 in the textbook (pages 159-164).


8. March 16, 2011. Semantics of Description Logics (DL). Read Section 5.2, pages 172-180. Reasoning in DLs. Michael Zakharyaschev's slides on automated reasoning in DLs (do exercises on slides 19 and 20). Reducing inference problems to the (un)satisfiability problem. Negation Normal Form. Tableaux Algorithm with blocking for ALC. Read the textbook Sections 5.3 - 5.3.3 (pages 181-196). Pascal Hitzler's slides 4-40 on tableaux with blocking for ALC. Also, read Michael Zakharyaschev's slides 8-26 on tableaux in ALC (without blocking), but note that notation is different from the textbook.
   Exploring the following links is not required.
   Section 3.4 (pages 12-16) from the Chapter 3 on "Description Logics" written by F. Baader, I. Horrocks, and U. Sattler. Several important and influential papers on DLs are linked from a course on Description Logics taught by Enrico Franconi at Free University of Bozen-Bolzano, Italy. Some of these papers are included in the comprehensive Description Logic Handbook, a paperback copy of the 2nd edition, published by Cambridge University Press, 2011.


9. March 23, 2011: OWL2 and its fragments. OWL 2 Reference Card is a handy summary of OWL2. Read the textbook: Chapter 4 (pages 111-156) and Section 5.1.3-5.2 (pages 165-181). The description logic SROIQ(D) provides logical foundations for OWL2. The slides 15-25 about the description logic SROIQ are prepared by Pascal Hitzler for his course "Knowledge Representation for the Semantic Web". He also prepared slides about OWL syntax. Ian Horrocks presented a tutorial on OWL2 to Ontolog Forum on Thursday, July 29, 2010. Read his slides and listen to an audio recording of the session (you need MP3 compatible player to listen).
   The following links are optional: you are not required to read W3C documents linked here.
   Web Ontology Language (OWL2) Primer and more details about fragments (profiles) of OWL2. Also, OWL2 has Formal Direct Semantics


10. Read the texbook, Chapter 6: Sections 6.1 - 6.3. Ontologies and Rules. Datalog: syntax and semantics. Combining rules with OWL DL. Rule Interchange Format (RIF). Part 2: OWL2 Rules. Tutorial at the 32nd Annual German Conference on Artificial Intelligence (on September 15, 2009) prepared by Pascal Hitzler, Markus Krötzsch, Sebastian Rudolph. This tutorial also includes Part 1: Introduction to OWL 2 that covers OWL2.
    The following links are optional: you are not required to read W3C documents linked here. RIF Primer and RIF Overview. RIF became W3C Recommendation on 22 June 2010.


11. SPARQL. Conjunctive Queries for OWL DL. Chapter 7 of the textbook.

Foundations of Semantic Technologies