FEDERAL URDU UNIVERSITY OF ARTS,
SCIENCE AND TECHNOLOGY
Course : Discrete structure
Semester 3rd , B
ASSIGNMENT (GRAND)
Name :Wania saleem Teacher: Miss Salwa
Seat no: 23122129
June 12 2025
1. The cardinality of the set of odd positive integers less than 10 is 5 ?
2. The members of the set S = {x | x is the square of an integer and x < 100} is
S={0,1,4,9,16,25,36,49,64,81}.
3. The binary relation {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2)} on the set {1, 2, 3} is not in binary
relation on the set because (2,4) contains an element (4) not in a set.
4. Express the statement in words: “Every student in class has studied Calculus.” Using quantifiers.
let ;
p(x)= x is a student in the class .
Q(x)=x has studied calculus.
Quantifier = ∀x(p(x)→Q(x))
5. Prove ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q by LAW OF LOGIC.
Taking L.H.S
= ¬(p ∨ (¬p ∧ q))
= ¬((p ∨¬p) ∧ (p ∨ q)) |distribution law|
= ¬(t ∧ (p ∨ q)) |pV¬p = t ;negation law|
= ¬(pVq) | p∧t = p ; identity law |
= ¬p ∧ ¬q (proved !_) | demorgan law |
6. Prove (p ∧ q) → (p ∨ q) ≡ T. (with Truth Table)
p q (p ∧ q) (p ∨ q) (p ∧ q) → (p ∨ q)
T T T T T
T F F T T
F T F T T
F F F F T
Proved !
7. Determine whether f(x) = 𝑥 2+1/ 𝑥 2+2 ; x ∈N is bijective or not.
To check whether the function is bijection or not on x∈N ,we have to check two things
1. It should be one-to-one.
2. It should be onto.
Check Injectivity (One-to-One)
f(x1)= f(x2)
x12+1 / x12+2 = x22+1 / x22+2
(x12+1)( x22+2)=( x22+1)( x12+2)
x12x22+2x12+x22+2 = x12x22+2x22+x12+2
x12x22+2x12+x22+2- x12x22-2x22-x12-2= 0
x12= x22
so the function is one-to-one on N.
Check Surjectivity (Onto)
f(x) = 𝑥 2+1/ 𝑥 2+2
x=1⇒f(1)=0.666
x=2=0.833
x=3=0.909
x=10⇒0.990
As x→ ∞, f(x)→1, but never reaches it.
So the range is :
{ 𝑥 2+1/ 𝑥 2+2:x∈N}⊂(0.5,1)
The function is not surjective .
Since the function is not bijective .
8. Prove that the following argument is valid: “All dogs are carnivorous.“, “Some animals are dogs.”
Therefore “some animals are carnivorous”.
Arguments :
● All dogs are carnivorous
● Some animals are dogs
Therefore : some animals are carnivorous.
Let :
● D(x): x is a dog.
● C(x) : x is carnivorous.
● A(x) : x is an animal.
Premises:
1. ∀x(D(x)→C(x)) all dogs are carnivorous.
2. ∃x(A(x)∧D(x)) some animals are dogs
To prove :
∃x(A(x)∧C(x)) some animals are carnivorous.
PROOF :
From premises 2:
● There exists some x such that A(x)∧D(x) is true.
So for particular x , both A(x) and D(x) holds.
From premises 1:
● For all x , if D(x) then C(x)
So if D(x) is true for this specific x, C(x) must be true.
Therefore , for that same x.
● A(x)∧C(x) is true.
Thus ∃x(A(x)∧C(x)) is true .
9. Determine which of the following sets are finite/infinite.
A = {month in the year} (finite)
B = {even integers} (infinite)
C = {lines parallel to x-axis} (infinite)
D = {x ∈R | x100 + 29x50 – 1 = 0} (finite)
E = {circles through origin} (infinite)
10.Let A be the set of people living in the world today. A binary relation R is defined on A as follows:
for all p, q ∈A, pRq ⇔ p has the same first name as q. Determine whether the relation R is
reflexive, symmetric and/or transitive.
We are given
● Set A : the set of all people living in the world today.
● Relation R on A , for all p, q ∈A,
p R q ⇔ p has the same first name as q
We are to determine whether the relation R is
1. Reflexive
2. Symmetric
3. Transitive
Reflexive
A relation R is reflexive if for every p∈A, pRp.
● Does every person have the same first name as themselves ?
Yes , obviously.
Symmetric
A relation R is symmetric if for all p, q∈A
If pRq then qRp.
● If person p has the same name as person q, then person q also has the same first
name as person p.
Yes , clearly.
Transitive .
a relation is transitive if for all p,q , r∈A
if pRq and qRr then pRr.
Suppose
P has the same first name as q ( e.g, both named wania)
q has the same first name as r ( e.g, both named wania
then p and r must also both be named wania.
● In this case , p and r have the same first name
R is transitive.
R is an equivalence relation.
11.Define h: Z →Z by the rule h(n) = 4n - 1 for all n ∈ Z, Is h onto? Prove or give a counter example.
We are given a function
h:Z→Z,h(n)=4n−1
A function h: Z→Z is onto if for every y∈Z , there exists some n ∈Z such that:
h(n) = y
Suppose
h(n) = y ⇒ 4n – 1= y
solve for n
𝑦+1
4n = y+1 ⇒ n = 4
𝑦+1
For a given y∈Z , is 4
∈Z?
𝑜+1 1
Not always i.e if y=0 then ; 4
= 4
∉Z
So there is no integer n such that h(n)= 0
Counter example
Let y= 0
𝑜+1 1
4
= 4
∉Z
Not valid
12. Let a function f be defined on a set of real numbers as f( x )= x+1/ x-1 forxx1 all real numbers x
≠1. Show that f is a bijective function on R-{1}.Find the inverse function f-1
we are given
f(x) = x+1 /x-1 for x ∈R\{1}
show that f is bijective on R{1}
check injectivity
assume f(x1)=f(x2) then :
x1+1/x1-1 = x2+1/x2-1
(x1+1)(x2−1)=(x2+1)(x1−1)
x1x2−x1+x2−1= x1x2−x2+x1−1
−x1+x2=−x2+x1
−x1+x2−(−x2+x1)=0
−x1+x2+x2−x1=0
2x1=2x2
x1=x2 | function is injective |
check surjectivity
let y ∈R {1} . we want to find x ∈R \{1} such that :
f(x) = x+1 /x-1 =y
solve for x:
x+1=y(x−1)
x+1=yx−y
x−yx=−y−1
x(1−y)=−(y+1)
x=−(y+1)/1-y
We must check that this x≠1. Suppose x=1
1=−(y+1)/1-y
1−y=−(y+1)
1-y= -y-1
1= -1 | thus f is surjective |
Therefore f is bijective on R\ {1}
Find the inverse f-1
y = x+1/x-1 ⇒ x = -(y+1)/1-y
To simplify, multiply numerator and denominator by -1:
x= y+1 /y-1
so ,
f-1(y) = y+1/y-1, for y∈R \{1}
13.Find explicit formulas for sequences with the initial terms given:
1) 0, 1, -2, 3, -4, 5, …
an = (-1)n n
2) 2, 6, 12, 20, 30, 42, 56, …
an = n(n+1)
14.Use mathematical induction to prove that
1. 1+2+22 + … + 2n = 2n+1 - 1 for all integers n ≥0
Solution
Step 1 base case :
Let n= 0
LHS :20 =1
RHS : 20+1-1 =2-1 =1
LHS = RHS
Step 2 inductive step :
Assume for n= k
1+2+22+⋯+2k=2k+1−1
To Prove:
1+2+22+⋯+2k+2k+1=2k+2−1
Add 2k+1 on both side
(2k+1−1)+2k+1=2k+1+2k+1−1=2⋅2k+1−1=2k+2−1
The formula holds for k+1, so by induction, the formula is proven for all n≥0
2. 1/2+ 1/4 +1/8+1/16+……..
Step 1 base case
Let n = 1
1
LHS : 2
1 1 1
RHS : 1- 2^1 =1- 2
= 2
Base case holds .
Step 2 inductive step
Assume for n = k
1 1 1 1
2
+ 4
+…+ 𝑘 = 1- 𝑘
2 2
To prove
1 1 1 1 1
2
+ 4
+…+ 𝑘 + 𝑘+1 =1- 𝑘+1
2 2 2
1
Add 𝑘+1 on both side
2
1 1 1 1
(1- 𝑘 )+ 𝑘+1 = 1- 𝑘 + 𝑘+1
2 2 2 2
2 1 1
1–( 𝑘+1 − 𝑘+1 ) = 1- 𝑘+1
2 2 2
So, by induction, the formula holds for all n≥1
15.Let U = {1, 2, 3, 4, 5}, C = {1, 3}and A and B are non empty sets. Find A in each of the following:
● U={1,2,3,4,5}
● C={1,3}
● Sets A and B are non-empty.
(i)A ∪ B = U, A ∩ B = φ and B = {1}
B = {1}
AUB = U = {1, 2, 3, 4, 5}
A∩B=∅ so A and B must be disjoined set
A∪{1}={1,2,3,4,5}
A=U∖B={2,3,4,5}
A={2,3,4,5}
(ii) A ⊂ B and A ∪ B = {4, 5}
Given:
● A⊂B
● A∪B={4,5}
● A,B≠∅
Let’s consider all non-empty subsets of {4,5} where A⊂B
Possible combinations:
● If B={4,5}, then:
o A={4}
o A={5}
These are valid, as:
● A⊂B
● A∪B={4,5}
Possible answers:
● A={4},B={4,5}
● or A={5},B={4,5}So
A={4} A={5}
(iii) A ∩ B = {3}, A ∪ B = {2, 3, 4} and B ∪ C = {1,2,3}
● A∩B={3}
● A∪B={2,3,4}
● B∪C={1,2,3}
We know:
● C={1,3}
Step 1: From B∪C={1,2,3}
B∪{1,3}={1,2,3}⇒B must include 2
And since B∪{1,3}={1,2,3}, the only new element in B could be 2.
So possible B: includes 2 and 3, may or may not include 1.
Try B={2,3}, then:
● A∪B={2,3,4}⇒A must include 4 and 3 (since 2 is already in B)
● A∩B={3}⇒A includes 3, but not 2
So:
● A={3,4}, B={2,3}
Answer: A={3,4}
(iv) A and B are disjoint, B and C are disjoint, and the union of A and B
is the set {1, 2}.
Given:
● A∩B=∅ (A and B disjoint)
● B∩C=∅ (B and C disjoint)
● A∪B={1,2}
Step 1: Try values of B that are disjoint from C = {1, 3}
So B cannot include 1 or 3. From A∪B={1,2}, possible values for B:
● B={2}⇒A={1}
● Check disjointness:
o A∩B=∅(true )
o B∩C=∅ (true )
Answer: A={1}
