Material to review for first exam

Note: be sure to see answer key for homework #9 which you turned in on 9/28

NO CALCULATORS ALLOWED. SHOW ALL WORK

Know Polya’s steps in problem solving

1. understand the problem

2. devise a plan

3. implement the plan

4. look back

Know formulas for

permutations n!/ (n-r)!

order matters

combinations n!/ r!(n-r)!

Sets

Order doesn’t matter

Duplicates not allowed

Collection of elements

Set operations: union, intersection, Cartesian product, complement, difference Venn diagrams

Terms:

binary operations,

unary operations,

closure,

subsets,

power set,

null set,

cardinality

proper subset

countable / uncountable

Counting

Multiplication principle

Additional principle

disjoint

using principles together

Pigeonhole principle

Propositional logic

Main question: is a given argument valid?

p. 21 - “a propositional wff is a valid argument when it’s a tautology”

Symbols

And conjunction

Or disjunction

Not negation

Implies implication

Page 8 chart

Commutative tautological equivalence

Associative tautological equivalence

Distributive tautological equivalence

Complement tautological equivalence

Identity tautological equivalence

Show me an example of a given T.E

What T.E. is this?

Double Negation

DeMorgan’s law - page 9

Equivalence rules – p. 23

Commutative

P OR Q IS EQUIVALENT TO Q OR P

P AND Q IS EQUIVALENT TO Q AND P

Associative

(P OR Q) OR R IS EQUIVALENT TO P OR (Q OR R)

(P AND Q) AND R IS EQUIVALENT TO P AND (Q AND R)

DeMorgan’s law - page 9

(P OR Q)’ IS EQUIVALENT TO P’ AND Q’

(P AND Q)’ IS EQUIVALENT TO P’ OR Q’

Implication

P IMPLIES Q IS EQUIVALENT TO P’ OR Q

Double Negation

(P’)’ IS EQUIVALENT TO P

Definition of equivalence

P <-> Q IS EQUIVALENT TO (P IMPLIES Q) AND (Q IMPLIES P)

Inference Rules

Used to prove that an argument is valid

Modus ponens

Modus tollens

Conjunction (and-ing)

Simplication (de-and-ing)

Addition (or-ing)

Deduction method

More Inference Rules

Hypothetical syllogism

Disjunctive syllogism

Contrapositive (2)

Distributive (2)

Self-reference (2)

Exportation

Inconsistency

ALGORITHM - an unambiguous step by step (method, procedure, process) for solving a problem in a finite amount of time using a finite amount of space

Well formed formula - wff - a syntactically legitimate string

Predicate logic

Has quantifiers :

For all – universal

There exists - existential

Instantiation

Generalization

Remember to thing: for all - implication

There exists - conjunction

Things to worry about

Understanding the problem

How do I translate English into logic?

If you use A as a proposition – state what it stands for

(i.e. A is ann is a teacher)

What is the problem really asking ?