CS 486, Spring ’01

February 1, 2001

10 questions

Quiz 1

 

 

  1. degree (((p Ú q) & r) É q)) = 4

true

false

 

 

 
  1. In any tree, finite or infinite, each point has only finitely many
    predecessors.

true

false

 

  1. Circle each line which is not a subformula of ((p Ú q) & r) É (q & r)

            (perhaps all are or none are)

a.      (p Ú q)

b.      r

c.       q

d.      (q & r)

e.      r É q

 

  1. The truth table for ((p Ú q) & r) É (q & r) has this number of rows:
    1. 22 = 4
    2. 23 = 8
    3. 25 = 32
    4. 33 = 27

 

  1. A formula X is called satisfiable iff ~X is true in at least one
    Boolean valuation

true

false

 

 

 
  1. left : A + right : B = right : B + left : A

true

false

 

 

 
  1. ((study implies goodgrades) and not(goodgrades)) implies not(study)
    is a true fact of psychology but not a tautology (logically true)

true

false

 

 

 
  1. Every propositional formula is truth functionally equivalent to either t or f

true

false

 

  1. Circle the best among these translations of $X:Form.(X = p1)
    1. all formulas contain p1
    2. p1 is a formula
    3. some formula is p1
    4. no formula is p1

 

  1. Circle all statements that are in our metalanguage
    1. " X : Form.(X = p1  or  not(X = p1))
    2. (p1 Ú p2)
    3. (p1 É p1) is a tautology
    4. (p1 É (p2 É p1))