George Mason University

Department of Computer Science

Fall 2006

INFS 501 - Discrete and Logical Structures for Information Systems

Wed 7:20 p.m. - 10:00 p.m.

Science and Tech I  Room 122

12/15/2006 0030

Announcements

  • A reminder regarding point totals: I divide the homework scores by 40 to make the relative value more realistic with respect to the 10% weight. Remember that at the end of the term I multiply by the factor necessary to make the HW count exactly 10% of your final grade. Until the end of the term we can not tell if these numbers will go up or down. It will depend on how many points there are in each category, and the effect will be different for each student.

   Q1   Q2   MID   Q3   Q4   Q5   FIN   HW   TOT 
 TOT 10 12 140 13 14   68 29.5 286.5
 AVG 7.6 6.3 103.3 4.9 12.2   50.0 23.6 208
 HI 10 12 137 9 14   68 29.3 274.3

Homework Assignments   (Updated after each lecture)

Finals Schedule

Academic Calendar

Text Errata

Activating your Mason e-mail


                                            Dr. Michael Smeltzer
                                              msmeltze dot gmu dot edu

                                               Office Hours: By Appointment


                                            Huaming Liu
                                              hliu5 dot gmu dot edu

Graduate Teaching Assistant
                                       
Office Hours: Thursday 5:30.7:00 STII Room 432 Table #8
By Appointment  


PREREQUISITES :

Six credits in undergraduate mathematics


DESCRIPTION :

Course Catalog

Study of discrete and logical structures for information systems analysis and design including basic set theory and proof techniques, propositional and predicate logic, trees and graphs, finite state machines, formal languages and their relation to automata, computability and computational complexity, formal semantics-operational, axiomatic and denotational approaches.


TEXT:

Discrete Mathematics with Applications
Susanna Epp
Third Edition, Thomson - Brooks/Cole, 2004

From the Preface:  Logic and Proofs....to think abstractly.  Induction and Recursion.... to divide and conquer smaller problems. Combinatorics...to count and arrange objects.  Algorithms and Their Analysis... to solve problems, determine correctness and manage resources.  Discrete Structures...to develop general models.


A Second Reference:

Logic and Language Models for Computer Science
Henry Hamburger and Dana Richards
Prentice Hall, 2002

*****This text is NOT required and is only provided as another sorurce on the subject of propositional and predicate logic.*****

From the Preface:   This book, used in CS 330 at GMU, is about language and knowledge models, and formal methods. Logic and formal language share the job of modeling, with logic providing models of meaning and formal language paying attention to form..... Logic supports proofs of results throughout mathematics and computer science.... Material pertinent to INFS 501: Chapter 2 - Propositional Logic: Propositions, operators, and truth tables. Proofs of equivalence with truth tables. Laws of propositional logic. Chapter 3 - Proving Things: Rules of inference. Proof by rules. Assumptions. Proof examples. Types of theorems and proof strategies. Chapter 4 - Predicate Logic: Predicates and functions. Predicates, English, and sets. Quantifiers. Multiple quantifiers. Logic for data structures. Chapter 5: Proving with Predicates: Inference rules with predicates. Proof strategies with predicates. Applying logic to mathematics. mathematical Induction. Limits of logic.

The second half of the book is on language models and is not a a helpful reference for this course.


"NOTIONAL" SCHEDULE:

WEEK CHAPTERS TOPIC
8/30 1.1 Introduction; Slides-> Propositional logic; truth tables, proofs and logical equivalence;  De Morgan's laws. 
9/6 1.2; 1.3 Conditional statements; Slides-> Other methods of proof: substitution, rules of inference.  
9/13 2.1  QUIZ1: Rules of inference
9/20 2.2; 2.3; 2.4  Slides-> Predicate logic; Universal and existential quantifiers  
9/27   3.1, 3.4 QUIZ2: Start methods of proof  
10/4 3.5; 3.6; 3.7; 5.1 Finish methods of proof;   Set theory;  Venn diagrams;
10/11 5.2; 5.3; 5.4 Slides-> Set operations, set partitions, set proofs, set paradoxes.
10/18   MIDTERM
10/25 6.1 , 6.2 Midterm Review Slides-> Counting and probability
11/1 6.3; 6.4
11/8 7.1; 7.2; 7.3; 7.4 QUIZ3: Slides-> Functions, one-to-one and onto, inverse functions, pigeon hole principle, composition of functions
11/15 10.1; 10.2; 10.3 Slides-> Relations, equivalence relations, equivilence classes
11/22   Thanksgiving Recess
11/29 10.4 QUIZ 4: Cryptography
12/6 10.5 Partial Order Relations
12/13   FINAL at 7:30

GRADING:

Grades will be calculated as follows:
Quizzes 30 %
Midterm Exam 30 %
Final Exam 30 %
Homework 10 %


EXAMS AND HOMEWORK:

The quizzes will be closed book.
The midterm and final will be open book.
There will be NO extra credit offered.

University Finals Schedule


Homework will be assigned, graded, and is critical for your understanding. It is due at the biginning of class every week. Hints and solutions will be made available the day after it is handed in. Late homework will not be accepted. The homework will be the basis for five difficult, in-class quizzes which will cover the material covered since the preceding exam. There will be one midterm and a final. The final will cover the whole course, but will emphasize the material studied after the midterm exam. If you have a valid excuse such as business travel and inform me "beforehand" by at least 24 hours that you will miss a class, you can make up a quiz. If you inform me after the fact or on the day of the quiz, you can not. You can NOT make up the midterm or final, and you must take the final during the registrar's official scheduled timeslot -ABSOLUTELY NO EXCEPTIONS!! - Coordinate your travel accordingly.

I reserve the right to compare problem solutions, programming code, pseudo code submitted by students to any other code or solutions (either students or otherwise) by any means necessary (automated or non-automated) to identify violations of the
GMU Honor Code