COS 203 - Discrete Structures

Flashcards for Discrete Structures course, covering topics from propositional logic to sequences and summations.

Propositions

Statements that are either true or false.

Connectives

Logical connectives used to form complex statements.

Conjunction (AND, ^)

A logical connective that is true only if both propositions are true.

Disjunction (OR, v)

A logical connective that is true if at least one proposition is true.

Negation (NOT, ¬)

The inverse of a proposition.

Implication (IF…THEN, →)

If this is the case, then this will happen.

Biconditional (IF AND ONLY IF, ↔)

Connective when both propositions are either true or false.

Truth Table

A table that lists all possible truth values of propositions and their combinations.

Logical Equivalences

Propositions that have the same truth values in all scenarios.

De Morgan's Laws

¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q

Predicate Logic

Extends propositional logic by dealing with predicates and quantifiers.

Universal Quantifiers (∀)

Indicate the predicate is true for all elements in the domain. Represented by symbol ∀.

Existential Quantifiers (∃)

Indicates that there exists at least one element in the domain for which the predicate is true. Represented by symbol ∃.

Negation of Quantifiers

¬∀xP(x) ≡ ∃x¬P(x) and ¬∃xP(x) ≡ ∀x¬P(x)

Set

A collection of distinct objects, considered as an object in itself.

Roster Notation

Listing elements explicitly. e.g., A = {1, 2, 3, 4}

Set Builder Notation

Defining elements by a property they satisfy. e.g., B = {x | x > 0}

Union (∪)

Combines elements from both sets.

Intersection (∩)

Elements that are common to both sets.

Difference (-)

Elements in one set but not in the other.

Complement (A')

Elements not in the set.

Function (f: A -> B)

Assigns each element in A exactly one element in B.

Injective (One-to-one)

Different elements in A are mapped to different elements in B.

Surjective (Onto)

Every element in B is mapped by some element in A.

Bijective (One-to-one Correspondence)

Function is both Injective and Surjective.

Sequence

An ordered list of elements, typically defined by a function an where n is a positive integer.

Arithmetic Sequence

Each term is obtained by adding a constant difference to the previous term.

Geometric Sequence

Each term is obtained by multiplying the previous term by a constant ratio.

Summation (∑)

Denotes the sum of terms in a sequence.