CS计算机代考程序代写 Logic (PHIL 2080, COMP 2620, COMP 6262) Bonus Material: Recap on Set Notation

Logic (PHIL 2080, COMP 2620, COMP 6262) Bonus Material: Recap on Set Notation

Logic (PHIL 2080, COMP 2620, COMP 6262)
Bonus Material: Recap on Set Notation

Pascal Bercher

Planning & Optimization

Yoshihiro Maruyama

Logic
Intelligent Agents

College of Engineering and Computer Science
the Australian National University (ANU)

25 February 2021

Set Notation

Set Notation

Pascal Bercher and Yoshihiro Maruyama 1.5

Set Notation

Sets versus Lists

We will heavily base upon sets.
Sets are invariant against repetition.
• E.g., {a, a, b, b, b, c} = {a, b, c}.

Sets are invariant against re-ordering.
• E.g., {a, b, a, b, c, b} = {a, a, b, b, b, c}.
• Thus, we also get {a, b, a, b, c, b} = {a, a, b, b, b, c}

= {a, b, c} = {a, c, b}
= {b, a, c} = {b, c, a}
= {c, a, b} = {c, b, a}

Therefore, sets are fundamentally different from lists!
• Lists are also called sequences or tuples.
• E.g., the list (a, b, c) is different from both (a, c, b) and (a, a, b, c)

Pascal Bercher and Yoshihiro Maruyama 2.5

Set Notation

Set Notation

The empty set {} is usually always denoted by the symbol ∅.
In contrast, the empty list (i.e., empty sequence) is denoted by ε.

Let X be a finite set. Then, 2X denotes its “power set” that
contains all subsets.
• E.g., if X = {a, b, c}, then

2X = {{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, ∅}
The “cardinality” of a set X is the number of its elements and
denoted by |X |. Cardinality is not recursive!
• E.g., if X = {a, b, c}, then |X | = 3.
• Regarding non-recursiveness: if, e.g., X = {{a, b}, c}, then
|X | = 2, because it has two elements, not three.

Note that for all possible X it holds that |2X | = 2|X |.
• E.g., if X = {a, b, c}, then |2X | = 2|X | = 23 = 8

Pascal Bercher and Yoshihiro Maruyama 3.5

Set Notation

Set Notation, cont’d

We write a ∈ X if a is contained in X , i.e., an element of X . We
say a /∈ X if a is not contained in X . Again, this is not recursive!
• E.g., if X = {{a, b}, c}, then only {a, b} ∈ X and c ∈ X , but

a /∈ X and b /∈ X . Also {c} /∈ X .
We write Y ⊆ X if Y is a (not necessarily strict) subset of X . We
write Y * X if this does not hold.
• E.g., {a, b, c} ⊆ {a, b, c} (in fact, X ⊆ X for all sets X ).
• E.g., {a, c} ⊆ {a, b, c}.
• E.g., if X = {{a, b}, c}, then {c} ⊆ X and {{a, b}} ⊆ X ,

but {{a, c}} * X and {a, b} * X .
Let X ,Y , Z be sets. Then X × Y × Z is the cartesian product of
these sets. It’s the set of tuples with one element from each set.
• Formally, X × Y × Z = {(x , y , z) | x ∈ X , y ∈ Y , z ∈ Z}
• One normally uses standard math notation, e.g., X 2 = X × X . We

use X n for exactly n times X , and X∗ for all numbers in N ∪ {0}.

Pascal Bercher and Yoshihiro Maruyama 4.5

Set Notation

Set Operations

X ∪ Y denotes the set union of X and Y , i.e., X ∪ Y contains all
elements that occur in any of those sets.
• Formally: X ∪ Y = {z | z ∈ X or z ∈ Y}

X ∩ Y denotes the set intersection, i.e., X ∩ Y contains all
elements that are contained in both sets.
• Formally: X ∩ Y = {z | z ∈ X and z ∈ Y}

X \ Y denotes the set subtraction, i.e., X \ Y contains all
elements that are contained in X , but not (“minus the ones”) in Y .
• Formally: X \ Y = {z ∈ X | z /∈ Y}

Pascal Bercher and Yoshihiro Maruyama 5.5

Set Notation