CP3210 Logic Tutorial II

  1. Express each of the following sentences in 1st order logic
    1. All birds can fly.
    2. Not all birds can fly.
    3. All babies are illogical.
    4. Some babies are illogical.
    5. If x is a man, then x is a giant.
    6. Some men are giants.
    7. Some men are not giants.
    8. All men are giants.
    9. All men are not giants.
    10. There is a student who likes mathematics but not history.

    Answer

    1. forall X [bird(X) => fly(X)].
    2. not (forall X [bird(X) => fly(X)]).
    3. forall X [baby(X) => illogical(X)].
    4. exists X [baby(X) ^ illogical(X)].
    5. (man(X) => giant(X)).
    6. exists X [man(X) ^ giant(X)].
    7. exists X [man(X) ^ not(giant(X))].
    8. forall X [man(X) => giant(X)].
    9. forall X [man(X) => not(giant(X))].
    10. exists X [student(X) ^ likes(X, mathematics) ^ not(likes(X, history))].

  2. Express each of the following sentences in 1st order logic, first using no existential quantifiers, and then using no universal quantifiers
    1. Not all cars are BMWs.
    2. No dogs are intelligent.
    3. All babies are illogical.
    4. Some numbers are not real.
    5. Not every graph is connected.
    6. Some people are religious or pious.
    7. Every number is negative or has a square root.
    8. Every connected and circuit-free graph is a tree

    Answers

    1. not (forall X [car(X) => bmw(X)]).
    2. forall X [dog(X) => not intelligent(X)].
    3. forall X [baby(X) => illogical(X)].
    4. not (forall X [number(X) => real(X)]).
    5. not (forall X [graph(X) => connected(X)]).
    6. not (forall X [people(X) => not(regious(X) | pious(X))]).
    7. forall X [number(X) => (negative(X) | has-sqroot(X))].
    8. forall X [(connected(X) ^ circuit-free-graph(X)) => tree(X)].

    1. exists X [car(X) ^ not(bmw(X))].
    2. not (exists X [dog(X) ^ intelligent(X)]).
    3. not (exists X [baby(X) ^ not(illogical(X))]).
    4. exists X [number(X) ^ not(real(X))]).
    5. exists X [graph(X) ^ not(connected(X))]).
    6. exists X [people(X) ^ (regious(X) | pious(X))].
    7. not (exists X [number(X) ^ not(negative(X) | has-sqroot(X))]).
    8. not (exists X [connected(X) ^ circuit-free-graph(X) ^ not(tree(X))].

  3. Use resolution to derive the empty clause from the set 
         { p(X,Y),
       ~p(f(X,Y),g(X,Y)),
       ~p(X,h(Y)) v p(X,Y),
       ~p(X,h(Y)) v ~p(X,X),
       ~p(X,Y) v p(X,X) v p(X,h(Y)) }

    Answer 

         ~p(X,h(Y)) v ~p(X,X)  + ~p(X,Y) v p(X,X) v p(X,h(Y))
                           = ~p(h(Y),Y)
     ~p(h(Y),Y) + p(X,Y)   = FALSE
    This effectively demonstrates how many possible resolutions there are, even though the solution is simple.

  4. 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.
    Now convert it to CNF in a form ready for a refutation proof, and give a refutation proof of the conjecture.

    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))

     ~vegie(X) | ~beef(X)
     ~vegie(X) | ~pork(X)
     vegie(sk1)
     eggs(sk1)
     pork(X) | ~bacon(X)
     ~eggs(X) | bacon(X)

     ~vegie(X) | ~pork(X)   + vegie(sk1)  = ~pork(sk1)
     pork(X) | ~bacon(X)    + ~pork(sk1)  = ~bacon(sk1)
     ~eggs(X) | bacon(X)    + ~bacon(sk1) = ~eggs(sk1)
     ~eggs(sk1)             + eggs(sk1)   = FALSE

  5. Use linear-input resolution to derive the empty clause from the set 
         S = { ~r(Y) v ~p(Y),
           p(b),
           r(a),
           p(S) v ~p(b) v ~r(S),
           r(c) }

    Answer 

         ~r(Y) v ~p(Y)          + r(a)
     ~p(a)                  + p(S) v ~p(b) v ~r(S)
     ~p(b) v ~r(a)          + p(b)
     ~r(a)                  + r(a)
     FALSE
  6. Express the following scenario and conclusion in 1st order logic
    If you are a normal person, then you like at least one form of music and you dislike at least one form of music. There is a person who likes all music. Therefore there is a person who is not a normal person.
    Now convert it to CNF in a form ready for a refutation proof, and give a linear-input refutation proof of the conjecture.

    Answer 

         ! [X] :
       ( normal(X)
      => ( ? [Y] :
             ( music(Y)
             & likes(X,Y) )
         & ? [Y1] :
             ( music(Y1)
             & ~ likes(X,Y1) ) ) ) 
     ? [X] :
       ( person(X)
       & ! [Y] :
           ( music(Y)
          => likes(X,Y) ) )
     ? [X] :
       ( person(X)
       & ~ normal(X) )

     ~normal(X) | music(sk1(X))
     ~normal(X) | likes(X,sk1(X))
     ~normal(X) | music(sk2(X))
     ~normal(X) | ~likes(X,sk2(X))
     person(sk3)
     ~music(X) | likes(sk3,X)
     ~person(X) | normal(X)

     ~normal(X) | ~likes(X,sk2(X))    + ~person(X) | normal(X)
     ~person(X) | ~likes(X,sk2(X))    + person(sk3)
     ~likes(sk3,sk2(sk3))             + ~music(X) | likes(sk3,X)
     ~music(sk2(sk3))                 + ~normal(X) | music(sk2(X))
     ~normal(sk3)                     + ~person(X) | normal(X)
     ~person(sk3)                     + person(sk3)
     FALSE

  7. Convert the following to CNF. Notation: & for AND, | for OR, ! for universal quantifier, ? for existential quantifier. 
         ~ ( ? [Y] :
         ! [X] :
           ( element(X,Y)
         <=> element(X,X) )
      => ~ ( ! [X1] :
             ? [Y1] :
             ! [Z] :
               ( element(Z,Y1)
             <=> ~ element(Z,X1) ) ) )

    Answer