Page 132 **Definition** A **predicate** is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables. The **domain** of a predicate variable is the set of all values that may be substituted in place of the variable. --- Page 132 **Definition** If $P(x)$ is a predicate and $x$ has domain $D$, the **truth set** of $P(x)$ is the set of all elements of $D$ that make $P(x)$ true when they are substituted for $x$. The truth set of $P(x)$ is denoted $$ \{x \in D | P(x)\} $$ --- Page 133 **Definition** Let $Q(x)$ be a predicate and $D$ the domain of $x$. A **universal statement** is a statement of the form "$\forall x \in D, Q(x)$." It is defined to be true if, and only if, $Q(x)$ is true for each individual $x$ in $D$. It is defined to be false if, and only if, $Q(x)$ is false for at least one $x$ in $D$. A value for $x$ for which $Q(x)$ is false is called a **counterexample** to the universal statement. --- Page 134 **Definition** Let $Q(x)$ be a predicate and $D$ the domain of $x$. An **existential statement** is a statement of the form "$\exists x \in D$ such that $Q(x)$." It is defined to be true if, and only if, $Q(x)$ is true for at least one $x$ in $D$. It is false if, and only if, $Q(x)$ is false for all $x$ in $D$. --- Page 140 **Notation** Let $P(x)$ and $Q(x)$ be predicates and suppose the domain of $x$ is $D$. - The notation $P(x) \Rightarrow Q(x)$ means that every element in the truth set of $P(x)$ is in the truth set of $Q(x)$, or, equivalently, $\forall x, P(x) \to Q(x)$. - The notation $P(x) \Leftrightarrow Q(x)$ means that $P(x)$ and $Q(x)$ have identical truth sets, or, equivalently, $\forall x, P(x) \leftrightarrow Q(x)$. --- Page 145 **Theorem 3.2.1 Negation of a Universal Statement** The negation of a statement of the form $$ \forall \text{ in } D, Q(x) $$ is logically equivalent to a statement of the form $$ \exists \text{ in } D \text{ such that } \neg Q(x) $$ Symbolically, $$ \neg(\forall x \in D, Q(x)) \equiv \exists x \in D \text{ such that } \neg Q(x) $$ --- Page 146 **Theorem 3.2.2 Negation of an Existential Statement** The negation of a statement of the form $$ \exists \text{ in } D \text{ such that } Q(x) $$ is logically equivalent to a statement of the form $$ \forall x \text{ in } D, \neg Q(x) $$ Symbolically, $$ \neg(\exists x \in D \text{ such that } Q(x)) \equiv \forall x \in D, \neg Q(x) $$ --- Page 148 **Negation of a Universal Conditional Statement** $$ \neg(\forall x, \text{ if } P(x) \text{ then } Q(x)) \equiv \exists x \text{ such that } P(x) \text{ and } \neg Q(x) $$ $$ \neg(\forall x, P(x) \to Q(x)) \equiv \exists x, (P(x) \wedge \neg Q(x)) $$ --- Page 150 **Definition** Consider a statement of the form $\forall x \in D, \text{ if } P(x) \text{ then } Q(x)$. 1. Its **contrapositive** is the statement $\forall x \in D, \text{ if } \neg Q(x) \text{ then } \neg P(x)$. 2. Its **converse** is the statement $\forall x \in D, \text{ if } Q(x) \text{ then } P(x)$. 3. Its **inverse** is the statement $\forall x \in D, \text{ if } \neg P(x) \text{ then } \neg Q(x)$. --- Page 151 **Definition** - "$\forall x, r(x)$ is a **sufficient condition** for $s(x)$" means "$\forall x, \text{ if } r(x) \text{ then } s(x)$." - "$\forall x, r(x)$ is a **necessary condition** for $s(x)$" means "$\forall x, \text{ if } \neg r(x) \text{ then } \neg s(x)$" or, equivalently, "$\forall x, \text{ if } s(x) \text{ then } r(x)$." - "$\forall x, r(x)$ **only if** $s(x)$" means "$\forall x, \text{ if } \neg s(x) \text{ then } \neg r(x)$" or, equivalently, "$\forall x, \text{ if } r(x) \text{ then } s(x)$." --- Page 156 **Interpreting Statements with Two Different Quantifiers** If you want to establish the truth of a statement of the form $$ \forall x \text{ in } D, \exists y \text{ in } E \text{ such that } P(x, y) $$ your challenge is to allow someone else to pick whatever element $x$ in $D$ they wish and then you must find an element $y$ in $E$ that "works" for that particular $x$. If you want to establish the truth of a statement of the form $$ \exists x \text{ in } D \text{ such that } \forall y \text{ in } E, P(x, y) $$ your job is to find one particular $x$ in $D$ that will "work" no matter what $y$ in $E$ anyone might choose to challenge you with. --- Page 160 **Negations of Statements with Two Different Quantifiers** $\neg(\forall x \text{ in } d, \exists y \text{ in } E \text{ such that } P(x, y)) \equiv \exists x \text{ in } D \text{ such that } \forall y \text{ in } E, \neg P(x, y)$ $\neg(\exists x \text{ in } D \text{ such that } \forall y \text{ in } E, P(x, y)) \equiv \forall x \text{ in } D, \exists y \text{ in } E \text{ such that } \neg P(x, y)$ --- Page 169 **Universal Instantiation** If a property is true of _everything_ in a set, then it is true of _any particular_ thing in the set. --- Page 170 **Universal Modus Ponens** _Formal Version_ $$ \forall x, \text{ if } P(x) \text{ then } Q(x) \\ P(a) \text{ for a particular } a \\ \therefore Q(a) $$ _Informal Version_ $$ \text{If } x \text{ makes } P(x) \text{true, then } x \text{ makes } Q(x) \text{ true.} \\ a \text{ makes } P(x) \text{ true.} \\ \therefore a \text{ makes } Q(x) \text{ true.} $$ --- Page 172 **Universal Modus Tollens** _Formal Version_ $$ \forall x, \text{ if } P(x) \text{ then } Q(x) \\ \neg Q(a) \text{ for a particular } a \\ \therefore \neg P(a) $$ _Informal Version_ $$ \text{If } x \text{ makes } P(x) \text{true, then } x \text{ makes } Q(x) \text{ true.} \\ a \text{ does not make } Q(x) \text{ true.} \\ \therefore a \text{ does not make } P(x) \text{ true.} $$ --- Page 173 **Definition** To say that an _argument form_ is **valid** means the following: No matter what particular predicates are substituted for the predicate symbols in its premises, if the resulting premise statements are all true, then the conclusion is also true. An _argument_ is called **valid** if, and only if, its form is valid. It is called _sound_ if, and only if, its form is valid and its premises are true. --- Page 176 **Converse Error (Quantified Form)** _Formal Version_ $$ \forall x, \text{ if } P(x) \text{ then } Q(x) \\ Q(a) \text{ for a particular } a \\ \therefore \neg P(a) \text{ is an invalid conclusion} $$ _Informal Version_ $$ \text{If } x \text{ makes } P(x) \text{true, then } x \text{ makes } Q(x) \text{ true.} \\ a \text{ makes } Q(x) \text{ true.} \\ \therefore a \text{ makes } P(x) \text{ true. } \text{ is an invalid conclusion} $$ --- Page 176 **Inverse Error (Quantified Form)** _Formal Version_ $$ \forall x, \text{ if } P(x) \text{ then } Q(x) \\ \neg P(a) \text{ for a particular } a \\ \therefore \neg \neg Q(a) \text{ is an invalid conclusion} $$ _Informal Version_ $$ \text{If } x \text{ makes } P(x) \text{true, then } x \text{ makes } Q(x) \text{ true.} \\ a \text{ does not make } P(x) \text{ true.} \\ \therefore a \text{ does not make } Q(x) \text{ true. } \text{ is an invalid conclusion} $$ --- Page 177 **Universal Transitivity** _Formal Version_ $$ \forall x P(x) \to Q(x) \\ \forall x Q(x) \to R(x) \\ \therefore \forall x P(x) \to R(x) $$ _Informal Version_ $$ \text{Any } x \text{ that makes } P(x) \text{ true makes } Q(x) \text{ true.} \\ \text{Any } x \text{ that makes } Q(x) \text{ true makes } R(x) \text{ true.} \\ \therefore \text{Any } x \text{ that makes } P(x) \text{ true makes } R(x) \text{ true.} \\ $$