Other useful sets are:
Binary
=
{0,1}
the binary values
Binary∗
=
{0,1}∗
set of all finite binary strings
Bools
=
{true,false}
truth values
Bools∗
=
{true,false}∗ set of finite sequences of truth values
Char
=
{a,b,···}
set of all alphanumeric characters
Char∗
=
{a,b,···}∗
set of all finite character strings
A.1.6
Set operations: union, intersection, complement
If A and B are sets, then the intersection A ∩ B is the set consisting of all elements that
are in both A and B. The union A ∪ B is the set consisting of all elements that are either
in A or in B or in both A and B. We can express these definitions using variables as:
A ∩ B = {x | x ∈ A ∧ x ∈ B},
A ∪ B = {x | x ∈ A ∨ x ∈ B}
where ∧ is the notation for the logical and and ∨ is the symbol for the logical or. The
predicate “x ∈ A ∧ x ∈ B” reads “x is a member of A and x is a member of B”; “x ∈ A ∨ x ∈
B” reads “x is a member of A or x is a member of B.” The logical and of two predicates
is also called their conjunction and their logical or is also called their disjunction. The
symbols ∧ and ∨ are called logical connectives.
If A, X are sets, then X \ A is the set consisting of all elements in X that are not in A (think
of it as set subtraction, X − A). When A ⊂ X, X \ A is called the complement of A in X.
When X is understood, we can write Ac instead of X \ A.
Lee & Varaiya, Signals and Systems
661
A.1. SETS
A ∪ B
A ∩ B
Ac
A
A
B
X
(a)
(b)
Figure A.1: (a) Union and intersection. (b) Set complement.
We gain some intuitive understanding by depicting sets and set operations using pictures.
Figure A.1 illustrates union, intersection, and complement.
A.1.7
Predicate operations
Given two predicates P(x) and Q(x) we can form their conjunction P(x) ∧ Q(x), and their
disjunction P(x) ∨ Q(x). These predicate operations correspond to the set operations of
intersection and union:
{x ∈ X | P(x) ∧ Q(x)} = {x ∈ X | P(x)} ∩ {x ∈ X | Q(x)}
{x ∈ X | P(x) ∨ Q(x)} = {x ∈ X | P(x)} ∪ {x ∈ X | Q(x)}.
(A.9)
There is a helpful visual similarity between ∧ and ∩, and between ∨ and ∪.
The counterpart of the complement of a set is the negation of a predicate. We denote
by ¬Pred(x) the predicate that evaluates to false for any value of x for which Pred(x)
evaluates to true, and that evaluates to true for any value of x for which Pred(x) evaluates
to false. We read “¬Pred(x)” as “not Pred(x)” or the “negation of Pred(x).” For example,
{n ∈ N | ¬(n < 5)} = {5,6,7,···},
since ¬(n < 5) evaluates to true if and only if n < 5 evaluates to false, which happens if
and only if n is larger than or equal to 5.
662
Lee & Varaiya, Signals and Systems
A. SETS AND FUNCTIONS
In general we have the following correspondence between predicate negation and set com-
plement:
{x ∈ X | ¬Pred(x)} = X \ {x ∈ X | Pred(x)}.
(A.10)
We can combine (A.9), (A.9), and (A.10) to obtain more complex identities. If P(x) and Q(x) are predicates, then
{x ∈ X | ¬(P(x) ∧ Q(x))} = {x ∈ X | ¬P(x) ∨ ¬Q(x)},
{x ∈ X | ¬(P(x) ∨ Q(x))} = {x ∈ X | ¬P(x) ∧ ¬Q(x)}.
(A.11)
These identities have counterparts for set operations. For some set X , if and Y ⊂ X and
Z ⊂ X, then
X \ (Y ∩ Z) = (X \Y ) ∪ (X \ Z),
X \ (Y ∪ Z) = (X \Y ) ∩ (X \ Z).
When the set X is understood, we can write these as
(Y ∩ Z)c = Y c ∪ Zc,
(Y ∪ Z)c = Y c ∩ Zc.
These identities are called de Morgan’s rules.
A.1.8
Permutations and combinations
Given a set X with a finite number n of elements, we sometimes wish to construct a subset
with a fixed number m ≤ n of elements. The number of such subsets is given by
n
n!
=
,
(A.12)
m
m!(n − m)!
where the exclamation point denotes the factorial function. The notation n is read “n
m
choose m”. It gives the number of combinations of m elements from the set n.
A combination is a set, so order does not matter. Sometimes, however, order matters.
Suppose for example that X = {a, b, c}. The number of subsets with two elements is
3
3!
6
=
=
= 3.
2
2!1!
2
Lee & Varaiya, Signals and Systems
663
A.1. SETS
These subsets are {a, b}, {a, c}, and {b, c}. Suppose instead that we wish to construct
ordered subsets of X with two elements. In other words, we wish to consider [a, b] to be
distinct from [b, a] (note the temporary use of square brackets to avoid confusion with un-
ordered sets). Such ordered subsets are called permutations. The number of m-element
permutations of a set of size n is given by
n!
.
(A.13)
(n − m)!
The number of permutations is a factor of m! larger than the number of combinations in
A.12. For example, the number of 2-element permutations of X = {a, b, c} is six. They
are (a, b), (a, c), (b, c), (b, a), (c, a), and (c, b).
A.1.9
Product sets
The Cartesian product X ×Y of two sets X and Y consists of all pairs of elements (x, y)
with x ∈ X and y ∈ Y , i.e.
X ×Y = {(x, y) | x ∈ X, y ∈ Y }.
The product of two sets may be visualized as in Figure A.2. These pictures are informal,
to be used only to reinforce intuition. In Figure A.2(a), the set X = [0, 6] is represented
by a horizontal line segment, and the set Y = [1, 8] is represented by the vertical line
segment. The product set X × Y = [0, 6] × [1, 8] is represented by the rectangle whose
lower left corner is the pair (0, 1) and upper right corner is (6, 8).
In Figure A.2(b), the discrete set X = {1, 2, 3, 4, 5, 6} is represented by six points, while
and Y = [1, 8] is represented the same as before. The product set is depicted by six vertical
line segments, one for each element of X . For example, the fifth segment from the left is
the set {(5, y) | 1 ≤ y ≤ 8}. One point in that set is shown.
In Figure A.2(c), the product of two discrete sets is shown as an array of points. Unless
these are ordered sets, there is no significance to the the left-to-right or top-to-bottom or-
der in which the points are shown. In all three cases in the figure, there is no significance
to the choice to depict the first set in the product X ×Y on the horizontal axis, and the sec-
ond set on the vertical axis. We could have done it the other way around. Although there
is no significance to which is depicted on the vertical axis and which on the horizontal,
there is significance to the order of X and Y in X × Y . The set X × Y is not the same as
Y × X unless X = Y .
664
Lee & Varaiya, Signals and Systems
A. SETS AND FUNCTIONS
Basics: Tuples, strings, and sequences
Given N sets, X1, X2, · · · , XN, (which may be identical), an N-tuple is an ordered collec-
tion of one element from each set. It is written in parentheses, as in
(x1, x2, · · · , xN),
where
xi ∈ Xi for each i ∈ {1, 2, · · · , N}.
The elements of an N-tuple are called its components or coordinates. Thus xi is the
i-th component or coordinate of (x1, · · · , xN). The order in which the components are
given is important; it is part of the definition of the N-tuple. We can use a variable to
refer to the entire N-tuple, as in x = (x1, · · · , xN).
Frequently the sets from which the tuple components are drawn are all identical, as in
(x1, x2, · · · , xN) ∈ XN.
This notation means simply that each component in the tuple is a member of the same set
X . Of course, this means that a tuple may contain identical components. For example,
if X = {a, b, c} then (a, a) is a 2-tuple over X.
Recall that a permutation is ordered, like a tuple, but like a set and unlike a tuple,
it does not allow duplicate elements. In other words, (a, a) is not a permutation of
{a,b,c}. So a permutation is not the same as a tuple. Similarly, an ordered set does not
allow duplicate elements, and thus is not the same as a tuple.
We define the set of finite sequences over X to be
{(x1,···xN) | xi ∈ X,1 ≤ i ≤ N,N ∈ N0}.
where if N = 0 we call the sequence the empty sequence. This allows us to talk about
tuples without specifying N. Finite sequences are also called strings, although by con-
vention, strings are written differently, omitting the parentheses and commas, as in
x1x2 · · · xN.
We may even wish to allow N to be infinite. We define the set of infinite sequence over
a set X to be
{(x1,x2,···) | xi ∈ X,i ∈ N0}.
Lee & Varaiya, Signals and Systems
665
A.1. SETS
{1, 2, 3, 4, 5, 6} × [1, 8]
(6,8)
(5,6)
Y = [1,8]
[0, 6] × [1,8]
Y = [1,8]
(0,1)
1
2
3
4
5 6
X = [0,6]
X = {1, 2, 3, 4, 5, 6}
(a)
(b)
{a, b, c, d, e, f} × {g, h, i, j}
g
h
Y = {g, h, i, j}
i
j
a
b
c
d
e
f
X = {a, b, c, d, e, f}
(c)
Figure A.2: Visualization of product sets. (a) The rectangle depicts the product set
[0, 6] × [1, 8]. (b) Together, the six vertical lines depict the product set {1, · · · , 6} ×
[1, 8]. (c) The array of dots depicts the set {a, b, c, d, e, f } × {g, h, i, j}.
666
Lee & Varaiya, Signals and Systems
A. SETS AND FUNCTIONS
We generalize the product notation to three or more sets. Thus if X ,Y, Z are sets, then
X ×Y × Z is the set of all triples or 3-tuples,
X ×Y × Z = {(x, y, z) | x ∈ X, y ∈ Y, z ∈ Z},
and if there are N sets, X1, X2, · · · , XN, their product is the set consisting of N-tuples,
X1 × · · · × XN = {(x1, · · · , xN) | xi ∈ Xi, i = 1, · · · , N}.
(A.14)
We can alternatively write (A.14) as
N
∏ Xi.
(A.15)
i=1
The large Π operator indicates a product of sets.
X × X is also written as X2. The N-fold product of the same set X is also written as XN.
For example,
N
N
R is the set of all N-tuples of real numbers, and C is the set of all N-tuples
of complex numbers. In symbols,
N
R
=
{x = (x1,··· ,xN) | xi ∈ R,i = 1,··· ,N},
N
C
=
{z = (z1,··· ,zN) | zi ∈ C,i = 1,··· ,N}.
Predicates on product sets
A variable over X × Y is denoted by a pair (x, y), with x as the variable over X and y as
the variable over Y . We can use predicates in x and y to define subsets of X ×Y .
Example A.1: The set
{(x,y) ∈ [0,1] × [0,2] | x ≤ y}
(A.16)
can be depicted by the shaded region in Figure A.3. The unshaded triangle depicts
the set
{(x,y) ∈ [0,1] × [0,2] | x ≥ y}.
(A.17)
Lee & Varaiya, Signals and Systems
667
A.1. SETS
Y = [0, 2]
x = y
X = [0, 1]
Figure A.3: The rectangle depicts the set [0, 1] × [0, 2], the shaded region depicts
the set given by (A.16), and the unshaded triangle depicts the set given by (A.17).
Example A.2: The solid line in Figure A.4(a) represents the set
{(x,y) ∈ 2
R | x + y = 1},
the shaded region (including the solid line) depicts
{(x,y) ∈ 2
R | x + y ≥ 1},
and the unshaded region (excluding the solid line) depicts
{(x,y) ∈ 2
R | x + y < 1}.
Similarly the shaded region in Figure A.4(b) depicts the set
{(x,y) ∈ 2
R | − x + y ≥ 1}.
The overlap region in Figure A.4 (c) depicts the intersection of the two shaded
regions, and corresponds to the conjunction of two predicates:
{(x,y) ∈ 2
R | [x + y ≥ 1] ∧ [−x + y ≥ 1]}.
668
Lee & Varaiya, Signals and Systems
A. SETS AND FUNCTIONS
x + y = 1
- x + y = 1
(a)
(b)
- x + y = 1
x + y = 1
(c)
Figure A.4: (a) The solid line depicts the subset of
2
R satisfying the predicate
x + y = 1. The shaded region satisfies x + y ≥ 1. (b) The solid line satisfies −x + y =
1, and the shaded region satisfies −x + y ≥ 1. (c) The overlap region satisfies
[x + y ≥ 1] ∧ [−x + y ≥ 1].
Lee & Varaiya, Signals and Systems
669
A.1. SETS
A.1.10
Evaluating an expression
We have evaluated expressions several times in this appendix, each time relying on our
mathematical ability with simple expressions. We can develop systematic methods for
evaluating expressions that rely less on intuition, and can therefore handle more compli-
cated and intricate expressions.
Some examples of patterns of expressions are:
• A,B,N,··· , names of sets
• A = {list of elements}
• x ∈ A, x /∈ A, set membership
• A = B, B ⊂ A, and A ⊃ B, set inclusion
• A ∩ B, A ∪ B, X ×Y, X \ A, Ac, set operations
• x,y,···, names of variables
• P(x),Q(x),···, predicates in x
• ∀x ∈ Set, P(x) and ∃x ∈ Set, Q(x), assertions obtained by quantification
• NewSet = {x ∈ Set | Pred(x)}, set definition
• P(x) ∧ Q(x), P(x) ∨ Q(x), ¬(P(x)), predicate operations
The patterns define the rules of grammar of the notation. The notation itself consists of
expressions, which are composed of
• constants, such as numbers and pre-defined sets,
• variables, which are names that are not pre-defined,
• operators, such as ∈, ∩, or = (as an assertion),
• quantifiers, such as ∀ and ∃, or
• definitions, namely = (as an assignment).
670
Lee & Varaiya, Signals and Systems
A. SETS AND FUNCTIONS
An expression is well-formed if it conforms to the established patterns.4 For example, if
P, Q and R are predicates, then the syntax implies that
¬[[¬(P(x)) ∨ Q(x)] ∧ [P(x) ∨ [R(x) ∧ ¬(P(x))]]]
(A.18)
is also a predicate. Just as in the case of a computer language, you learn the syntax of
mathematical expressions through practice.5
In an expression, constants have a single meaning. For example, “20” is a number,
“Berkeley” is a city, and the constant “true” has a truth value. By contrast, a variable,
such as x, has no single meaning, unless it has been defined (which turns it into a con-
stant). An expression on constants has a single meaning. For example, “10 + 3” means
“13.” However, “x + 3” has no single meaning, unless x has been defined. We say that in
the expression “x + 3,” x is a free variable. An expression with a free variable acquires a
single meaning when that free variable is given a single meaning, if it is well formed with
that meaning. For example, “x + 3,” has meaning 13 if x has meaning 10, but it is not well
formed if x has meaning Berkeley.
Quantifiers remove free variables from expressions.
Example A.3:
In the expression “x = 0,” x is free. In the expression “∃ x ∈
R,
x = 0,” x is no longer free. In fact, this expression has value true. In the
expression “∀ x ∈ R, x = 0,”, again x is not free, but this expression has value
false. The expression “∃ y ∈ R, x + 1 = y” still has free x. However, “∀ x ∈
R, ∃ y ∈ R, x + 1 = y” has no free variables, and has value true. The expression
“∀ x ∈ R, x + 7,” however, is not well formed. It has neither free variables nor a
value.
A predicate expression is one that either has a meaning that is a truth value (true or false),
or can have such a meaning if its free variables are appropriately defined. Expression
(A.18) is an example a predicate expression.
4In this text, we do not attempt to define precisely what these established patterns are. To do so, we would
have to define a grammar, something that can be done formally, but is beyond our scope.
5The syntax of a language is the set of rules (or patterns) whereby words can be combined to form
grammatical or well-formed sentences. Thus the syntax of the ‘C’ language is the set of rules that a sequence
of characters (the code) must obey to be a C program. A C compiler checks whether the code conforms to the
syntax. Of course, even if the code obeys the syntax, it may not be what you intend; i.e. it may not execute
the intended computation.
Lee & Varaiya, Signals and Systems
671
A.1. SETS
¬
∧
∨
∨
¬
Q(x) P(x)
∧
R(x) ∧ (¬P(x))
R(x)
P(x)
¬
¬P(x)
P(x)
Figure A.5: Parse tree for the expression (A.18).
Expressions also contain punctuation, such as parentheses. These help define the rela-
tionships among the components of the expression. It is beyond the scope of this book
to define completely the rules for constructing expressions6, but we can hint at the issues
with a brief discussion of parsing.
Parsing
To show that (A.18) is indeed a well-formed predicate expression, we must show that it
can be constructed using the syntax. We do this by parsing the expression (A.18) with
the help of matching brackets and parentheses. Parsing the expression will also enable us
to evaluate it in a systematic way.
The result is the parse tree shown in Figure A.5. The leaves of this tree (the bottom-
most nodes) are labeled by the elementary predicates P, Q, R, and the other nodes of the
tree are labeled by one of the predicate operations ∧, ∨, ¬. Each of the intermediate
nodes corresponds to a sub-predicate of (A.18). Two such sub-predicates are shown in
the figure. The last leaf on the right is labeled P(x). Its parent node is labeled ¬, and so
that parent node corresponds to the sub-predicate ¬(P(x)). Its parent node is labeled ∧,
6A text on compilers for computer programming languages will typically do this.
672
Lee & Varaiya, Signals and Systems
A. SETS AND FUNCTIONS
and it has another child node labeled R(x), so this node corresponds to the sub-predicate
R(x) ∧ ¬(P(x)).
If we go up the tree in this way, we can see that the top of the tree (the root node) indeed
corresponds to the predicate (A.18). Since at each intermediate node, the sub-predicate is
constructed using the syntax, the root node is a well-formed predicate.
Evaluating
Suppose we know whether the predicates P(x), Q(x), R(x) evaluate to true or false for
some value of x. Then we can use the parse tree to figure out whether the predicate (A.18)
evaluates to true or false. To do this, we begin with the known truth values at the leaves
of the parse tree, use the meaning of the predicate operations to figure out the truth values
of the sub-predicates corresponding to the parents of the leaf nodes, and then the parents
of those nodes, and work our way up the tree to figure out the truth value of the predicate
(A.18) at the root node. In Figure A.6 the parse tree is annotated with the truth values of each of the nodes. Since the root node is annotated ‘false,’ we conclude that (A.18)
evaluates to false.
Truth tables
The way in which the predicate operations transform the truth values is given in the fol-
lowing truth table:
P(x)
Q(x)
¬P(x) P(x) ∧ Q(x) P(x) ∨ Q(x)
true
true
false
true
true
true
false
false
false
true
false
true
true
false
true
false
false
true
false
false
Consider a particular row of this table, say the first row. The first two entries specify that
P(x) is true and Q(x) is true. The remaining three entries give the corresponding truth
values for ¬P(x), P(x) ∧ Q(x) and P(x) ∨ Q(x), namely, ¬P(x) is false, P(x) ∧ Q(x) is
true, and P(x) ∨ Q(x) is true. The four rows correspond to the four possible truth value
assignments of P(x) and Q(x). This truth table can be used repeatedly to evaluate any
well-formed expression given the truth value of P(x) and Q(x).
Lee & Varaiya, Signals and Systems
673
A.1. SETS
¬ ← False
∧ ← True
∨ ← True
∨ ← True
¬ ← True True True
∧ ← False
True
True
¬ ← False
True
Figure A.6: Parse tree for the expression (A.18) annotated with the truth values
of each of the nodes.
674
Lee & Varaiya, Signals and Systems
A. SETS AND FUNCTIONS
Thus, given the truth values of predicates P1(x), . . . , Pn(x), the truth