CP3210 Logic Tutorial I Answers

  1. Express the following axioms and conjecture in propositional logic
    1. All the dated letters in this room are written on blue paper.
    2. None of them are in black ink, except those that are written in the third person.
    3. I have not filed any of them that I can read.
    4. None of them that are written on one sheet are undated.
    5. All of them that are not crossed are in black ink.
    6. All of them written by Brown begin with "Dear Sir"
    7. All of them written on blue paper are filed.
    8. None of them written on more than one sheet are crossed.
    9. None of them that begin with "Dear Sir" are written in third person.
    10. Prove that letters by Brown cannot be read.

    Answer 

         dated => blue_paper
     black_ink <=> third_person
     can_read => ~filed
     one_sheet => dated
     ~crossed => black_ink
     by_brown => dear_sir
     blue_paper => filed
     ~one_sheet => ~crossed
     dear_sir => ~third_person

     by_brown => ~can_read
  2. Determine whether each of the following inferences is valid or faulty. If the inferences is valid, show the sequence of valid inference rules used. If the inferences is faulty, produce a combination of truth values that confirm/indicate a fallacy or point out the unsound inference rule(s) used.
    1. (a) If today is David's birthday, then today is Januaru 24. (b) Today is Januaru 24. (c) Hence, today is David's birthday.
    2. (a) If the client is guilty, then he was at the scene of the crime. (b) The client was not at the scene of the crime. (c) Hence, the client is not guilty.
    3. (a) If David passes the final exam, then he will pass the course. (b) David will pass the course. (c) Hence, David passes the final exam.
    4. (a) If the graphs are isomorphic, then they have the same number of edges. (b) The graphs have different number of edges. (c) Hence, the graphs are not isomorphic.
    5. (a) If Joe or Abe needs a vacation, then Ted deserves an assistant. (b) Hence, if Joe needs a vacation, then Ted deserves an assistant.
    6. (a) If the cup is styrofoam, then it is lighter than water. (b) If the cup is lighter than water, then Joe can carry it. (c) Hence, if the cup is styrofoam, then Joe can carry it.
    7. (a) Mathematicians are ambitious. (b) Early risers do not like oatmeal. (c) Ambitious people are early risers. (d) Hence, Mathematicians do not like oatmeal.

    Answer

    1. The inferences is faulty. (DB => J24) and J24 do not imply DB. Note that an inference can be faulty even if it gives a correct conclusion unless the inference rules used are sound ones.
    2. The inferences is valid. (CG => AtSc) and "not AtSc" imply "not CG". Inference rules used are contrapositivity and Modus Ponens.
    3. The inferences is faulty. (PF => PC) and PC do not imply PF.
    4. The inferences is valid. (Iso => SNE) and "not SNE" imply "not Iso".
    5. The inferences is valid. ((JV | AV) => TDA) implies (JV => TDA).
    6. The inferences is valid. (CS => LTW) and (LTW => JC) together imply (CS => JC) by transitivity.
    7. The inferences is valid. (M => A), (A => ER) and (ER => not LO) together imply (M => not LO) by transitivity.
  3. Use the definition of logical consequence and a truth table to show that
           (q => p) | ~(q => (p | r))
    is a logical consequence of the set: 
         { p | q | r, 
       r => (p | q), 
       (q ^ r) => p, 
       ~p | q | r }

    Answer 

         p q r p|q|r r=>(p|q) (q^r)=>p ~p|q|r   A  (q=>p)|~(q=>(p|r))
     T T T   T     T         T        T     T        T
     T T F   T     T         T        T     T        T
     T F T   T     T         T        T     T        T
     T F F   T     T         T        F     F
     F T T   T     T         F        T     F
     F T F   T     T         T        T     T        T
     F F T   T     F         T        T     F
     F F F   F     T         T        T     F
    In all interpretation where the axioms are true, the conjecture is true. Thus the conjecture is a logical consequence of the axioms.
  4. Use unsatisfiability and a truth table to show that
           ~rf
    is a logical consequence of the set: 
         { ~rf | td,
       ~gc | td,
       ~td | ph,
       ~ph }

    Answer 

         rf td gc ph  ~rf|td ~gc|td ~td|ph ~ph rf    A U {~F}
     T  T  T  T      T      T      T    F  T       F
     T  T  T  F      T      T      F    T  T       F
     T  T  F  T      T      T      T    F  T       F
     T  T  F  F      T      T      F    T  T       F
     T  F  T  T      F      F      T    F  T       F
     T  F  T  F      F      F      T    T  T       F
     T  F  F  T      F      T      T    F  T       F
     T  F  F  F      F      T      T    T  T       F
     F  T  T  T      T      T      T    F  F       F
     F  T  T  F      T      T      F    T  F       F
     F  T  F  T      T      T      T    F  F       F
     F  T  F  F      T      T      F    T  F       F
     F  F  T  T      T      F      T    F  F       F
     F  F  T  F      T      F      T    T  F       F
     F  F  F  T      T      T      T    F  F       F
     F  F  F  F      T      T      T    T  F       F
     
         There is no model of the axioms and the negated conjecture, i.e.,
     they're unsatisfiable. Thus the conjecture is a logical consequence 
     of the axioms.

  5.  Use resolution to show that
    
     
           p
     
    
     is a logical consequence of the set:
     
         { q v p,
       ~q v r,
       ~r v s,
       ~s v ~r v t,
       ~t v p }
     
    
     
    
     Answer
     Negate the conjecture p to form ~p, and add it to
     the set. Then use resoolution.
     
         ~p     + q v p       = q
     q      + ~q v r      = r
     r      + ~r v s      = s
     s      + ~s v ~r v t = ~r v t
     ~r v t + r           = t
     t      + ~t v p      = p
     p      + ~p          = FALSE
     
    

  6.  Given the 1st order logic language:
     
         V = { V : V starts with uppercase }
     F = { holden/0, ford/0, honda/0 main_competitor/1 }
     P = { fast/1, faster/2 }
     
    
     and the interpretation:
     
         D = { commodore, laser, prelude }
     F = { holden -> commodore,
           ford -> laser,
           honda -> prelude,
           main_competitor(commodore) -> prelude,
           main_competitor(laser) -> prelude,
           main_competitor(prelude) -> commodore }
     R = { fast(commodore) -> TRUE,
           fast(laser) -> FALSE,
           fast(prelude) -> TRUE,
           faster(commodore,commodore) -> FALSE,
           faster(commodore,laser) -> TRUE,
           faster(commodore,prelude) -> TRUE,
           faster(laser,commodore) -> FALSE,
           faster(laser,laser) -> FALSE,
           faster(laser,prelude) -> FALSE,
           faster(prelude,commodore) -> FALSE,
           faster(prelude,laser) -> TRUE,
           faster(prelude,prelude) -> FALSE }
     
    
     Show the steps of the interpretation of:
     
     
      
     
    •  faster(main_competitor(ford),holden)
     
    •  fast(main_competitor(main_competitor(honda)))
     
    •  forall X ( faster(main_competitor(X),ford) ^ fast(X) )
     
    •  exists X ( fast(main_competitor(main_competitor(X))) |
                     forall Y ( faster(X,Y) ) )
     
    
         
     
    
     Answer
     
         faster(main_competitor(ford),holden)
     faster(main_competitor(laser),commodore)
     faster(prelude,commodore)
     FALSE

     fast(main_competitor(main_competitor(honda))
     fast(main_competitor(main_competitor(prelude)))
     fast(main_competitor(commodore))
     fast(prelude)
     TRUE

     forall X ( faster(main_competitor(X),ford) ^ fast(X) )
     X = commodore
         faster(main_competitor(commodore),ford) ^ fast(commodore)
         faster(prelude,laser) ^ TRUE
         TRUE ^ TRUE
         TRUE
     X = laser
         faster(main_competitor(laser),ford) ^ fast(laser)
         faster(prelude,laser) ^ FALSE
         TRUE ^ FALSE
         FALSE
     FALSE

     exists X ( fast(main_competitor(main_competitor(X))) |
                forall Y ( faster(X,Y) ) )
     X = commodore
         fast(main_competitor(main_competitor(commodore))) |
         forall Y ( faster(commodore,Y) )
         fast(main_competitor(prelude)) | forall Y ( faster(commodore,Y) )
         fast(commodore) | forall Y ( faster(commodore,Y) )
         TRUE | forall Y ( faster(commodore,Y) )
         TRUE
     TRUE
     
    

  7.  Express the following scenario and conclusion in 1st order logic
     
    
     No vegetarian likes either beef or pork.
     There are some vegetarians who like eggs.
     If someone doesn't like pork, then they don't like bacon.
     Therefore there is someone who likes eggs but not bacon.
     
    
     
    
     Answer
     
         ~exists X (vegie(X) ^ (beef(X) | pork(X)))
     exists X (vegie(X) ^ eggs(X))
     forall X (~pork(X) => ~bacon(X))
  
     exists X (eggs(X) ^ ~bacon(X))