[SPRING
2015] ASSIGNMENT
|
PROGRAM
|
BSc IT
|
|
SEMESTER
|
SECOND
|
|
SUBJECT CODE & NAME
|
BT0069, Discrete Mathematics
|
Q. NO. 1
If U= {a, b, c, d, e}, A= {a, c, d}, B= {d, e}, C= {b, c, e}
Evaluate
the following:
A. A’ X (B – C )
B. (A U B)’ X (B∩C)
C. (A - B) X (B -C)
D. (B U C)’ X A
E. (B - A) X C’
Solution:
(A) A’ = U – A = {a, b, c, d, e } –
{a, c, d} = {b, e}
B – C = {d, e}
– {b, c, e} = {d}
Therefore A’ X
(B - C) = {b, e} x {d} = {(b, d)(e, d)}
(B) (A U B)’ = U – (A U B) = {a, b,
c, d, e} – {a, c, d, e} = {b}
B∩C = {d, e} ∩
{b, c, e} = {e}
Therefore (A U B)’ X (B ∩ C )
= {b} x {e} = {(b, e)}
(C) A
– B = {a, c, d} – {d, e} = {a, c}
B – C = {d, e}
– {b, c, e} = {d}
Therefore (A -
B) X (B - C) = {a, c} x {d} = {(a, d)(c, d)}
(D) B
U C = {d, e} U {b, c, e} = {b, c, d, e}
Therefore (B U
C)’ = U – (B U C) = {a}
Therefore (B U
C)’ X A = {a} x {a, c, d} = {(a, a), (a, c), (a, d) }
(E) B-A
= {d, e} – {a, c, d} = {e}
C’ = U – C = U – {b, c, e} = {a, d}
Therefore (B - A) X C’ = {e} x {a, d} = {(e, a), (e, d)}
Q.NO.2 (i)
State the principal of inclusion and exclusion.
(ii) How
many arrangements of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, contain at least
one of the patterns 289, 234or 487?
Solution:
(i) for any two sets P and Q, we have;
a)
|PUQ|≤|P| + |Q| where |P| is the number of
elements in P, and |Q| is the number elements in Q.
b)
|P∩Q|≤ min (|P|, |Q|)
c)
|P ⊕ Q| = |P| + |Q|
– 2|P ⊕ Q| where ⊕ is the symmetric difference.
ii) Let A289 be the event of having pattern 289.
Similarly A234 and A487.
We have to
find |A289 or A234 or A487|.
Now |A289| = 8! , as 289
considered as a group, which is a single object and the remaining seven
single digits. Similarly |A234| = |A487| = 8!
Also since 2
cannot be followed by both 3 and 8, we have |A289 ∩
A234| = 0.
Similarly |A289
∩ A487| = 0. But
|A234 or
A487| = 6! , since 23487
as a single object and remaining 5 single objects.
|A289 ∩ A234 ∩ A487| =
0.
Therefore,
by the principle of inclusion and exclusion –
|A289 U
A234 U A487| = 8! + 8! + 8! - 0 – 0 – 6! +
0 = 3 X 8! - 6!
Q.NO.3 If
G is the group, than prove that,
i.
The identity element of G is unique.
ii.
Every element in G has unique inverse in G.
iii.
For any a∈ g, we have (a power -1)whole
power -1=a
iv.
For all a,b∈G, we
have (a.b)whole power -1=b power-1.a power-1.
Solution:
i) Let
e, f be two identity elements in G. Since e is the
identity, we have e.f = f. Since f is the identity,
we have e.f = e. Therefore, e = e.f =
f. Hence the identity element is unique.
ii)
Let a be in G and a1, a2 are two inverses of a in
G.
Now a1 = a1.e (since e is the
identity)
= a1.(a.a2) (since a2 is the
inverse of a)
= (a1.a).a2 (by associativity)
= e.a2 (since a1 is the inverse of a)
= a2.
Hence the inverse of an element in G is unique.
iii) Let
a ∈ G. Since a.a-1 = e = a-1.a,
we have that a is the inverse of a-1.
Hence (a-1)-1 = a.
iv) Let
a, b ∈ G. Consider (b-1.a-1)(a.b)
= b-1.(a-1.a).b = b-1.e. b = b-1.b
= e.
Similarly e = (a.b).(b-1.a-1).
This shows that (a.b)-1 = b-1.a-1.
Q.NO.4
(i) Define valid argument
(ii) Show that ~ (P ^Q) follows
from ~ P ^ ~Q.
Solution: (i) We call an
argument deductively valid (or, for short, just "valid")
when the conclusion is entailed by, or logically follows from, the premises.
Validity is
a property of the argument's form. It doesn't matter what the
premises and the conclusion actually say. It just matters whether the argument
has the right form. So, in particular, a valid argument need not have
true premises, nor need it have a true conclusion. The following is a valid
argument:
1.
All cats are
reptiles.
2.
Bugs Bunny
is a cat.
3.
So Bugs
Bunny is a reptile.
Neither of
the premises of this argument is true. Nor is the conclusion. But the premises
are of such a form that if they were both true, then the
conclusion would also have to be true. Hence the argument is valid.
To tell
whether an argument is valid, figure out what the form of the
argument is, and then try to think of some other argument of that same
form and having true premises but a false conclusion. If you succeed,
then every argument of that form must be invalid. A valid form of argument
can never lead you from true premises to a false conclusion.
(ii) Assume ~ (~ (P ^
Q)) as an additional premise. Then,
(1) ~ (~ (P ^ Q)) Rule P
{1} (2) P ^ Q Rule T
(3) P Rule T
(4) ~P ^ ~ Q Rule P
{4} (5) ~ P Rule T
{3, 5} (6) P ^ ~ P Rule T
Therefore P ^
~ P is a contradiction. Hence by the indirect method of proof, ~
(P ^ Q) follows from ~ P ^ ~
Q.NO.5(i)
Construct a grammar for the language:
L={ x|x∈ {a,b}, the number of a’s in x is a multiple
of 3}
(ii) find
the highest type number that can be applied to the following production:
1. Sà A0, Aà1|2| B0, Bà012.
2. Sà ASA | b, Aà bA | c,
3. 3.SàBs | bc.
Solution:
(i)
Let T = {a, b} and N = {S,
A, B},
S is a starting symbol.
The set of productions:
S à bS
S à b
S à aA
A à bA
A à aB
B à bB
B à aS
B à a
For instance,
bbababbab can be generated as
follows.
S è bS è bbS è bbaA è bbabA è bbabaB è bbababbB è bbababbaS è bbababbab
Therefore, the grammar G = (VT
= {a, b}, VN = {S, A, B}, AΦ, S )
(ii) 1. Here, S à A0, A à B0 and B à 012 are of type 2, while A à 1 and A à 2 are type 3. Therefore, the highest type number is 2.
2. Here, S à ASB is of type 2, while S à b, A à bA and A à c are type 3. Therefore, the highest type number is
2.
3. Here, S à bS is of type 3, while S à ab is of type 2. Therefore, the highest type number is 2.
Q.No.6(i)
Define tree with example.
(ii) Prove
that any connected graphs with ‘n’ vertices and n-1 edges is a tree.
Solution: (i)
A connected
graph without circuits is called a tree.
A tree is a mathematical structure that can
be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between
elements, giving a tree graph.Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.
A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with
The points of connection are known as forks and the segments as branches. Final segments and the nodes at their ends are called tree leaves. A tree with two branches at each fork and with one or two tree leaves at the end of each branch is called a binary tree.
A graph can be tested in the Wolfram Language to see if it is a tree using TreeGraphQ[g] or using TreeQ[g] in theWolfram Language package Combinatorica`.
Example : Trees with one, two, three and four vertices are given in the Fig. below:
|
|
|
|
Fig: Graph Theory
(ii) Let “G” be a connected graph with n vertices and
n - 1 edges. It is enough to show that G contains no circuits.
If possible, suppose that G contains a circuit.
Let “e” be an edge in that circuit.
Since “e” in a circuit, we have that G - e is still
connected.
Now G - e is connected with „n‟ vertices, and so it should
contain at least n - 1 edges, a contradiction (to the fact that G - e contain
only (n-2) edges).
So G contains no circuits. Therefore, G is a tree.
No comments:
Post a Comment