Spring 2008

Be neat and organized. Clearly indicate your answers. 100 points possible.

1. (10 pts.) Write the truth table for this statement form.

p® ~ q

2. (10 pts.) Use a truth table to determine whether the argument form is valid or invalid. Clearly label the ``critical rows.''

                       p®( ~ qÙr)

                       pÚq

\therefore r

3. (10 pts.) For the given truth table, construct (a) a Boolean expression having the given table as its truth table and (b) a circuit having the given table as its input/output table. (The inputs are P, Q, and R; the output is S. The symbolic representations of the NOT-, AND-, and OR-gates are shown on the board.)

P        Q        R        S        1        1        1        0        1        1        0        0        1        0        1        0        1        0        0        1        0        1        1        0        0        1        0        1        0        0        1        0        0        0        0        0

4. (10 pts.) Convert 525 from decimal notation to hexadecimal, base four, and binary notation.

5. (10 pts.) Write the negation for each of the following statements.

(Move the negation ``all the way inward,'' or ``all the way right,'' just as we always did in class.)

(a) For all x Î D, if x² Î S or x³ Î T, then x⁴ Î U.

(b) "p Î R⁺, $q Î R⁺ such that "n Î Z⁺, pq > n.

(c) "x(Square(x) ®(Small(x)ÚLeftOf(c,x)))

6. (10 pts.) For the Tarski World shown on a supplemental page, determine whenter each statement is true or false. LeftOf(x,y) means x is closer to the left side than y.

(a) "x"y((Square(x)ÙCircle(y))® LeftOf(x,y))

(b) "x$y(Triangle(y)ÙSameCol(x,y))

(c) $x"y(Square(y)®LeftOf(x,y))

7. (10 pts.) Decide whether each argument is valid or invalid.

(a)All sane people can do logic.

My son can not do logic.

  \therefore My son is not sane.

(b)All incompetent people are always blundering.

Jenkins is always blundering.

  \therefore Jenkins is incompetent.

(c) All ripe fruit is wholesome.

This apple is not ripe.

  \therefore This apple is not wholesome.

8. (10 pts.) Prove the following statement directly from the definitions, using the definitions of even and of divisible.

For all integers n, if n is even, then n²+28 is divisible by 4.

9. (10 pts.) Prove the following statement.

For all integers n, n²+2n is of the form 8k, or 8k+3, or 8k+7 for some integer k.

(Hint: Divide n by 4.)

10. (10 pts.) Find the final values of j, s, and t after the following algorithm is executed. A supplemental page has the corresponding flowchart.

j:=-2

s:=5

t: = 10

while j ¹ 3

if (j < 0 or j=2)

then t:=t+j

else s:=s-1

j:=j+1

end while