ರಿಲೇಶನ್‌ಗಳ ನಿರೂಪಣೆ (Representation) ಮತ್ತು ಗುಣಗಳು (Properties) | Representation and Properties of Relations
In the syllabus of UGC NET CS
Saved in this browser only. Sign in to keep your ticks on every device. See all revisions due
Key points
- ರಿಫ್ಲೆಕ್ಸಿವ್: ಡಯಾಗೊನಲ್ ಪೂರ್ತಿ 1; ಸಿಮೆಟ್ರಿಕ್: ಮ್ಯಾಟ್ರಿಕ್ಸ್ = ಟ್ರಾನ್ಸ್‌ಪೋಸ್. | Reflexive: diagonal all 1; symmetric: matrix equals its transpose.
- ಸಿಮೆಟ್ರಿಕ್ ಮತ್ತು ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ ವಿರುದ್ಧಾರ್ಥಕಗಳಲ್ಲ; ಡಯಾಗೊನಲ್ ರಿಲೇಶನ್ ಎರಡೂ. | Symmetric and antisymmetric are not opposites; a diagonal relation is both.
- ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ ಸಂಖ್ಯೆ 2 ರ ಘಾತ n × 3 ರ ಘಾತ [n(n − 1)/2]. | Antisymmetric count: 2 to the power n times 3 to the power [n(n − 1)/2].
- ಅಸಿಮೆಟ್ರಿಕ್ ಎಂದರೆ ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ ಮತ್ತು ಇರ್ರಿಫ್ಲೆಕ್ಸಿವ್. | Asymmetric means antisymmetric and irreflexive.
- S ∘ R ನಲ್ಲಿ ಮೊದಲು R ಅನ್ವಯವಾಗುತ್ತದೆ. | In S ∘ R, R is applied first.
On this page
ಮೂರು ನಿರೂಪಣೆಗಳು | Three representations
- ಜೋಡಿಗಳ ಪಟ್ಟಿ: R = {(1, 2), (2, 3)} | List of pairs: R = {(1, 2), (2, 3)}
- ಜೀರೋ-ಒನ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ (Zero-One Matrix): (a, b) ∈ R ಆದರೆ ಸಾಲು a, ಕಾಲಂ b ನಲ್ಲಿ 1. | Zero-one matrix: a 1 in row a, column b when (a, b) ∈ R.
- ಡೈಗ್ರಾಫ್ (Digraph): ಪ್ರತಿ ಜೋಡಿ (a, b) ಗೆ a ಇಂದ b ಗೆ ಬಾಣ; (a, a) ಒಂದು ಲೂಪ್ (Loop). | Digraph: an arrow from a to b for each pair (a, b); (a, a) is a loop.
ಆರು ಗುಣಗಳು ಮತ್ತು ಅವುಗಳನ್ನು ಗುರುತಿಸುವುದು | The six properties and how to spot them
| ಗುಣ | Property | ವ್ಯಾಖ್ಯೆ | Definition | ಮ್ಯಾಟ್ರಿಕ್ಸ್‌ನಲ್ಲಿ | In the matrix |
|---|---|---|
| ರಿಫ್ಲೆಕ್ಸಿವ್ (Reflexive) | Reflexive | ಪ್ರತಿ a ಗೆ (a, a) ∈ R | (a, a) ∈ R for every a | ಡಯಾಗೊನಲ್ ಪೂರ್ತಿ 1 | diagonal all 1 |
| ಇರ್ರಿಫ್ಲೆಕ್ಸಿವ್ (Irreflexive) | Irreflexive | ಯಾವ a ಗೂ (a, a) ಇಲ್ಲ | no (a, a) at all | ಡಯಾಗೊನಲ್ ಪೂರ್ತಿ 0 | diagonal all 0 |
| ಸಿಮೆಟ್ರಿಕ್ (Symmetric) | Symmetric | (a, b) ಇದ್ದರೆ (b, a) ಕೂಡ | (a, b) implies (b, a) | ಮ್ಯಾಟ್ರಿಕ್ಸ್ = ಅದರ ಟ್ರಾನ್ಸ್‌ಪೋಸ್ (Transpose) | matrix equals its transpose |
| ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ (Antisymmetric) | Antisymmetric | (a, b) ಮತ್ತು (b, a) ಇದ್ದರೆ a = b | (a, b) and (b, a) imply a = b | ಡಯಾಗೊನಲ್ ಹೊರಗೆ ಎರಡೂ ಕಡೆ 1 ಇಲ್ಲ | no 1 on both sides off the diagonal |
| ಅಸಿಮೆಟ್ರಿಕ್ (Asymmetric) | Asymmetric | (a, b) ಇದ್ದರೆ (b, a) ಇಲ್ಲ | (a, b) implies (b, a) is absent | ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ ಮತ್ತು ಡಯಾಗೊನಲ್ ಪೂರ್ತಿ 0 | antisymmetric with an all-0 diagonal |
| ಟ್ರಾನ್ಸಿಟಿವ್ (Transitive) | Transitive | (a, b) ಮತ್ತು (b, c) ಇದ್ದರೆ (a, c) | (a, b) and (b, c) imply (a, c) | R ವರ್ಗ ⊆ R ಎಂಬ ಬೂಲಿಯನ್ ಗುಣಾಕಾರ ಪರೀಕ್ಷೆ | Boolean product test: R squared ⊆ R |
ಸಿಮೆಟ್ರಿಕ್ ಮತ್ತು ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ ವಿರುದ್ಧಾರ್ಥಕಗಳಲ್ಲ. ಡಯಾಗೊನಲ್‌ನ ಯಾವುದೇ ಭಾಗ ಮಾತ್ರ ಇರುವ ರಿಲೇಶನ್ ಎರಡೂ ಆಗಿರುತ್ತದೆ; {(1, 2), (2, 1), (2, 3)} ಯಾವುದೂ ಅಲ್ಲ. | Symmetric and antisymmetric are not opposites. A relation made only of diagonal pairs is both; {(1, 2), (2, 1), (2, 3)} is neither.
ಖಾಲಿ ರಿಲೇಶನ್ (Empty Relation) ಸಿಮೆಟ್ರಿಕ್, ಆಂಟಿಸಿಮೆಟ್ರಿಕ್, ಟ್ರಾನ್ಸಿಟಿವ್ ಮತ್ತು ಇರ್ರಿಫ್ಲೆಕ್ಸಿವ್; ಸೆಟ್ ಖಾಲಿ ಅಲ್ಲದಿದ್ದರೆ ರಿಫ್ಲೆಕ್ಸಿವ್ ಅಲ್ಲ. | The empty relation is symmetric, antisymmetric, transitive and irreflexive; on a non-empty set it is not reflexive.
n ಸದಸ್ಯರ ಸೆಟ್‌ನ ಮೇಲೆ ಎಣಿಕೆ ಸೂತ್ರಗಳು | Counting formulas on a set of n elements
| ರಿಲೇಶನ್ ಪ್ರಕಾರ | Kind of relation | ಸಂಖ್ಯೆ | Number | n = 3 | n = 3 |
|---|---|---|
| ಎಲ್ಲಾ ರಿಲೇಶನ್‌ಗಳು | All relations | 2 ರ ಘಾತ (n ವರ್ಗ) | 2 to the power (n squared) | 512 | 512 |
| ರಿಫ್ಲೆಕ್ಸಿವ್ (Reflexive) | Reflexive | 2 ರ ಘಾತ (n ವರ್ಗ − n) | 2 to the power (n squared minus n) | 64 | 64 |
| ಇರ್ರಿಫ್ಲೆಕ್ಸಿವ್ (Irreflexive) | Irreflexive | 2 ರ ಘಾತ (n ವರ್ಗ − n) | 2 to the power (n squared minus n) | 64 | 64 |
| ಸಿಮೆಟ್ರಿಕ್ (Symmetric) | Symmetric | 2 ರ ಘಾತ [n(n + 1)/2] | 2 to the power [n(n + 1)/2] | 64 | 64 |
| ಆಂಟಿಸಿಮೆಟ್ರಿಕ್ (Antisymmetric) | Antisymmetric | 2 ರ ಘಾತ n × 3 ರ ಘಾತ [n(n − 1)/2] | 2 to the power n times 3 to the power [n(n − 1)/2] | 216 | 216 |
| ಅಸಿಮೆಟ್ರಿಕ್ (Asymmetric) | Asymmetric | 3 ರ ಘಾತ [n(n − 1)/2] | 3 to the power [n(n − 1)/2] | 27 | 27 |
| ರಿಫ್ಲೆಕ್ಸಿವ್ ಮತ್ತು ಸಿಮೆಟ್ರಿಕ್ | Reflexive and symmetric | 2 ರ ಘಾತ [n(n − 1)/2] | 2 to the power [n(n − 1)/2] | 8 | 8 |
ಎಲ್ಲಾ ಸೂತ್ರಗಳ ತರ್ಕ ಒಂದೇ: ಡಯಾಗೊನಲ್‌ನ n ಸ್ಥಾನಗಳು ಮತ್ತು ಡಯಾಗೊನಲ್ ಹೊರಗಿನ n(n − 1)/2 ಜೋಡಿ ಸ್ಥಾನಗಳಿಗೆ ಎಷ್ಟು ಆಯ್ಕೆಗಳಿವೆ ಎಂದು ಎಣಿಸಿ. ಆಂಟಿಸಿಮೆಟ್ರಿಕ್‌ನಲ್ಲಿ ಪ್ರತಿ ಜೋಡಿಗೆ 3 ಆಯ್ಕೆಗಳು: ಯಾವುದೂ ಇಲ್ಲ, (a, b) ಮಾತ್ರ, (b, a) ಮಾತ್ರ. | Every formula uses the same reasoning: count the choices for the n diagonal cells and for each of the n(n − 1)/2 off-diagonal pairs. For antisymmetric each pair has 3 choices: neither, (a, b) only, or (b, a) only.
ಕಾಂಪೊಸಿಶನ್ (Composition) ಮತ್ತು ಕ್ಲೋಶರ್‌ಗಳು (Closures) | Composition and closures
- S ∘ R = {(a, c) : ಯಾವುದಾದರೂ b ಗೆ (a, b) ∈ R ಮತ್ತು (b, c) ∈ S}. ಮೊದಲು R, ನಂತರ S. | S ∘ R = {(a, c) : (a, b) ∈ R and (b, c) ∈ S for some b}. First R, then S.
- ರಿಫ್ಲೆಕ್ಸಿವ್ ಕ್ಲೋಶರ್ (Reflexive Closure) = R ∪ ಡಯಾಗೊನಲ್. | Reflexive closure = R ∪ the diagonal.
- ಸಿಮೆಟ್ರಿಕ್ ಕ್ಲೋಶರ್ (Symmetric Closure) = R ∪ R ನ ಇನ್ವರ್ಸ್ (Inverse). | Symmetric closure = R ∪ the inverse of R.
- ಟ್ರಾನ್ಸಿಟಿವ್ ಕ್ಲೋಶರ್ (Transitive Closure) = R ∪ R ವರ್ಗ ∪ ... ∪ R ಘಾತ n; ವಾರ್ಷಲ್ ಅಲ್ಗಾರಿದಮ್ (Warshall Algorithm) ಇದನ್ನು n ಘನ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕಿಸುತ್ತದೆ. | Transitive closure = R ∪ R squared ∪ ... ∪ R to the power n; the Warshall algorithm computes it in n cubed time.
R = {(1, 2), (2, 3)} ಟ್ರಾನ್ಸಿಟಿವ್ ಅಲ್ಲ, ಏಕೆಂದರೆ (1, 3) ಇಲ್ಲ. ಅದನ್ನು ಸೇರಿಸಿದರೆ ಟ್ರಾನ್ಸಿಟಿವ್ ಕ್ಲೋಶರ್ {(1, 2), (2, 3), (1, 3)}. | R = {(1, 2), (2, 3)} is not transitive because (1, 3) is missing. Adding it gives the transitive closure {(1, 2), (2, 3), (1, 3)}.
Practice questions
Answer all, then check. Explanations appear after checking.
Finished this topic? Tick it off.
Saved in this browser only. Sign in to keep your ticks on every device. See all revisions due