MATH 430   FORMAL LOGIC  SPRING 2000

Time: MWF at 9:00 AM

Place: TH 117

Prerequisites: Math 320 or MCS 261 or consent of the instructor.

Instructor: Olivier Lessmann

Office: SEO 622

Phone: 413-9153

Email: lessmann@uic.edu

Office hours: W from 10 to 12 AM, or by appointment.

Text: Logic for Mathematics and Computer Science, by S. N. Burris, Prentice Hall, 1998 (available at the bookstore).

Course content: We will essentially cover the following sections

Chapter 1 Sections 1.1 and 1.2 (Introduction)

Chapter 2 Sections 2.1--2.9 (Propositional Calculus)

Chapter 3 Sections 3.1--3.3

Chapter 4 Sections 4.1--4.2

Chapter 5 Sections 5.1--5.11 (First Order Logic)

We will make forays into more computational topics depending on time and interest.

Exams: There will be two in-class midterms (the first midterm is Wednesday February 16 in SES 130, the second midterm is Friday April 14 in BH 308) and a Final Exam, Tuesday May 2, 8:00 - 10:00 AM in Room BH 208. There will be a review session May 1, 3:00 - 6:00 PM in Room TH 117.
In addition, there may be short quizzes at the end of the hour. The quizzes may or may not be announced.
No make-up will be given for a missed quiz.

Homework: Problems will be assigned in class each week  and collected the following Monday (see below for the list).
Some of the homework assignments will be graded. No late homework will be accepted.
You are encouraged to discuss homework problems with your fellow students and to work in group, but you should write your own solutions.

Grading policy: The grade of the course will be based on:

Final exam (40 %)

Midterms (20 % each)

Homework, quizzes, and class participation (20 %)

Semester holidays: Monday January 17 (Martin Luther King, Jr. holiday), March 13 -- 17 (Spring Break). Instruction ends April 28.

Add/Drop:The last day to add or drop this class is Friday January 21.

Assignments:
Due Wednesday January 19, 2000:

• Ex 1.2.1, 1.2.2, 1.2.3.
• Ex: Given a formula A, consider the occurrences of symbols in A, one by one in left to right order, and, starting with a count of 0, increase the count by 1 every time a ( is encountered, and decrease by 1, every time a ) is encountered. Prove by induction on the construction, that for each propositional formula the final count is 0, and the count never becomes negative.

Due Monday January 24, 2000:

• Ex 2.1.1. c: Compare the truth tables of (P and (P or Q)) and (P or (P and Q)).
• Ex 2.1.1. d: Compare the truth tables of (not (P or Q)), ((not P) and (not Q)), (not (P and Q)), and ((not P) or (not Q)).
• Ex 2.2.2 b: Decide wether ((Q implies R) iff S) implies ((P and S) implies S) is a tautology, a contradiction, or neither.
• Ex 2.2.4: Decide which pairs among the following p.f. are truth equivalent:
a.  not ( P iff ( R iff P ))
b. P or (( P iff R ) or P )
c. R or (( not Q iff P ) iff Q )
d. ( R implies ( not P implies P )) or P
e. ( R iff P ) or (( P or ( Q or R )) implies P )
 

Due Monday January 31, 2000:

• Ex 2.4.1 a. b. c. d.
• Ex 2.4.2
• Ex 2.5.4

Due Monday February 6, 2000:

• Ex 2.5.5 a. b.
• Ex 2.5.8
• Ex 2.5.9
• Ex 2.5.11 a. b.
• Ex 2.6.1 d.

Due Monday February 13, 2000:

• Ex 2.7.3
• Ex 2.7.6 a. b. c.

Due Monday March 6, 2000:

• Ex 2.9.1 a, b, g
• Ex 2.9.2
• Ex 2.9.7 a, d, h
• Ex 2.9.8

Due Monday March 20, 2000:

• Ex 2.9.9 a, b,
• Ex 5.3.1 a
• Ex 5.3.2 a, f
• Ex 5.3.3 a

Due Monday March 27, 2000:

• Ex 5.4.1 a, b
• Ex 5.4.2 b
• Ex 3.3.3 b, c
• Ex 5.7.1 a, d
• Ex 3.3.4 b
• Ex 5.7.2 a, b

Due Monday April 3, 2000:

• Ex 3.3.2 a, b, c
• Ex 5.8.1 c, d
• Ex: In the language consisting of two unary relation symbols A(x) and B(x), show that
• Ex (A(x) and B(x)) implies (Ex A(x)) and (Ex (B(x))  is valid.
• ((Ex A(x)) and Ex B(x)) implies Ex (A(x) and B(x)) is not valid.

Due Monday April 22, 2000:

• Ex 5.10.1 a,b
• Ex 5.10.2 b, c, f
• Ex 5.11 b,d
• Ex 5.11.2