جامعة بابل- كلية العلوم للبنات- قسم الحاسبات العام الدراسي 2017-2018 الاحتسابية lecture1:Set

Sets

A set is a collection of "things" called the elements or members of the set. •Common forms of describing sets are:

  • List all the elements, e.g. {a, b, c, d}
  • Form new sets by combining sets through operators (see next page).

Terminology and Notation: •

To indicate that x is a member of set S, we write x∈S. •We denote the empty set (the set with no members) as {}or ∅.

•If every element of set A is also an element of set B, we say that A is a subset of B, and write A⊆B

•If every element of set A is also an element of set B, but B also has some elements not contained in A, we say that A is a proper subset of B, and write A⊂B

•We may also use the inverse notation: B⊇A and B⊃A for B is a (proper) superset of A.

Note: It is essential to have a criterion for determining, for any appropriate “thing”, whether it is or is not a member of the given set. This is called the membership criterion. Languages – which we will introduce later - are sets. These sets contain specific strings over an alphabet, according to certain specifications or conditions, which describe the language. Grammars and automata can be used to describe languages (and therefore also sets). Membership criteria and appropriate decision algorithms are a central topic in the study of formal languages.

Operations on Sets

?The union of sets A and B, written

AB

is a set that contains everything that is in A, or in B, or in both.

?The intersection of sets A and B, written

A∩B

is a set that contains exactly those elements that are in both A and B.

?The set difference of set A and set B, written

A – B

is a set that contains everything that is in A but not in B.

?The complement of a set A, written as -A or

(A bar)

is the set containing everything that is not in A. We assume for this definition some universal set U that contains "everything" (meaning "everything we are interested in at the moment"). Then =U - A.

ex: U={1,2,3,4,5,6} and A={3,5,6} then ={1,2,4}

?The lengthof a set A, written |A|, is the number of elements in a set A.

Example: A={a,b,c,d} then length of A is 4

DONE

Instructor: MohamedU. Mahi

1