Homework 3 Due, 11:55 p.m.

Comp Sci 250:
Hw3
Due: via Moodle 11:55 pm, Thu, 10/9/14
As usual, hand this in on Moodle as FirstnameLastnameHw3.pdf or FirstnameLastnameHw3.txt. Note two
changes to our keyboard representations of symbols: from now on please use “/\” for “∧” and “\/” for “∨”.
Also, instead of “Pred Logic” we will from now on use the acronym “FO” to denote “First-Order Logic with
Equality” and instead of “Prop Logic” we will from now on use the acronym “QF: to denote “Quantifier-Free
FO”. Where before in Prop Logic we used PVar = {p, q, r, s, p0 , q0 , r0 , s0 , p1 , q1 , r1 , s1 , . . .}, in QF we would just
use the 0-ary predicate symbols, PVar = {P 0 , Q0 , R0 , S 0 , P00 , Q00 , R00 , S00 , P10 , Q01 , R10 , S10 , . . .}. This is not needed
for hw3, so more about this later.
In answer to a student’s question after L13, I very much encourage you to buy or look at or consult the book How
to Prove It by Dan Velleman, who – by the way – is a logician and mathematician at Amherst College.
This homework has two problems. It is meant to be challenging, but doable, especially with the help you will get
from L13, L14, d4, and L15 and talking with us and each other on Piazza which will be ready by Monday morning,
or perhaps even Sunday night. Please ask questions about this hw early and often, but obviously following my
Piazza rules:
P1. Be positive, encouraging, supportive and inclusive. Say, “I’m not sure what is meant here,” or “Is this
perhaps a typo?”. Don’t say, “This is impossible,” nor, “I’m an idiot”, nor, “What you wrote was stupid,”
and especially not, “You’re stupid.”
P2. Never ask for – nor give away – any part of a solution to an assigned problem. It is good to ask questions
or provide replies to try to clarify any of the problems or course material.
This homework uses the following two vocabularies:
ΣRGB = (E 2 , R2 , G2 , B 2 , S 1 , F 1 , H 1 , V 1 ; s0 , t0 , e1 , r1 , g 1 , b1 ) colored graphs + 4(edge colors, function symbols)
ΣN = (≤2 ; 00 , 10 , +2 , ∗2 )
number theory
1. [50 pts.] For each of the following FO formulas, αi , i = 1, 2 do the following steps:
νi Convert αi into an equivalent formula, νi , in NNF.
ρi Next convert νi into an equivalent formula, ρi in prenex normal form, using the algorithm posted on
the syllabus page.
Check! After both of the above steps, check that the formula you built agrees with αi on the three worlds
below. (If not then you made a mistake: go back and correct your error.) For this part, just provide the
three bits: Wij (αi ), j = 1, 2, 3.
σi Skolmize ρi , using the skolemization algorithm which is, or soon will be, posted on the syllabus page,
to obtain the skolemization, σi , of ρi which is a universal formula σi that is not equivalent to αi , but is
satisfiable iff αi is satisfiable.
Ei Finally, translate αi to a clear, sensible English sentence, Ei .
1
α1
=
def
(∀x ∃!y R(x, y)) ∧ ∀xyz (R(x, y) ∧ R(x, z) → y = z)
α2
=
def
∀x (square(x) → ∀z (prime(z) ∧ z|x → z ∗ z|x))
square(x) ,→ ∃y (y ∗ y = x)
prime(x) ,→ x 6= 0 ∧ x 6= 1 ∧ ∀y (y|x → y = 1 ∨ y = x)
In the following and from now on, when we define worlds, if we don’t mention the meaning of a predicate
symbol then it is assumed to be ∅, i.e., always false. If we don’t define the meaning of a function symbol,
fi , then it is assumed to be the constant 0 function, i.e, for all a ∈ (U W )ri , fi (a) = 0.
W11 = U = {0, 1}, R = {(0, 0), (1, 0)}
W12 = U = {0, 1}, R = {(0, 1), (1, 0)}
W13 = U = {0, 1}, R = {(0, 0), (0, 1)}
W21 = N,
, i.e., the standard Natural numbers
W22 = U = {0, 1}, 0W22 = 0, 1W22 = 1, ∗ = {((0, 0), 0), ((0, 1), 0), ((1, 0), 0), ((1, 1), 1)}
W23 = U = {0, 1}, 0W23 = 1W23 = 0, ∗ = {((0, 0), 0), ((0, 1), 0), ((1, 0), 1), ((1, 1), 0)}
2. [15 pts.] Write a natural deduction proof that ` ∀x ∃y r(x) = y.
3. [35 pts.] Translate each of the following English statments Ei , to a ΣRGB formula, ϕi . Then for each such
ϕi ,
• If ϕi is FO-VALID, then give a natural deduction proof of ` ϕi .
• If ϕi is FO-UNSAT, then give a natural deduction proof of ` ¬ϕi .
• If ϕi is neither, then produce two appropriate worlds Ai , Bi such that Ai |= ϕi and Bi |= ¬ϕi .
E1
=
R is the graph of the function r meaning that R(a, b) is true exactly when r(a) = b.
E2
=
R is the graph of a function.
E3
=
R is the graph of a total function
E4
=
r is a function
E5
=
r is total, i.e., the domain of r includes the entire universe
E6
=
r is a 1:1 function
2

Download Report