Discrete Mathematics for Computer Science: Sets and Basic Logic

Flashcards covering key vocabulary and concepts from Discrete Mathematics lecture notes, focusing on Sets and foundational aspects of Propositional Logic, including definitions, notations, operations, and logical connectives.

Set Builder Notations

A way to describe a set, typically as A = {a  A | P(a)} or {expression: rule}.

Subset (A ⊆ B)

Set A is a subset of set B if and only if every element of A is also an element of B.

Not a Subset (A ⊗ B)

Set A is not a subset of set B.

Cardinality of a finite set (|A|)

The number of distinct elements of a finite set A.

Power Set (P(A))

The set of all possible subsets of a set A.

Cartesian Product (A â B)

The set of all ordered pairs (a, b) where 'a' is an element of set A and 'b' is an element of set B (also called ordered 2-tuples).

Cartesian Product (n sets)

For n sets A1, A2…An, the set of an ordered n-tuple (a1, a2,…,an) where a1  A1, a2  A2 and an  An.

Union of Sets (A  B)

The set of all elements that are elements of A OR B (A  B = {x | x  A OR x  B}).

Intersection of Sets (A  B)

The set of all elements that are elements of both A AND B (A  B = {x | x  A AND x  B}).

Difference of Sets (A - B)

The set containing the elements of A that are NOT in B (A - B = {x | x  A AND x â B}).

Complement of a Set (A or Ac)

The set difference of the universal set U and set A (A = {x  U | x â A}).

Identity Laws (Sets)

Rules stating A â = A and A â U = A.

Domination Laws (Sets)

Rules stating A â U = U and A â = .

Idempotent Laws (Sets)

Rules stating A â A = A and A â A = A.

Complement Laws (Sets)

Rules stating A â A = U and A â A = .

Absorption Laws (Sets)

Rules stating A â (A â B) = A and A â (A â B) = A.

Double Complement Laws (Sets)

A rule stating (A) = A.

Commutative Laws (Sets)

Rules stating A â B = B â A and A â B = B â A.

Associative Laws (Sets)

Rules stating (A â B) â C = A â (B â C) and (A â B) â C = A â (B â C).

Distributive Laws (Sets)

Rules stating A â (B â C) = (A â B) â (A â C) and A â (B â C) = (A â B) â (A â C).

De Morganâ Laws (Sets)

Rules stating A â B = A â B and A â B = A â B.

Proof

A method for establishing the truth.

Logic

The study of formal reasoning; a systematic way of thinking that allows one to deduce new information from old information.

Proposition (Statement)

A sentence that is either true or false but not both.

Compound Proposition

A proposition created by connecting individual propositions with logical operations (connectives).

Connectives (Logical Operations)

Logical operations used to form compound propositions, including Negation, Conjunction, Disjunction, Exclusive Or, Conditional, and Biconditional.

Truth Table

A representation showing the relationship between the truth values of propositions and all possible combinations of truth values for its component propositional variables.

Negation (p)

The opposite truth value of a proposition p.

Conjunction (p  q)

The logical operation "p AND q," which is true only if both p and q are true.

Disjunction (p  q)

The logical operation "p OR q," which is true if at least one of p or q is true.

Order of Operations (Logic)

The precedence for logical connectives: 1) Negation (), 2) Conjunction (), 3) Disjunction ().

Exclusive Or (p  q)

The logical operation "p XOR q," which is true if exactly one of p or q is true, but not both.