Q.3 (a)
Question:
Define a complete graph and find the order and size of the graph
K2025.
Definition: Complete Graph
A complete graph is a simple graph in which every pair of distinct vertices is connected by exactly one edge.
A complete graph with n vertices is denoted by Kn.
Order of the Graph:
The order of a graph is the number of vertices in the graph.
Order of K2025 = 2025
Size of the Graph:
The size of a graph is the number of edges.
A complete graph with n vertices has:
n(n − 1)/2 edges
For K2025:
= 2025 × 2024 / 2
= 2025 × 1012
= 2049300 edges
Final Answer:
Order of K2025 = 2025
Size of K2025 = 2049300
Q.3 (b)
Question:
Show that the proposition
[(p → q) ∧ (q → r)] → (p → r)
is a tautology.
Method: Truth Table
We construct the truth table for the given proposition.
| p | q | r | p → q | q → r | (p → q) ∧ (q → r) | p → r | Whole Proposition |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
Conclusion:
From the truth table, we observe that the final column is true for all possible values of p, q, and r.
Therefore, the given proposition is a tautology.
Q.3 (c)
Given:
Let
R = { a + bi : a, b ∈ ℤ }
with usual addition and multiplication. Show that (R, +, ×) is an integral domain.
Step 1: R is a Commutative Ring with Unity
Take any two elements x = a + bi and y = c + di in R.
(i) Closure:
x + y = (a + c) + (b + d)i ∈ R
x × y = (ac − bd) + (ad + bc)i ∈ R
Hence, R is closed under addition and multiplication.
(ii) Additive Identity:
0 = 0 + 0i ∈ R
(iii) Additive Inverse:
For a + bi, its additive inverse is −a − bi, which belongs to R.
(iv) Commutativity:
Addition and multiplication of complex numbers are commutative.
(v) Multiplicative Identity:
1 = 1 + 0i ∈ R
Hence, (R, +, ×) is a commutative ring with unity.
Step 2: R Has No Zero Divisors
Suppose
(a + bi)(c + di) = 0
⇒ (ac − bd) + (ad + bc)i = 0 + 0i
Comparing real and imaginary parts:
ac − bd = 0
ad + bc = 0
These equations imply either a = b = 0 or c = d = 0.
Hence,
(a + bi) = 0 or (c + di) = 0
Therefore, R has no zero divisors.
Conclusion:
Since R is a commutative ring with unity and has no zero divisors,
(R, +, ×) is an integral domain.
Q.3 (OR) (a)
Given:
P = {1, 2, 3, 5, 11, 13, 17, 19, 23}
Relation ≤ is defined by: x ≤ y ⇔ x divides y
Solution:
In the given set, the number 1 divides every element, and all other elements are prime numbers.
Hence, there is a direct relation from 1 to each prime number.
No prime divides another prime.
So the Hasse diagram has:
- 1 at the bottom
- All prime numbers above it
1 → {2, 3, 5, 11, 13, 17, 19, 23}
This represents the Hasse diagram.
Q.3 (OR) (b)
Given:
Relation R is defined on real numbers by
R = { (a, b) : a ≤ b , a and b are real numbers }
Check whether R is reflexive, symmetric, and transitive.
(i) Reflexive:
For any real number a, we have a ≤ a.
Hence, R is reflexive.
(ii) Symmetric:
If a ≤ b, it is not necessary that b ≤ a.
Example: 2 ≤ 3 but 3 ≤ 2 is false.
Therefore, R is not symmetric.
(iii) Transitive:
If a ≤ b and b ≤ c, then a ≤ c.
Hence, R is transitive.
Conclusion:
R is reflexive and transitive but not symmetric.
Q.3 (OR) (c) (i)
Question:
Does there exist a graph with 20 edges and each vertex of degree 3?
Solution:
Let the number of vertices be n.
Sum of degrees = 2 × number of edges
3n = 2 × 20
3n = 40
n = 40 / 3
Since n is not an integer, such a graph cannot exist.
Therefore, no such graph exists.
Comments
Post a Comment