CSC165H1F Tutorial # 2 | Sample Solutions Fall 2011
As in Tutorial 1, suppose that you are given seven di▯erent programs A;C;E;G;I;K;M, each meant to carry out
the same task, where programs C;G;K;M are written in Python and programs A;E;I are written in Java. Let
P represent the set of all programs (our \universe" or \domain"), J represent the set of all Java programs, and T
represent the set of all correct programs.
Recall that in class, we saw how set notation like \x 2 T" can be expressed in predicate notation as \T(x)", and
how this can be used to write di▯erent sentences symbolically. Make sure that you understand this correspondence
well before answering the following questions.
1. For each English sentence below, give the \standard" symbolic representation of that sentence, as discussed
in class (where all quanti▯ers are over the universe P and predicate notation is used everywhere else), then
give a second, di▯erent symbolic representation of the same sentence (where you are allowed to quantify over
di▯erent domains or to change the order of predicates, when appropriate, but without introducing any new
predicate or set).
Note: We show some variants for some of the answers. Keep in mind that these do not constitute
all possible correct answers.
(a) Some incorrect program is written in Java.
Standard: 9x 2 P;:T(x) ^ J(x)
Non-standard: 9x 2 T;J(x) or 9x 2 J;:T(x)
(b) No Java program is correct.
Standard: :9x 2 P;J(x) ^ T(x) or 8x 2 P;J(x) ) :T(x)
Non-standard: 8x 2 J;:T(x) or 8x 2 T;:J(x)
(c) Only programs written in Python are incorrect.
Standard: 8x 2 P;J(x) ) T(x) or 8x 2 P;:T(x) ) :J(x)
Non-standard: 8x 2 T;:J(x) or 8x 2 J;T(x)
(d) The program is correct and is written in Python.
Standard: T(x) ^ :J(x)
Non-standard: there was no signi▯cantly di▯erent way to write this one, because it contains
(e) If some Java program is correct, then all Java programs are correct.
▯ ▯ ▯ ▯