cse541
LOGIC for COMPUTER SCIENCE
  Fall 2021



Course Information

NEWS: 

MIDTERM is given  on THURSDAY, October 21 in class
MIDTERM  covers Chapter 1, Chapter 3, Chapter 4, and Chapter 5 Lectures 5, 5a

Q1 SOLUTIONS posted


Time:  Tuesday, Thursday  8:15pm  -9:35pm

Place:  Engineering 143

WE  HAVE  our own  LOGIC LECTURES  YOUTUBE CHANEL

  LOGIC, Theory of Computation 

The first 4 Lectures are Theory of Computation,  LOGIC LECTURES follow
Please use them for study  study during the semester

Professor:

Anita Wasilewska

208  New CS Building
phone:  (631) 632-8458

e-mail: anita@cs.stonybrook.edu

Professor Office Hours:  Tuesday, Thursday  1:30pm - 2:30pm
In person: 208  New CS Building   and email and
ZOOM  on demand


Teaching Assistants  Office Hours

Name: Michael Dixon
short questions via email any time 
e-mail: Michael.Dixon@stonybrook.edu
Office hours:  Tuesday, Thursday  2:30pm - 3:30 pm
In person: 208  New CS Building
ZOOM:
on request via email

Name: Rory Bennet

short questions via email any time
e-mail: Rory.Bennet@stonybrook.edu

Office hours: Wednesday 2:00pm - 3:00pm
In person: 208  New CS Building 
ZOOM:
on request via email

Name:  Georgian  Borca- Tasciuc

short questions via email any time
 e-mail:  gborcatasciu@cs.stonybrook.edu
Office hours:  Tuesday 11:30 am- 12:30pm,  Thursday 1:00pm - 2:00pm
ZOOM
on request via email
 

TESTING

ALL QUIZZES and TESTS, including the FINAL Examination will be given in CLASS

ALL GRADES are listed on BLACKBOARD
Contact TAs if you need more information or need to talk about grading

Course Textbook

Anita Wasilewska

LOGICS FOR COMPUTER SCIENCE:  Classical and Non-Classical

Springer 2018

ISBN 978-3-319-92590-5             ISBN 978-3-319-92591-2 (e-book)

You can get the book in Hard cover, or in Electronic form
Springer also has an option of providing you with chapters of your choice

Course Goal

The goal of the course is to make student understand the need of, and to learn the formality of logic. 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 language, definitions and problems

Course Structure

I will progress relatively slowly, making sure that the pace is appropriate for the students in class. The book is written with students on my mind so that they can read and learn by themselves, even before coming to class. For sure, it is also essential to study after the class.
  Students are also responsible to study chapters examples  and problems that are not included in Lectures. I may include them in Quizzes and Tests.

  Preliminary STUDY PLAN  

WEEK 1: August 23 - 29
Chapter 1 VIDEO: Introduction: Paradoxes and Puzzles- material included in Class Lecture 1

WEEK 2: August 30 - September 5
Chapter 2 VIDEO: Introduction to Classical Logic - material included in Class Lectures 2, 2a, 2b

WEEK 3: September 6 - September 12
Chapter 3 VIDEO: : Propositional Semantics: Classical and Many Valued- material included in Class Lectures 3, 3a, 3b

WEEK 4: September 13 - September 19
Chapter 3 VIDEO: : Propositional Semantics: Classical and Many Valued- material included in Class Lectures 3c, 3d

WEEK 5: September 20 - September 26
Chapter 3 VIDEO: : Propositional Semantics: Classical and Many Valued- material included in Class Lectures 3e

WEEK 6: September 27 - October 3  Q1 Tuesday, September 28
Chapter 4 VIDEO: : General Proof Systems - material included in Class Lectures 4, 4a

WEEK 7: October 4 - October 10
Chapter 5 VIDEO: : Hilbert Proof Systems for Classical Propositional Logic - material included in Class Lecture 5

WEEK 8: October 11 - October 17   Fall Break October 11-12
Chapter 5 VIDEO: : Hilbert Proof Systems for Classical Propositional Logic - material included in Class Lecture 5a

WEEK 9: October 18 - October 24   MIDTERM October 21
Chapter 5 VIDEO: : Hilbert Proof Systems for Classical Propositional Logic - material included in Class Lecture 5b

WEEK 10: October 25 - October 30 
Chapter 6 VIDEO: : Automated Proof Systems for Classical Propositional Logic -  Class Lectures 6, 6a

WEEK 11:   November 1- November 7
Chapter 6 VIDEO: : Automated Proof Systems for Classical Propositional Logic -  Class Lectures 6a, 6b

Grading General Principles and Workload

Workload and  GRADING
There will be 2 Quizzes,  Midterm,   Practice Final (for extra credit),  and  Final examination

None of the grades will be curved

Quizzes: 50pts
2 quizzes, 25 points each

Midterm:  75pts
Midterm  will covers material from Q1 and  material covered after Q1 in class before Midterm

Practice Final: 15 extra pts

Final:  75pts

Final grade computation

You can earn up to 200 points + x extra points = 200+x points during the semester
The grade will be determined in the following way: number of earned points divided by 2 = % grade
The % grade is translated into a letter grade in a standard way - see SYLLABUS for explanation

Quizzes and Tests PRELIMINARY Schedule:

Q1 -  Tuesday, September 28
Fall Break  - October 11-12
MIDTERM -  Thursday, October 21  
Q2 - Thursday, November 18  
Thanksgiving Break - November 24 - 28  
Practice Final - posted December 2,   due December 6  
 Final  December 9, 8:30pm -11pm, Engineering 143


DOWNLOADS

Q1 SOLUTIONS

SYLLABUS

CLASS Lectures Slides

COURSE GENERAL STRUCTURE and GOALS

Book Chapter 1: Introduction: Paradoxes and Puzzles

Lecture 1:  Logic Motivation: Paradoxes and Puzzles

Book Chapter 2: Introduction to Classical Logic

Lecture 2: Propositional Language and Semantics
Lecture 2a: Predicate Language and Semantics
Lecture 2b: Chapter 2 Review

Book Chapter 3: Propositional Semantics: Classical and Many Valued

Lecture 3: Formal Propositional Languages
Lecture 3a: Classical Propositional Semantics 
Lecture 3b : Extensional Semantic
Lecture 3c : Many Valued Semantic: Lukasiewicz, Heyting, Kleene, Bohvar
Lecture 3d: Tautologies, Equivalence of Languages
Lecture 3e:Chapter 3 Review

Book Chapter 4: General Proof Systems: Syntax and Semantics

Lecture 4: General Proof Systems
Lecture 4a: Review Definitions and Problems

Book Chapter 5: Hilbert Proof Systems: Completeness of Classical Propositional Logic

Lecture 5: Hilbert Proof Systems for Classical Logic, Deduction Theorem
Lecture 5a: Completeness Theorem Proof 1
Lecture 5b: Completeness Theorem Proof 2

Book Chapter 6: Automated Proof Systems for Classical Propositional Logic 

Lecture 6: RS Systems
Lecture 6a: Gentzen Sequents SystemStrong Soundness and Constructive Completeness
Lecture 6b: Original Gentzen Sequents System, Hauptzatz Theorem

Book Chapter 7: Introduction to Intuitioniostic and Modal Logics

Lecture 7; Introduction to Intuitionistic Logic
Lecture 7a: Gentzen Systems for Intuitionistic Logic
Lecture 7b: Introduction to Modal Logics S4 and S5

Book Chapter 8: Classical Predicate Languages, Semantics, and Proof Systems

Lecture 8: Formal Predicate Languages
Lecture 8a:Classical Semantic
Lecture 8b: Predicate Tautologies

Book Chapter 9: Completeness and Deduction Theorem for Classical Predicate Logic

Lecture 9:Reduction Predicate Logic to Propositional
Lecture 9a: Henkin Method
Lecture 9b: Proof of Completeness Theorem
Lecture 9c:Deduction Theorem, Other Axiomatizations

Book Chapter 10: Predicate Automated Proof Systems

Lecture 10: Predicate Languages, QRS-Automated Proof System for Classical Predicate Logic
Lecture 10a: Proof of Completeness Theorem for QRS

Book Chapter 11: Formal Theories and Godel Theorems

Lecture 11: Hilbert Program, Godel Incompleteness Theorems

VIDEO LECTURES  Slides

CHAPTER 1
CHAPTER 1 
CHAPTER 2  
CHAPTER 3
CHAPTER 4
CHAPTER 5
CHAPTER 6
CHAPTER 7
CHAPTER 8
CHAPTER 9
CHAPTER 10
CHAPTER 11

Few Old Tests for Practice

Midterm 2 Solutions
Practice Midterm 1 Solutions
Practice Midterm 1 Solutions by a STUDENT
PRACTICE MIDTERM 2 SOLUTIONS
Lecture Problems SOLUTIONS by student 1
Lecture Problems SOLUTIONS by student 2

MIDTERM 1 SOLUTIONS
Another MIDTERM 1 Solutions
Another MIDTERM 1 Solutions
Another MIDTERM 2 SOLUTIONS



ACADEMIC INTEGRITY STATEAMENT

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 http://http://studentaffairs.stonybrook.edu/dss 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: http://www.sunysb.edu/ehs/fire/disabilities.shtml 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