Prerequisite : Predicates and Quantifiers Set 1, Propositional Equivalences Logical Equivalences involving Quantifiers Two logical statements involving predicates and quantifiers are considered equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements irrespective of the domain used for the variables in the propositions. Figure 2.10: Four important rules of predicate logic. Subjects to be Learned. In any case, then, the truth values of ¬(∀xP(x)) and ∃x(¬P(x)) are the same. Let P be a formula of predicate logic which contains one or more predicate variables. With this in mind, we can define logical equivalence and the closely related concept of tautology for predicate logic. Definition 2.9. g) If x is any positive number, then there is a number y such that \(y^{2}=x\). Watch the recordings here on Youtube! The sentence “Someone has the answer to every question” is ambiguous. d) ∃n(∀s(L(s, n) → (∃x∃y∃z(s = xyz ∧ R(x, y) ∧ T(y) ∧ U(x, y, z)))). If so, give one with a domain of at most 5 elements. Express Johan Cruyff’s statement “There is only one ball, so you need to have it” in predicate logic. A similar argument would show that ¬(∃xP(x)) ≡ ∀x(¬P(x)). Express the first meaning in predicate logic. Notation: In propositional logic proofs (and later, predicate logic proofs), we can omit uses of associativity and commutativity rules and treat them as being implicit. It lets us express some propositions which we otherwise would not have been able to b) ∃n(∀s(L(s, n) → P(s))). For more information contact us at info@libretexts.org or check out our status page at https://status.libretexts.org. Draw a Tarski world for the last exercise. It might not be clear exactly why this qualifies as a ‘simplification’, but it’s generally considered simpler to have the negation operator applied to basic propositions such as R(y), rather than to quantified expressions such as ∀y(R(y) ∨ Q(y)). In predicate logic, two formulas are logically equivalent if they have the same truth value for all possible predicates. The LibreTexts libraries are Powered by MindTouch® and are supported by the Department of Education Open Textbook Pilot Project, the UC Davis Office of the Provost, the UC Davis Library, the California State University Affordable Learning Solutions Program, and Merlot. Predicate Logic. Two formulas P and Q are said to be logically equivalent if P ↔ Q is a tautology, that is if P and Q always have the same truth value when the predicate variables they contain are replaced by actual predicates. ≡ ∀x(¬(P(x) ∧ (∀y(Q(y) → Q(x)))), ≡ ∀x((¬P(x)) ∨ (¬∀y(Q(y) → Q(x)))) Because identity is an equivalence relation, it is symmetric, transitive and reflexive,. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable. Let us start with a motivating example. The other laws allow you to interchange the order of the variables when two quantifiers of the same type (both ∃ or ∀) occur together. Translate each of the following propositions into an unambiguous English sentence: 10. The identity = = = is actually a two place predicate which tells us that a given term can always be replaced by the other. So, the truth of ¬(∀xP(x)) implies the truth of ∃x(¬P(x)). Explain why the second meaning is not expressed by ∀x(Dog(x) →LooksFor(jane, x)). What is the difference between the following two statements? 1.4.4: Tarski’s world and formal structures. If you are not convinced about this, try to draw up a Tarski’s world that shows this unequivalence. ∃xRed(x) ∧ ∃xSquare(x) and ∃x(Red(x) ∧ Square(x)). Does an instance of a Tarski World exist with these properties? f) Anyone who passes the final exam will pass the course. 1. Clearly, there are pairs of propositions in predicate logic that mean the same thing. Example 1 for basics. Since P(a) is false, ¬P(a) is true. ≡ ∀x((¬P(x)) ∨ (∃y(¬(Q(y) → Q(x))))). So to test for logical equivalence we just test for the logical truth of the biconditional: To determine whether the closed predicate logic sentences, X and Y, are logically equivalent, test their biconditional, X=Y, for logical truth. Rather, we end with a two examples of logical equivalence and deduction, to pique your interest. To calculate in predicate logic, we need a notion of logical equivalence. For example, consider the wff x P(x). We also acknowledge previous National Science Foundation support under grant numbers 1246120, 1525057, and 1413739. This is a really trivial example. In your answer, the ¬ operator should be applied only to individual predicates. Express the proposition “There are exactly three happy people” in predicate logic. logical equivalence in predicate logic. Consider the following description of a Tarski World. 6. Let P be a formula of predicate logic which contains one or more predicate variables. A. Einstein In the previous chapter, we studied propositional logic. We could extend predicate logic by talking about identity, something we are all familiar with. 11. E.g., to prove Consider ¬(∀xP(x)) and ∃x(¬P(x)). Ask Question Asked 1 year, 11 months ago. P can be any one-place predicate, and Q can be any two-place predicate. Predicate Logic deals with predicates, which are propositions containing variables.. Predicate Logic – Definition. These two principles could be used as definitions of the concepts of logical inference and logical equivalence in terms of the concept of tautology in propositional logic. A full treatment of predicate logic is beyond the scope of this text. For example, \(\neg \forall y(R(y) \vee Q(y)) \equiv \exists y(\neg(R(y) \vee Q(y)))\), \(\equiv \exists y((\neg R(y)) \wedge(\neg Q(y))\). d) All purple elephants have green feet. Find the negation of each of the following propositions. b) Any white bird is not a crow. c) ∃n(∀s(L(s, n) → (∃x∃y∃zQ(x, y, z)))). Suppose that the domain of discourse for a predicate P contains only two entities. e) There is no one who does not like pizza. They are especially fond of the sentence “Jane is looking for a unicorn”, which is not ambiguous when applied to the real world. These statements have the same truth value: If not everyone is happy, then someone is unhappy and vice versa. Give two translations of this sentence into predicate logic, and explain the difference in meaning. For instance: ∀x∃y(R(x, y)) ̸≡ ∃y∀x(R(x, y)). The other meaning is that Jane is looking for any old dog—maybe because she wants to buy one. From Wff to Proposition. (It's still okay to spell them out, of course.) Have questions or comments? So, there must be some entity a for which P(a) is false. 9. We will give two facts: john is a father of pete and pete is a father of mark.We will ask whether from these two facts we can derive that john is a father of pete: obviously we can.. 12. Predicate Logic \Logic will get you from A to B. 13. Example 21. We’ll see that these are crucial pieces of writing proofs. Viewed 59 times 0 $\begingroup$ I was studying discrete mathematics, one of the basic subjects in cs department. These two equival- ences, which explicate the relation between negation and quantification, are known as DeMorgan’s Laws for predicate logic.