8. 1.7. Logical Equivalence in Predicate World

It turns out that we can define logical equivalences even for the predicate world, we can define predicates, we can have quantified statements and we can have two different expressions and we can verify whether the two expressions are logically equivalent or not.

In predicate logic, logical equivalence helps us understand how two different expressions can mean the same thing. To determine if two expressions are logically equivalent, we need to check if they hold true or false under the same conditions.

Imagine two different weather reports predicting the same weather conditions. If both reports indicate 'It will rain tomorrow,' they are logically equivalent regardless of the specific wording used.

So how do we prove logical equivalences involving predicates? Well, what was our definition of logical equivalence in the propositional world? If you have two compound propositions x and y we said that x is logically equivalent to y if and only if x bi-implication y is a tautology.

Logical equivalence in predicate logic is similar to that in propositional logic. This means two expressions are equivalent if they consistently have the same truth values. Thus, if every instance of x leads to the same truth value as y, they are logically equivalent.

Think of two routes to a destination that both take the same time. Whether you take Route A or Route B, if both get you there at the same time, they are getting you the same result—in essence, they are logically equivalent in terms of travel time.

But now we are talking about arbitrary domains, arbitrary predicate functions and so on. Intuitively, we will say that my expressions involving predicate functions are logically equivalent if they are equivalent with respect to any possible domain.

Logical equivalence in predicate logic must hold true across all potential domains of discourse. This means that the equivalence is not limited to specific cases, but is instead reliable for any set of values that can be considered.

Consider the phrase 'All cats are mammals.' It holds for any type of cat (Persian, Siamese, etc.) and any species of mammal. The equivalence of being a 'cat' and 'mammal' remains true in any discussion about these animals.

So let us start with the LHS part here, what was your LHS part? The LHS part says that for all x conjunction of P(x) and Q(x) is true.

To verify logical equivalences, we often start by examining one side of the equation (the left-hand side or LHS). For the expression to be true, it must hold under all values in the domain, meaning both predicates P and Q must be true for each x value considered.

Think of two friends, Alice and Bob, who always agree on whether they like a movie. If we consider every movie represented by 'x', for them both to agree (P(x) for Alice and Q(x) for Bob), they must consistently have the same opinions — just like P and Q must hold true for every instance of x.

Now what I do is, I just shuffle the terms here, I bring all the P terms together and all the Q terms together.

By rearranging the terms in the logical expressions, we can simplify verifying equivalences. This method involves organizing predicates to better see and demonstrate how they relate to each other and confirm whether the expressions yield the same truth values.

Consider trying to organize your backpack for school. If you gather all your notebooks (P terms) in one section and your folders (Q terms) in another, it becomes much easier to see clearly if you have everything you need for class, just like isolating predicates helps highlight logical equivalences.

In the same way we can prove De Morgan's law involving quantified statements, so for instance we can prove that if you have a negation symbol outside for all x, you can take the negation inside and for all become there exist and you take the negation and put it before your predicate P(x).

De Morgan's laws provide rules for transforming logical statements, particularly when dealing with negations in quantified expressions. This is important for manipulating logical statements correctly while demonstrating their equivalences.

Imagine guarding a treasure chest: if you say 'not all treasures are safe,' it’s equivalent to saying 'there exists at least one treasure that isn't safe.' Both statements communicate the same idea about your treasures, just expressed differently.

--