Maths for Regular Expressions/sets/subsets Flashcards Preview

Paper 1 - Computer Science > Maths for Regular Expressions/sets/subsets > Flashcards

Flashcards in Maths for Regular Expressions/sets/subsets Deck (46)
Loading flashcards...
1

What is a set and an important rule of sets?

What are the three types of sets?

A set is an unordered collection of values or symbols.
Any value or symbol occurs at most once.
Sets can be common, finite and infinite

2

What is the notation used for a set?

A = {1,2,3,4,5}
B = {-1,0,3,16,18}
C = {red, orange, yellow}
A set is usually denoted by a capital letter
A member is usually denoted by a lowercase letter

3

What are some commonly used sets?

Natural numbers, the set of integers, real numbers and rational numbers and empty sets

4

How is an empty set represented

- A = { Ø } or {} means an empty set

5

What is the cardinality of a set?
What is the cardinality of sets A and B?
A = {1,2,3}
B = {}

The cardinality of a set is the number of elements in the set. The cardinality of set A is 3 and the cardinality of set B is 0 (empty sets have a cardinality of 0)

6

What does the symbol | mean?

- the symbol | means "such that"

7

What does the x represent?

- x represents the values of the set listed after the | symbol

8

What does N mean?

- N means natural numbers

9

what does the∊symbol mean?

-The∊symbol indicates membership so x ∊ N is read as “x belongs to N”

10

What does x >= 1 mean?

- x >=1 means where x is greater or equal to one

11

What does the ^ symbol mean

The ^ symbol stands for "and"

12

Why do we use sets?

- Means we can group objects together and view them as a single entity
- A set becomes an abstraction
- Set theory and logic have a close relationship
- Many programming languages support sets as an abstract data type

13

What is an infinite set?

An infinite set may be countable or uncountable.
- It has an infinite number of elements

(this includes natural, integer and real number sets)

14

What is a finite set?

- A finite set is one whose elements can be counted off by natural numbers up to a certain number.
- It has a finite number of elements

15

What is a countably infinite set?

Give examples of countably infinite sets

- Contains an infinite number of elements which can be mapped one to one to the set of of natural numbers.

- Natural and integer numbers are infinite countable sets

16

What is an uncountably infinite set?

Contains an infinite number of elements which cannot be mapped one to one to the set of of natural numbers. Real numbers are an uncountable finite set

17

What is compact representation/format?

It uses set comprehension to compact the set into a formula. for example : B = { n2 | n ∊ N ^ n < 5 }

18

What is the cartesian product of two sets X and Y?

Can be written as X x Y or (X cross Y) is the set of all crossed pairs (x, y) where x is a member of X and y is a member of Y.
X = {1, 3, 5}
Y = {12, 25, 40}
Z = X x Y
Z = {(1, 12), (1, 25), (1, 40), (3, 12), (3, 25), (3, 40), (5, 12), (5, 25), (5, 40)}

19

What does the set of {0^n1^n | n>=1} look like?

It will be a list of strings where each string has an equal number of 0's and 1's: {01, 0011, 000111, 00001111,...}

20

What is a subset?

A set where all the elements of one set are elements of another set

21

What is a proper subset?

A set that does not include all the elements of the set to which it belongs.

22

What is the notation for a subset?

if X is a subset of Y
X = {1,2,4,6} , Y = {4,6,1,2}
This can be written as X ⊆ Y

23

What is the notation for a proper subset?

This can be written as X ⊂ Y
if X is a subset of Y
X = {1,2,4,6} , Y = {4,6,1,2,9,13}

24

What does A ⊆ B mean?

That subset A has fewer elements than or is equal to set B

25

What does A ⊂ B mean?

Subset A has fewer elements than set B

26

What is a set operation?

It defines the relationship between two or more different sets

27

What is membership?

A set operation used to check whether an element is a member of a particular set

28

What is the Union of two sets? And what is the symbol used to denote a Union?

- The union of two sets is the set that contains all the elements of these sets
- X U Y

29

What is the Intersection of two sets? And what is the symbol used to denote a intersection?

- The intersection of two sets is the set that contains only the elements which are in both sets
- X ∩ Y

30

What is the Difference of two sets? And what is the symbol used to denote a Union?

- The difference of two sets is the set that contains all the elements which are in one set but not both.
- X - Y