80-210 Final Exam
Introduction to Logic



Instruction: There are 80 True or False questions. You will get 1
point for a correct answer, get no point if you do not answer the
question, and have half a point deducted from your score for an
incorrect answer.


1-4) True or false:

		1) From R & R one can derive R OR R.
		2) From R OR R one can derive R & R.
		3) P -> Q and ~ Q -> ~ P are consistent statements.
		4) P -> Q and ~ Q -> ~ P are independent statements.


4-8) Suppose we define a new logical operator @ as follows:
        (P @ Q) <-> ~(P OR Q)

        True or false:

      4) ~ P <-> P @ P				
      5) P V Q <-> (P @ P) @ (Q @ Q)	
      6) P -> Q <-> P @ (Q @ Q)		
      7) ~(P OR Q) <-> (P @ (P OR Q))	
      8) P & Q <-> (P @ Q) @ (P @ Q)	


9-14) Assume that P is false, Q is true, R is false and S is true.  
Then give the correct truth value for the composite sentence below:

		 9) P & Q V ~ R
		10) P V Q & R V S
		11) P <-> Q <-> S
		12) ~ ~ ~ R
		13) P -> Q -> R
		14) P V Q <-> R V S


15-22) Suppose you are given the following four premises
		P (1) P <-> Q
		P (2) R -> Q
		P (3) R OR S
		P (4) ~ Q

For each of the following sentences, tell whether it is true or false
that the sentence is derivable from these premises:

		15) ~ R -> ~ P
		16) ~ S -> R
		17) P OR R
		18) S -> P
		19) P -> R
		20) P <-> R
		21) ~ P OR S
		22) ~ R & ~ S







23-27) Counterexample.  Consider the following argument and give truth
values to P, Q, R, S and T which show the argument is not valid:
			Derive: T
		P (1) Q <-> P
		P (1) R -> Q
		P (3) ~ S OR R
		P (4) ~(S <-> T)

		23) Truth value for P
		24) Truth value for Q
		25) Truth value for R
		26) Truth value for S
		27) Truth value for T


42-49)  True or false:  Is the expression a tautology?

		42) P V ~(P & ~ P) V ~ P
		43) P V P & ~ P V ~ P
		44) P & Q <-> ~ P -> Q -> ~ Q
		45) (A X)(X + 1 > X)
		46) P -> Q <-> Q
		47) ~ R & P & Q V R V ~ P V ~ Q
		48) P & Q -> R <-> P -> Q -> R
		49) (P V ~ P) & (Q V ~ Q)


50-59)  True or false in integer arithmetic:

		50) (A X Y) (X > Y -> (E Z) (X -> Z & Z > Y))
		51) ~ (E X)(A Y)(~ X = 0 -> Y > -Y)
		52) ~ (A X)(X > -X V ~ 0 = 1)
		53) (A X)(E Y)(X > Y -> X > -X)
		54) (E X)(A Y)(E Z)(Z < Y & X = Z + Y)
		55) (A X Y Z)(E Z1)(X > Y & Y > Z -> Z1 > Y & X + Z > Z1)
		56) (A X Y)(X + Y > -(Y + X) -> X > 0 V 0 > Y)
		57) ~ (E X)(A Y)(E Z)(X * Y = Z)
		58) ~ (A X Y)(E Z)(Z > 0 & (X + Z = Y V Y + Z = X))
		59) ~ (A X Y Z)(X + Y > Z -> X * Y > Z)


60-64) For each argument, true or false that the argument is valid?

      60) All economists are moneymakers.	
          Some moneymakers are illiterate.
          Therefore, some economists are illiterate.

      61) No cloudwalkers are vegetarians.	
          All cloudwalkers are fools.
          Therefore, no vegetarians are fools.

      62) Some music lovers are shortsighted.	
          No museumgoers are shortsighted.
          Therefore, some music lovers are not museumgoers.

      63) No children are apple blossoms.	
          Some children are angels.
          Therefore, some angels are not apple blossoms.
     
      64) No fish are mammals.	
          All dogs are mammals.
          Therefore, no dogs are not fish.

      65) If the team wins, someone in the backfield is a good tailback.
	  Adams is a good tailback.
	  Therefore, if Adams is in the backfield, the team wins.	


74-76) For each of the following, tell whether it is true or false that
the statements are consistent: 

		74) (E X)(P(X) & ~ Q(X))
		    (A X)(R(X) -> Q(X))
		    ~(A X)(P(X) -> ~ R(X))

		75) (A X)~(M(X) & ~ W(X))
		    (A X)(M(X) -> W(X)) -> (E X)(D(X) & S(X))
		    (A X)(D(X) -> ~ S(X))

		76) ~(E X)(~ P(X) & Q(X))
		    (A X)(E Y)(P(Y) & R(X Y) -> ~ Q(Y))


77-80) The following is an invalid argument:

		(P) (E X)(P(X) & Q(X))
		(P) (A X)(P(X) & Q(X) -> R(X))
		(P) (A X)(~ Q(X) -> R(X))
		(P) (E X)(R(X) & P(X))

		(C) (E X)~(R(X) -> P(X) V ~ Q(X))

State for each of the following integer arithmetic interpretations whether
it is true or false that it can be used to show the argument invalid:

		77) P(X):  X = X	Q(X):  X = 1	R(X): X = X
		78) P(X):  X = 1	Q(X):  X = 0 	R(X): X = X
		79) P(X):  X > 0	Q(X):  X = X 	R(X): X = 1
		80) P(X):  X = 1	Q(X):  X = X 	R(X): X = 1
	



(A) 10 points. Prove the following using only elimination/introduction
rules and indirect rules (no transformation rules):

P:  ~ (e  & [{~a v ~b} v {c & ~d}]) v p

Goal: (~e  v ( ~[(~a & ~b) v (~ (c -> d)))) -> P 



(B) 5 points. Prove the following:

(Ex)(Fx v Gx) <-> ((Ax)Fx v (Ax)Gx))



(C) 10 points. Prove the following:

P1.(Ax)((Ax v Bx) -> (Gx & ~ Hx))
P2 (Ax)(Gx -> Hx)
P3 (Ax)((Dx & Ex) -> Bx)
P4 ~ (Ex) (Px & ~ Ex)
Goal: ~(E x)(Px & (Ax v Dx))







(D) 15 points. Translate into predicate logic the following:

None of Ockham's followers like any realist. Every Ockham's followers
likes at least one of Hobbes' followers. Moreover, Ockham does have
some followers. Therefore, some of Hobbes's followers are not realist.

List the dictionary you're using. Prove the statement.



(E) Extra Credit: 25 points. Translate into predicate logic and prove
the following:

For every x, y, if x precedes y, then it is not the case that y
precedes x. For every x, and z, if x precedes y and y precedes z, then
x precedes z. For every x and y, if x precedes y, then x is not
equal to y. For every x,y ,z if y is between x and z, then either x
precedes y and y precedes z or z precedes y and y precedes x. For
every x,z, if x is not equal to z, then there is y such that y is
between x and z. Therefore, for every x,z, if x precedes z, then there
is a y such that x precedes y and y preceds z.