Keys:

 

    1-5:     BCBCED

    6-10:    CCCCB

    11-15:   ABEDB

    16-20:   ADAEB

 

COSC3302          Test-1                  3/5/2007

 

      Name_______________________________________

 

      THROUGHOUT THIS TEST, THE FOLLOWING NOTATIONS ARE APPLICABLE:

 

      1. $:             Universal Quantifier.

      2. %:             Existential quantifier.

      3. ^:             Conjunction operator. (AND)

      4. +:             Disjunction operator. (OR)

      5. ~:             Negation operator. (NOT)

      6. ->:            Implication operator (IMPLIES)

      7. V,W,X,Y,Z:     A variable.

      8. a,b,c,d:       A constant.

      9. f,g,h:         A function.

     10. P,Q,R,S:       A predicate (in Predicate Calculus)

     11. A,B,C,D:       A Literal   (in Propositional Calculus)

     12. E.R:           Equivalence Relation.

 

    PART-A.       Multiple-Choice questions           (60 points)

 

      Clearly write down a BIG A,B,C,D,E, or F in CAPITAL by each

      question number and nowhere else.

 

      First 3 questions are about the following conditional statement:

                  “if A then B”

1.     Which is its Converse?

a.       if not(A) then not(B)

b.       if B then A

c.       both.                  d. neither.

2.     Which is its Contrapositive?

a.       if not(A) then not(B)

b.       if not(B) then not(A)

c.       both.                  d. neither.

3.     Which is its equivalence?

a.       If not(B) then not(A)

b.       not(A) + B

c.       both.                  d. neither.

 

Next 3 questions about the following binary relation:

            1 1 0 0

            1 1 0 0

            0 0 0 0

            0 0 0 1

4.     The relation is

a.       reflexive

b.       symmetric

c.       transitive

d.       All above        e. Two above            f. None

5.     The relation is

a.       Antisymmetric

b.       Irreflexive

c.       Both.

d.       Neither.

 

 

6.     Which is its minimum E.R.?

a.    1 1 1 0     b.    1 1 1 1     c.    1 1 0 0

      1 1 1 0           1 1 1 1           1 1 0 0

      1 1 1 0           1 1 1 1           0 0 1 0

      0 0 0 1           1 1 1 1           0 0 0 1

d.       none

 

7.     Which is a fundamental disjunction?

a.       ~A + ~B

b.       A + B + ~C

c.       Both.            d.    neither.

 8.   Which is equivalent to:       A -> B -> C

a.       (A->B) -> C

b.       (A^~B) + C

c.       Both.       d.    neither.

 9.   Which is equivalent to: $X(P(X) ^ Q(X))

a.       $X P(X) ^ ($Y Q(Y))

b.       $X P(X) ^ ($X Q(X))

c.       both.       d.    neither.

10.   Which is equivalent to:       %X(P(X) + Q(X))

a.       %X P(X) ^ (%X Q(X))

b.       %X P(X) + (%Y Q(Y))

c.       both.       d.    neither.

11.   Which is implied by:          %X$Y (P(X,Y))

a.       $Y%X (P(X,Y))

b.       $X$Y (P(Y,X))

c.       both.       d.    neither.

12.   Which is implied by:          %X (P(X) -> Q(X))

a.       %X P(X)

b.       $X P(X) -> (%Y Q(Y))

c.       both.       d.    neither.    

13.  Which is a tautology?

a.       A ^ B ^ C -> D

b.       A ^ B ^ C -> A

c.       A ^ B ^ C -> B + D

d.       All above         e.    Two above.

14.   Which is a contradiction?

a.       A -> ~A

b.       A ^ ~A

c.       A ^ ~A ^ B

d.       Two above.        e.    None above.

 

Next two questions are about the following functions:

      f(X) = X/2 (Integer division, so 3/2 is 1 and 4/2 is 2)

                  mapping N to N

g(X) = 2*X mapping N to N where N={0,1,2,3,…,inf}.

 

      15.   The function f() is

a.       injective.

b.       surjective.

c.       Both.             d.    Neither.

16.   The function g() is 

a.       injective.

b.       surjective.

c.       Both.             d.    Neither.

 

 

17.   Parts of a grammar include, among others:

a.       set of terminal symbols

b.       set of nonterminal symbols

c.       set of production rules.

d.       All above.        e.    two above.

18.  A grammar is ambiguous if

a.       it generates at least one ambiguous sentence.

b.       if generates no ambiguous sentence.

c.       Both.       d.    Neither.

 

For the next two questions, consider the following CFG:

      S  ->       S  S

      S  ->       ( )

      S  ->       ( S )

 

19.   Which is a sentence generated by this grammar?

a.       (())()

b.       ()()()

c.       The empty-string

d.       All above.        e. two above.           f. none above.

20.   Which is an ambiguous sentence?

a.       ()()

b.       ()()()()

c.       (())()

d.       all above.        e. two above.           f. none

 

      PART-B.     Other problems.               (40 points)

 

A.    Give an Adjacency Matrix for the smallest binary relation over the set A ={a,b,c,d} for each of the following 3 cases:

 

            1. Symmetric and Reflexive and Transitive.

            2. Transitive and Anti-symmetric but not Reflexive.

3. Not Reflexive and not Irreflexive.

(1)

1
	1
		1
			1

 

 

            (2)

0
	0
		0
			0

 

 

            (3)

0
	0
		0
			1

 

 

 

 

      B.    Convert the following argument into a wff in Predicate Logic and

            show all the clauses needed for the resolution procedure to establish

            the validity of the argument, that is, to show that the intended

            conclusion indeed logically follows from the set of premises.

     

            P1: Some freshmen like all sophomores.

            P2: No freshman likes any junior.

            C:  Therefore, no sophomore is a junior.

 

 

 

 

 

      C.    ((A -> B -> C) ^ D) -> X

 

            Give resulting implication or implications after

            removing the two implication operators of the antecedent.