ACSC191: Discrete Mathematics - Lecture 4: Predicate Logic

This lecture focuses on predicate logic, a key component of discrete mathematics that extends the concept of simple propositions to include more complex statements involving variables. In previous discussions, we were limited to specific propositions, but to handle real-world applications effectively, we must develop general statements that involve variables.

Understanding Predicates

Predicates, often referred to as propositional functions, are statements with variables that do not inherently possess a truth value until values are assigned to their variables. For example, the statement "x > 3" can be denoted as P(x). Here, P(x) is a predicate because it does not have a truth value until a specific value is substituted for x. Conversely, when we assign a value, such as P(4), we convert it into a proposition: "4 > 3", which evaluates as true.

Similarly, for P(2), we get the proposition "2 > 3", which evaluates as false. Predicates can also involve multiple variables, such as the expression "x + y = z", which we can denote as Q(x, y, z). In predicate logic:

A predicate with n variables is termed an n-place predicate.
A predicate with 0 variables is simply a proposition.
For instance, P(x): x < 2 is a one-place predicate, while Q(x, y, z) = x + y > z is a three-place predicate.

Validity of Predicates

We've also defined key terms related to the truth values of predicates:

If a predicate P(x1, x2, ..., xn) is true for all possible values assigned to x1, x2,..., xn, it is termed valid.
If it holds true for some assignments of values but not all, it is called satisfiable.
If it evaluates to false for every possible assignment, it is termed unsatisfiable.

Connecting Predicates

Logical operators can connect predicates to form compound statements. Examples include:

(x + 3 = y) ∧ ¬(y > 5)
(x < 0) → (x + y = 1)
(((x > 0) ∧ (x < 1)) → (x > x²))

Quantifiers in Predicate Logic

To turn predicates into propositions, we can assign values to all variables or utilize quantifiers. There are two primary types of quantifiers:

Universal Quantifier: Denoted as ∀ x P(x), signifies that a property P(x) is true for all x within a specific set, known as the universe of discourse or domain.
Existential Quantifier: Denoted as ∃ x P(x), indicates that a property P(x) is true for at least one x within the set.

The Universal Quantifier

If the universe of discourse U can be effectively listed, then ∀ x P(x) becomes equivalent to the conjunction P(x1) ∧ P(x2) ∧ … ∧ P(xn). Additionally, the negation of quantified statements reveals important equivalences:

¬∀ x P(x) ≡ ∃ x ¬P(x)
¬∃ x P(x) ≡ ∀ x ¬P(x)

The Existential Quantifier

Conversely, ∃ x P(x), if U can be listed, translates to the disjunction P(x1) ∨ P(x2) ∨ … ∨ P(xn). The process of understanding these conveying quantifications often involves practical examples, such as searching and looping through sets.

Working with Multiple Quantifiers

When employing multiple quantifiers, it is crucial to read them left to right:

∀ x ∀ y P(x, y) means the property P holds for every combination of x and y.
∀ x ∃ y P(x, y) indicates for each x there exists a corresponding y that satisfies P.
∃ x ∃ y P(x, y) indicates there exists at least one x and one y for which P holds true.

Commutativity of Quantifiers

While certain quantifications commute, such as ∀ x ∀ y P(x, y) and ∃ x ∃ y P(x, y), others, like ∀ x ∃ y P(x, y) and ∃ y ∀ x P(x, y), do not. This distinction is critical, as it reflects different meanings in terms of logical relationships. For example:

∀ x ∃ y Q(x, y) - "For every x, there exists a y such that Q is true".
∃ y ∀ x Q(x, y) - "There exists a y that makes Q true for all x".

Translating English Statements into Logic

We explored how to translate English sentences into logical expressions through various examples:

The statement "Every student in this class has studied calculus" becomes expressed in logical format as ∀ x C(x), where C(x) signifies the property of studying calculus.
Conversely, statements involving existential quantifiers like "Some student in this class has visited Mexico" can be written as ∃ x M(x), with M(x) representing the property of having visited Mexico.

Conclusion

The lecture culminates with exercises that encourage practicing these concepts, including determining truth values and translating various propositions into logical forms using different universes of discourse.

Predicate Logic in Discrete Mathematics

Predicate Logic in Discrete Mathematics