Discrete Mathematics Exam 1

Derived Implications

The original implication (P

Boolean Algebra

A __, bB, consists of an associated set, B, together with three operators and four axioms. The binary operators + and * map elements of B x B to elements of B. The unary operator complement, (bar), maps elements of B to elements of B.

Proposition 2.29: The Uniqueness of 0 and 1

In any Boolean algebra, the distinct elements 0 and 1 are unique.

Duality Principle (for Boolean Algebras)

Let T be a theorem that is valid over a Boolean algebra. Then if all 0s and 1s are exchanged, and if all + and * are exchanged (with a suitable exchange in parentheses to preserve operator precedence), the result is a theorem that is also valid over the Boolean algebra.

Biconditional

p if and only if q (p

Boolean Algebra

A __, bB, consists of an associated set, B, together with three operators and four axioms. The binary operators + and * map elements of B x B to elements of B. The unary operator complement, (bar), maps elements of B to elements of B.

Cardinality; Infinite Set

The __ of a set is the number of elements in the set. The cardinality of the set, S, is denoted by S .

A set, S, is said to be __ if for each positive integer, n, there is a proper subset, Sn S, with Sn = n.

Cartesian Product

Let {Si | i = 1, 2, ...., n} be a fine collection of two or more sets. The Cartesian product of the collection, denoted S1 X S2 X S3 X ... X Sn, is the set of all ordered n-tuples with coordinate ai a member of Si. That is,

The Cartesian products S X S X ... X S is often abbreviated as S^n.

Complement

The __ A-bar of the set A is the set of all elements of the universal set that are not elements of A.

Conditional

A statement that is nor a taut. nor a contra. is called a __ statement.

Contradiction

A statement is called a __ if every entry in its truth table is F.

Deferred Acceptance Algorithm

round = 1

All suitors are initially considered unattached.

while at least one suit has no pending proposal, repeat the following:

Each unattached suitor proposes to his or her string of suitors, rejecting all except the highest ranked suitor. That suitor is told to wait while the proposal is considered. (The waiting suitor therefore becomes attached for the next round.)

Add 1 to round.

end while

All suits accept the proposal of the single suitor waiting for an answer.

Derived Implications

The original implication (P -> Q); The contrapositive (-Q -> -P) (logical equiv. to orig.); The converse (Q -> P); The inverse (-P -> -Q) (logically equiv. to conv.)

Difference

The set of all elements that are in A but are not in B. Denoted by A - B.

Disjoint

sets that have no elements in common

Duality Principle (for Boolean Algebras)

Let T be a theorem that is valid over a Boolean algebra. Then if all 0s and 1s are exchanged, and if all + and * are exchanged (with a suitable exchange in parentheses to preserve operator precedence), the result is a theorem that is also valid over the Boolean algebra.

Empty Set

∅, a set with no elements

implication

if p, then q. Denoted as P -> Q.

Intersection

The set of elements that are common to two or more sets. Denoted by A (upside down U) B.

Logical Equivalence

when 2 statements imply each other (the statements must both be true or both be false).

Negation of AND, OR, and NOT

just remember the negation symbol and that it undoes NOT. NAND and NOR.

Partition

A __ of a set A is a set of non-empty subsets of A that are pairwise disjoint and whose union is A. Basically a divided set.

Power Set

The __ of S, denoted P(s), is the set of all subsets of S (including the empty set and S itself).

Proper subset

B is a (underlined c) of A, but B is not equal to A. Denoted by a sideways U.

Proposition 2.17

Let A and B be sets. Then A (union) B (is a subset of) A.

Proposition 2.18

Let A and B be sets. Then

(A - B) U (B - A) = (A U B) - (A B)

Proposition 2.19: A De Morgan Law for Sets

Let A and B be sets. Then

(A U B)(complement) = A (intersects/or) B

Proposition 2.20: Eliminating Set Difference

Let A and B be sets. Then A - B = A (intersects/or) B (bar).

Proposition 2.29: The Uniqueness of 0 and 1

In any Boolean algebra, the distinct elements 0 and 1 are unique.

René Descartes advice

- Never accept anything as true unless I recognize it to be certainly and evidently true.

- Divide each of the difficulties that I encounter into as many parts as possible and necessary for an easier solution.

- Think an orderly fashion, beginning with the things that are simplest and easiest to understand and gradually reaching toward more complex knowledge.

- In both the process of searching and in reviewing when in difficulty, make enumerations so complete, and reviews so general, that I will be certain nothing is omitted.

Set Equality

two sets are equal if and only if they have the same elements

Set; Element; Member; Universal Set

Informally, a set is a collection of distinct objects, each thought of as a single entity. The set is the aggregate collection. The objects in the set are called the elements or members of the set. The potential elements are considered to be members of a set U, called the universal set.

The notation x (exists in) A is used to indicate that x is an element of the set A. The notation y -(exists in) A indicates that y is not an element of A.

Stability (Thm)

The Deferred Acceptance Algorithm always produces a stable assignment.

Stable Assignment

Given a collection of n men, m1.....mn, and n women, w1.....wn, we wish to associate every person with a mate. Suppose that each person ranks the people of the opposite gender by preference with no ties. An assignment is one of the possible collections of n couples. An assignment is stable if there does not exist a man, mi, and a woman, wj, who are not partners but mi prefers wj to his assigned bride and wj prefers mi to her assigned groom.

Subset

Set A is a __ of set B if and only if every element of set A is also in set B. This is denoted by B (underlined c) A.

Symmetric Difference

The symmetric difference of the sets A and B is denoted A (triangle) B which = (A-B) U (B-A).

Tautology

A statement is called a __ if every entry in its truth table is T.

Termination (Thm)

The Deferred Acceptance Algorithm always t_s.

The Operators AND, OR, and XOR

up arrow is and, down arrow or

Truth Table

A table used as a convenient method for organizing the truth values of statements

Unattached

A suitor will be called __ if he/she is not currently waiting for a suitee to respond to a proposal

Union

The set that contains all of the elements of two or more sets. Denoted by A U B.

Union and Intersection of Multiple Sets

Let {Si | i Y} be a collection of sets with index set Y. Their union is the set

Their intersection is the set

Viable

A suitee is __ to a suitor if that suitee has not already rejected a proposal from that suitor