Answer:
A rule of inference must be valid, i.e. if the rule tells you that from phi
you can infer psi, then it should be that indeed phi |= psi (semantically).
Propositional resolution as stated is valid, but not if you drop more than
one pair.
E.g. from the premises:
p&q => r
s => p|q
we cannot drop both p and q and infer s=>r
(if we know s, we know p or q, but not p&q, so we cannot infer r)
(an interpretation which shows this: assigns true to s,p and false to q,r)
Sorry to everyone for bobbling the "unless" example in class. As we discovered together, the version on the slide I showed was incorrect. I have since fixed this and placed the correct translation in the slides on the website.
The "unless" construct in English is complex. There is a basic (weak) meaning that pretty much everyone agrees to, and there is an extended (stronger) version that is occasionally but not always intended.
The statement that "p is true unless q is true" can be rephrased as "p is true if q is not true", i.e. -q => p. In the weak interpretation, that is the entire meaning; the statement says nothing at all about the case when q is true; p may be true or p may be false in that case.
In the strong interpretation, p is furthermore required to be false when q is true, i.e. q => -p. The strong interpretation is equivalent to the sentence "p unless q" as "p is true unless q is true in which case p is false". Note that, in this case, the interpretation is (p <=> -q) or, equivalently, (p xor q), as someone mentioned in class.
Example of weak interpretation: A raven can fly unless it is sick, in which case it may or may not be able to fly well depending on how hardy it is.
Example of strong interpretation: A raven is black unless it is an albino. Equivalent sentence: A raven is black unless it is an albino in which case it is white (i.e. no black).
You will not pass this course unless you understand these examples.
Answer: You got it exactly right.
Answer: No. Both the existential and the universal quantifiers are relevant for this definition.
Another way to see the definition of substitutability is: a term tau can be safely substituted for a variable occurrence v in phi iff every variable in tau remains unbound after the substitution.
Q2:Consider the sentence psi:
p(f(g(y),a)) & Ax.q(y,x) & Ey.r(y) (with a object constant, and x,y, variables)
What are the free occurrences of y in psi and what are the bound occurrences (an occurrence of a variable is bound if it
is within the scope of a quantifier that binds it; and it is free otherwise).
Answer: The first two occurrences are free, the third is bound by Ey.
Notice: The term f(a,g(x))
is substitutable only in the first free occurrence of y. It is not substitutable in the second occurrence of y, because then
x in the term would become bound (i.e. x is bound in Ax.q(f(a,g(x)),x)).
And the third occurrence of y in psi is a bound occurrence and so by definition is never
substituted.
Notice: We can find another formula phi that is logically equivalent to psi (i.e. phi <=> psi is a logically
valid sentence) but in which the term can be substituted, by renaming the bound occurence of x to z:
phi = p(f(g(y),a)) & Az.q(y,z) & Ey.r(y). Notice that free occurrences of variables remain the same; it is only
bound variables that we rename (this is called "renaming of bound variables" or "alpha-renaming").
Now we can substitute the term for y in the new phi and get: p(f(g(f(a,g(x))),a)) & Az.q(f(a,g(x)),z) & Ey.r(y).
Notice that x in the term remains free after the substitution (whereas if we had used psi, x in the term would become bound).
Notice: In Ax.(p(x)&Ex.q(x)), the first occurrence of x is bound by Ax, while the second is bound by Ex. It's like local shadowing in programming languages. (See also comment in Lecture errata on slide 13 of lecture 5).
Object constant: 0 Relations: W(x): x is a whole number, i.e. 1, 2, 3, ... N(x): x is a natural number, i.e. 0, 1, 2, 3, ... Q(x): x is a rational number R(x): x is a real number x > y: x is greater than y
(a) "Every natural number greater than 0 is a whole number."
Ax.(N(x) & x>0 => W(x))
(b) "Some real numbers are rational numbers, but some aren't."
Ex.(R(x) & Q(x)) & Ex.(R(x) & ~Q(x))
(c) "For every pair of natural numbers there is a rational number between them."
Ax.Ay.( N(x) & N(y) => Ez.(Q(z) & ((y > z & z > x) | (x > z & z > y) )))
Translating the english verbatim gives you what is above. If you translated the mathematical fact that for every pair of distinct natural numbers there is a rational number between them, you would conjoin (x>y | y>x) to the left hand side of the implication.
Example: Is Ax.Ay.(p(x)=>p(y)) valid?
Answer: No.
Intuitive explanation: It's not true in general that for any two elements, if p is true of one then p
is true of the other.
Systematic explanation: Suppose that for some i and v, t_iv(Ax.Ay.(p(x)=>p(y)))=false.
That means (by definition of the meaning of Ax) that for some element alpha in the universe of discourse,
t_iv1(Ay.(p(x)=>p(y)))=false, where v1 is like v except v(x)=alpha.
So that means, for some element beta in the universe of discourse, t_iv2(p(x)=>p(y))=false,
where v2(x)=alpha and v2(y)=beta.
So that means t_iv2(p(x))=true and t_iv2(p(y))=false.
So that means t_iv2(x) is in i(p) and t_iv2(y) is not in i(p).
So that means alpha is in i(p) and beta is not in i(p).
So this gives as instructions on how to build a countermodel: take |i|={*,%} and i(p)={*}.
If you take v2(x)=* and v2(y)=% then t_iv2(p(x)=>p(y))=false. So that means (going backwards)
that t_iv2(Ax.Ay.(p(x)=>p(y)))=false.
If instead you tried to start with (Ax.p(x))=>(Ay.p(y)) and assumed it's false under some interpretation and assignment, you'd reach a contradiction, showing the sentence is true under all interpretations and assignments, i.e. valid.
Let's say that if S is a set of sentences, mod(S) is the set of models of S, i.e. the set of interpretations that satisfy S.
(a) Then notice that Gamma |= psi if and only if mod(Gamma) subset-or-eq mod({psi}).
(b) Also notice: if we add sentences to Gamma, then Gamma needs to satisfy more conditions, therefore its set of models
shrinks. I.e., if Gamma subset-or-eq Gamma' then mod(Gamma) superset-or-eq mod(Gamma').
Conversely, if we remove sentences from Gamma, then it needs to satisfy fewer conditions, so it has more models.
Consequently, if Gamma is empty, it is satisfied by all possible models! (and not: if Gamma is empty then mod(Gamma) is
empty).
(c) A sentence phi is logically valid if and only if it is satisfied by every interpretation and assignment, which is if and only if {} |= phi (phi is logically entailed from the empty set of sentences), which is if and only if mod({phi}) is the set of all interpretations.
(d) A sentence phi has a formal proof using no premises if and only if it is logically valid. How do we know? By the soundness and completeness theorem (slide 26 lecture 8). The theorem says that phi is provable from Gamma iff Gamma |= phi. Therefore, phi is provable from no premises if and only if {} |= phi , which is if and only if phi is a valid sentence.