Predicate Logic and Interpretations

Diagnostic lens 1: Assumptions and meaning

Diagnostic lens 2: What an exact test establishes

Diagnostic lens 3: Constructing a counterexample

The contrast between ∀x∃y and ∃y∀x represents different dependency structures; a finite table can make one true and the other false. A responsible solution states a semantic domain, separates definitions from empirical observations, and identifies the particular output that would refute the assertion. The student should carry this distinction forward to the worked cases rather than substitute confidence for a visible check.

A free variable requires an assignment before its formula receives a determinate truth value in a given interpretation. Confusing free and bound occurrences is a common substitution error. A responsible solution states a semantic domain, separates definitions from empirical observations, and identifies the particular output that would refute the assertion. The student should carry this distinction forward to the worked cases rather than substitute confidence for a visible check.

In a restricted institutional domain, “all enrolled people” may be a useful universal claim, but it does not license conclusions about non-enrolled people without a domain-extension argument. A responsible solution states a semantic domain, separates definitions from empirical observations, and identifies the particular output that would refute the assertion. The student should carry this distinction forward to the worked cases rather than substitute confidence for a visible check.

Begin with the following problem: Compare “every student follows some researcher” with “one researcher is followed by every student.” A two-student, two-researcher table can separate these readings. Write the problem in ordinary language first. Identify which words introduce conjunctions, alternatives, negations, quantifiers, or claims of necessity. Then separate object-level statements from the evaluator's assumptions. State a proposed formalization and one plausible alternative. For each, ask what observation or interpretation would distinguish them. Finally, explain which parts can be checked by logic alone and which require additional factual or policy evidence. A correct formal answer must be precise enough for another student to reproduce without guessing the intended meanings.

1. Central idea and precise vocabulary

An n-place predicate denotes a property or relation over a specified domain. Variables and constants denote individuals; sentences must be evaluated in a structure that assigns extensions to symbols. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: Student(x), Advises(x,y).

Worked example: Let the domain consist of {Ari, Bo, Chen}. Student(Ari) may be true while Student(Bo) is false; the same predicate label is not itself universally true. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: Do not interpret quantifiers before fixing the domain and symbol meanings. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: What changes if alumni are added to the domain but the predicate extension stays fixed? The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Model mentorship matching as a finite relation table. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Model mentorship matching as a finite relation table.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object Student(x), Advises(x,y). Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “Do not interpret quantifiers before fixing the domain and symbol meanings.” and the question “What changes if alumni are added to the domain but the predicate extension stays fixed?”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

1. Central idea and precise vocabulary

∀xP(x) says every domain element satisfies P; ∃xP(x) says at least one does. Their negations interchange quantifier and polarity. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: ¬∀xP(x) ≡ ∃x¬P(x).

Worked example: If two of three enrolled students submit work, “every student submitted” is false and “some student did not submit” is true. Identify the non-submitter as a witness. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: A particular observed example proves existence but never a universal claim. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: What if the study domain is empty? State the usual classical truth conventions. The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Compute group coverage by quantifying over all registered students. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Compute group coverage by quantifying over all registered students.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object ¬∀xP(x) ≡ ∃x¬P(x). Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “A particular observed example proves existence but never a universal claim.” and the question “What if the study domain is empty? State the usual classical truth conventions.”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

1. Central idea and precise vocabulary

Quantifier order often changes meaning when variables are connected by a relation. A scope diagram prevents accidental swapping of dependencies. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: ∀x∃y R(x,y) versus ∃y∀x R(x,y).

Worked example: Each student may have a different supervisor; this supports ∀x∃y Follows(x,y) but not necessarily one common supervisor. Construct a two-by-two relation matrix. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: Do not exchange nested quantifiers just because both phrases include “every” and “some.” Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: Find the smallest countermodel separating the two quantified statements. The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Translate “each proposal has a reviewer” in a database model. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Translate “each proposal has a reviewer” in a database model.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object ∀x∃y R(x,y) versus ∃y∀x R(x,y). Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “Do not exchange nested quantifiers just because both phrases include “every” and “some.”” and the question “Find the smallest countermodel separating the two quantified statements.”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

1. Central idea and precise vocabulary

An occurrence is free if it is not within the scope of a matching quantifier. Capture-avoiding substitution may require variable renaming. Identity expresses sameness of denotation in a given structure. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: ∀x R(x,y) has y free.

Worked example: Replacing y by x inside ∀x R(x,y) without first renaming the bound x changes meaning by variable capture. Alpha-rename to ∀z R(z,y), then substitute. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: Do not infer identity from similarity of recorded attributes alone. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: How can two distinct database records share a label without denoting the same individual? The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Inspect a symbolic expression editor for accidental capture. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Inspect a symbolic expression editor for accidental capture.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object ∀x R(x,y) has y free. Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “Do not infer identity from similarity of recorded attributes alone.” and the question “How can two distinct database records share a label without denoting the same individual?”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

1. Central idea and precise vocabulary

To refute a first-order entailment, construct one interpretation in which every premise is true and the conclusion false. A finite model is often enough to expose an invalid generalization. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: ∀x(P(x)→Q(x)), ∃xP(x) ⊨ ∃xQ(x).

Worked example: Take domain {a,b}, P={a}, Q={a,b}; premise and conclusion are true. The proposed counterexample fails, confirming that this model supports rather than refutes the entailment. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: A favorable model is not a proof of validity across all models. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: Can you find a countermodel to ∃x P(x) ⊨ ∀x P(x)? The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Build a relationship table for an access-control claim. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Build a relationship table for an access-control claim.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object ∀x(P(x)→Q(x)), ∃xP(x) ⊨ ∃xQ(x). Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “A favorable model is not a proof of validity across all models.” and the question “Can you find a countermodel to ∃x P(x) ⊨ ∀x P(x)?”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

Challenge. Compare “every student follows some researcher” with “one researcher is followed by every student.” A two-student, two-researcher table can separate these readings. Develop a short technical note with an exact formal statement, one chosen method of evaluation, and a counterexample search. The note should make at least one original decision-table row or proof trace available for checking. Explain why the result would be insufficient to justify a real-world institutional or engineering decision without premise validation. Attach a paragraph comparing the method used in this unit with a method from an earlier unit, or with a possible method to be learned later.

Scoring rubric. Allocate 20 points to definitions and domain, 25 to formalization, 25 to correct derivation or model checking, 15 to counterexamples and limitations, and 15 to clarity and reproducibility. A solution that asserts validity without a general argument or a complete finite enumeration receives at most partial credit. For a claim of invalidity, one genuine countermodel with all premise evaluations shown is decisive. For an application claim, assess the formal result and the evidence for inputs separately.

Instructor follow-up. Ask each student to change one premise and predict whether the final judgment flips. Comparison of predictions with actual outputs identifies memorization without semantic understanding. Archive the original translation, the revised translation, and the reason for revision; these form a transparent record of how the claim was sharpened.