Syllabus:

• Propositional Logic
  • Truth tables
  • Truth trees
  • Checking tautologies
  • Logical equivalences
  • Consistent sets of formulas
  • Arguments and validity
  • Translation
  • Formal proofs (Fitch-style natural deduction)
  • Proofs in mathematics
  • Advanced topics in prop. logic
    1. CNF and DNF
    2. Soundness and completeness of propositional logic
    3. Horn clauses and satisfiability
    4. Resolution
• Sets
  • Cartesian Product
  • Power set
  • Set operations
  • Set identities
  • Boolean algebras
• Predicate Logic
  • Formulas
  • Meaning
  • Validity
  • Translation
  • Formal proofs
  • Proofs in mathematics
  • Advanced topics in predicate logic
    1. Soundness and completeness of predicate logic
    2. Incompleteness
    3. Undecidability
• Induction and Recursion
  • Weak Induction
  • Strong Induction
  • Structural Induction
  • Recursive Definition
• Functions and Relations
• Graph Theory

Required Textbooks:

1. Math Foundations of Informatics, 2nd Edition, E. Haghverdi, ClassPak Publishing, IU, Bloomington, Indiana, 2007. ISBN: 1-4211-0697-3.
2. Tarski's World Revised and Expanded, D. Barker-Plummer, J. Barwise and J. Etchemendy, CSLI Publications, Stanford, 2008. ISBN-13 978-1-57586-484-6, ISBN-10 1-57586-484-3.

Recommended Textbooks:

1. The Language of First-order Logic, 3rd Edition, J. Barwise and J. Etchemendy, CSLI Lecture Notes, 1993. ISBN 0-937073-99-7.
2. Discrete Mathematics and Its Applications, seventh edition, Kenneth H. Rosen, McGraw Hill Higher Education, 2012. ISBN 978-0-07-338309-5.

Handouts and Homework: All handouts and homework assignments will be posted on Oncourse.

Assistant Instructors:

Alex Gates
Office hours: Wednesday 12:00-2:00 pm.
Office: Info East Rm 400.
E-mail:ajgates@umail.iu.edu

Grading:

• Homework assignments: 20%
• There will be weekly homework.
• Each homework will consist of the following parts:
  1. Regular problems: A set of problems chosen from several sources including the textbooks above.
  2. Computer problems: A set of problems chosen from several sources that require the use of the software package Tarski's World.
• Each homework will be assigned on a Thursday and will be due the Friday after in the lab.
• Solutions must be written LEGIBLY.
• It is encouraged to discuss the problem sets with others, but everyone needs to turn in a unique personal write-up.
• Quizzes: 20%
• During each lab except for those during exam weeks there will be a 10-minute quiz, based on the homework assignment due that same week.
• The quizzes combined count more than a midterm.
• There will be NO make up quizzes. However, the lowest quiz grade will be dropped.
• Each lab session will include a discussion of the homework problems due that same week. In addition, you are welcome to discuss any other problems you need to with your AI.
• Computer assignments will be discussed during the lab hour.
• Midterm I: 15%
• Midterm I is scheduled on 02/21/2012.
• Midterm II: 15%
• Midterm II is scheduled on 04/05/2012.
• Final exam: 30%.
• Final exam is scheduled for 2:45-4:45 p.m., Tues., May 1.
• We will have a closed book, closed-note exam. However, you are allowed to bring your letter-size cheat sheet to the exam.

Ground rules:

• I strongly advise you to attend all the classes and take good notes.
• NO make up quizzes. However, the lowest quiz grade will be dropped.
• Late homework will NOT be accepted. However, the lowest homework grade will be dropped.
• There will be NO make up midterm exams.
• Calculators are NOT allowed during the midterm and final exams. However, you can bring a letter-size sheet with notes and formulas.
• The final grade will be calculated according to the evaluation scheme given above and these grades will then be curved to determine your letter grades. However if you get less that 25/100 on the final exam or your total grade is less than 45/100 your final grade will automatically be an F.
• NO Incomplete grades will be given under any condition.
• NO extra work, extra credit or any thing outside the regular homeworks and quizzes will be assigned. Please plan your study strategy during the term accordingly.
• Grading mistakes:
  If during the semester you feel there has been a mistake made in your grading by the AIs, please contact them first. If after meeting with the AIs you still feel there is a problem with the marking, please contact me.
• Collaborative work:
  One of the best ways to learn new material is to collaborate in groups. You may discuss the homework problems with your classmates, and in this way make the learning process more enjoyable. However, the homework you hand in must be your own work, in your own words and your own explanation.
• Here is the link to The Code of Student Conduct.