3.1

 

>> power set : (2^C....)

>> Partition of [n] = {1, 2, .......n}

>> any acyclic directed graph

>> Divisors of n, or the integers by divisiblity (Z, | )

30 is least upper bound(supremum)(bound which preceeds all other uppper bounds) of 2&15 

1 is greatest lower bound(infimum)(bound which exceeds all other lower bounds) of 2&15

>> vertices in a rooted tree (eg : computer directory and family tree)

students and lib are uncompairable. (similarly many things are incompairable here)

>> strongly connected components in a directed graphs

agr khi loop bn rha hai to usko ek element maan lenge.

>>

>> HASSE DIAGRAM

chain or total order is a poset in which any 2 elements are compairable.

                                                     Lattices

>> Meet(greatest lower bound)(x.y)(And sign)

>> Join(least upper bound)(x+y)(or sign)

>> A poset (L, ≤) is a lattice iff every pair of elements in A have both a meet and a join.'

>>1) Commutative Law: -

(a) a ∧ b = b ∧ a     (b) a ∨ b = b ∨ a

2) Associative Law:-

(a) (a ∧ b)∧ c = a ∧(b∧ c)     (b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3) Absorption Law: -

(a) a ∧ ( a ∨ b) = a     (b) a ∨ ( a ∧ b) = a

>>Duality: change or to and , and to or.

>>A lattice L is called a bounded lattice if it has greatest element 1 and a least element 0.

>>

Properties of Bounded Lattices:

If L is a bounded lattice, then for any element a ∈ L, we have the following identities:

1. a ∨ 1 = 1
2. a ∧1= a
3. a ∨0=a
4. a ∧0=0

>>sublattice: L1 is sublattice of L is L is also a lattice and given that L1 is non empty.

>> lattice is distributive if for any of it's a, b, c elements it satisfies

1. a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
2. a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
3. otherwise it is non-distributive lattice..

>> if Lattice is bounded then a, b in lattice is bounded if

a ∨ x = I and a ∧ x = 0

and if all the pairs in lattice have a complment then it is called complemented lattice.

>>Two lattices L1 and L2 are called isomorphic lattices if there is a bijection from L1 to L2 i.e., f: L1⟶ L2, such that f (a ∧

b) =f(a)∧ f(b) and f (a ∨ b) = f (a) ∨ f (b)

>>Direct Product of lattices

Example: Consider a lattice (L, ≤) as shown in fig. where L = {1, 2}. Determine the lattices (L2, ≤), where L2=L x L.

Solution: The lattice (L2, ≤) is shown in fig:

>>

Game theory

>>Two-Person Zero-Sum Games:: means game is between 2 players and sum of gain of one player to loss of other player is zero.

Some Basic Terms:

1. Player: individual, group of individuals or an organization

2. stategy: options available to player from which he can decide.

Pure stategy: if player chooses same stategy every time with the objective to increase gains or decrease loses. other players know what he is going to choose

mixed stategy: if player chooses combination of stategy and other players keep guessing every time the stategy he has used is called mixed stategy it is used to increase gains or reduce loses.

3.Optimum Strategy: A course of action or play which puts the player in the most preferred position, irrespective

of the strategy of his competitors, is called an optimum strategy.

4. Value of the Game: The value of the game is the “expected gain to a player” if he and his opponent use their

best strategies.

5:Pay of a matrx: nxm ka matrix hoga jisme phla column and phla row 2 players ki stategies hongi and baaki jgah gain and loss of 1'st player hai.

ye game zero sum hai mtlb jitna phla player gain yaa loss krega utna doosra player loss ya gain krega.

>> MaxMin(pessimistic

decision criterion) :- player A ka gain and loss likha hai upper table m to player A har row me se minimum gain select krenga player A and phir saare minimum gain me se maximun select krega jisse uska min gain  maximize ho jaae .(upper table m MaxMin = 2) and this value is called maxmin value of game

>>MinMax :- Player B apne loss ko minimize krna chahega to vo upper table k har column se max gain of A(loss of B select krega) and then usme se min gain of A select krega isse uska loss minimize ho jaaega.

(MinMax = 4) and this value is called MinMax value of game.

>> MAXMIN = MINMAX then game have saddle(equilibrium point), corrosponding pure stategy is called optimum stategy and payoff is known as value of game.

Usually Maximin ≤ value of the game ≤ Minimax.

If Maximin = Minimax = 0, the game is fair.