summary discrete math lesson 1 which talks on logic

Discrete Math

1. A Brief Summary for Exam 1
Subject Topics
•Propositional Logic (sections 1.1, 1.2)
–Propositions
•Statement, Truth value,
•Proposition, Propositional symbol, Open proposition
–Operators
•Define by truth tables
•Composite propositions
•Tautology and contradiction
–Equivalence of propositional statements
•Definition
•Equivalence laws
•Proving equivalence (by truth table or equivalence laws)

2. •Predicate Logic (sections 1.3, 1.4)
–Predicates (Propositional functions)
–Universal and existential quantifiers, and the duality of
the two (wrt negation)
–When predicates become propositions
•All of its variables are instantiated
•All of its variables are quantified
–Nested quantifiers
•Quantifiers with negation
–Logical expressions formed by predicates, operators,
and quantifiers

3. •Mathematical reasoning (proofs) (section 1.5)
–Terminology (axiom, theorem, conjecture, argument, etc.)
–Rules of inference
–Valid argument (hypotheses and conclusion)
–Construction of valid argument using rules of inference
•Write down each rule used, together with the statements used by the
rule
–Proof methods (proof if P then Q)
•Direct proof: show if P true then Q must be true (i.e., P  Q  T)
•Indirect proof: show that if Q is false then P must be false (its
contrapositive is a tautology)
•Prove by contradiction: assume Q is false then derive a contradiction

4. •Set Theory (sections 1.6, 1.7)
–Basics
•Membership, subsets, cardinality, set equality
•Defining sets: enumeration, builder function
•Cartesian product
•Power set
–Set operations (union, intersection, difference, complement)
•Definitions (in words and in logical expressions)
•Set identity laws
•Show two sets are equal (by identity laws and by membership table)

5. •Functions (section 1.8)
–Basics
•What is a function (what are not function
•Domain, co-domain, range, image, pre-image
–Types of functions
•Injective (1-1), surjective (onto), bijective (1-1 and onto)
•Inverse function
•Composition of function

6. •Boolean Algebra (sections 10.1, 10.2)
–Boolean function and Boolean expression
•Domain ({0,1}), Boolean variables
•Boolean operations (sum, product, complement)
–Define Boolean function by table
•Two Boolean functions are equal if they have the same table
•Minterms: generate Boolean expression from table
–Correspondence between
•Propositional logic
•Sets
•Boolean algebra

7. •Algorithms (sections 2.1 – 2.3)
–Algorithm and its properties
•Definiteness, finiteness, and correctness
–Complexity of algorithm
•How much resource it takes to solve a problem
•What’s important is the growth (maters only with large problems)
•Big-O notation (upper bound)
•Common growth functions
•Useful rules for Big-O

8. Types of Questions
•Conceptual
–Definitions of terms
–True/false
–Multiple choice
•Problem solving
–Work with small concrete example problems
•Proofs
–Simple theorems or propositions
•No questions will be outside of this summary
and lecture notes