Logic6 - Predicate Logic

Predicate Logic

Introduction

• Predicate logic is an extension of propositional logic that allows for richer structures and quantifications.
• Example: Instead of just having propositional variables, we can talk about properties of elements (unary predicates) or relations between objects (binary predicates).
• Concrete objects can be represented by constants, and variables allow for quantification over unspecified objects.
• Predicate logic combines atomic formulas with connectives (conjunction, disjunction, negation) and quantifiers (universal and existential).
• Universal quantification: A formula holds for all elements in a set.
• Existential quantification: There exists an element in the set for which the formula holds.

Syntax of Predicate Logic

• Predicate logic allows us to express statements about individuals and their properties, which is not possible in propositional logic.
• Example: Consider the statement "All human beings are mortal. Socrates is a human being. Therefore, Socrates is mortal."
• In propositional logic, we would need three propositional variables (p, q, r) for each statement, losing the structure of the argument.
• Predicate logic allows us to express this with predicates like $H(x)$ (x is a human being) and $M(x)$ (x is mortal), and a constant $s$ for Socrates.
• The argument can then be expressed as: $∀x (H(x) → M(x)) ∧ H(s) ⊢ M(s)$.
  • This semantic entailment is valid in predicate logic.

Atomic Formulas

• Atomic formulas are the basic building blocks of predicate logic, constructed from predicates, constants, and variables.
• Examples:
  • $C(j)$ : Jane is clever (unary predicate C, constant j).
  • $K(a, b)$ : Anton knows Betty (binary predicate K, constants a and b).
  • $Line(x, y, z)$ : Points x, y, and z are on the same line (ternary predicate Line).

Connectives and Quantifiers

• Atomic formulas are combined using connectives (negation, conjunction, disjunction, implication, bi-implication).
• Examples:
  • $C(j) ∧ K(a, b)$ : Jane is clever and Anton knows Betty.
  • $¬K(a, a)$ : Anton does not know himself.
  • $K(a, b) ∧ ¬K(b, a)$ : Anton knows Betty, but Betty does not know Anton.
• Quantifiers are added to express statements about all or some elements.
  • $∃x C(x)$ : Somebody is clever (existential quantifier).
  • $∀x C(x)$ : Everybody is clever (universal quantifier).
• Semantic Equivalence Example: $¬∀x C(x) ≡ ∃x ¬C(x)$. Not everybody is clever is the same as saying someone is not clever.
• Another Equivalence Example: $∀x ¬K(x, x) ≡ ¬∃x K(x, x)$. Nobody knows himself is the same as saying there does not exist someone that knows himself.

Summary of Syntax

• Predicate logic extends propositional logic by:
  • Enriching propositional variables into structured elements.
  • Enabling quantification over variables.

Priority Levels and Scope

• Quantifiers ($\forall$ and $\exists$) bind as strongly as negation.
• The scope of a quantifier is as small as possible.
• Example: $\forall x C(x) ∧ K(a, g)$. The brackets around $C(x)$ can be dropped.
• If the scope should extend over the entire formula, brackets are needed:
  • $\forall x (C(x) ∧ K(a, x))$.
• Redundant Brackets: Negation and universal quantification:
  • $¬∀x C(x)$. The brackets are redundant.

Terminology: Bound and Free Variables

• A variable is bound if it is within the scope of a quantifier.
• Otherwise, it is free.
• Example: $∃x (C(x) ∧ D(x))$. Both occurrences of $x$ are bound if brackets are in place. If there are no brackets, only x in C(x) is bound.
• Another Example: $(∃x C(x)) ∧ (∃x D(x))$. The two quantifiers bind different occurrences of $x$.

Practice Question

• Formula: $\forall x ∃x (C(x) ∧ D(x))$.
• Is the x inside C and D free or bound? If bound, by which quantifier?
• The $x$ inside $C$ is bound by the existential quantifier.
• The $x$ inside $D$ is bound by the universal quantifier.

Historical Note

• Predicate logic was developed by Gottlob Frege in the late 19th century.
• Frege's notation was based on flow diagrams.
• Bertrand Russell discovered a paradox related to Frege's work which led to the framework being rebuilt by distinguishing sets and classes.
  • Russell's Paradox: Consider the set R containing elements x that are not in x. Is R in itself or not?

Semantics of Predicate Logic

• Meaning is given to predicate logic formulas through models.

Building Models

• A model consists of a non-empty set of elements and an interpretation of constants and predicates.
• Example: Binary relation $L$ (love), constants $r$ (Robert) and $j$ (Jane).
• $L(r, j)$ expresses that Robert loves Jane.
• A model $M_1$ can be built where $L(r, j)$ holds (blue arrow from Robert to Jane).
• Another model $M_2$ can be built where $L(r, j)$ does not hold (blue arrow from Jane to Robert).
• The meaning of a formula varies depending on the model.

Defining Models

• In addition to the set of elements A, we need an interpretation of constants and predicates over A.
• For all $x, \phi$ holds in model $M$ if $\phi$ holds for every interpretation of x in A.
• For exists $x, \phi$ holds in model $M$ if $\phi$ holds for at least one interpretation of x in A.

Interpreting Formulas

• Example: Interpret $C(j)$, $L(r, j)$, and $¬∀x C(x)$
  • Model consists of all human beings on this planet.
  • Constant $j$ interpreted as Jane.
  • constant $r$ interpreted as Robert.
  • $C(x)$ is the cleverness relation - all human beings are clever.
  • $L(x, y)$ is a relation that holds if x loves y.

Smaller Models

• Model $M_1$: Robot loves Jane.
  • Jane is clever.
  • $(M \vDash C(j))$. Jane is clever.
  • $(M \vDash L(r, j))$. Robot loves Jane.
• Model $M_2$: Everybody is clever.
  • All elements are inside the pink circle, indicating they are clever.
  • $(M \nvDash L(r, j))$. Robot does not love Jane.
  • $(M \vDash (C(j) \land L(j, r)))$. Jane is clever and Jane loves robot.
• Harder question: $\exists x \exists y (L(x, y) \land L(y, x))$. There is a couple that loves each other.
  • This holds in the model as there is a pair loving each other.

Interpreting More Formulas

• Given model $M$ with elements $p<em>1$, $p</em>2$, and $p<em>3$. Constants $a$ and $b$ are interpreted as $p</em>1$ and $p_3$, respectively.
• Blue arrows represent the knowing relation $K$, and pink circles represent the clever relation $C$.
• Is $(M \vDash K(a, b))$? Yes, because there is a blue arrow from $p<em>1$ to $p</em>3$.
• Is $(M \vDash K(b, a))$? No, because there is no blue arrow from $p<em>3$ to $p</em>1$. So, $(M \vDash \neg K(b, a))$.
• Does b know himself? Yes, because the blue arrow exists from p3 to p3.
• Is a clever? Yes.
• Is b clever? No. $(M \vDash \neg C(b))$.

Quantifiers - Formulas

• $(M \nvDash \forall x C(x))$. Not everyone is clever. True because p3 is not clever, so this model holds.
• $(M \vDash \exists x C(x))$. There exists an x such that c x holds, which is true.
• $(M \vDash \exists x \neg C(x))$. Yes, because p3
• $(M \vDash \forall x (C(x) \implies \exists y K(x, y)))$. If you're clever, then you know somebody - False, because p2 doesn't know anybody.
• $(M \vDash \forall x (C(x) \lor K(x, x)))$. Everyone is clever or knows himself - True.
• $(M \nvDash \exists x \forall y K(x, y))$. There is someone who knows everybody - False, because nobody knows everybody.
• $(M \vDash \forall x (\exists y K(x, y) \implies \exists y (K(x, y) \land C(y))))$ - True, Because all three elements satisfy the condition.

Terminology: Tautologies, Contradictions, Contingent

• A tautology is true in all models.
• A contradiction is false in all models.
• A contingent formula is true in some models and false in others.
• A satisfiable formula is true in some model.
• $L(r, j) \land C(j)$ is contingent.
• $\forall x C(x)$ is also contingent.

Semantic Entailment in Predicate Logic

• In propositional logic, semantic entailment means for all valuations, if $\phi<em>1$ to $\phi</em>n$ are true, then $\psi$ is also true.
• In predicate logic, semantic entailment means for all models, if $\phi<em>1$ to $\phi</em>n$ hold, then $\psi$ holds.
• A counterexample consists of a specific model.
• Consider $\forall x (H(x) \implies M(x)) \land H(s) \vDash M(s)$.
  • In any model $M$, if $\forall x (H(x) \implies M(x))$ and $H(s)$ are true, then so is $M(s)$.
  • Because the interpretation of s in model m is an element where H holds.
  • and the elements where H holds, is included in the set of elements where the predicate M holds in model M.
  • This semantic entailment holds.
• Is "All fish are mortal. I am mortal. Therefore, I am a fish" logically true?
  • Counterexample of Socrates is not a fish:
    • Let model consist of Socrates who is not a fish.
    • $(M \vDash \forall x (F(x) \implies M(x))$ holds because there are no fish.
    • $(M \vDash M(s))$ also holds. Socrates is mortal.
    • But $(M \nvDash F(s))$, Socrates is not a fish.

Semantic Equivalences

• Semantic Equivalence: A famous scene from Alice in wonderland shows semantic equivalence.
  • Alice : I mean what I say, is the same as I say what I mean.
  • Mad Hatter : Not the same thing at all! Why, you might just as well say that “I see what I eat” is the same thing as “I eat what I see!”
• The same principles apply to predicate logic.
• DeMorgan's Rule in Predicate Logic Example:
  • Let P(x) mean