The Gateway to Computer Science Excellence
+41 votes

Suppose $L = \left\{ p, q, r, s, t\right\}$ is a lattice represented by the following Hasse diagram:

For any $x, y \in L$, not necessarily distinct , $x \vee y$ and $x \wedge y$ are join and meet of $x, y$, respectively. Let $L^3 = \left\{\left(x, y, z\right): x, y, z \in L\right\}$ be the set of all ordered triplets of the elements of $L$. Let $p_{r}$ be the probability that an element $\left(x, y,z\right) \in L^3$ chosen equiprobably satisfies $x \vee (y \wedge z) = (x \vee  y) \wedge (x \vee  z)$. Then

  1. $p_r = 0$
  2. $p_r = 1$
  3. $0 < p_r ≤ \frac{1}{5}$
  4. $\frac{1}{5} < p_r < 1$
in Set Theory & Algebra by Boss (30.7k points)
edited by | 5.7k views
What does ordered triplet mean in this question?
'Not necessarily distinct' &  'Ordering is important'
Where it is mentioned that we can take repeated values in the triplet?

5 Answers

+59 votes
Best answer

Number of elements in $L^3 =$ Number of ways in which we can choose $3$ elements from $5$ with repetition $= 5 * 5 * 5 = 125.$

Now, when we take $x = t,$ then the given condition for $L$ is satisfied for any $y$ and $z.$ Here, $y$ and $z$ can be taken in $5 * 5 = 25$ ways. 

Take $x = r, y = p, z = p.$ Here also, the given condition is satisfied.
When $x = t,$ we have $5*5 = 25$ cases $($for any $y$ and $z$$)$ where the given conditions are satisfied. Now, with $x = r, y = p, z = p,$ we have one more case. So, $26/125$ which means strictly greater than $1/5.$
So, this makes $p_r > \frac{25}{125}$ 

for $x = q, y = r, z = s,$ the given condition is not satisfied as $q \vee (r \wedge s) = q \vee p = q,$ while $(q \vee r) \wedge  (q \vee s) = t \wedge t = t.$ So, $p_r \neq 1.$

These findings make option A, B, C as FALSE.

Hence, answer = option D

by Veteran (430k points)
edited by
why Pr >1/5 , why not Pr=1/5
When x = t, we have 5*5 = 25 cases (for any y and z) where the given conditions are satisfied. Now, with x = r, y = p, z = p, we have one more case. So, 26/125 which means strictly greater than 1/5

sir Pr !=1 fine because lattice is not distributive.
but "For x=p, y=r, z=t  the given condition is not satisfied"  how ??
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
p ∨ (r ∧ t) = (p∨ r) ∧ (p ∨ t)
p ∨ r = r ∧ t
r = r
is it not  true ??

Yes, you are right. I have corrected :)
Do we need to manually try for all combinations with x=t whether the condition is satisfied or not? (as stated above that condition is satisfied for all combinations with x=t)
sir only when triplet form from q,r,s then only not distributive. we can arrange then in 6! ways . so can we say exact probability will be 125-6= 119

sir, can we choose all elements same also in the triplet? for example(t,t,t)
@Arjun Sir.

As lattice always satisfies associative property  so choosing pqr is same as choosing prq.I mean it should be combination with unlimited repetition instead of permutation.Because for distributive i just need 3 elements.And order of those elements should not matter as lattice satisfies associative. any arrangement of qrs will not satisfy.And it should be combination instead of permutaion ?
Now, with x = r, y = p, z = p, we have one more case. So, 26/125 which means strictly greater than 1/5
So, this makes pr>25125pr>25125




Not get it????????
@Arjun sir, the probability is >1/5 ia all you have shown but the exact probability is 119/125 as shown in the answer below by Wali, right?
+62 votes

Each element of {q,r,s} has two complement.So,these element can't be chosen in the triplets<x,y,z>.One element should be such that it has unique complement to meet the given distributive property.

So,ways can't be chosen = 3! = 6


So,<x,y,z> be chosen 5$\times$5$\times$5=125 ways.

So,Ans = $\frac{125-6}{125}$ = $\frac{1}{5}\lt\frac{119}{125}\lt1$       (D)

by (489 points)
edited by
Distributive Lattice property here. When CL is distributive, complement is always unique. (y)
If we take a triplet <t,r,p>

where r has 2 complement. So, according to this logic it shouldnot satisfy distributive property

But how it is satisfying?
What he is saying is if at least one of those 3 is having unique complement then it will satisfy the distributive property.

Here in your eg., t and p both have a single complement so a/c to his definition it should be correct.
Please share a reference for your answer's theory
@adactive18 @sreshta

Fine,r has two complement,but if atleast one of <x,y,z> has unique complement it will satisfy the given property.You can check by yourself or please provide a counter example for my solution.Thanks.
what about triples containing <q,r,t> here q, r, t don't have unique complements. you haven't  considered this kind of triplets

 <q,r,t> satisfies distributive property right?


@aditi19 t has unique complement so it will satisfy distributive property.

@rajashish I'm not sure but, if we take all the elements as same. for e.g <q, q, q>, here no element has a unique complement, but still, the left and right-hand side of equations come out to be q?

We can take all elements as same because we're considering the total no of cases as 5*5*5.
+15 votes

For p=1 we have to satisfy the condition of distributive lattice i.e. x V (y ⋀ z) = (x V y ) ⋀ (x V z) 

but it is not distributive as q has here more than one complement.

If we take (q,r,s) and apply distributive formula, we can see it is not satisfying i.e.  x V (y ⋀ z) ≠ (x V y ) ⋀ (x V z) 

So, from here we can say obviously pr < 1

Here(x,y,z) can take p,q,r,s,t i.e. 5 values in 5*5*5=125 ways

Now, for proving  pr >1/5 we have to check some triplets which satisfying distributive conditions, 

take for t 






these 25 points satisfied distributive property, right?i.e. pr =25/125=1/5

Now take 1 more point to say pr>1/5

take any  satisfactory point .e.g  take (r,r,p) 

So, we can easily say 1/5 < p< 1

Ans (D)

by Veteran (118k points)

generallly if we take 3 values x,y,z

and atleast one in that has only one complement then 3 values will satisfy distributive property ?
where distributive property violating?

u can also chk selected ans


What he is saying is if at least one of those 3 is having unique complement then it will satisfy the distributive property. 

is this statement true ?

@Srestha, not directly related to the question but is the complement of 'r' = { q, s } ?
Another easy view of this question is

it is not distributive lattice as there are more than one complement for point q,r,s

But individually some point must be distributive

So, option A) and B) ruled out easily

Now question lies, which points are not distributive?

For any combination of q,r,s will not be distributive

So, there will be 3!=6 combination will be not distributive

Among 125 combinations 6 are not distributive and 119 distributive

So, ans will be easily D)
So can we conclude that always the elements which have more than one complement in a lattice which when taken as ordered triplet ,do not follow distributive property?
+8 votes
here , short cut to this question

by watching figure u can guess that it's not distributive lattice, becoz for q there is 2 complement so , it cant satisfy distributive property , therefore, probability cant be 1 , so option (a) is wrong

now if u apply distributive property for any 3 elements which are in straight line they will satisfy the distributive property , it concludes that its probability cant be 0, therefore option (b) is wrong

now no of possible distributive equation will be 5*5*5=125 because repetition is allowed here. since in above line, i hav proved that elements in straight line will follow the distributive prop then no of possible distributive with 3 element is 3*3*3=27 (since repeatition is allowed , u might ask question that there are 5 elements then why 3 ? since we have to fix 2 as universal lower bound and upper bound ) so 27/125 is greater than 1/5


so d option is correct
by Active (5.1k points)
+4 votes
answer is d
by Active (1.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
104,735 users