SE-561

Math Foundations of Software Engineering

Homework Assignment 2 (Due Friday, Oct. 26)

    1. Use the predicate specifications

             B(x, y): x beats y
                 F(x): x is an American football team
             Q(x, y): x is quarterback of y
              L(x, y): x loses to y

         and constant symbols

               c: Wildcats
               j: Jayhawks

         to translate the following to predicate logic:

            a. Every football team has a quarterback
            b. If the Jayhawks beat the Wildcats, then the Jayhawks do not lose
                to any football team.
            c. The Wildcats beat some team, which beat the Jayhawks.

    2.Prove the validity of the following sequents in predicate logic:

            a. $x (~P(x) \/ Q(x)) |- $x (~(P(x) /\ ~Q(x)))
            b. "x (P(x) /\ Q(x)) |- "x (P(x) --> Q(x))
            c. "x (P(x) --> Q(x)) |- ("x ~Q(x)) --> ("x ~P(x))

     3.  Draw the parse trees for the following formulas:

          a. ~("x (($y P(x, y, z)) /\ ("z P(x, y, z)))).
          b. $x (P(y, z) /\ ("y (~Q(y, x) \/ P(y, z))))