Learn more about our help with Assignments: Discrete Math
Search & Filtering
Discrete Mathematics
Any subset of A × A is called a relation on the set A. A relation R on A is symmetric if
(a, b) ∈ R ⇒ (b, a) ∈ R ∀ a, b ∈ A. Give one example each, with justification, of
i) a symmetric relation on ,
ii) a relation that is not symmetric on the set {2, 3, 5, 7}.
(a, b) ∈ R ⇒ (b, a) ∈ R ∀ a, b ∈ A. Give one example each, with justification, of
i) a symmetric relation on ,
ii) a relation that is not symmetric on the set {2, 3, 5, 7}.
Discrete Mathematics
I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let B=(L,R,E) be an undirected bipartite graph, ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2.....n connect u to wi, where w∈R.
The problem is to find a minimum set K from L covering all R in B, K⊆L , ∑u∈K is minimal.
To clarify what I mean by covering: all vertices of R should should have at least one edge to any u∈K.
My intuition is that it's NP-Hard. If that is the case, any idea of what would be the best way to approximate the result (ie a minimum set K of L covering R) ?
Edit: Here is an example, consider the following bipartite graph: G={L∪R,E},
L={1,2,3,4,5,6},
R={A,B,C,D} ,
E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D}
And here is a covering minimum set will be {2,4}
Let B=(L,R,E) be an undirected bipartite graph, ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2.....n connect u to wi, where w∈R.
The problem is to find a minimum set K from L covering all R in B, K⊆L , ∑u∈K is minimal.
To clarify what I mean by covering: all vertices of R should should have at least one edge to any u∈K.
My intuition is that it's NP-Hard. If that is the case, any idea of what would be the best way to approximate the result (ie a minimum set K of L covering R) ?
Edit: Here is an example, consider the following bipartite graph: G={L∪R,E},
L={1,2,3,4,5,6},
R={A,B,C,D} ,
E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D}
And here is a covering minimum set will be {2,4}
Discrete Mathematics
write the following boolean expressions in an equivalent sum of product canonical form in three variables x1, x2, and x3:
1. x1*x2 ?
2. x1⊕x2 ?
3. (x1⊗X2)'*X3
1. x1*x2 ?
2. x1⊕x2 ?
3. (x1⊗X2)'*X3
Discrete Mathematics
Simplify the following Boolean function using k -map
F = A’C + A’B + AB’C + BC
F = A’C + A’B + AB’C + BC
Discrete Mathematics
Expand the following Boolean functions into their canonical form:
i. f(X,Y,Z)=XY+YZ+X'Z+X'Y'
ii. f(X,Y,Z)=XY+X'Y'+X'YZ
i. f(X,Y,Z)=XY+YZ+X'Z+X'Y'
ii. f(X,Y,Z)=XY+X'Y'+X'YZ
Discrete Mathematics
consider the set consisting of counting numbers 1-20
Discrete Mathematics
Expand the following Boolean functions into their canonical form:
i. f(X,Y,Z)=XY+YZ+ X Z+ X Y
ii. f(X,Y,Z)=XY+ X Y + X YZ
i. f(X,Y,Z)=XY+YZ+ X Z+ X Y
ii. f(X,Y,Z)=XY+ X Y + X YZ
Discrete Mathematics
If we have 100 people (80 male and 20 female) and we need to choose a committee.
The committee must contain exactly 2 females, then how many different 5 person committees are possible?
The committee must contain exactly 2 females, then how many different 5 person committees are possible?
Discrete Mathematics
In a certain village of 1000 houses, 750 have a car, 800 have a refrigerator, 850 have a telephone and 950 have a radio. What is the least number of houses that have all four?
Discrete Mathematics
Consider the sample space S = {copper, sodium, nitrogen, potassium, uranium, oxygen, zinc}, and the events A={copper, sodium, zinc}, B={uranium, nitrogen, potassium}, C={oxygen}.
List the elements of the sets corresponding the following events:
i) A ∪ C
ii) (A ∩ B') ∪ C'
iii) (A' ∪ B') ∩ (A' ∩ C)
List the elements of the sets corresponding the following events:
i) A ∪ C
ii) (A ∩ B') ∪ C'
iii) (A' ∪ B') ∩ (A' ∩ C)
