Discrete mathematics set theory notes

SET THEORY

SETS AND SUBSETS

A set should be a well specified collection of objects. “it must be possible for  us to decide whether the object belongs to the collection ( under consideration) or not.

We  use capital letter to represent sets and lowercase letters to represent elements. For set A we write  if x is an elements of A :  indicates that y is not a member of A.

A set can be designated by listing its elements within set braces ( tabulation methods).

Example : if A is the set consisting of the first few positive integers, then we write  Here but 6 not belongs A

Another standard notation is to specify the set by starting a characteristics property which all the elements of the set possess and which no other object possess [ Rule Method]

Example : we can also represent the above set as . Here the vertical line | within the set braces is read “such that”. The symbol } are read “ the set of all x such that. The properties following | help us determine the defined all the set that is being described.

Consider it self is the set of all elements in a discussion. It is represented by  U. all sets that we consider are subsets of U. U s also called universe of discussion or the universe for that discussion.

Finite set is a set that has a finite number of elements.

Example :

 

Cardinality : for any finite ser  denotes the number of elements in A and is referred to as the cardinality or size of A for that above example.

Example :  }

}

Subset: if are sets from a universe we say that C is a subset of ‘D’ and write  or , every elements of  as elements of .

If in addition, contains an elements that is not in C, then c is called proper subset of D. and these denoted by .

Equal sets:

For the universe  consider the set  then member of. B are 1, 2,. Here A and  B containe the same elements. And no other elements. Hence the sets A and B are equal.

However it is also true, here that and

Power Set: If  A is a set from a universe  , the power set of A. denoates of  is the collection ( or set ) of all subsets of A

Example : let

Null set := the null set or empty set is the (unique) set containing no elements it is denoted by  or .

Example :

Set operations and the laws of set theory

For  we defined the following

( the Union of A and B ) =

( the Intersection of A and B ) =

Example : With

Let , The sets S and T are called disjoint or mutually disjoint, when

Example : for the above ser    and

For  the relation (Complement) of A in B denoted  is given by.

Theorem: set , then set S and T are disjoint if and only if

Proof := we start with S, T disjoint, consider an x in

If  (or perhaps both). But with S and T disjoint,

We have

For the opposite inclusion, if  , then

So

For

Now we have     and

 

If follows from definition mentioned before that

The Laws of Set Theory

For any sets A, B and C tokens from a universe

·

 

Law of Double Complement
·

·

 

Demorgans Laws
·

·

 

 

Commutative Laws
·

·

 

Associative Laws
·

·

 

Distributed Laws
·

·

 

Idempotent Laws
·

·

 

Identity Laws
·

·

 

Inverse Laws
·

·

 

Domination Laws
·

·

Absorption Laws

 

 

Counting and Venn Dagram: Relationship sets can be depicted on diagrams called Venn Diagrams

Proof of Demorgan’s Law

Proof : let  then

SO

To established the opposite completion we find that

Consequently with and

That is

Proof of Distributive Law

 

 

 

 

Simplify the expression

(Demorgans Law)

(Laws of Double Absorption)

(Associative law of intersection Law)

(Commutative Law)

(Associative law of intersection Law)

(Absorption Law)

Problem : if a finite set A has n elements prove that the power ser has  elements.

Proof : if  set A  has n elements, then A subset of A can have no element, one element, two element, ———-n-1 elements.

The subset having no element of A gives a singleton subset A and they are n in number. Each combination of two elements of A. gives subset of A containing 2 elements, their number in  .

Similarly the number of subsets of A having three elements is and so on.

There fore the total number of subsets of Ais

 

 

 

Binominal Theorem

   

Prove the following

Duality : let s be a general statement dealing with the equality of two set expression each such expression may involve one or more occurrence of and . And only the set operators symbols . The dual of s, denoted by . Is obtained from s, of by replacing (1) each occurrence of  and by    and respectively and (2) each occurrence of (in s) by  respectively.

Write the dual of the following statement

 

  • Prove that :

Proof :

  • Prove that :

 

  • Prove that :

 

  • Prove that :
  • Prove that :

Proof :

 

 

Simplify

=

=

 

 

=

 

 

Membership Table  :

 0000
0101
1001
1111
01
10

 

We observe that for sets . An element . Satisfies exactly one of the following four solutions

When x is an element of a again set we write a 1 in the column. Representing that set in the membership table when x is not in the set we enter a 0.

 
00000000
00100010
01000100
01111111
10001111
10101111
11001111
11111111

these two are identical columns

Prove that :

0011101
0110101
1001101
1100010

 

these two are identical columns

For sample of 100 such gates we let A,B,C be the subsets (of these 100 gates)  having defects  respectively with

And  How many gates in the sample have at least one of the defects

Note:

 

 

  1. If A, B, C are finite sets then

Proof :  is the set of elements that belong A but not to B or C

 

 

  1. Q) A Professor has two dozens textbooks on Computer Science and s concerned about their coverage of topics

1) Compiler

2) Data Structure

3) operating system the following are the number of text books that contains materials on these topics

  1. How many of the textbooks include materials on exactly one of these topics
  2. How many do not deal with any of the topics
  3. How many have no material on compiles
  4. Let be the text books having only complies

Let  be the text books having only complies

Let  be the text books having only complies

  1. Q) A computer company requires 30 programmers to handle systems programming jobs and AD programmers for applications programming. If the company appoints 55 programmers to carry out these jobs

(a) how many of these perform jobs of both types

(b) How many handle only system programming jobs

(c) How many handle only application programming

Let A denotes set of Programmers who handle system programming jobs

B denotes set of Programmers who handle Application  programming jobs

denotes set of Programmers to carry out these jobs

  1. |
  2. Q) A survey of 500 television viewers of a sports channel produced the following information 285 watch cricket 195 hockey 115 watch football, 45 watch cricket and football, 70 watch cricket and hockey, 50 watch hockey and football and 50 do not watch any of the three kinds of games.
  3. a) how many viewers in the survey watch all three kinds of games.
  4. b) how many viewers watch exactly one of the sports.

let  denotes the set of viewers who watches only cricket

let  denotes the set of viewers who watches only cricket hockey and let  denotes the set of viewers who watches only cricket football

|=325

  1. Q) A survey of a sample of 25 new cars being sold by an auto dealer was conducted to see which of the three popular options. Air conditioning radio and power windows, were ready installed the survey found 15 had ac, 12 had radio 11 had power 5 had ac and power a had ac and radio, 4 had radio and power and 3 had all 3 options

Find the number of cars that had.

  • only power
  • only ac
  • only radio
  • only one of the options
  • at least one options
  • number of the options

The total number of cars having one option

Number of cars which hat at least one option is

  1. Q) Thirty cars are assembled in a factory. The operations. Available are music system, an are coordinator and power contains. It is known that 15 of the cars have music systems, 8 have ac and 6 have power windows further 3 have all options to determine at least how many cars do not have an operation at all.

Answer: 7

  1. Q) in a survey of 60 people it was found that 25 read weekly magazines, 26 read fortnightly magazines 26 read monthly magazines: 9 read both weekly and monthly magazines, || read both weekly and fortnightly 8 both fort and monthly and 3 read all three magazines.

Find a) number of people who read at least one of the 3 magazines and

  1. b) number of people where read exactly magazines

A First Word on Probabilit

When one perform an experiment such as tossing a single for coin rolling a single fair die or selecting two students as random from a class o 0 to work on a project, a set of all possible outcomes for each situations is called a samle space.

Sample space of Experiment (1)

Sample space of Experiment (2)

Sample space of Experiment (3)

In dealing with the sample sequence  for all the roll of single fair die. We fail that each of the size possible outcomes has the same or equal level hood of occurrences.

Definition for portability that was given b the French mathematician Pirre-Simon da Laplace in his analytical.

Theory of Probability: Under the assumptions of equal likhe hood. Let S be a sample space for an experiment E. Each subset A of S, including the empty subset is called an element, each element of S determines an outcome so of  and

  1. Q) A fair die is rolled. What is the probability of getting

(B) an even numbers

Solution : a) we have element

  1. b) we have element

Find the portability of occurrence of exactly two heads in three tosses of a coin possible outcomes

Outcomes with exactly 2 heads

{HHT,HTH,THH}

An integer is selected as random from 3 through 17 inclusive. If A is the element that a no divisible by 3 is chosen and B is the element that the chosen number exceeds 10 determine

Number of divisible by 3 =

No exceeding 10

The probability that an Will have defective etching is 0.12, the probability that it will have a crack defect in 0.29 and the probability that it will have both defect is 0.07 what is the probability that a ninety manufactures chip will have (i) an etches or crack defect (ii) neither defects.

Let A-Etchiy definition

Let B-crack Definition

Problem with no definition

A computer services company has 300 programmers it is known that 180 of these can program in JAVA, 120 in C++ and 30 in .NET, 12 in JAVA and .NET18 in C++and .NET, 12 in JAVA and C++ and 6 in all 3 languages .

  1. If a programmer in selected at random what in the probability that she can program in exactly 2 languages.
  2. If two programmers are selected at random what is the probability that they can (1) both program JAVA (ii) both can program only in JAVA.
  3. JAVA and C++ -6
  4. JAVA and .NET 6

exactly 2 languages

  1. Number of ways of selecting 2 programmers from 200 in number of selecting 2 from those who program in JAVA  number of ways of selecting 2 programmers who can program only in JAVA in

 

Probability of selecting one of them in

  1. Q) there are 20 students enrolled in a class if the teacher wants to select two of her students at random, to work on a project.

Suppose that X and  are two of the 20 students in the class and. Let A be the event that X is selected, B be the event that Y is selected.

Find the probability that

  1. both x and y are selected.
  2. Neither X nor Y is selected.
  3. X but not Y is selected.

The selection of 2 students from 20 students can be made in ways

s

 

  1. Q) Jerry tosses a fair win six times what is the probability that gets
  2. All Heads
  3. One Head
  4. Two heads
  5. At least four Heads

Sample Space –

Countable  And Uncountable Sets: Consider two non-empty sets we say that A and B that have the same size or the same cardinality of then exists a one to one correspondence between their elements, that is given in element a of A, we can find a corresponding element b of B and inverse.

If the sets have the same cardinality we say that are equivalent and we write

Since have the same number of elements there does exist a one-to-one correspondence between the elements corresponding to each other.

Consider the set of all the positive integers. And the set of all the positive elements then given an in we can find a corresponding  in and given b into 0 correspondings between the element of   Z(Set of all int)

That’s why

Countable Set

A set A is said to be countable (or Denumerable) if

  • An in a finite set or

Equation:  is countable because the set a is finite.

Also is countable because

Show that :

Countable set the elements of given set S form the sequence

Show that

The elements of the given set A form the sequence { } where  = 1

  • ( n – 1) for n>= 2

The given set A in a subset of z which is countable

Show that set of all integers in countable

The set of all integers are

The elements of Z are 0, 1, -1, 2, -2, 3, -3,……

In listing  0 is the first element 1,….

Then the elements of Z can be arranged as a sequence {

Where

if n is odd and    if n is even

i.e., is a countable set