home—info—lectures—exams—archive
exam01
exam 1
Instructions:
Closed book, closed most-notes,
but you can have one single-sided 8.5″x11″ page of notes/pictures
in your own handwriting (no photocopying etc).
# | pts possible | pts |
1 | 8 | |
2 | 6 | |
3 | 8 | |
4 | 12 | |
5 | 6 | |
6 | 4 | |
7 | 8 | |
8 | 4 | |
9 | 4 | |
10 | 6 | |
Σ | 66 | |
- (8pts)
Let n be the proposition
“a null pointer exception occurs”,
let v be the proposition
“the array index is valid”, and
let a be the proposition
“the array has been initialized”.
Give a propositional formula expressing:
-
If a null pointer exception occurs, then the array has not been initialized.
-
The array index is valid, but a null pointer exception occurs.
-
Initializing the array and having a valid array index is
sufficient to avoid a null pointer error.
-
(Challenge:)
Initializing the array and having a valid array index is
necessary to avoid a null pointer error.
- (6pts)
Use truth tables to show that the following is a tautology:
[¬q∧(p∨q)] → p.
- (8pts)
For each of the following, indicate whether or not they are true,
over the domain of the integers:
-
true or false?: ∃x. ((30 < x²) ∧ (x² < 40))
-
true or false?: ∃x. ((30 < x²) ∨ (x² < 40))
-
true or false?: ∀x. ((30 < x²) ∧ (x² < 40))
-
true or false?: ∀x. ((30 < x²) ∨ (x² < 40))
- (12pts)
Let Q(x,y)
be the statement
“student x has been a contestant on quiz show y”.
Express each of the following sentences as a first-order logic formula,
where the domain for x is all RU students,
and y is all TV quiz shows.
-
“Amy McCoy IV has been a contestant on Family Feud.”
(You may abbreviate Family Feud as “FF”.)
-
“There is an RU student who has been a contestant on Jeopardy
and on Family Feud”
-
“There is a RU student who has been a contestant on a TV quiz show.”
-
“No RU student has ever been a contestant on a TV quiz show.”
-
“Every TV quiz show has had an RU student as a contestant.”
-
“At least two RU students have been contestants on Jeopardy.”
- (6pts)
The symmetric difference of two sets A and B,
denoted A ⊕ B,
is the set of elements which are in A or in B, but not in both.
Fill in the blank below
with
a logic formula expressing this, where that formula does not
use the binary exclusive-or operator (also denoted ⊕):
A⊕B = { x | }
- (4pts)
Draw a Venn diagram for each of the following:
-
A-(B∩C).
-
(A-B)∪(A-C).
- (8pts)
Prove that, for sets A,B,C,
(A ∩ B ∩ C) ⊆ A ∪ B.
Be sure to use the definition of ⊆, ∩, and ∪ appropriately,
and any justifications you need from Rosen's Table
1 (attached).
- (4pts)
In the following, φ represents the empty set, {},
and P(A) represents the power set of A (where A is any set).
- true or false?: φ ∈ P({φ,{φ}})
- true or false?: φ ⊆ P({φ,{φ}})
- true or false?: {φ} ∈ P({φ,{φ}})
- true or false?: {φ} ⊆ P({φ,{φ}})
- (4pts)
Consider the Java method
parseInt
which takes in any String and
returns what int the string represents (in base 10).
(If the String doesn't represent a number,
it does not return a value — it throws an exception.)
For example,
parseInt("+18")=18,
and
parseInt("001")=1.
-
Why is parseInt not a function
from Strings to ints?
-
Concisely describe a domain and codomain for which it is a function.
- (6pts)
Use propositional equivalences
to show that
(a→b) ∨ a ≡ true.
(that is, (a→b) ∨ a is a tautology).
Your answer will be a series of formulas, joined by ≡,
with each line justified
by one of the reasons from
the attached Table 6 from Rosen.
You may combine any associativity or commutativity steps
with other steps; just cite that additional justification.
home—info—lectures—exams—archive