Ahmed_Mohamed_Al3adl's blog

By Ahmed_Mohamed_Al3adl, history, 19 months ago, In English

Set theory

Set

  • Collection of objects
  • Set objects called elements or members
  • Set elements can be anything: numbers, words, objects, or other sets.
  • Set elements can be a mix of several types.
  • Set elements are unique; so the set of {1,2,2} is the same set of {1,2}.
  • Set elements are unordered; so the set of {1,3,2} is the same set of {3,1,2}.
  • Set is denoted by a capital letter, often italicized as A, B, and so on.

Defining Sets

Restor notation

  • It's a way to define a set by listing its elements inside curly braces.
  • Can be inconvenient for large sets.
  • We can abbreviate large numeric sets that have a clear, unambiguous pattern, like: {1,2,3, ..., 998, 999, 1000}.
  • We can use the ellipsis character (...) to say that this set will continue forever, with its clear, unambiguous pattern, like: {1,2,3,4, ...} or {..., -3,-2,-1,0} or {..., -2,-1,0,1,2, ...}.
  • The sets with will known fixed elements called: Finite set.
  • The sets that continue forever are called Infinite sets.

    Examples
  • A = {1,2,3,4}

  • B = {"Ahmed", "Ali", "Osama"}
  • C = {{2, "Musa"}, {1, "Mohamed"}}
  • D = {1,2,3,...,99,100}
  • E = {1,2,3, ...}

Description Notation

  • It's a way to define a set by describing its elements within curly braces, like: {calendar months}.
  • The set description should be objective, not subjective. It means that the description should have the same sets always. So you can't tell that this set is well-defined: {Great movies}

    Example
  • A = {Numbers devisable by 2}

Special Sets

  • They are predefined sets we can use and reference.
Example
  • Set with no elements, its called: null set or empty set, and its equal to: {} or $$$\emptyset$$$.
  • Set contains every element of interest: It means every element in the context, like: {all school students} or {all rational numbers}. These sets are called universal set, and it's notated by U.
  • There are predefined sets for numbers that can be written with a special font Blackboard font. like these:
    • $$$\mathbb{R}$$$ = {real numbers}
    • $$$\mathbb{Q}$$$ = {rational numbers}
    • $$$\mathbb{Z}$$$ = {integers}
    • $$$\mathbb{N}$$$ = {natural numbers}
    • $$$\mathbb{C}$$$ = {complex numbers}

Set Builder Notaion

  • A most formal way to define sets of numbers, in textbooks and papers. Example: A = {x: $$$x \in \mathbb{N}$$$, x < 6}
  • In the Exmaple: A = {x: $$$x \in \mathbb{N}$$$, x < 6}. The Set A mean: x is a member of a set A as long as x meets the specified conditions x<6 & $$$x \in \mathbb{N}$$$.
  • If we will describe set A in this example: A = {x: $$$x \in \mathbb{N}$$$, x < 6}. We can say: A is the set of all x such that x is in $$$\mathbb{N}$$$ and x<6.
  • We can write the previous example like this also: A = {x| $$$x \in \mathbb{N}$$$, x < 6}. You can note that we just replace : with |.
  • The comma , between conditions, is means AND. This means x should achieve all AND conditions.
  • You can see that $$$x \in \mathbb{N}$$$ is define the type of the x (natural number). And this is good, because you will be confused if this condition does not exist, and there is just this one x<6; Then you will think that if x means just integers or includes natural or irrational numbers, or what?!
  • We can shortcut this expression: A = {x: $$$x \in \mathbb{N}$$$, x < 6} with: A = {$$$x \in \mathbb{N}$$$: x < 6}. This type of expression is common, You first express the type of the x, and then the conditions. So both expressions are ok. and express the same set.
  • We can use a Describe notaion with Set Builder Notation like this: B = {x: x is square of an integer, x <= 100}
  • We can use the OR keyword, within conditions like this: B = {$$$x \in \mathbb{N}$$$: x is the square of an integer OR x <= 10}

Interval notation

  • Is a compact way to reference or define sets of continuous Real numbers $$$\mathbb{R}$$$ over a range.
  • Is a shortened form of Set Builder Notation for continuous ranges of real numbers $$$\mathbb{R}$$$

    Example
    • W = {$$$x \in \mathbb{R}$$$: 0<=x<=1}
    • Set W equal also to: W = [0, 1].
    • For the Interval notation, we use [ for the inclusive beginning and ( for exclusive beginning. And ] for the inclusive end and ) for exclusive end.
Examples
  • W = {$$$x \in \mathbb{R}$$$: 0<=x<=1} = [0, 1]
  • W = {$$$x \in \mathbb{R}$$$: 0<x<=1} = (0, 1]
  • W = {$$$x \in \mathbb{R}$$$: 0<=x<1} = [0, 1)
  • W = {$$$x \in \mathbb{R}$$$: 0<x<1} = (0, 1)

Cardinality

  • Number of elements in a set.
  • Its notation is $$$|S|$$$, and this means: the cardinality of set S.
  • There are several ways to represent the cardinality, like:
    • $$$|A|$$$
    • n( A )
    • # A

Example:

  • A = {3,4,5,6}, So $$$|A|$$$ = 4.
  • B = {1,2,3,4,3}, So $$$|B|$$$ = 4. You can remember that there are no duplicate things in a set, even there are we ignore them, because duplicating things in a set is meaningless.
  • null set = {}, So $$$|\emptyset|$$$ = |{}| = 0. and this is Identity. [Identity: Is a statement that's always true.].
  • C = {{}}. So $$$|C|$$$ = 1; The set contains null set, and this is 1 thing in the set.

Set Membership:

  • You can say that 3 is an element of Set A by this notation: $$$3 \in A$$$
  • If you reverse it like this: $$$A \ni 3$$$. It will mean: Set A contains 3.
  • You can use $$$3 \notin A$$$ for saying: element 3 is not a member of set A.
  • You can use $$$A \not\ni 3$$$ for saying: Set A not contains element 3.

Venn Diagrams

  • It's a diagrammatic depiction of sets.
  • Universal set U in Venn diagrams denoted by a large rectangle, and you can label the rectangle with U in the top left corner.
  • Sets are usually drawn as ovals or circles within the rectangle. And you can put the set values inside the oval, or shade its interior.
  • When you shade the inside of an oval of set B. Then the Venn diagram represents the set of B.
    shade B set
  • When the hole of the rectangle is shaded, including the ovals inside it, we represent the U set ( universal set ).
    shaded rectangle
  • When You shade nothing, so the Venn Diagram represents $$$\emptyset$$$.
    Nothing shaded
  • And there is more about shading, we will discover it during this blog post.

Subset

  • If we have two sets A and B. And every element in set A is also in the set B. Then set A is a Subset of set B.
  • The subset symbole is: $$$ \subseteq$$$. So to say A is a subset of B we write: $$$A \subseteq B$$$.

    Example

    • A = {1, 2, 3, 4}
    • B = {1, 2, 3, 4, 5, 6} You can note that every element in set A is exist in set B, So $$$A \subseteq B$$$.
  • To draw the subset in Venn Diagram for this relation: $$$A \subseteq B$$$. You will draw the A oval inside the B oval.
    Set 'A' is a subset of set 'B'
  • If we have set A and set B and both of them have the same element, so each of them is a subset of each other. So $$$A \subseteq B$$$ AND $$$B \subseteq A$$$.
  • For subset we have three identities:
    • Any set is a subset of itself: $$$A \subseteq A$$$
    • $$$\emptyset$$$ = {} is a subset of every set.
    • Every set is a subset of U ( universal set )

      Proper subset

  • In the relation of subset like this: $$$A \subseteq B$$$. Set B can be equal to A exactly.

  • But with Proper subset ( $$$A \subset B$$$ ): Set B must contain all elements in Set A and more.
  • From this you can know that if: $$$A \subset B$$$, Then: $$$|A| \lt |B|$$$
  • You can realize that the set can't be a Proper subset of itself: $$$A \nsubset A$$$.

Superset

  • The opisit of subset is superset, And this is its notation: $$$\supseteq$$$. So if $$$A \subseteq B$$$, then $$$B \supseteq A$$$.
  • For superset we have three identities:
    • Any set is a superset of itself: $$$A \supseteq A$$$
    • Every set is a superset of the $$$\emptyset$$$.
    • U ( universal set ) is the superset of every set.

Proper Superset

  • In the relation of superset like this: $$$B \supseteq A$$$. Set B can be equal to A exactly.
  • But with Proper superset ( $$$B \supset A$$$ ): Set B must contain all things in Set A and more.
  • From this you can know that if: $$$B \supset A$$$, Then: $$$|A| \lt |B|$$$
  • You can realize that the set can't be a Proper superset of itself: $$$A \nsupset A$$$.

Set Operations

  • Used to create new sets from existing sets.
  • We can perform set Operations on sets to get different sets. It's similar to arithmetic operations, when you operate on 2 numbers to get a new number.

Unary set Operations

  • Unary set operations operate on one set.
Absolute Complement operation
  • Produce a new set of elements that exist in the universal set U and do not exist in the set S.
  • A set of elements that are not in the set.
  • There are several ways to notation the Set complement:
    • $$$A^c$$$
    • $$$A'$$$
    • $$$\overline{A}$$$
Example
  • If universal set U = {1, 2, 3, 4, 5}
  • And A = {1, 2, 5}
  • Then $$$A^c$$$ = {3, 4}
  • Always $$$|A|$$$ + |$$$A^c$$$| = $$$|U|$$$
  • We can describe the complement of a set with a Set builder notation like this: $$$A^c$$$ = {x: $$$x \in U$$$, $$$x \notin A$$$}
  • 2 Identities here:
    • $$$\emptyset ^ c$$$ = $$${} ^ c$$$ = U
    • $$$U ^ c $$$ = $$$\emptyset$$$ = $$${}$$$
Power Set
  • $$$\mathcal{P}(S)$$$ Produce a new set of all subsets of S.

    Example
    • S = {a, b}
    • $$$\mathcal{P}(S) =$$$ {{}, {a}, {b}, {a, b}}.
  • You may ask yourself how many subsets of a set with a large size, for sure I will not list them, so there is a mathematical rule for that, write?!
  • That's true there is one: $$$|\mathcal{P}(S)| = 2 ^ {|S|}$$$
How do we get the math rule for calculating the number of subsets of a set?
  • Basically, think of each element of the set, that it has 2 choices: (exist in a subset or not).
  • So, if you imagine a set with 3 elements. Each of one have 2 choices, so the number of subsets you can create from them is $$$2 \cdot 2 \cdot 2 = 2^3$$$
  • If you ask yourself why we used the multiply rule, you can imagine that the first element has two choices, and every one of the 2 choices of the 1st element has 2 choices for the 2nd element, and so on.
  • So now our math rule is clear: the number of subsets of a set = $$$2 ^ {the length of the set (set cardinality)}$$$
  • $$$|\mathcal{P}(S)| = 2 ^ {|S|}$$$

Binary Set Operations

  • Binary set operations operate on 2 sets.
Intersection Operation
  • It produces a new set with common elements between 2 sets.

    Example
    • If you have set A = {a, b, c, d}. and set B = {a, f, c, d}.
    • Then $$$A \cap B$$$ ( Set A intersect Set B. ) = {a, c, d}.
  • So from the previous example we can see that: $$$A \cap B$$$ = {x: $$$x \in A$$$, $$$x \in B$$$}
  • This is Venn Diagram for the Intersection operation:
  • Some Idintities about Intersection operation:
    • $$$A \cap A$$$ = A
    • $$$A \cap \emptyset$$$ = $$$\emptyset$$$
    • $$$A \cap U$$$ = A
  • The intersection operation obeys the commutative law: $$$A \cap B$$$ = $$$B \cap A$$$.
  • Disjoint sets are sets that have no elements in common; So if Sets A, and B are Disjoint sets, then $$$A \cap B$$$ = {} = $$$\emptyset$$$.
  • The intersection set operation is analogous to the logical operator AND; because an element must belong to both sets. In fact, very casually, $$$A \cap B$$$ is sometimes called: A AND B
Union Operation
  • It produces a new set of all elements of the 2 sets.
  • We can describe it by the Set Builder notation like this: $$$A \cup B$$$ = {x: $$$x \in A$$$ or $$$x \in B$$$}. We can translate this to: $$$A \cup B$$$ = All x values that belong to set A or set B.
  • The union operation obeys the commutative law: $$$A \cup B$$$ = $$$B \cup A$$$.
  • Some Idintities about union operation:
    • $$$A \cup A$$$ = A
    • $$$A \cup \emptyset$$$ = A
    • $$$A \cup U$$$ = U
  • This is Venn Diagram for the Union operation:
  • The Union set operation is analogous to the logical operator OR, because an element must belong to one of the sets. In fact, very casually, $$$A \cup B$$$ is sometimes called: A OR B
Inclusion-Exclusion Principle

The inclusion-exclusion principle is about how to make the union operation accurate.
You may ask: Why does the union operation need a special principle?

The reason is that the union operation, as we know, it includes all the elements of the sets in the operands of the operation.
So You might think $$$|A \cup B| = |A| + |B|$$$, but that only works when there's no overlap. You miss a small thing.
If sets A and B overlap, then both include the shared elements. So when you add $$$|A| + |B|$$$, the intersection $$$|A \cap B|$$$ is counted twice. To correct this, subtract it once.
So now you need to subtract $$$|A \cap B|$$$ from your last equation, so our new equation is: $$$|A \cup B| = |A|+|B|-|A \cap B|$$$
Note: Your previous one ( $$$|A \cup B| = |A| + |B|$$$ ) work, But just in case there no overlaps, but our new one ( $$$|A \cup B| = |A|+|B|-|A \cap B|$$$ ) can work for all situations.

Inclusive-exclusive principle It's called like that, because we include the sizes of the sets and then exclude the sizes of their overlaps (intersections) to avoid overcounting.

Now let us move on to a more complex question: $$$|A \cup B \cup C| = ??$$$
Here we need to know the cardinality of A union B union C. Let's take it easy, step by step:
- Firstly: we know that the union of 2 sets is a set with the elements of the 2 sets. What if there is a third one?
— Exactly, it includes all elements from A, B, and C.
— So $$$|A \cup B \cup C| = |A| + |B| + |C|$$$. At this point, you might be thinking: "Wait, isn't that wrong?" — and yes, it is!.
— That's incorrect, because any shared elements are counted twice.
— But now, there's something new:
— Now consider elements shared by all three sets: ( $$$A \cap B \cap C$$$ ).
— Can you estimate how many times these shared elements are counted?
- Secondly: how can we determine how often elements from intersections are counted when we sum all set cardinalities?!
— The basic way is to determine 2 things:
— 1st thing: Is the sum operation occurring, like here: $$$|A| + |B| + |C|$$$.
— 2nd thing: Is that intersection set, like this: $$$A \cap B \cap C$$$
— Then, for each time one of the sets that the intersection is part of it, and summed in the sum operation, you will count it as a +1 if it is added and -1 if it is subtracted.
— So in our example A, B, and C the intersection is a part of them and is added once; so your counter = 1; — So elements in this set $$$A \cap B \cap C$$$ calculated triple times. And this is logical, because $$$A \cap B \cap C$$$ produces the common elements between the 3 sets that are added.
— Now we discovered that: We added the intersection between every 2 sets twice, and between every 3 sets 3 times.
— From this, we realize an important fact: when we calculate the cardinalities of n sets and sum them up, any element that appears in multiple sets will be counted multiple times, exactly as the number of sets that contain it. (Let's call this: 1st rule)
- Thirdly If you have a common element between 3 sets, then it's also common between each combination of 2 sets of them.
— This is logical and can be generalized by saying that: If a number of elements is common between N sets, then it's common between each intersection of $$$N-1$$$ sets of them, until $$$N-(N-1)$$$. (Let's call this: 2nd rule)
Now let's try to solve the problem: $$$|A \cup B \cup C| = ??$$$

Firstly: I will sum the cardinalities of all sets: $$$|A| + |B| + |C|$$$
Now I know I sum every intersection of 2 sets twice and every 3 sets triple. And I need to sum them just once.
Secondly: I will subtract the cardinality of every intersection of 2 sets; So the equation is: $$$|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C|$$$ Now I get rid of the repetition of every intersection of 2 sets, but what about the repetition in the intersection of the 3 sets?
It might seem right to subtract it three times, but that's incorrect, because our equation improved to $$$|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap A|$$$ That changes the total count of triple intersections.
If you remember our 2nd rule you find the following:

  1. we need our last equation: $$$|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap A|$$$.
  2. we need to determine the sets that are included our set $$$|A \cap B \cap C|$$$ from the equation: And they are A, B, and C, $$$|A \cap B|$$$, $$$|A \cap C|$$$ and $$$|B \cap A|$$$.
  3. let's apply our 2nd rule:
  • So let's start by that I sumed $$$|A \cap B \cap C|$$$ zero times.
  • The sets A, B and C cardinalities are summd so now I can say I sum $$$|A \cap B \cap C|$$$ 3 times.
  • Then the sets $$$|A \cap B|$$$, $$$|A \cap C|$$$ and $$$|B \cap A|$$$ are subtracted so I will subtract 3, so I can say that I sumed $$$|A \cap B \cap C|$$$ zero times again. So the subtraction of all pairwise intersections cancels out the three-way intersection, which we must add back.
    Thirdly: I will add every intersection of 3 sets. So now our equation is: $$$|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap A| + |A \cap B \cap C|$$$. And this is the right answer, because now we are sure that every element in all sets is summed just once.

Ok, it looks good, but long work, is there something faster?!
Of course, I will share it with you, while solving: $$$|A \cup B \cup C \cup D| = ??$$$
The mathematician discovered that there is a clear pattern:

  • When we sum the cardinality of the sets of a union equation, we are always adding twice every 2 sets' intersection of the N-sets that are summed.
  • And when we subtract them, we always accidentally remove every 3 sets' intersection of the N-sets that are summed.
  • And when we add them, we are always adding twice every 4 sets' intersections of the N-sets that are summed.
  • And so on, until you get rid of the repetition of the intersection of all sets in the union operation.
  • So our equation answer is: $$$|A \cup B \cup C \cup D| = |A| + |B| + |C| + |D| - |A \cap B| - |A \cap C| - |A \cap D| - |B \cap C| - |B \cap D| - |C \cap D| + |A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D| - |A \cap B \cap C \cap D|$$$

Here’s a simple trick to make this easier:
If you aren't sure about getting all the intersections of N-sets. You can easily use the combination rule.
For example, you are not sure that you get all the 2 sets' intersections of 4 sets:

  • You basicley use the combination rule: nCr = $$$ n! / ((n-r)! * r!)$$$.
  • So 4C2 = $$$ 4! / ((4-2)! * 2!) = 4! / (2! * 2!) = (4 * 3 * 2!) / (2! * 2!) = (4 * 3) / 2! = 12/2 = 6$$$
  • So now you see you should have 6 intersections of 2 sets of the 4 sets.

What about subtracting: If I have a universal set and I want to get its cardinality and subtract it from the cardinality of $$$|A \cup B \cup C \cup D|$$$
Basically, you can do one of these 2 choices:

1st choice: you can get the cardinality of $$$|A \cup B \cup C \cup D|$$$ like you learn and subtract it from the $$$|U|$$$.
2nd choice: you can subtract them one by one and apply the rule but reverse it, look like this: $$$|U| - |A| - |B| - |C| - |D| + |A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D| - |A \cap B \cap C| - |A \cap B \cap D| - |A \cap C \cap D| - |B \cap C \cap D| + |A \cap B \cap C \cap D|$$$
You can see we can reverse the Inclusion and Exclusion rule so we start with subtracting, then adding, then subtracting again, and so on.

Relative complement
  • It produces a new set with all elements of a set, say A, and not in another set, say B.
  • The Relative complement operator is: \ Or -. So we can say: A - B = A \ B.

    Example
    If A = {1, 2, 3, 4}, B = {2, 3, 5, 6}
    Then $$$A \setminus B$$$ = A not in B = **Relative complement of B with respect to A = Relative complement of A in B = {1, 4}
    And we also can say that: $$$B \setminus A$$$ = B relative complement A = {5, 6}.
  • Here is a Venn Diagram for the relation: $$$A \setminus B$$$
     Venn Diagram for the relative complement of set Bin set A
  • You can relise the Set builder notation for relative complement for expression like this: $$$A \setminus B$$$ = {x: $$$x \in A$$$, $$$x \notin B$$$}.
  • When you take a complement against the set U ( universal set ), So this is the Absolute complement ( $$$S ^ c$$$ ).
  • Whan you take a complement against another set like B, So this is a Relative complement, like: $$$A \setminus B$$$.
  • The relative complement operator does not obey the commutative law: $$$A \setminus B \ne B \setminus A$$$
  • Try to imagine this truly relation: $$$A \setminus B$$$ = $$$A \cap B ^ c$$$.
Symmetric difference
  • It produces a new set with all elements of the operand sets except the common elements.
  • The operation operator can be $$$\oplus$$$ ( XOR ) or $$$\bigtriangleup$$$ ( Delta ). So $$$A \bigtriangleup B$$$ = $$$A \oplus B$$$.
  • The set builder notation for **Symetric difference for this expression: $$$A \bigtriangleup B$$$ = {x: $$$x \in A \oplus x \in B$$$.
  • The XOR ( $$$\oplus$$$ ): is a logical operation like AND and OR, and it's mean that one of the condition should be true, and the other is false, It not accept that both be true to false.
  • Below is the Venn diagram for Symmetric Difference to relise this truly expression: $$$A \oplus B$$$ = $$$(A \cup B) \setminus (A \cap B)$$$ = $$$(A \setminus B) \cup (B \setminus A)$$$
    Venn diagram for Symmetric Difference
  • Symmetric Difference obey the commutative law: $$$A \oplus B = B \oplus A$$$.
Cartesian Product (Cross Product)
  • Produce a new set of combinations of each element in the left operand set with each element in the right operand set, in parentheses or angle-brackets, and the elements separated with a comma.
  • Produce a new set of ordered pairs of the elements of the 2 sets in the operation.
  • The Cross Product operator is: $$$\times$$$

    Example
    • A = {a, b}
    • B = {1, 2, 3}
    • $$$A \times B$$$ = {(a, 1), (b, 1), (a, 2), (b, 2), (a, 3), (b, 3)}
  • We can express it by Set Builder Notation: $$$A \times B$$$ = {(x,y): $$$x \in A$$$, $$$y \in B$$$}.
  • Note: {1, 2} is not an ordered pair, because a set is not ordered by definition. But this (1, 2) is an ordered pair. So {1, 2} $$$=$$$ {2, 1}, But $$$(1, 2) \ne (2, 1)$$$.
  • $$$|A \times B| = |A| \cdot |B|$$$: The cardinality of cross product of 2 sets = The product of the cardinalities of both sets.
  • The cross product does not obay commutative law: $$$A \times B \ne B \times A$$$.
  • The cross product cardinalies obay commutative law: $$$|A \times B| = |B \times A|$$$.

More than 2 operands (2 Sets)

When you try to manipulate more than 2 sets, there are some rules you need to know to be sure that you get the right set that you need.

Associative Law
  • You can use Union operation between multiple sets in any order; because Union operationI obays the Associative Law, Like: $$$A \cup B \cup C = B \cup C \cup A$$$
  • It's the same for Intersection operation: $$$A \cap B \cap C = B \cap C \cap A$$$
  • It's the same for Symmetric difference operation: $$$A \oplus B \oplus C = B \oplus C \oplus A$$$. I will share the Venn diagram for this operation because it may confuse you:

    I expect that maybe you are confused about the shaded center area, maybe you think that all intersecting areas should not be shaded, but let me clarify this for you:
  • First: you can choose any 2 of the sets and make the Symmetric difference operation between them. You will get 2 shaded sets, except for the intersection area between them.
  • Secondly, you will make the Symmetric difference operation between the result of the last step and the remaining set. You will recognised that the center area is being not shaded in the last result, but in the same time it's a part of the set that not involve to the previous operation, so now the elements of the center area is belong to the remainder set and not belong to the last result, so it can be shaded respected for the Symmetric difference operation.
Distributive Law
  • When we use the Union and intersection operations, we should pay attention to the order of operations, which can be established with parentheses.
  • We need the pay attention to the order; because the mix of these operations does not respect the Associative Law. So $$$(A \cup B) \cap C \ne A \cup (B \cap C)$$$
  • Expression with union and intersection obay the Distributive Law, So:
    • $$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$$. It's like $a \cdot (b + c) = (a \cdot b) + (a \cdot c).
    • $$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$$.
  • It's called Distributive because what is outside parentheses is distributed inside them.
De Morgan's Laws
  • They are Identities about sets complemetns:
    • The complement of the union = The intersection of complements.

      Example

      $$$(A \cup B) ^ c = A ^ c \cap B ^ c$$$.
      We can translate this rule to logical words: NOT ( A OR B ) = NOT A AND NOT B. — The complement of the intersection = The union of the complements.

      Example:
      $$$(A \cap B) ^ c = A ^ c \cup B ^ c$$$.
      We can translate this rule to logical words: NOT ( A AND B ) = NOT A OR NOT B.

Full text and comments »

  • Vote: I like it
  • -24
  • Vote: I do not like it

By Ahmed_Mohamed_Al3adl, history, 19 months ago, In English

How to count how many rectangles of size r × s fit inside a larger rectangle of size n × m.

Example:

Now, if I have a 5*8 rectangle, and I want to know how many 3*2 rectangles are inside the 5*8 rectangle?
Here, 5*8 is n * m and 3*2 is r * s. But I use letters to express a general rule.

Let's get the rule

Let's take a step-by-step approach to create the rule:
- Firstly, it's logical when I am at any square in n * m chape, and I want to draw r * s rectangle, it should still have >(r-1) squares in n dimension, and >(s-1) squares in m dimension.
- Secondly: The last valid square in n dimention will be n - (r - 1), and any squere blew it is also valid, so n - (r - 1) is the number of valid squares as a base point in n dimention, if I think on the chape base start from right bottom corner, and it's the (0, 0) position.
- Thirdly: We apply the same for the m dimension, so now we know that the valid quares in the m dimension are equal to m - (s - 1).
- Forthly: multiply the number of valid squares in n and m dimensions, to get all valid squares.
The general rule is: (n - (r -1)) * (m - (s - 1)).

Apply the rule in the example:

  • r * s = 3 * 2 AND n * m = 5 * 8.
  • r = 3, s = 2, n = 5 and m = 8;
  • (n - (r - 1)) * (m - (s - 1)) = (5 - (3 - 1)) * (8 - (2 - 1)) = (5 - 2) * (8 - 1) = 3 * 7 = 21.
  • So there are 21 rectangles with the dimensions 3*2 in the rectangle with 5*8 dimensions.

Full text and comments »

By Ahmed_Mohamed_Al3adl, history, 19 months ago, In English

Permutations and Combinations

Permutation

  • Is associated with arranging things in a different order.
  • The order of things matters.

Simple Example

If you have 3 letters A, B, C, and you order them like this: ABC, ACB, BCA.
So now you have 3 permutations. Because order is important, ABC, ACB, and BCA are different things for permutations.

Simple Example 2

If you have the letters: A, B, C, D, and I want you to give me how many different ways you can arrange 2 of the four letters?
- You can make a list for possible arrangements like this: AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.
- Note: You can't duplicate things when you try to arrange letters, like AA, BB, CC, or DD. These are not possible arrangements.
- Now count our list of arrangements, you will find 12.

Math rule

Now you can see that finding a permutation will consume more time, if the question is more complex, like: find different ways to arrange 3 letters of the 26 letters?
So you will waste your time listing them, which may lead to many mistakes.
So now we have a mathematical rule that helps us to express permutations, and an equation to find the answer faster.
To express permutation, we used this: nPr:
- n is the whole number of things, like 4 in our last sample example.
- r is the number of things that I will arrange in a single way, like 2 in our last simple example.
- P is just a short expression for Permutation word.
The Permutation rule is: nPr = n!/(n-r)!:
- n!: is n factorial, factorial is the product of all numbers from n to 1: like if I say: 3! (3 factorial) it's equal: 3 * 2 * 1 = 6.
- r!: is r factorial.

How do we get the rule of Permutation for distinct things

Imagine with me that you have 5 letters, and you need to know how many words of length 3 letters you can create with these 5 letters, without using every letter just once in each word.
So now go with me step by step:
- Firstly, imagine that you have 3 blank ears like this: __ __ __. And you have 5 letters to use.
- Now, how many possible letters can you add in the blank area? The answer is absolutely, you can put any letter from the 5 letters. So now for the 1st blank area, you have 5 possibilities.
- For the 2nd blank area, how many letters can you possibly add there?! The answer is 4.
- If you ask why 4? The basic answer is because when you add any letter of the 5's to the 1st blank area, you will not use this letter again, so now you have just one possible 4 letters, you can choose one of them to add.
- Now you can see that for the 1st blank area, you have a possible 5 letters you can add, and for each one of the 5 letters that can be in the 1st blank area, you have possible 4 letters, can be in the 2nd area. So you now can expect there are 20 possibilities for just how to arrange the 5 letters in the 1st 2 blank areas.
- Now, for the 3rd blank area, what possible letters can you add to it? I expect you to answer this by yourself, it's 3 letters.
- Now, for each one of the 20 possible arrangements for 5 letters in the 1st 2 blank areas, there are 3 possible letters that can be added next to each of the 20 possibilities, it's main there are 20*3 possibilities for how you can arrange 3 letters of 5 letters.
- So all possibilities are equal to 60.
- Now remember what we do, we produce the possibilities of the 1st blank (5 letters) with possibilities of the 2nd blank (4 letters) with the possibilities of the 3rd blank (3 letters) = 5 * 4 * 3 = 60.
- Now, how does this lead us to the permutation rule?!
- Basically, mathmation says the 5 * 4 * 3 is a part of 5! (5 factorial). But we ignored the rest of the 5! specifically (2 * 1).
- So on 5! (5 * 4 * 3 * 2 * 1) How can we delete the 2 * 1? The answer is: by just dividing by 2! (2 * 1).
- So, how can we get the 2 from the base information: 5P3 (arrange 3 letters of 5 letters).
- By subtracting 3 from 5 = 2. And this can work for each question like this that the things that we deal with are unique and there is no duplication.
- So now our rule is nPr = n!/(n-1)!

Simple example:

If you have the letters: A, B, C, D, and I want you to give me how many different ways you can arrange 2 of the four letters?
- This time, will we use our equation: nPr = n!/(n-r)!.
- Our n is the number of things = 4.
- Our r is the number of things in one arrangement = 2.
- 4P2 = 4!/(4-2)! = 4!/2! = 4*3*2*1/2*1 = 4*3 = 12.

Complex example (important)

If you have 5 books, find how many ways you can arrange them. For this question, I have 5 books, and I need to know how many ways I can order them. so my Permutation expression will be like this: 5P5 = 5!/(5-5)! = 5!/0!.
Now you may feel confused because you may think that 0! = 0. This is wrong, 0! = 1. So now we can complete: 5!/0! = 5!/1 = 5! = 5 * 4 * 3 * 2 * 1 = 120.

Permutation for duplicated things:

Assume that you want to know how many times you can arrange the word "amaddisss".
As you learn, you will say it's 9P9, so it's equal to 9!/1, and this is wrong, because of the duplication of a, d, and s.
Your way will calculate amaddisss, amaddisss, amaddisss, amaddisss, amaddisss, amaddisss, amaddiss, amaddiss,... (there are still more) as a multiple arrangement although they are just one way, but you treat the 3 's' letters and 2 'a' letters and 2 'd' letters as: s1, s2, s3, a1, a2, d1, d2. But in fact, they just produce the same word, multiple times.
So there is a unique rule for permutation for duplicated things: n!/(k1!*k2!...):
- The n is the number of things.
- The k1, k2, and so on, are the number of repetitions for each repeated letter.
- In our example 'amaddisss', we have 3 repeated letters, with 3 repetitions for s and 2 repetitions for a and d.
- Now our formula for this question is: 9!/(3! * 2! * 2!)

How do we get the rule of Permutation for duplicated things

Mathematicians started with a simple example like: 'aa'
Now, how many ways can you arrange the latter of the word 'aa'?
With our normal way it will be 2P2 = 2! = 2.
But in reality, it's just 1, so we divide the 2! by 2! to get the right answer.
What about 'aaa'?
Ok thie ways to arrange it are 3P3 = 3! = 6.
Ok, this is wrong, it's just 1. So again, the solution is 3!/3! = 1.
What about this 'aab'? Ok the ways to arrange it is 3P3 = 3! = 6.
Ok, this is wrong because aab is the same as aab if I just swapped the 2 a's.
But from previous work, we know that we divide by the number of repetitions to get the right answer: 3!/2! = 3. Yeah, 3 is the right answer.
What about this 'aabb'?
Now we know that 4! is the wrong answer, and to delete the repetition swapping a's, we will use this 4!/2! = 12.
But this is wrong because we still need to get rid of the repetition of answers that we get from the repetition of b.
We know that we can also get rid of it by taking the last answer 12 and dividing by 2! = 12/2 = 6. And this is the right answer.
Now you don't need to separate the division, you can just multiply them and get the same answer, because we know if I say: (a/b)/c = a/b * 1/c = a/(b*c).
So now our rule is: n!/(k1! * k2! *...)

Compination

  • Is concerned about combining things.
  • The order of things doesn't matter.

Simple Example

If you have 3 letters A, B, C, and you order them like this: ABC, ACB, BCA.
So there's only 1 combination because order doesn’t matter. ABC, ACB, and BCA all represent the same group of letters in combinations.

Simple Example 2

If you have the letters: A, B, C, D, and I want you to tell me how many different ways we can combine 2 of the 4 letters?
- You can first make a list of possible combinations like this: AB, AC, AD, BC, BD, CD.
- Note: that you can't duplicate things when you try to combine letters, like say: AA, BB, CC, or DD. These are not possible combinations.
- Note Also: In combination order does not matter, so all of: BA, CA, DA, CB, DB, and CD are not possible combinations, because they are just different orders for the same other combinations.
- Now count our list of combinations, you will find 6.

Math rule

Now you can see that finding a combination will consume more time, if the question is more complex, like: find different ways to combine 3 letters of the 26 letters?
So you will waste your time listing them, which may lead to many mistakes.
So now we have a mathematical rule that helps us to express combinations, and an equation to find the answer faster.
To express the combination, we used this: nCr:
- n is the whole number of things, like 4 in our last sample example.
- r is the number of things that I will combine in a single way, like 2 in our last simple example.
- C is just a short expression for a Combination word.
The Combination rule is: nCr = nPr/r! = n!/((n-r)! * r!):
- n!: is n factorial, factorial is the product of all numbers from n to 1: like if I say: 3! (3 factorial) it's equal: 3 * 2 * 1 = 6.
- r!: is r factorial.

How do we get the rule of Combination for distinct things

  • The base difference between combination and permutation is that combination is not interested in the order of the things, and for that reason, the combination results are always <= the permutation results. So, the combination results are part of the permutation.
  • You can also note that when you get a permutation for unique things, you will always find that the repetition of appearance of the combination of things is equal. like: for a, b, c. when you arrange 2 of them, you get this: ab, ac, ba, bc, ca, cb. You can note that a and b appear with each other twice, and also the same for a, c and c, b.
  • And if you want to know how many times can combination of things can be repeated in any permutation, just think about how mach for a number of things you arrange can be repeated. I mean, when I say arrange 3 books, the number of repeated arrangements is basically how many ways they can be arranged, it's 3! (6 ways).
  • So in any nPr, each possibility value, if we ignore the order and think about the combination of things, the same unique things combine in different orders r! times.
  • So, basically, the combination rule dates this repetition by dividing the result of the permutation by the r!.
  • Now our rule: nPr/r! = (n!/(n-r)!)/r! = (n!/(n-r)!)*1/r! = n!/((n-r)! * r!).

Simple example:

If you have the letters: A, B, C, D, and I want you to tell me how many different ways we can combine 2 of the 4 letters?
- This time, will we use our equation: nCr = nPr/r! = n!/((n-r)!*r!).
- Our n is the number of things = 4.
- Our r is the number of things in one arrangement = 2.
- 4C2 = 4!/((4-2)! * 2!) = 4!/(2!*2!) = 4*3*2*1/2*1*2*1 = 4*3*2*1/4 = 3 * 2 * 1 = 6.

Full text and comments »

By Ahmed_Mohamed_Al3adl, history, 19 months ago, In English

Karatsuba algorithm

When we need to multiply 2 huge numbers, like 12093 * 23801, we can use the normal way we learned in school, which will cost nearly O(n^2), because each number should multiply with the other numbers. So if you have two big integers with a length of 100, it will cost you 10000 multiplication operations. Karatsuba algorithm is more optimizer because it cost O(n^1.58).

The logic behaind the Karastuba Algorithm

  • Let's imagine we have a number with 2 digits like "23".
  • We split the number into 2 parts: 2 and 3, we will call them a AND b.
  • Now a = 2 and b = 3, and the original number = a * 10 + b;
  • If we say that n is the length of the digit, then our original number is: a * 10^n/2 + b;
  • If you confused you can calculate: a = 2, b = 3, n = 2 (the integer length) so 2 * 10^1 + 3 = 23.
  • If we call our "23" number with x, we need to multibly it with another number y = 59.
  • We will split y also so: c = 5, and d = 9; and y = c * 10^n/2 + d
  • so now we can say: x x y = (a * 10^n/2 + b) . (c * 10^n/2 + d)
  • When distributing the equation, we get: (a * 10^n/2 + b). (c * 10^n/2 + d) = (a*10^n/2).(c*10^n/2) + ad * 10^n/2 + bc * 10^n/2 + bd
  • Now I want you to know that (a*10^n/2). (c*10^n/2) is the same as: a * 10^n/2 * c * 10^n/2; because we don't need priority for multiplication operations if the part just contains multiplication. so we can say: a * 10^n/2 * c * 10^n/2 = ac * 10^(2(n/2)).
  • Also for this part: ad * 10^n/2 + bc * 10^n/2, we can devide the equation by 10^n/2 so it will be: 10^n/2(ad+bc).
  • Let's improve the equation now, with the last 2 steps: ac * 10^(2(n/2))+ 10^(n/2). (ad+bc) + bd
  • Now x.**y** = ac * 10^(2(n/2))+ 10^(n/2) . (ad+bc) + bd
  • You cee that we need 3 important values: ac & db & (ad+bc). And the gift here is that we can do that by just 3 multiplication operations:
    • ac = karatsuba(a, c) //You can see that we will recursively use the Karatsuba algorithm.
    • bd = karatsuba(b, d)
    • ad_plus_bc = karatsuba(a+b, c+d) - ac - db// This looks strange, but you can see we multiply (a+b) with (c+d), then we subtract (ac) and (db), so why!!
      • Lets try to go throw the operation: (a+b) * (c+d) — ac — db = ac + ad + bc + bd — ac — db = ad + bc.
      • So you can find that when we solve the operation we get the sum of the ad and bc in one step, and this makes our algorithm effective, because we replace 2 multiply operations a * d and b * c and then adding both with just one multiply operation.

Example

  • x = 23 | y = 59
  • a = 2 & b = 3
  • c = 5 & d = 9
  • ac = 10
  • bd = 27
  • a+b * c+d = 5 * 14
  • Note that because the operation of a+b * c+d is not between numbers under than 10 (cause 14), we need to treat it as a separate multiply operation:
    • x_ = 5 | y_ = 14
    • a_ = 0 & b_ = 5
    • c_ = 1 & d_ = 4
    • a_ * c_ = 0
    • b_ * d_ = 20
    • a_ + b_ * c_ + d_ = 5 * 5 = 25
    • a_ * d_ + b_ * c_ = (a_ + b_ * c_ + d_ ) — a_ * c — b_ * d_ = 25 — 0 — 20 = 5
    • Apply the results in the equation: x_ * y_ = a_ * c_ * 10^(2(n/2)) + 10^(n/2) * (a_ * d_ + b_ * c_) + b_ * d_
    • a_ * c_ * 10^(2(n/2))+ 10^(n/2) * (a_* d_ + b_ * c_) + b_ * d_ = 0 * 10^(2(2/2)) + 10^(2/2) * 5 + 20 = 50 + 20 = 70
  • So now a+b * c+d = 70
  • ad+bc = (a+b * c+d) — ac — bd = 70 — 10 — 27 = 33
  • Apply the results in the equations: x.**y** = ac * 10^(2(n/2))+ 10^(n/2) . (ad+bc) + bd
  • 10 * 10^(2(2/2)) + 10^(2/2) * 33 + 27 = 10 * 100 + 10 * 33 + 27 = 1000 + 330 + 27 = 1330 + 27 = 1357
  • And yeah, this is the right answer: 1357.

Full text and comments »

  • Vote: I like it
  • -28
  • Vote: I do not like it

By Ahmed_Mohamed_Al3adl, history, 19 months ago, In English

Enhance functions parameters

  • When you pass parameters in most of high level languages, you don't think about how it passed, because in general there is specific way language treat with the variables and asigned values.
  • Here in C++ things is different, If you pass the argument to your function in in a wrong way it can cost you un nessessary operations, so now we will see different ways to deal with passing parameters.

Pass the parameter as a Value

  • When you pass the parameter as a value it will copied, and then passed.
  • If the you pass huge data or object like so long String it will cost you so mutsh to copy then pass.
  • It's prefered to use with cheap data like int, char, bool, double.
  • Don't use it with values that it's size > sizeof(veid*) * 2.

Example

double sum(double num1, double num2) // ✅ Because double is cheap.
vector<bool> num_greater_than_0(vector<int> nums) // ❌ Because vector can be so huge and it will be high cost to copied.

Pass the parameter as a lvalue reference

  • When you pass the parameters as a rvalue reference, it means that the parameter point to the same location argument point to. and prevent the parameter to copy the value of the argumetns.
  • It's good for huge sized objects, like String, vector, array, etc.
  • It's bad approch for low sized objects, because it just make overhead without great benifit. low sized objects or data types can be like: bool, int, char, double.
  • Don't use it with values it's size <= sizeof(void*) * 2.

Example

double sum(double& num1, double& num2) // ❌ Because double is cheap and reference is expensive, and it also add unneccessary indirect for the argument.
vector<bool> num_greater_than_0(vector<int>& nums) // ✅ Because vector can be so huge and it will be high cost to copied, reference will avoid unneeded copy.

Pass the parameter as a rvalue reference

  • When you pass the parameters as a rvalue reference, it means that the parameter transfare the ownership of the resource of the original variable to the parameter, and the old varibale will be no longer asigned to the value. and prevent the parameter to copy the value of the argumetns.
  • It's good for huge sized objects, like String, vector, array, etc.
  • It's bad approch for low sized objects, because it just make overhead without great benifit. low sized objects or data types can be like: bool, int, char, double.
  • Don't use it with values it's size <= sizeof(void*) * 2.

Example

double sum(double& num1, double& num2) // ❌ Because double is cheap and lvalue reference is expensive, and it also add unneccessary indirect for the argument.
vector<bool> num_greater_than_0(vector<int>&& nums) // ✅ Because vector can be so huge and it will be high cost to copied, lvlaue reference will avoid unneeded copy.

Save your original data from modification

  • You can use const keyword to prevent parameter of a varible from changing.

    Example

    const double PI = 22/7;
    vector<string> add_prefix(const vector<string>& words);
    

    What is the difference between lvalue and rvalue references?

  • Both references prevent coping of your valuable value.

Lvalue reference type&

  • Lvalue reference it refer to the same location the original variable refere.

    Example

    string a = "Ahmed Al-3adl";
    string& b = a; // Asign lvalue reference *b* to the left-value a
    
  • Lvalue reference cannot bind to rvalues.

    Example

    string full_name(string& first_name, string& last_name)
    full_name("Ahmed", "Al-3adl"); // ❌ ERROR: Cannot bind rvalue to lvalue reference
    

    Rvalue reference type&&

  • Rvalue reference it refer to the same location the original variable refer, but chang the originla variable to refer to nothing.

    Example

    string a = "Ahmed Al-3adl";
    string&& b = std::move(a); // You need std::move because it's not normal for rvalue reference to refer to left-value(variable) 
    
  • It you try to refer to right-value(un asigned value) it will asigned temporary to some location in the memory.

    Example

    string full_name(string&& first_name, string&& last_name);
    full_name("Ahmed", "Al-3adl"); // ✅ It will work
    
  • Note: if you ask your selfe what about if I pass rvalue to a noramal parameter that will take it as a value. The noremal parameter will copy it.

    Example

    string full_name(string first_name, string last_name);
    full_name("Ahmed", "Al-3adl"); // ✅ It will work and the data will copied
    

    what we mean by rvalue and lvalue

    Rvalue => Right value

  • We mean it the value the be in the right of asign operator = and it at most times is a pure values.

    Example
    int a = 9; // You can see 9 in the right of the asign operator.
    

    Lvalue => Left value

  • We mean it the value that be in the left of asign operator = and it always a variable.

    Example
    int a = 9; // You can see a in the left of the asign operator.
    

Full text and comments »

  • Vote: I like it
  • -35
  • Vote: I do not like it

By Ahmed_Mohamed_Al3adl, history, 19 months ago, In English

From this problem I try to solve on exercism I get an interested discussion, opening my eyes to bitwise operators.

Bitwise Operations in C++

Bitwise operations manipulate individual bits of integers. C++ provides six bitwise operators:

Operator Name Example
& Bitwise AND x & y
| Bitwise OR x | y
^ Bitwise XOR x ^ y
~ Bitwise NOT (Complement) ~x
<< Left Shift x << n
>> Right Shift x >> n

Bitwise AND (&)

Performs a bitwise AND operation on the corresponding bits of two numbers. Only 1 & 1 results in 1, everything else is 0.

Example

int x = 5;  // 0101
int y = 3;  // 0011
int result = x & y; // 0001 (1 in decimal)

Use Cases:

  • Masking specific bits
  • Checking if a number is even/odd (x & 1 == 0 for even)

Bitwise OR (|)

Performs a bitwise OR operation. If at least one bit is 1, the result is 1.

Example

int x = 5;  // 0101
int y = 3;  // 0011
int result = x | y; // 0111 (7 in decimal)

Use Cases:

  • Combining bit masks

Bitwise XOR (^)

Performs an exclusive OR operation. If bits are different, the result is 1, otherwise it's 0.

Example

int x = 5;  // 0101
int y = 3;  // 0011
int result = x ^ y; // 0110 (6 in decimal)

Use Cases:

Swapping two numbers without an extra variable:

int a = 5, b = 3;
a = a ^ b; // 0101 ^ 0011 = 0110 (6)
b = a ^ b; // 0110 ^ 0011 = 0101 (5)
a = a ^ b; // 0110 ^ 0101 = 0011 (3)

Bitwise NOT (~)

Flips all bits (**1 → 0, 0 → 1**). This is a one's complement operation.

Example

int x = 5;   // 0000 0101
int result = ~x; // 1111 1010  (Two's complement form for -6)

Caution:

~x is not simply -x, it's actually -(x+1) in signed integers due to two's complement representation.

Use Cases:

  • Finding the negative of a number (~x + 1 is -x)
  • Flipping bits in low-level programming

Left Shift (<<)

Shifts all bits to the left by n positions. Fills right with 0s.

Example

int x = 5;   // 0000 0101
int result = x << 1; // 0000 1010 (10 in decimal)
  • Equivalent to multiplying by 2^n

    Use Cases:

  • Fast multiplication by powers of 2 (x << 3 = x * 8)
  • Bit manipulation tricks

Right Shift (>>)

Shifts all bits to the right by n positions.

Example

int x = 5;   // 0000 0101
int result = x >> 1; // 0000 0010 (2 in decimal)
  • Equivalent to integer division by 2^n

    Use Cases:

  • Fast division by powers of 2 (x >> 2 = x / 4)
  • Extracting individual bits
  • For signed integers, behavior depends on the compiler (logical vs arithmetic shift).


Summary Table

Operator Effect Equivalent To
x & y Bitwise AND —
x | y Bitwise OR —
x ^ y Bitwise XOR —
~x Bitwise NOT -(x+1) (for signed)
x << n Left shift (multiply by 2^n) x * (2^n)
x >> n Right shift (divide by 2^n) x / (2^n)

Bonus: Checking if a Number is a Power of 2

bool isPowerOf2(int x) {
  return (x > 0) && ((x & (x - 1)) == 0);
}

Full text and comments »

  • Vote: I like it
  • -29
  • Vote: I do not like it