CS 3EA3 - Course Outline Sep.2008

Instructor

Instructor: Dr. Ivan Bruha, ITB-219, bruha@mcmaster.ca

Course title

Software Specifications and Correctnes

Course outline


1. Syntax and semantic systems
- Definitions, proof, theorem, semantically valid formula, tautology
- Combined and complete systems, inconsistency
2. Propositional logic (partly Ch. 1 of the following book)
- Definitions of syntax as well as semantic systems, Tarski's approach
- Various lemmas: Reflexivity, deduction, transitivity, transposition, etc.
- Additional propositional functors, and lemmas above them
- Substitution and extensionality
- Completeness of Propositional logic
- Well-defined formulas, Literal, Conjuctive normal form
3. Predicate logic (partly Ch. 2 of the following book)
- Definition of syntax system
- Quantifiers, substitution, various lemmas in Predicate logic
- Semantics for Predicate logic
- Undecidability of Predicate logic
- Resolution principle
4. Program verification (Ch. 4 and partly 3 of the following book)
- Tools for verification
- Validation
- Model checking

There is this recommended book:
M.R.A. Huth and M.D. Ryan: "Logic in Computer Science, Modelling and Reasoning about Systems"

Marking scheme

  • 2 tests 30% (each 15%)
  • 1 assignment 20%
  • 1 final exam 50%

    • Students will be informed about tests at least two weeks in advance. Please, read Announcement on our web side. Also, the office hours are posted there.

    Any student picking up back her/his marked test is to display her/his student ID card to the TA of this course. Similarly, when contacting the instructor in his office.

    The assignment: An essay on a topic related to this course.
    Please, discuss your essay topic with the instructor: by 29.Sep.2008
    Due date of the essay (to the TA): 20.Nov.2008

    Format of the essay

  • .Regular fonts, single spacing, 10 pages including figures, tables, and references.
  • Figures and Tables should be properly documented. References should be properly introduced.

    • Split the essay to several chapters; the following ones should always occur in you writeup:
  • - Introduction (a brief but a complete summary of the entire topics);
  • - Methodology (you can split this part to several sections);
  • - Conclusion (include comparison if possible).

    • Marking scheme of the essay

  • - Figures + Tables: 2 points
  • - References: 2 points
  • - Actual topic: 16 points
  • If your essay exceeds 10 pages 2 point will be reduced.
  • If your essay is just a plain copy of other source(s) 10 point will be reduced.


    • Penalty for 1 to 3 days late: 10% off per day. The assignment more than 3 days late will not be accepted.

    Academic dishonesty consists of misrepresentation by deception or by other fraudulent means and can result in serious consequences, e.g. the grade of zero on an assignment, loss of credit with a notation on the transcript (notation reads: "Grade of F assigned for academic dishonesty"), and/or suspension or expulsion from the university. It is your responsibility to understand what constitutes academic dishonesty.
    For information on the various kinds of a academic dishonesty please refer to the Academic Integrity Policy, specifically Appendix 3, located at http://www.mcmaster.ca/senate/academic/ac_integrity.htm

    Here are some examples that would be interpreted as academic dishonesty IN THIS COURSE:
    a// Collecting/ possessing/ buying copies of the former midterm tests (MTT) or final exams (FE) of this course.
    b// Distributing/ selling copies of the former MTT/FE of this course.
    c// Communicating/ talking to a classmate during MTT/FE.
    d// Changing the answers in the MTT/FE in order to get a better evaluation.

    Some of the questions in the tests and final exam will be of the form of 'generalized multiple-choice' ones, i.e. given a few answers for a question, zero or one or more questions could be correct. If you do not mark ALL correct answers you'll get 0 (zero) for that question. E.g.

    Q: How much is 1+1 ?
    a/ 3
    b/ 2
    c/ always 2
    d/ sometimes 2, sometimes 3
    e/ a number from the interval <2; 3>
    f/ one of these results: 2, 3
    g/ any number from the interval <2; 3>
    Correct answer(s): .............