Boolean Algebra & Switching Circuits - Lecture 01 (Vocabulary Flashcards)

Vocabulary flashcards covering key concepts from Lecture 01: power sets, relations, and partial orders.

Power set

The set of all subsets of a given set.

Subset

A set Y is a subset of X if every element of Y is also an element of X.

P(X) (Power set notation)

The set of all subsets of X.

Cartesian product A × B

The set of all ordered pairs (a, b) with a ∈ A and b ∈ B.

Relation

A relation from A to B is a subset of A × B; if A = B, it is a relation on A.

Reflexive relation

A relation R on A is reflexive if for every a ∈ A, (a, a) ∈ R.

Symmetric relation

A relation R is symmetric if aRb implies bRa (i.e., (b, a) ∈ R).

Antisymmetric relation

A relation R is antisymmetric if whenever aRb and bRa, then a = b.

Transitive relation

A relation R is transitive if aRb and bRc imply aRc.

Partial Order (poset)

A relation that is reflexive, antisymmetric, and transitive.

Equivalence relation

A relation that is reflexive, symmetric, and transitive.

Equivalence class

For an equivalence relation ~ on a non-empty set S and a ∈ S, the equivalence class of a is { x ∈ S | x ~ a }.

Non-empty

Having at least one element.

Comparable

In a POSET, two elements x and y are comparable if x ≤ y or y ≤ x.

POSET (Partially Ordered Set)

A non-empty set with a partial order relation (usually written as ≤).