Week 11

It's now time for revision. The reading list is just re-reading. You've done quite a lot in the past 10 weeks!

Re-reading

Chapter 4, Venn Diagrams and Logical Connectives.

Chapter 6, Features and Predicates.

Chapter 7, Patterns of Reasoning.

Chapter 8, More Patterns of Reasoning.

Chapter 10, Sequent Calculus.

Chapter 12, Karnaugh Maps.

Chapter 16, Relations and Quantifiers.

Chapter 18, Expression Trees.

Chapter 19, Checking Satisfiability.

Chapter 20, Efficient CNF Conversion.

Chapter 23, Counting Satisfying Valuations.

Chapter 28, Regular Expressions.

Chapter 29, Regex and Machines.

Chapter 30, Deterministic Finite Automata.

Chapter 31, Nondeterministic Finite Automata.

Chapter 32, Machines to Regex.

Chapter 33, Regex to Machines.

Videos

The first video introduces a very important idea.

In previous years this idea has not been examined. This year it may be one of the things that go beyond the required material to allow you to score an excellent mark overall.

This is the idea of inductive definitions.

CL18 rules

Slides 2 — 5 each give an example of an inductive definition that we have already studied earlier in the course.

Slide 7 gives another example, implicit in our previous work, but now made explicit.

If you look back at our code for FSMs and NFA, you will see that the ideas of reachability and ε-closure give two more examples.

Slides 6, 7, 8 introduce the key concepts of soundness and completeness.

Finally, slides 9 and 10 work through some example questions on FSM, DFA, and regex. To get the most benefit from thses slides you should attempt the questions before watching this section.

This is a raw video from 2019. I've not yet had time to edit it into chunks. If you have any questions, or find any errors, please let me know on Piazza.

Slides
Video (55:01)

This is a raw video from 2019. I've not yet had time to edit it into chunks. If you have any questions, or find any errors, please let me know on Piazza.

The remaining videos are dedicated to revision.

CL20 syllogisms arrowrule
Slides
Video (53:56)
CL21 CNF KM Gentzen Tseytin
Slides
Video (55:01)
CL22 Tseytin Satisfaction DPLL
Slides
Video (53:47)

THE END