DM - Functions & Relations -Q14

+1 vote

Let L be the set of all propositions generated by P and Q (Where P and Q are Two Propositions) using at most one of the following logical operations : \wedge, \vee, \oplus , \rightarrow, \leftrightarrow, \uparrow, \downarrow, Where \uparrow, \downarrow are NAND and NOR operators respectively.

i.e. L = \{P,Q, P\wedge Q,P \vee Q,P \oplus Q ,P \rightarrow Q,P \leftrightarrow Q,P \uparrow Q,P \downarrow Q\}

A Relation R is defined on L such that (a,b) \in R \,\,\,if\,\,and\,\,only\,\,if\,\, " a \rightarrow b"  is Tautology. 

The relation R is 

A. An equivalence relation

B. Not an equivalence relation because R is Not transitive.

C. A partial order relation

D. Not a partial order relation because R is Not anti-symmetric.

asked Jun 24 in Discrete Maths by gbeditor (44,500 points)
reshown 6 days ago by gbeditor

1 Answer

0 votes
Best answer

R is reflexive because X \rightarrow X  is always a Tautology. X \rightarrow X = X + X' =1

R is antisymmetric. xRy and yRx  implies x \equiv y . Since, no two elements in the set L are equivalent so R is antisymmetric.

R is transitive because Implication operation is Transitive. (x \rightarrow y ) \wedge (y \rightarrow z ) \rightarrow (x \rightarrow z )

Hence, R is partial order But Not Equivalence relation.

answered 4 days ago by deepak-gatebook (112,390 points)