discrete math symbols cheat sheet

Guri Bee

3 min read

·

21-10-2024

1

0

Share

Demystifying Discrete Math Symbols: A Cheat Sheet for Beginners

Discrete mathematics is a fundamental branch of mathematics that deals with countable objects and their relationships. Understanding its symbols is crucial for grasping its concepts and tackling its problems. This cheat sheet aims to demystify common discrete math symbols, making them accessible to beginners.

Fundamental Symbols and Their Meanings:

1. Sets:

• **}** Empty set (a set containing no elements). Example: { represents an empty set.
• ∈: Element of. Example: x ∈ A means x is an element of set A.
• ∉: Not an element of. Example: x ∉ A means x is not an element of set A.
• ⊆: Subset. Example: A ⊆ B means every element in set A is also in set B.
• ⊂: Proper subset. Example: A ⊂ B means A is a subset of B but not equal to B.
• ∪: Union of sets. Example: A ∪ B represents the set containing all elements of A and B.
• ∩: Intersection of sets. Example: A ∩ B represents the set containing only the common elements of A and B.
• |S|: Cardinality of a set. Example: |{1, 2, 3}| = 3 (the set contains 3 elements).

2. Logic and Proofs:

• ¬: Negation (NOT). Example: ¬p means "not p".
• ∧: Conjunction (AND). Example: p ∧ q means "p and q".
• ∨: Disjunction (OR). Example: p ∨ q means "p or q".
• ⇒: Implication (IF...THEN). Example: p ⇒ q means "if p then q".
• ⇔: Equivalence (IF AND ONLY IF). Example: p ⇔ q means "p if and only if q".
• ∀: Universal quantifier (FOR ALL). Example: ∀x ∈ A (P(x)) means "for all x in A, P(x) is true."
• ∃: Existential quantifier (THERE EXISTS). Example: ∃x ∈ A (P(x)) means "there exists an x in A such that P(x) is true."

3. Functions:

• f: A → B: A function f from set A to set B.
• f(x): The value of function f at input x.
• Dom(f): The domain of function f (the set of all possible inputs).
• Ran(f): The range of function f (the set of all possible outputs).
• 1-to-1 (injective): A function where each input maps to a unique output.
• Onto (surjective): A function where every output has at least one corresponding input.
• Bijective: A function that is both 1-to-1 and onto.

4. Graph Theory:

• V: The set of vertices in a graph.
• E: The set of edges in a graph.
• (u,v): An edge connecting vertices u and v.
• deg(v): The degree of vertex v (number of edges connected to it).
• G(V,E): A graph with vertex set V and edge set E.

Practical Examples:

1. Set Theory:

• Example: Let A = {1, 2, 3} and B = {2, 3, 4}. Then:
  • A ∪ B = {1, 2, 3, 4}
  • A ∩ B = {2, 3}
  • A ⊆ B is false
  • A ⊂ B is false

2. Logic:

• Example: Consider the statement "If it is raining, then the ground is wet".
  • Let p: It is raining.
  • Let q: The ground is wet.
  • The statement can be represented by the implication p ⇒ q.

3. Functions:

• Example: Consider the function f(x) = x^2, with domain A = {1, 2, 3} and range B = {1, 4, 9}.
  • This function is not 1-to-1 because f(1) = f(-1) = 1.
  • This function is onto because every element in B has at least one corresponding element in A.

4. Graph Theory:

• Example: A graph with V = {a, b, c} and E = {(a, b), (b, c), (a, c)} has a degree of 2 for each vertex. This graph is connected because every pair of vertices is connected by a path.

Conclusion:

Understanding these symbols is crucial for anyone delving into discrete mathematics. This cheat sheet provides a quick reference and clear explanations. Remember, practice is key. As you work through problems and engage with the material, these symbols will become increasingly familiar and intuitive. Remember to always refer back to this cheat sheet whenever you need a quick refresher!

Note: This cheat sheet is based on the content from various Github resources, but it is not directly attributed to any specific user or repository. The examples and explanations are provided for learning purposes and may not represent the complete scope of each topic.