Plan for SEM1A6 (Logic)

Mark Ryan

The module will be based on sections from the draft of a forthcoming book,

Logic and its Applications in Computer Science, by Michael Huth and Mark Ryan, to appear in 1998
which will be available as a handout. It will consist of two lectures per week and one exercise class. There are assessed exercises each week, which are to be handed in during the exercise class. One percentage point of the module is given for a serious attempt at the assessed exercises, so if you hand in all 10 you will get 10% of the marks before you take the exam.

The plan of the module is as follows:

Week 1.
The language of propositioinal logic. Natural deduction. The rules , , , , MT.

1.1, 1.2.1 (up to and including the section ``Rules for eliminating implication'').

Assessed exercises: p5 Q5, Q6, Q9(a,e,h); p6 Q1; p8 Q2.

Week 2.
The rule , the rules for , the rules for . Derived rules; RAA and LEM.

1.2.1 (rest), 1.2.2.

Assessed exercises: p14 Q1(b), Q2(g,j,n,p,q); p17 Q1 (a,b,f,g).

Week 3.
Summary of natural deduction. The ND proof editing tool.

1.2.3.

Assessed exercises: p18 Q2 (d); p 23 Q1 (all of it).

Week 4.
Propositional logic as a formal language. Truth tables for propositional logic. Soundness and completeness (without proof).

1.3

Assessed exercises: p27 Q1(b,f), Q2, Q9; p33 Q2, Q3, Q5.

Week 5.
The language of Predicate logic.

2.1, 2.2.

Assessed exercises: p43 Q1, Q2, Q5; p48 Q1, Q2, Q4(a,b,c).

Week 6.
Natural deduction for predicate logic. 2.3.

Assessed exercises: p60 3(d,f), 5(a), 11(d,e), 12(a,c).
NB. More than these ones are labelled with *, but only the ones mentioned here are assessed. The model answers will include all the ones labelled with *.

Week 7.
Program logic. Correctness: partial and total. Hoare triples. A simple programming language. The rules for composition and assignment. 4.1, 4.2, 4.3.1, 4.3.2.

Assessed exercises: pgif Q1, Q2.
NB. For Weeks 7--10, the assessed exercises are (accidentally) not labelled with * in the text. Model answers will still be provided.

Week 8.
The rule for If-statements. 4.3.3.

Assessed exercises: pgif Q1, Q2.

Week 9.
The rule for while-loops. 4.3.4, up to but excluding the section ``A case study: Minimal sum section''.

Assessed exercises: pgif Q3, Q4, Q8.

Week 10.
Case study: Minimal-sum section. The section ``A case study...'' beginning p91.

Assessed exercises: pgif Q1, Q3.

Week 11.
Room for expansion; revision.


Mark D Ryan
Thu Feb 19 12:09:15 GMT 1998