Predicates

Definition

A predicate is a logical expression containing one or more variables that becomes either true or false when values are assigned to those variables.

For example:

• Let $P(x)$: “x is an even number”
• If $x = 4$, then $P(4)$ is true
• If $x = 5$, then $P(5)$ is false

In formal logic, a predicate is often written as:

• $P(x)$, $Q(x, y)$, $R(x, y, z)$

where:

• $P, Q, R$ are predicate symbols
• $x, y, z$ are variables
• the truth value depends on the values assigned to the variables

A predicate is also called an open statement because it does not have a definite truth value until its variables are specified.

Main Content

1. Predicate and Proposition

• A proposition is a declarative statement that is definitely true or false, such as “2 + 3 = 5” or “The sky is green.”
  A predicate becomes a proposition only after assigning values to its variables. For example, “x > 10” is a predicate, but “7 > 10” is a proposition with a false truth value.

• The main difference is that propositions have a fixed truth value, whereas predicates are variable-dependent. This makes predicates more flexible for expressing general statements in mathematics and computer science.

Examples:

• Proposition: “5 is prime” → true
• Predicate: $P(x)$: “x is prime”
• $P(5)$ → true
• $P(6)$ → false

This distinction is important in logic because many real-world conditions are not about a single fixed statement but about a property that applies to different objects.

2. Domain and Variables in Predicates

• The domain is the set of all possible values that a variable in a predicate may take. For example, if $x$ is an integer, then the domain may be all integers; if $x$ is a student ID, then the domain may be all students in a class.

• The truth of a predicate depends not only on the formula itself but also on the domain. For example, the predicate $x^2 > 4$ has different interpretations depending on whether the domain is integers, real numbers, or natural numbers.

Examples:

• $P(x)$: “x is greater than 0”
• Domain: integers
• $P(-2)$ → false

• $P(3)$ → true

• $Q(x, y)$: “x is the parent of y”

• Domain: people
• $Q(\text{Alice}, \text{Bob})$ may be true or false depending on the relationship

Predicates can have:

one variable

• : $P(x)$

two variables

• : $Q(x, y)$

three or more variables

• : $R(x, y, z)$

The more variables a predicate has, the more detailed the relationship it can describe.

3. Quantifiers and Predicate Logic

• Predicates become very powerful when combined with quantifiers, which tell us how many values in the domain satisfy the predicate. The two main quantifiers are:
• Universal quantifier: $\forall$ meaning “for all”

• Existential quantifier: $\exists$ meaning “there exists”

• Quantifiers help convert predicates into complete logical statements. For example:

• $\forall x\, P(x)$: “For all x, P(x) is true”
• $\exists x\, P(x)$: “There exists at least one x such that P(x) is true”

Examples:

• $P(x)$: “x is even”
• $\forall x\, P(x)$ is false if the domain is all integers

• $\exists x\, P(x)$ is true if the domain is all integers, because some integers are even

• $Q(x)$: “x is a student who passed”

• $\exists x\, Q(x)$ means at least one student passed
• $\forall x\, Q(x)$ means every student passed

Quantifiers are essential in formal reasoning, proofs, and logical specifications. They allow us to express:

• general rules
• existence of an object with a property
• conditions in algorithms and machine states

Working / Process

1. Identify the statement and variables

Start by finding the part of the sentence that depends on a variable. For example, in “x is divisible by 3,” the variable is $x$, and the statement is a predicate because it is not yet true or false until $x$ is chosen.

2. Specify the domain and evaluate truth

Decide the set of values the variable can take. Then substitute a particular value to determine whether the predicate is true or false. For example, if the domain is integers and $P(x)$: “x is divisible by 3,” then $P(9)$ is true and $P(10)$ is false.

3. Use quantifiers to form complete logical statements

Combine predicates with $\forall$ or $\exists$ to express more powerful conditions. For example:

• $\forall x\, (x > 0 \rightarrow x^2 > 0)$
• $\exists x\, (x^2 = 16)$

These steps are often used in mathematical proof writing, algorithm specification, and state-machine transition conditions.

Advantages / Applications

• Predicates allow us to describe properties of objects and relationships between objects in a precise way. This is useful in mathematics, where statements like “every even number is divisible by 2” can be expressed rigorously.

• They are widely used in computer science and programming for writing conditions, defining constraints, and creating logic in programs, databases, and software testing. For example, a condition in an if statement is often a predicate.

• Predicates are important in formal verification, theorem proving, and finite state machines, where states and transitions are controlled by logical conditions. They help specify when a transition should occur, such as “move to the next state if the input is 1” or “accept the input if a condition is satisfied.”

Summary

• Predicates are statements with variables that become true or false only after values are assigned.
• They extend propositions by allowing general conditions and relationships to be expressed clearly.
• Quantifiers such as $\forall$ and $\exists$ turn predicates into complete logical statements useful in proofs and computation.
• Predicates are a core idea in logic, programming, and finite state machine design.