cse541

LOGIC for COMPUTER SCIENCE

Spring 2015



GENERAL NEWS:

FINAL EXAM: May, 18 5:30pm - 8pm  in our classroom

I will have extra office hours on FRIDAY, MAY 15, 3-5pm

I POSTED  a short Test on Introduction to Predicate Logic I gave during the last class
Study also Lectures on the
Introduction to Predicate Logic and QRS System

IMPORTANT REMINDER ABOUT FINAL GRADE COMPUTATION
 1. BY  THE COURSE Syllabus you  can get 20 extra points that are PART of computation of
 your grade in the course

2. I  GAVE MUCH MORE EXTRA POINTS  WORK DURING THE SEMESTER!

3.  I DECIDED (it is also stated in the Syllabus) to ALLOW  additional  20pts, i.e. to allow a total of  

40 extra points to be used, together with all tests points to compute grades within A-range
that is a range for passing  Ph.D.  Quals

4. The  additional  extra points above allowed 40pts might be counted  in your grade computations
only for grades  below A range

5. It means that the highest grade you can obtained by use of extra points above its total 40pts is B+


Solutions to MIDTERM 2  are POSTED

Lecture 13- QRS proof system for Predicate Logic  is POSTED

This material will be included in FINAL

PRACTICE MIDTERM 2 SOLUTIONS are POSTED

PRACTICE MIDTERM 2 TEST is POSTED


I also posted TWO SOLUTIONS of Lecture 9 problems written by 2 students (THANK You guys!)
Read and COMPARE them

MIDTERM 2: Tuesday, April 28 in class

Study PROOF ONE of  Completeness Theorem proof and Examples

For extra Tests, Problems examples please look at cse371 webpage
http://www3.cs.stonybrook.edu/~cse371/

  • Lectures 10, 10a  (Chapter 10), Lectures 11, 12  POSTED

  • PLEASE SUBMIT extra Credit problems I gave in class- and published in Lectures slides
  • Do it for exercise and extra credit

  • LECTURES may include new material - not yet in the BOOK CHAPTERS-  so read both
  • I posted INTRODUCTION TO PREDICATE LOGIC lectures  for you to READ

  • Class Meets:

    Tuesday, Thursday, 1:00pm - 2:20pm

    Place:

    ESS 079

    Professor:

    Anita Wasilewska

    1428 CS Building; 632-8458
    e-mail: anita@cs.stonybrook.edu
    Office Hours: Tuesday, Thursday, 11:30am - 12:30 pm, and by appointment

    TA: tba

    e-mail: tba
    Office Hours: tba
    Office Location: Room 2110, CS department.

    Course Texbook

    AN INTRODUCTION TO CLASSICAL and NON-CLASSICAL LOGICS
    Anita Wasilewska

    This is a book in progress

    Full Book Text and Lecture Slides are in Downloads

    Course Reading Book

    Introduction to Mathematical Logic, Fourth Edition
    Elliot Mendelson

    General Course Description:

    The goal of the course is to make student understand the need of logic as a field and to learn the its formality and basic techniques. I will progress relatively slowly, making sure that the pace is appropriate for all students in the class. The book is written with students on my mind so that they can read and learn by some parts by themselves. The book, and the course is developed to teach not only intuitive understanding of different logics, but (and mainly) to teach formal logic as scientific subject, with its languages, definitions, main theorems and problems.

    General Course Information

    There will be TWO MIDTERMS and a FINAL examination.
    There also will be assigned sets of homework problems students must work out and learn for the tests. The complete solutions to all problems are posted on the course webpage.
    Students are also responsible to learn all Examples and Exercises in the text book and some PROOFS of the main Theorems.


    All tests are CLOSED NOTES and CLOSED BOOK.
    If a student is found using notes or a book during a test, he/she will receive AUTOMATICALLY 0pts for a given test.


    There are many exercises-homeworks sets posted on the web. NONE will be collected or graded.
    Students are responsible for working out and writing DETAILED solutions explaining all steps and methods used, as it is done in our book. We will cover some of such detailed solutions in class and post ALL of them on our web page for you to study and learn how to properly write them. Students are also responsible to learn and work out all Examples, Exercises and Homeworks in the text book as well as some PROOFS of the main Theorems.
    Your GRADES on the tests will depend on the form, attention to details, and carefulness of your written solutions.

    Course Content

    The course will follow the book very closely and in particular we will cover some, or all of the following chapters and subjects.

    Chapter 1: Introduction: Mathematical Paradoxes and Computer Science Puzzles

    Chapter 2: Introduction to Classical Propositional Logic

    Chapter 3: Propositional Languages

    Chapter 4: Classical Propositional Semantics

    Chapter 5: Some Extentional Three and Many Valued Logics Semantics

    Chapter 6: Classical tautologies, Logical Equivalences and Equivalences of Languages

    Chapter 7: General Proof Systems

    Chapter 8: Hilbert Proof Systems; Deduction Theorem

    Chapter 9: Two Proofs of Propositional Classical Logic Completeness Theorem

    Chapter 10: Classical Automated Proof systems: RS and original Gentzen

    Chapter 11: Introduction to Intuitionistic Logic; Conections between Classical and Intuitionistic Logics.

    Chapter 12: Gentzen Proof System for Intuitionistic Logic.

    Chapter 13: Classical Predicate Logic: Hilbert Formalization

    Chapter 14: Classical Predicate Logic: Automated Proof System QRS

    Chapter 15: Hilbert and Gentzen Proof Systems for Intuitionistic Predicate Logic

    Chapter 16: Introduction to Modal Logics, Modal S4 and S5 and their connections with Intuitionistic logic.

    Chapter 17: Goedel Incompleteness Theorem

    TESTS SCHEDULE

    PRACTICE Midterm 1,  TAKE HOME,  posted Thursday, March 5

    MIDTERM 1, Thursday, March 12, in class

    Spring Break: March 16 - 23

    MIDTERM 2, Tuesday, April 28, in class

    LAST DAY OF CLASSES- May 8

    FINAL: May, 18 5:30pm - 8pm  in our classroom

    DOWNLOADS

    Syllabus
    PRACTICE MIDTERM 1
    PRACTICE MIDTERM 2

    LECTURES SLIDES

    Lecture 1
    Lecture 2
    Lecture 3
    Lecture 4
    Lecture 5
    Lecture 5a
    Lecture 6
    Lecture 7
    Lecture 8
    Lecture 9
    Lecture 9a
    Lecture 10
    Lecture 10a
    Lecture 11
    Lecture 12
    Lecture 13
    Consequence Operation Properties (by a student)

    INTRODUCTION TO PREDICATE LOGIC

    Introduction 1
    Introduction 2

    Short Test

    2015 Solutions

    MIDTERM 2 SOLUTIONS
    PRACTICE MIDTERM 1 SOLUTIONS
    PRACTICE MIDTERM 1 SOLUTIONS by a STUDENT
    PRACTICE MIDTERM 2 SOLUTIONS
    Lecture 9 Problems SOLUTIONS by student 1
    Lecture 9 Problems SOLUTIONS by student 2

    FEW TESTS for PRACTICE

    MIDTERM 1 - a format of test as could be given in class for you to take it as a practice test
    MIDTERM 1 SOLUTIONS
    Another MIDTERM 1 Solutions
    Another MIDTERM 1 Solutions

    Practice MIDTERM 2 for you to take it as a practice test
    Extra Credit Short Test
    Another MIDTERM 2 SOLUTIONS

    TAKE HOME PRACTICE FINAL

    Take home Practice Final Example

    SOME BASIC DEFINITIONS and FACTS

    Operations on Sets, Functions, Relations, Equivalence Relations
    Order Relations, Lattices, Boolean Algebras
    Cardinalities of Sets

    Exercises - Homework Problems

    Homework Exercise 0
    Homework Exercise 01
    Homework-Exercise 1
    Homework-Exercise 2
    Homework-Exercise 3
    Homework-Exercise 4
    Homework-Exercise 5
    Homework-Exercise 6
    Homework-Exercise 7
    Homework-Exercise 8
    Homework-Exercise 9
    Homework-Exercise 9(1)
    Extra Credit Exercise 9a
    Homework-Exercise 10
    Homework-Exercise 11
    Homework-Exercise 12

    Exercises - Homework SOLUTIONS

    Homework-Exercise 0 Solutions
    Homework-Exercise 1 Solutions
    Homework-Exercise 2 Solutions
    Homework-Exercise 3 Solutions
    Homework-Exercise 4 Solutions
    Homework-Exercise 5 Solutions
    Homework-Exercise 6 Solutions
    Homework-Exercise 7 Solutions
    Homework-Exercise 8 Solutions
    Homework-Exercise 10 Solutions
    Homework-Exercise 11 Solutions
    Homework-Exercise 12 Solutions

    Book Chapters

    Chapter 1: Introduction
    Chapter 2: Indroduction to Classical Propositional Logic
    Chapter 3: Propositional Languages
    Chapter 4: Classical Propositional Semantics
    Chapter 5 Some Extensional Multivalued Semantics
    Chapter 6 Classical Tautologies and Logical Equivalences
    Chapter 7 General Proof Systems
    Chapter 8 Hilbert Proof Systems, Deduction Theorem
    Chapter 9 Propositional Logic Completeness Theorem - NEW
    Chapter 10 Gentzen Style Proof Systems for Classical Logic
    Chapter 11 Introduction to Intuitionistic Logic
    Chapter 12 Gentzen Proof System for Intuitionistic Logic
    Chapter 13, Predicate languages
    Chapter 13, Part 1: System QRS Definition and Examples
    Chapter 13, Part 2: System QRS Completeness
    Chapter 14, Part 1: Hilbert System for Predicate Logic
    Chapter 14, Part 2: Hilbert System for Predicate Logic

    Academic Integrity Statement

    Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at Academic Judiciary Website

    Stony Brook University Syllabus Statement

    If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact Disability Support Services at (631) 632-6748 or Disability Support ServicesWebsite They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to the following website: Disability Support Services Website