8. 1. Predicate Logic

In this lecture we will discuss predicate logic and its motivation, we will discuss about quantification mechanisms and we will discuss logical equivalence in predicate logic.

Predicate logic extends propositional logic by allowing more expressive statements. While propositional logic deals with true/false values of whole statements, predicate logic deals with statements that can include variables and predicates defined over them. This enhances our ability to express mathematical truths.

Think of propositional logic as looking at individual boxes—each box represents a complete statement (like 'The door is open'). When we use predicate logic, it's like examining the contents of each box to understand what might be true inside, like 'For all boxes: if there is something heavy, then that box is closed.' This allows us to explore truths across a range of possibilities.

Propositional logic cannot represent all kinds of mathematical statements. For instance, consider the statement 'x is greater than 3.' This is not a proposition because we don’t know if it's true or false until we assign a value to x.

In propositional logic, a proposition must have a definite truth value—true or false. However, statements involving variables, like 'x is greater than 3,' don't have a definite value until the variable is assigned. Predicate logic allows us to express such statements using predicates, which consider these variables.

Imagine you are trying to decide whether you can go on a trip next week. You can't confirm 'I will go next week' until you know your schedule. Predicate logic lets you say, 'If my schedule allows, then I will go,' acknowledging the uncertainty about your plans.

We introduce a function called a predicate function, represented by capital letters. For example, we can define P(x) which indicates a property of x. If we assign a concrete value to x, then P(x) becomes a simple proposition.

A predicate function is a way to express properties or characteristics that can apply to a range of values. By using capital letters to denote these functions, we differentiate them from lower-case propositional variables. When a specific value is assigned to the variable in the predicate, it becomes a concrete proposition that can be evaluated as true or false.

Think of a predicate function as a recipe. The recipe itself (P(x)) can apply to many ingredients (values of x). When you choose a specific ingredient (say, '4'), you can evaluate the recipe's outcome to see if it works with that ingredient. So, if P(4) is true, it tells you something specific about using '4' in the recipe.

We can define multi-valued predicate functions to represent statements involving multiple subjects. For instance, P(x, y) could denote a relationship between x and y, and it becomes a proposition when specific values are assigned.

Predicate functions can take more than one variable, allowing us to express relationships or conditions involving multiple elements. For instance, a statement like 'x equals y + 3' can be expressed in predicate form as P(x, y). When we assign values to both variables, we can evaluate the expression for its truth status.

Consider multiple friends deciding what game to play based on the number of players. A predicate function could represent possible game choices based on the number of players (P(x, y)), where x is the number of players and y is the game. Only when specific numbers are assigned can you determine which games are feasible.

We will discuss quantified statements and the two main forms of quantifications: universal quantification and existential quantification.

Quantification allows us to make statements about all members of a domain or at least one member. Universal quantification, denoted by ∀ (for all), asserts a property is true for every element, while existential quantification, denoted by ∃ (there exists), asserts a property is true for at least one element in the domain.

If a teacher says 'All students must submit homework,' that's universal quantification—applying to everyone in the class. If the teacher says 'At least one student has submitted the homework,' that indicates existential quantification—a specific case rather than the whole.

Universal quantification is asserted using the notation ∀. For example, 'For all x, P(x) is true.' If we find just one counterexample, then the statement is false.

Universal quantification means the expression 'For all x, P(x)' holds true only when the predicate P is satisfied for every single element in the domain. If there’s even one instance where P is false, the entire statement fails, making it false.

Consider a bag of apples claimed to be all fresh. If you find even one rotten apple, the claim is false. Here, that one rotten apple serves as the counterexample to the universal claim of freshness.

Existential quantification asserts that a property holds true for at least one element in the domain, represented as ∃. For example, 'There exists an x such that P(x) is true.'

Existential quantification means that we are asserting the truth of a property for at least one instance. This doesn't require all instances to satisfy it; just one 'witness' is enough to validate the statement.

Imagine you’re looking for a friend at a party. If you ask, 'Is there a friend at the party?' the answer only needs to confirm that at least one friend is present. You don’t need to know about every guest.

A variable is called bound if there is a quantifier applied to it. If no quantifier is applied, it is free. It is important to understand these terms to correctly interpret logical statements.

Bound variables are those quantified by expressions like ∀ or ∃; they are restricted in their application. Free variables, on the other hand, have no quantifiers restricting them. Understanding which variables are bound or free is crucial to avoid ambiguity in logical statements.

Think of a game with rules (quantifiers). If a rule applies to a player (the player is bound by the rule), they must follow it. If there's no rule affecting someone, they can act freely (the player is free). Knowing how rules apply helps clarify the game's structure.

We can define logical equivalences even for predicates. Two expressions are logically equivalent if they have the same truth value for every possible domain.

Logical equivalence means that two predicates are true under the same conditions, no matter the domain. If one statement can be proven true or false based solely on equivalences of their components, it highlights the consistency in the logical structure.

Consider two twins who make the same decision under similar circumstances. If one twin's decision-making can be equated to the other's across various situations, you can say their decisions (predicates) are logically equivalent under those conditions.

--