CSC 244/444, Fall 2023 Sept 26/23 Homework Assignment 2 DUE: 9:39am, Tue Oct 3 PLEASE NOTE: This assignment is to be done independently by each student. Do not use LLMs or other AI aids for any part of this assignment. (Later assignments may involve use of ChatGPT or another LLM. At that point, please consult with the TAs or LS if you have no current access to an LLM.) LS and the TAs trust you to comply with the academic honesty guidelines. Note: The marks for each question part are indicated in parentheses (tot. 110). Note: Here sometimes a subscript is indicated with an underscore, e.g., |=_π“œ 1. (5) What is meant by the "aboutness" of language -- and how is this formalized in FOL semantics? (As always, be brief!) 2. (5) What role does truth play in analyzing the trustworthiness of rules of inference? 3. (5) Mention two of kinds of "know-how" (skills) that (at least some) people have that arguably would not be easy to represent in FOL, and probably not useful in that form in any case. Choose a mental skill and a physical skill, as different as you can from any mentioned in class/notes. 4. a. (2) In what respect is the concept of a first-order LANGUAGE more specific than the concept of first-order LOGIC? b. (8) Which of the following expressions (i) can be VARIABLE-FREE well- formed terms in a first-order language, which ones (ii) can be well- formed formulas WHOSE VARIABLE OCCURRENCES, IF ANY, ARE ALL BOUND BY QUANTIFIERS, and which ones (iii) cannot be either of these? Adhere to the syntactic conventions that have been stipulated in this course (ignoring the B&L text); for cases of (iii), give a quick reason: - USA - Neighbor-of(USA,Canada) - northern-neighbor-of(USA) - Β¬southern-neighbor-of(USA,Canada) - (A => B) - (A = B) ∧ (B = C) => (A = C) - (βˆ€x (P(x) => Q(x))) ∨ (βˆƒy (y = x)) - ((Happy(Snoopy) ∧ Dog(Snoopy)) => Happy(Dog(Snoopy))) 5.a. (5) In terms of set membership and set inclusion, & the interpretation function I (of a model π“œ = (π’Ÿ,I)), what are the truth conditions (relative to π“œ ) for - Aristotle is a philosopher - All philosophers are wise {refer to the initial semantics slides} Assume that our FO language includes individual constant (name) 'Aristotle' and predicate constants 'Philosopher' and 'Wise'. b. (5) Just being a little perverse -- going against the *intended* interpretation of the above constants IN ENGLISH -- make up a domain π’Ÿ of a very small set of integers, and an interpretation I for the constants, so that in this model the above sentences are true. (You'll need to show the values of I(Aristotle), I(Philosopher), and I(Wise).) c. (5) Make up another such model such that the first sentence is true and the second is false. 6. (5) Domains π’Ÿ in models π“œ = (π’Ÿ,I) can be finite or infinite. Likewise the vocabulary of constants in a FO language can be finite or infinite. One might think this means that for any domain π’Ÿ, there exists a vocabulary of names (individual constants) sufficiently large to contain a name for each element d of the domain π’Ÿ, i.e., for each d in π’Ÿ, there is a distinct individual constant C such that I(C) = d. But that's not the case -- there can be more elements of π’Ÿ than there can possibly be names even in a infinite vocabulary. Give an example of such a domain, and say why an infinite vocabulary (like C1, C2, C3, ...) won't suffice. (If you don't know anything about cardinalities, the answer can be inferred from the first page of https://en.wikipedia.org/wiki/Cardinality_of_the_continuum up to the little section on uncountability.) 7.a. (5) Consider the fomula 'Owns(Charlie,Snoopy)', and a model π“œ = (π’Ÿ,I). What set membership (∈) or set inclusion (βŠ†) conditions must I(Charlie), I(Snoopy), and I(Owns) satify (regardless of whether the formula is true or false in the model)? b. (5) State the following sentence concerning the truth conditions of the above formula relative to interpretation I entirely in English (we need not refer to the domain π’Ÿ here); i.e. avoid all metalinguistic symbols like I, |=, or angle brackts <, >: |=_I Owns(Charlie,Snoopy) iff ∈ I(Owns). Start your sentence exactly like this: 'Owns(Charlie,Snoopy)' is true under a given interpretation if and only if ... 8. Consider a FO language with individual constants 'Romeo', 'Juliet', 'Montague', and 'Capulet'; predicate constant 'Loves'; and function constant 'clan'. Let a model π“œ = (π’Ÿ,I) be the following: π’Ÿ = {r, j, m, c} I(Romeo) = r, I(Juliet) = j, I(Montague) = m, I(Capulet) = c, I(Loves) = {, , , }, I(clan) = {, , , } a. (5) Show the step-by-step evaluation of each of the following, starting with applying the term assignment function T_I - clan(Romeo) - clan(clan(Romeo)) b. (10) Show the step-by-step evaluation of the truth or falsity of each of the following formulas, in model π“œ ; use the term assignment function T_I; the evaluation chain for each formula Ο† should start with |=_π“œ Ο† iff ... (with a justification), and each additional step should assert another "iff" condition, and should *justify* that step if it is a truth condition, e.g., "by the truth conditions of predication", "by the truth conditions of '='", "by the truth conditions of 'Β¬'", etc.) - Loves(Montague,Capulet) - Β¬Loves(Montague,Capulet) {appeal to the previous result here & below} - Loves(Montague,Capulet) ∨ clan(Juliet) = clan(Capulet) 9. Consider the following model π“œ = (π’Ÿ,I)), where π’Ÿ = {a,b}, I(Alice) = a, I(Bob) = b, I(P) = {, }, I(f) = {, }, assuming that in our FO language 'Alice' and 'Bob' are individual constants, 'P' is a 2-place predicate constants, and 'f' is a (1-place) function constant. In addition, assume that we have variables 'x' and 'y', and a variable assignment function U, where U(x) = U(y) = a. a. (5) Formally prove the following claim (use T_{IU} and justify your steps): |=_π“œ P(Alice,f(x)) [U] b. (5) formally prove the following claim (use T_{IU} and justify your steps): |=_π“œ Β¬P(f(x),Bob) [U_x:b] (to start, apply the satif. cond. for 'Β¬') 10. (10) For the model in (9), formally prove the following truth-in-π“œ claim |=_π“œ (βˆƒx (βˆ€y P(x,y))) (to start, use the def'n of truth in terms of v.a.'s) Justify your steps in terms of satisfaction conditions. 11.a.(5) Classify the following formulas as valid, unsatifiable, or contingent (without proof). NB: the domain π’Ÿ of a model is *always* a nonempty set; assume that the constants occurring here are in our chosen FO language; we may use some "dot notation" for quantifier scopes here, for brevity: - (βˆ€x P(x)) => P(A) - βˆƒx.βˆ€y Q(x,y) - (P(A)∧¬P(A)) => Q(A,B) - βˆ€x.βˆƒy x=y - βˆ€x Exist(x) b. (5) Pick a formula from above that you say is contingent, and prove it by exhibiting a model in which it is true and another in which it is false (just show the models -- no detailed arguments for truth/falsity required) 12.a.(5) Formally prove the following entailment claim (no need for term assignments or variable assignments here, just simple truth conditions): {P(A), Q(A,B)} |= (P(A)=>Q(A,B)) ∨ A=B b. (5) Formally prove the following entailment claim; use the "full" definition of truth in a model, as it applies to formulas containing variables: βˆ€x.P(x) |= βˆ€y.P(f(y)) Hint: In considering an arbitrary model of the antecedent, establish a fact about I(P)