Skip to main content

Sets and Propositions in Discrete Mathematics

Introduction​

Sets and propositions are fundamental concepts in discrete mathematics, forming the basis for many other areas of study within computer science and mathematics. This guide aims to provide a thorough introduction to these topics, covering essential definitions, properties, and applications.

What are Sets?​

A set is a collection of unique elements, known as members or elements of the set. Sets are denoted using curly braces {} and are typically written in uppercase letters (e.g., A, B, C).

Key Points About Sets:​

  • Elements in a set are distinct and unordered.
  • Each element either belongs to a set or does not belong to the set; there is no partial membership.
  • Sets can contain elements from any domain, such as numbers, characters, or even other sets.

Example 1: Basic Set Notation​

A = \{1, 2, 3, 4\}
B = \{\text{apple}, \text{banana}, \text{cherry}\}

In this example:

  • Set A contains the numbers 1, 2, 3, and 4.
  • Set B contains the strings "apple", "banana", and "cherry".

Set Membership​

An element is said to belong to a set if it is one of the elements in the collection. This is denoted using the symbol ∈. If an element is not a part of a set, we use the symbol ∉.

3 \in A \quad \text{(3 is an element of set A)}
\text{orange} \notin B \quad \text{(orange is not an element of set B)}

Set Operations​

Set operations allow us to create new sets based on existing sets. Common operations include union, intersection, difference, and complement.

1. Union​

The union of two sets A and B, denoted by A ∪ B, is a set containing all the elements that are in A, in B, or in both.

A = \{1, 2, 3\}, \quad B = \{3, 4, 5\}
A \cup B = \{1, 2, 3, 4, 5\}

2. Intersection​

The intersection of two sets A and B, denoted by A ∩ B, is the set containing all elements that are both in A and B.

A \cap B = \{3\}

3. Difference​

The difference of two sets A and B, denoted by A - B or A \ B, is the set containing all elements that are in A but not in B.

A - B = \{1, 2\}

4. Complement​

The complement of a set A, denoted by A', is the set of all elements not in A, typically within a given universal set U.

U = \{1, 2, 3, 4, 5\}, \quad A = \{1, 2, 3\}
A' = \{4, 5\}

Propositions and Logic​

Propositions are statements that are either true or false. They form the basis of logic in discrete mathematics and are used to reason about sets and many other topics.

What is a Proposition?​

A proposition is a declarative statement that is either true or false but not both. Examples of propositions include:

  • "2 + 2 = 4" (true)
  • "The sky is green" (false)

Propositions can be combined using logical operators such as AND (∧), OR (∨), and NOT (¬).

Logical Operators​

  1. Conjunction (AND): The proposition P ∧ Q is true if both P and Q are true.

    Example:

    P: 2 + 2 = 4 \quad \text{(true)}
    Q: 3 > 5 \quad \text{(false)}
    P \land Q: \text{false}

  2. Disjunction (OR): The proposition P ∨ Q is true if either P or Q (or both) are true.

    Example:

    P \lor Q: \text{true}

  3. Negation (NOT): The proposition ¬P is true if P is false, and false if P is true.

    Example:

    P: 2 + 2 = 4 \quad \text{(true)}
    \neg P: \text{false}

Logical Equivalences​

Logical equivalences are statements that express the same truth value under all possible truth assignments. Some common equivalences include:

  • De Morgan's Laws:

    \neg (P \land Q) \equiv \neg P \lor \neg Q
    \neg (P \lor Q) \equiv \neg P \land \neg Q

  • Double Negation:

    \neg (\neg P) \equiv P

  • Commutative Laws:

    P \land Q \equiv Q \land P
    P \lor Q \equiv Q \lor P

Conclusion​

Understanding sets and propositions is critical in discrete mathematics, as they lay the foundation for more advanced concepts such as functions, relations, and proof techniques. By mastering the basic set operations and logic, you'll be well-equipped to explore other areas of mathematics and computer science.