LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc. DEGREE EXAMINATION – MATHEMATICS

XZ 23

SIXTH SEMESTER – APRIL 2008

MT 6601 – APPLIED ALGEBRA

 

 

 

Date : 21/04/2008                Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

 

PART – A

Answer ALL questions:                                                                                (10 x 2 = 20)      

 

1. Construct the truth table for the statement formula Pù Q.
2. What is meant by well formed formula.
3. When is a statement A said to tautologically imply a statement B?
4. Define conditional statement.
5. State Zorn’s lemma
6. Define Boolean Algebra and give an example of it.
7. Define Mealy and More automaton.
8. Give an example of a semi group which is not a monoid.
9. Define anti homomorphism and anti isomorphism of semi groups.
10. Define automata homomorphism.

 

PART – B

Answer any FIVE questions.                                                                       (5 x 8 = 40)

 

1. Show that

• ( P®(Q®R)ÛP®(ùQÚR) Û(PÙQ) ®R

(ii) ( ù PÙ (ù QÙ R) Ú(QÙR) Ú(PÙR) ÛR

1. Show that

((PÚQ) Ùù ( ù PÙ(ùQÚùR)) Ú( ùPÙùR) is a tautology.

1. Obtain a conjunctive normal form of each of the formula as given below

(i) (PÙ(P ®Q)    (ii) ù (PÚQ) D (PÙQ)

1. Obtain the product – of –sums canonical forms of the following formulas.

(i) (PÙQ) Ú ( ù PÚQ) Ú(PÙù Q)

(ii) (PÙQ) Ú ( ù PÙ QÙR)

1. Let be a lattice ordered set. If Π;     show that (L,Π,    ) is an algebraic lattice.
2. State and prove Representation theorem for Boolean Algebra.
3. For any semigroup (S,o), Show that there exists a set N such that (S,o) is embeddable in (N^N, o).
4. Show that for any monoid (S,o) there exists a semi automation whose monoid is isomorphic to (S,o).

 

 

PART – C

Answer any TWO   questions.                                                                      (2 x 20 = 40)        

 

1. a) Show that

(i) ù (PÙQ) ® ( ù PÚ( ù PÚQ) Û (ù PÚQ)

(ii) (PÙQ) Ù ( ù PÙ ( ù PÙQ) Û (ù PÙQ)

 

 

1. b) Show that the truth values of the following formulas are independent of their

components.

(i) (PÙ ( P® Q) ® Q

(ii) (P® Q) D( ù PÚQ)

 

1. a) Obtain the principal disjunctive normal forms of

(i) ( ù PÚQ)

(ii) (PÙQ) Ú( ù PÙR) Ú( QÙR)

1. b) Show that a modular lattice is distributive if and only if none of its sub lattices is isomorphic to the diamond lattice .

1. a) Explain marriage semi automation.

1. b) Let ~₁ and ~₂ be two congruence relations on (S,o). Show that ~₁, C ~₂ if and only if is an epimorphism of (S/~_1, o) onto (S/~₂, o).
2. c) For any f show that there exists a semi group F which is free on B.
3. a) For two automation if show that is a homomorphic image of .
4. b) If the automation is a homomorphic image of , show that is a homomorphic image of .
5. c) Explain parallel composition and series composition of two automata and .

 

 

 

Go To Main page