8.1 Predicates, Subjects, and Objects

Predicate logic expands on propositional logic by breaking statements into subjects, objects, and predicates. This allows for more nuanced expressions of relationships between entities. It introduces quantifiers to make general claims about groups of objects.

Predicates describe properties or relations, while subjects and objects are the entities involved. Understanding these components is crucial for constructing and analyzing complex logical statements in predicate logic.

Predicate Components

Structure of Predicates

Top images from around the web for Structure of Predicates

• 

  Logic for Computer Scientists/Predicate Logic/Syntax - Wikibooks, open books for an open world View original

  Is this image relevant?

• 

  SQL Abstract Syntax Trees Vocabulary View original

  Is this image relevant?

• 

  Predicate (grammar) - Simple English Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Logic for Computer Scientists/Predicate Logic/Syntax - Wikibooks, open books for an open world View original

  Is this image relevant?

• 

  SQL Abstract Syntax Trees Vocabulary View original

  Is this image relevant?

1 of 3

Top images from around the web for Structure of Predicates

• 

  Logic for Computer Scientists/Predicate Logic/Syntax - Wikibooks, open books for an open world View original

  Is this image relevant?

• 

  SQL Abstract Syntax Trees Vocabulary View original

  Is this image relevant?

• 

  Predicate (grammar) - Simple English Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Logic for Computer Scientists/Predicate Logic/Syntax - Wikibooks, open books for an open world View original

  Is this image relevant?

• 

  SQL Abstract Syntax Trees Vocabulary View original

  Is this image relevant?

1 of 3

• Predicates are expressions that represent relations or properties of objects
• Consist of a predicate symbol followed by a list of arguments enclosed in parentheses
• Arguments can be individual constants, variables, or complex terms
• Number of arguments a predicate takes is called its arity

Subject and Object Roles

• Subject is the entity or thing being described or related by the predicate
• Object is the entity or entities to which the subject is related or connected
• In the predicate "loves(John, Mary)", "John" is the subject and "Mary" is the object
• Some predicates only take a subject (unary predicates) while others relate a subject to one or more objects (binary or higher-arity predicates)

Arity of Predicates

• Arity refers to the number of arguments a predicate takes
• Unary predicates have an arity of one and represent properties of a single object (tall(John))
• Binary predicates have an arity of two and represent relations between two objects (loves(John, Mary))
• Predicates can have higher arities to represent more complex relations (gave(John, Mary, book))
• Arity of a predicate is fixed and determines the structure of the atomic formulas it can form

Quantification

Quantifiers and Variables

• Quantifiers are logical symbols used to specify the quantity or portion of a domain that satisfies a given predicate
• Two main quantifiers are the universal quantifier (∀) meaning "for all" and the existential quantifier (∃) meaning "there exists"
• Variables are symbols (usually letters like x, y, z) that serve as placeholders for objects in the domain
• Quantifiers bind variables to specify the scope and extent of the predicate (∀x tall(x) means "for all x, x is tall")

Individual Constants and Interpretation

• Individual constants are symbols that refer to specific objects in the domain of discourse
• Usually denoted by lowercase letters at the beginning of the alphabet (a, b, c)
• Interpretation function maps each individual constant to a specific object in the domain
• If the domain is people, the interpretation might map a to John, b to Mary, etc.
• Individual constants allow us to make statements about specific objects (loves(a, b) means "John loves Mary")

Interaction of Quantifiers and Constants

• Quantifiers and individual constants can be combined to express complex logical statements
• Universal statements use quantifiers without constants (∀x loves(x, x) means "everyone loves themselves")
• Existential statements use quantifiers with constants (∃x loves(a, x) means "there is someone John loves")
• Statements with multiple quantifiers express relations between objects (∀x ∃y loves(x, y) means "for every person, there is someone they love")
• Order and scope of quantifiers is crucial in determining the meaning of the statement

Logical Formulation

Domain of Discourse

• Domain of discourse is the set of objects that the predicates and quantifiers in a logical statement refer to
• Specifies the "universe" or context in which the statement is being evaluated
• Can be any non-empty set such as numbers, people, countries, etc.
• Interpretation of constants, predicates, and the truth of statements depends on the domain
• Statement ∀x (x > 0) is true in the domain of natural numbers but false in the domain of all integers

Atomic Formulas

• Atomic formulas are the basic building blocks of logical statements in predicate logic
• Consist of a predicate symbol applied to the appropriate number of arguments (matching its arity)
• Arguments can be individual constants (likes(a, b)), variables (likes(x, y)), or complex terms (likes(father(x), y))
• Atomic formulas have a truth value (true or false) that depends on the interpretation of the symbols and the domain
• Examples: red(apple), prime(7), loves(John, Mary), greaterThan(x, 5)

Constructing Logical Statements

• Complex logical statements are built up from atomic formulas using logical connectives and quantifiers
• Connectives like ∧ (and), ∨ (or), ¬ (not), → (implies) combine atomic formulas into compound statements
• Quantifiers ∀ (for all) and ∃ (there exists) bind variables to specify the quantity of objects that satisfy a predicate
• Statements can contain multiple quantifiers, connectives, and predicates to express rich logical relations
• Example: ∀x (person(x) → ∃y (person(y) ∧ loves(x, y))) means "for every person x, there is some person y such that x loves y"