Dependence logic, Spring 2011 Material discussed in the lectures The page numbers below refer to the course textbook "Dependence logic". Monday 14.3: pages 5-6. - Relations, structures, assignments, formulas of first-order logic Thursday 17.3: pages 7-9 and 16-19. - Semantics of first-order logic, negation normal form - teams and formulas of dependence logic Monday 21.3: pages 20-23. - Semantics of dependence logic Thursday 24.3: pages 23-24. - Semantics of dependence logic with further examples - Downward closure property of formulas (Closure Test) Monday 28.3: pages 29-31. - Concepts of logical consequence and equivalence - Examples of propositional equivalences in dependence logic Thursday 31.3: pages 32 and 35. - More examples of logical equivalences in dependence logic - "Change of free variables" and "Preservation of equivalence under substitution" lemmas Monday 4.4: pages 33-35. - Negation normal form for dependence logic, - Lemmas 3.27 3.29; -- truth of a formula depends only on the interpretations of the variables occurring free in the formula -- Isomorphism preserves truth Thursday 7.4: pages 37-39, 42-43, and 48-50. - A characterization for first-order formulas of dependence logic, - Flatness Test and the Flattening Technique, - How to express "even cardinality" in dependence logic Monday 11.4: pages 86-89. - Existential second-order logic, - Thm 6.2: a translation of dependence logic into existential second-order logic Thursday 14.4: pages 90-95. - Model theoretic properties of dependence logic: Compactness Theorem, Separation Theorem, Failure of the Law of Excluded Middle, - Determined and non-determined sentences, - Skolem Normal Form Theorem for existential second-order logic Monday 18.4: pages 96-98. - Thm 6.15: A translation of sentences of existential second-order logic into logically equivalent sentences of dependence logic Thursday 28.4: We began to study the complexity of quantifier-free formulas of dependence logic (based on the doctoral thesis of Jarmo Kontinen). - Basics of computational complexity theory: complexity classes L, NL, P, and NP, reductions and completeness, - The notion of k-coherence for quantifier-free formulas of dependence logic (Def. 3.0.9. on page 14 in the doctoral thesis of Jarmo Kontinen) Monday 2.5: pages 15-17 and 27 from the doctoral thesis of Jarmo Kontinen. - Propositions 3.1.1, 3.1.2, 3.1.3, 3.1.5, 3.1.6 - Theorem 3.2.5 Thursday 5.5: pages 37-42 from the doctoral thesis of Jarmo Kontinen. - Theorems 4.3.1, 4.3.3, and 4.3.5 (we did not go through the proof Thm 4.3.5).