Module 1: Propositional/Predicate Calculus Review #

Logical Connectives #

(\(\neg, \land, \lor, \Rightarrow, \Leftrightarrow\))

Comment: In truth tables, I will use 0 for False, and 1 for True.

Tautologies & Contradictions #

A formula is said to be a tautology when its column in a truth table only consists of “trues”.

Example:

Tautology

A formula is said to be a contradiction when its column in a truth table only consists of “falses”.

Example:

Contradiction

\bigskip

Comment: Most formulas are neither tautologies nor contradictions.

Equivalent Formulas

We say that formulas \(\phi\) and \(\psi\) are equivalent when \((\phi \Leftrightarrow \psi)\) is a tautology. This is the case exactly when the columns in the truth tables for \(\phi\) and \(\psi\) match*.

\bigskip

Example:

P and \(\neg \neg P\) are equivalent.

Example:

\((\neg P \land \neg Q)\) and \(\neg (P \lor Q)\) are equivalent.

\bigskip

*With the caveat that the tables contain the same propositional symbols.

\((\neg P \Rightarrow (Q \land \neg Q))\)

P and \((\neg P \Rightarrow (Q \land \neg Q))\) are equivalent.

Predicates v. Propositions A proposition is a statement/sentence that is either true or false and has no (free) variables.

Examples:

• \(\pi\) is an irrational number. (True)
• 13 is the sum of two perfect squares. (True: \(2^2 + 3^2\))
• 7587 is a prime number. (False: \(3^3 \cdot 281\))
• 14 is the best number. - Ambiguous/not well defined/not true/false (not a proposition)
• \(x^2 > 15\) — Free variable \(x\), truth value depends on \(x\), not a proposition.
• \(x^2 \geq 0\) — Free variable \(x\), not a proposition.
• For every real number \(x\), \(x^2 \geq 0\). (True: Here \(x\) is not a free variable, this is a proposition).
• There is a natural number \(x\) such that \(x^2 = 17\). (False)

Comments: In formulas, we use capital letters to represent propositions, and we can “build” more complex propositions by combining them using the logical connectives.

P: “2 is an even natural number.”

Q: “2 is an odd integer.”

\((Q \Rightarrow P)\) “If 2 is an odd int., then 2 is an even nat number.”

\(((P \wedge \neg Q) \Rightarrow (P \vee Q))\)

P: “1=0”

Q: “1=1”

R: “17=3”

a=b

c=d

then a+c = b+d

(P => Q) true!? flase.

Start with having 1=0.

Then 0=1

Then 1+0 = 0+1

Then 1=1

3=3

TRUE => False

False

14=0

A predicate is a statement with zero or more (free) variables that becomes a proposition when each (free) variable is assigned a value.

Examples: “\(\pi\) is an integer.” (Predicate with zero free variables/Proposition) (Also false)

“\(x^2 = 4\)” (Predicate with one variable: If \(x = 2\), true. If \(x = 17\), false.)

“\(x+y=7\)” (Predicate with two variables: If \(x = 1, y = 6\), true. If \(x=2, y=19\), false.)

Comments: We often use a “function-like” notation for predicates, using capital letters followed by the free variables in parentheses to represent predicates: e.g. \(P, R(x), Q(x,y),…\)

We can “build” more complex predicates by combining them using logical connectives.

Common Sets:

\(\emptyset = {}\) The Empty Set

\(\mathbb{N} = {1, 2, 3, 4, 5, \dots}\) The Natural Numbers

\(\omega = {0, 1, 2, 3, 4, 5, \dots}\) The Whole Numbers

\(\mathbb{Z} = {\dots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \dots}\) The Integers

\(\mathbb{Q} = \left{ \frac{p}{q} \mid p \text{ and } q \text{ are integers and } q \neq 0 \right}\) The Rational Numbers

\(\mathbb{P}\) The Irrational Numbers

\(\mathbb{R}\) The Real Numbers

\(\mathbb{C}\) The Complex Numbers

Comment: Only the value of a number determines what set(s) it is in, not how it is written. For example, \(\sqrt{16}\) is equal to 4, so it is in \(\mathbb{N}, \omega, \mathbb{Z}, \mathbb{Q}, \mathbb{R}\) and \(\mathbb{C}\).

\begin{align*} & \mathbb{Z}[i] \text{ “Gaussian integers”} \ &= { a + bi \mid a, b \text{ are integers} } \ & 4 + 5i \text{ is in } \mathbb{Z}[i] \ & 6 + \pi i \text{ is not in } \mathbb{Z}[i] \ & \frac{1}{2} - 3i \text{ is not in } \mathbb{Z}[i] \ & -2 + 3i \text{ is a Gaussian integer.} \end{align*}

Intervals: Intervals are special types of sets of real numbers.

We will use the following as our definitions:

\begin{align*} (a,b) &= {x \in \mathbb{R} \mid a < x < b} \ [a,b) &= {x \in \mathbb{R} \mid a \leq x < b} \ (a,b] &= {x \in \mathbb{R} \mid a < x \leq b} \ [a,b] &= {x \in \mathbb{R} \mid a \leq x \leq b} \ (-\infty, b) &= {x \in \mathbb{R} \mid x < b} \ (-\infty, b] &= {x \in \mathbb{R} \mid x \leq b} \ (a, \infty) &= {x \in \mathbb{R} \mid a < x} \ [a, \infty) &= {x \in \mathbb{R} \mid a \leq x} \ (-\infty, \infty) &= \mathbb{R} \end{align*}

Comments: Intervals are sets of real numbers between two values, (generally) they contain values that are not integers.

\((1,5] \neq {2,3,4,5}\)

Only has four elements.

Has infinitely many elements, including 2,3,4,5, but also 1.036, \(\pi, \sqrt{2}, 2.7, 4.5,…\)

Also order matters:

\([3,1) = {x \in \mathbb{R} \mid 3 \leq x < 1} = \emptyset\)

vs \((1,3] = {x \in \mathbb{R} \mid 1 < x \leq 3}\)

\begin{align*} [2,2] &= {x \in \mathbb{R} \mid 2 \leq x \leq 2} = {2} \ (2,2] &= {x \in \mathbb{R} \mid 2 < x \leq 2} = \emptyset \end{align*}

Set Operations:

Union: \(A \cup B = {x \mid x \in A \lor x \in B}\) %fix this add picture

Intersection: \(A \cap B = {x \mid x \in A \land x \in B}\)

Difference: \(A \setminus B = {x \mid x \in A \land x \notin B}\)

Comment: While the union symbol “\(\cup\)” looks like the letter, it is not the same

(\(U\) is \(\underline{\text{not}}\) the union symbol)

\textbf{Truth sets of Predicates}

Let \(P(x)\) be a predicate and let \(A\) be a set. The truth set of \(P(x)\) in \(A\) is: [ TS_A(P(x)) = {x \in A \mid P(x) \text{ is true}} ]

This is the set of every value in the set \(A\) that makes \(P(x)\) true.

\textbf{Example:} Consider \(P(x)\) to be “\(-2 < x \leq 5\)”

\begin{align*} TS_{\mathbb{N}}(P(x)) &= {1, 2, 3, 4, 5} \ TS_{\mathbb{W}}(P(x)) &= {0, 1, 2, 3, 4, 5} \ TS_{\mathbb{Z}}(P(x)) &= {-1, 0, 1, 2, 3, 4, 5} \ TS_{\mathbb{R}}(P(x)) &= (-2, 5] \ TS_{\emptyset}(P(x)) &= \emptyset \ TS_{\text{Primes}}(P(x)) &= {2, 3, 5} \end{align*}

Notice that to be in \(TS_A(P(x))\), a value both needs to be in the set \(A\) and needs to make \(P(x)\) true.

\((-2,5] = [-1,5]? \text{False!} \)

\begin{tikzpicture} \draw[latex-latex] (-3.5,0) – (5.5,0) ; %edit here for the axis \foreach \x in {-3,-2,-1,0,1,2,3,4,5} % edit here for the vertical lines \draw[shift={(\x,0)},color=black] (0pt,3pt) – (0pt,-3pt); \foreach \x in {-3,-2,-1,0,1,2,3,4,5} % edit here for the numbers \draw[shift={(\x,0)},color=black] (0pt,0pt) – (0pt,-3pt) node[below] {\(\x\)}; \draw[o-*] (-2.08,0) – (5.08,0); \draw[very thick] (-2.08,0) – (5.08,0); \end{tikzpicture}

% asdfds \begin{tikzpicture} \draw[latex-latex] (-3.5,0) – (5.5,0) ; %edit here for the axis \foreach \x in {-3,-2,-1,0,1,2,3,4,5} % edit here for the vertical lines \draw[shift={(\x,0)},color=black] (0pt,3pt) – (0pt,-3pt); \foreach \x in {-3,-2,-1,0,1,2,3,4,5} % edit here for the numbers \draw[shift={(\x,0)},color=black] (0pt,0pt) – (0pt,-3pt) node[below] {\(\x\)}; \draw[-] (-1.08,0) – (5.08,0); \draw[very thick] (-1.08,0) – (5.08,0); \end{tikzpicture}

Quantifiers

A different manner in which we can convert a predicate into a proposition is by “bounding/quantifying” the free variables.

The Universal Quantifier “\(\forall\)”

Let \(P(x)\) be a predicate and let \(A\) be a set.

\((\forall x \in A) (P(x))\) is read “For every (all) \(x\) in \(A\), \(P(x)\).”

and is true exactly when: \(TS_A (P(x)) = A\)

\underline{Example}: \((\forall x \in \mathbb{N}) (x \geq 1)\) is \underline{true} because: \(TS_{\mathbb{N}} (x \geq 1) = \mathbb{N}\)

\((\forall x \in \omega) (x \geq 1)\) is \underline{false} because \(TS_{\omega} (x \geq 1) = {1, 2, 3, …} \neq \omega\)

The Existential Quantifier “\(\exists\)”

Let \(P(x)\) be a predicate and let \(A\) be a set.

\((\exists x \in A) (P(x))\) is read “There exists (is) an \(x\) in \(A\) such that \(P(x)\).”

and is true \underline{exactly} when: \(TS_A (P(x)) \neq \emptyset\)

\underline{Example}: \((\exists x \in \mathbb{N}) (x < 1)\) is \underline{false} because \(TS_{\mathbb{N}} (x < 1) = \emptyset\)

\((\exists x \in \omega) (x < 1)\) is \underline{true} because \(TS_{\omega} (x < 1) = {0} \neq \emptyset\)

\textit{10}

\begin{align*} TS_{\mathbb{N}}(x \geq 1) &= {1, 2, 3, \dots} = \mathbb{N} \ TS_{\omega}(x \geq 1) &= {1, 2, 3, \dots} \neq \omega \ TS_{\mathbb{N}}(x < 1) &= \emptyset \ TS_{\omega}(x < 1) &= {0} \neq \emptyset \end{align*}

The Unique Existential Quantifier “\(\exists!\)”

Let \(P(x)\) be a predicate and let \(A\) be a set.

\((\exists!x \in A)(P(x))\) is read “There exists (is) a unique \(x\) in \(A\) such that \(P(x)\)”.

and is true exactly when \(|T S_A(P(x))| = 1\), i.e., when \(T S_A(P(x))\) has exactly one element.

Example: \((\exists!x \in \mathbb{N})(x < 1)\) is false because \(|T S_{\mathbb{N}}(x < 1)| = |\emptyset| = 0 \neq 1\)

\((\exists!x \in \omega)(x < 1)\) is true because \(|T S_\omega(x < 1)| = |{0}| = 1\)

\((\exists!x \in \mathbb{Z})(x < 1)\) is false because \(|T S_{\mathbb{Z}}(x < 1)| = |{…, -2, -1, 0 }| \neq 1\)

\((\exists!x \in \mathbb{N})(x < 4)\) is false because \(|T S_{\mathbb{N}}(x < 4)| = |{1, 2, 3 }| = 3 \neq 1\)

\underline{Comment}: There are other quantifiers that can be used in addition to \(\forall\), \(\exists\), and \(\exists!\)

\(\exists!\) can be written using only \(\exists\) and \(\forall\):

\((\exists!x \in A)(P(x))\) is equivalent to:

\(\left( (\exists x \in A)(P(x)) \wedge (\forall x \in A)(\forall y \in A)((P(x) \wedge P(y)) \Rightarrow x = y)) \right)\)

\textbf{An Interesting Case}

For any predicate \(P(x)\), notice that: \(TS_\emptyset(P(x)) = \emptyset\).

This means that we have: \((\forall x \in \emptyset) (P(x))\) is \underline{true} (no matter \(P(x)\))

and that we have: \((\exists x \in \emptyset) (P(x))\) is \underline{false} (no matter \(P(x)\))

For example:

\((\forall x \in \emptyset) (x \neq x)\) is true

\((\exists x \in \emptyset) (x = x)\) is false

In any other universe/set \(A\):

\((\forall x \in A) (x \neq x)\) is false

\((\exists x \in A) (x = x)\) is true

Terminology: We say that \((\forall x \in \emptyset) (P(x))\) is \underline{vacuously true}

\((\forall x \in \emptyset) (P(x)) \text{ is True}\)

\((\exists x \in \emptyset) (P(x)) \text{ is False}\)

\((\forall x \in \mathbb{Z}) (x \neq x)\)

\(TS_{\mathbb{Z}}(x \neq x) = \emptyset \neq \mathbb{Z} \text{so False}\)

\((\exists x \in \mathbb{Z}) (x = x) \text{True}\)

\(TS_{\mathbb{Z}} (x = x) = \mathbb{Z} \neq \emptyset\)

\begin{tabular}{|l} \(x = x \not \vdash \text{Not a prop.}\) \end{tabular}

\(12.5\)

Notation Comments:

In cases where the universe of discourse \(U\) is “understood” we may use the following notation:

\((\forall x \in U)(P(x))\) may be written: \((\forall x)(P(x))\) (Suppressing the \(U\))

\((\exists x \in U)(P(x))\) may be written: \((\exists x)(P(x))\)

As a general rule, avoid this shorthand especially when using multiple quantifiers bounding over different sets and when the universe isn’t clear.

Equivalencies: Let \(A \subseteq B\). Then, the following equivalencies hold:

\((\forall x \in A)(P(x))\) is equiv. to: \((\forall x \in B)(x \in A \Rightarrow P(x))\)

\((\exists x \in A)(P(x))\) is equiv. to: \((\exists x \in B)(x \in A \land P(x))\)

As \(A \subseteq A\) for any set:

\((\forall x \in A)(P(x))\) is equiv. to: \((\forall x \in A)(x \in A \Rightarrow P(x))\)

\((\exists x \in A)(P(x))\) is equiv. to: \((\exists x \in A)(x \in A \land P(x))\)

If we have an understood universe \(U\), and \(A \subseteq U\):

\((\forall x \in A)(P(x))\) is equiv. to: \((\forall x)(x \in A \Rightarrow P(x))\)

\((\exists x \in A)(P(x))\) is equiv. to: \((\exists x)(x \in A \land P(x))\)

\textbf{Multiple Quantifiers}

Many statements will have multiple quantifiers. When this is the case, it is important to be very careful with the order.

To examine this idea:

\(P(x, y)\) is a predicate with two free variables \((x \text{ & } y)\)

\((\exists y \in B) (P(x, y))\) is a predicate with \underline{one} free variable \((x)\)

\((\forall x \in A) (\exists y \in B) (P(x, y))\) is a proposition/predicate with no free variables.

Now: \((\forall x \in A) (\exists y \in B) (P(x, y))\) is true exactly when:

\(TS_A \left( (\exists y \in B) (P(x, y)) \right) = A\)

That is, when:

\(\left{ x \in A \mid (\exists y \in B) (P(x, y)) \right} = A\)

so that for every \(\hat{x} \in A\), we have that \((\exists y \in B) (P(\hat{x}, y))\) is true,

and that for every \(\hat{x} \in A\), we have that:

\(TS_B \left( P(\hat{x}, y) \right) \neq \emptyset\).

This means if we choose some \(\hat{x} \in A\), we will be able to find a value of \(y \in B\) that makes \(P(\hat{x}, y)\) true. (And the choice of \(\hat{x} \in A\) doesn’t matter)

\hfill 14

\(TS_A (\exists y \in B)(P(x,y)) \rightarrow\) The set of all \(x \in A\) for which \((\exists y \in B)(P(x,y))\) is true.

\((\forall x \in \mathbb{R})\ (\exists y \in \mathbb{R})\ (x+y=0) \rightarrow True\)

\(x=4 \rightarrow y=-4\) \(x=17.2 \rightarrow y = -17.2\)

\((\exists y \in \mathbb{R})\ (\forall x \in \mathbb{R})\ (x+y=0) \rightarrow False\)

Consider \(y=7\) \((\forall x \in \mathbb{R})\ (x+7=0)\)

Consider \(y=0\) \((\forall x \in \mathbb{R})\ (x+0=0)\)

\((\exists x \in \mathbb{R}) (\forall y \in \mathbb{R}) (x \leq y^2)\)

Consider \(x=1\)

\((\forall y \in \mathbb{R}) (1 \leq y^2) \rightarrow \text{False}\)

Consider \(x = -1\)

\((\forall y \in \mathbb{R}) (-1 \leq y^2) \rightarrow \text{True.}\)

This tells us that \(x = -1\) is in \(TS_{\mathbb{R}} ((\forall y \in \mathbb{R}) (x \leq y^2))\)

\(\neq \emptyset\)

\((\forall x \in \mathbb{R}) (\exists! y \in \mathbb{R}) (x+y=c) \rightarrow \text{True}.\)

\(\text{Next: } (\exists x \in A) (\forall y \in B) (P(x,y)) \text{ is true exactly when:}\) $$TS_A((\forall y \in B)(P(x,y))) \neq \emptyset$$ \(\text{That is, when there is at least one value of } x \in A \text{ such that }\) $$(\forall y \in B) (P(x,y)) \text{ is true.}$$ \(\text{Let } \hat{x} \in A \text{ be one of such values, i.e., so that } (\forall y \in B) (P(\hat{x},y)) \text{ is true. }\) \text{This means that:} $$TS_B (P(\hat{x},y)) = B$$ \text{That is:} $${y \in B \mid P(\hat{x},y) } = B$$ \(\text{This means that for } \hat{x} \in A, \text{ we have that } P(\hat{x},y) \text{ is true for every } y \in B.\)

\((\exists y \in \mathbb{R})(\forall x \in \mathbb{R})(x+y=0)\).

\((\forall x \in \mathbb{R})(\exists y \in \mathbb{R})(x+y=0)\) will be true if for every/any \(\hat{x} \in \mathbb{R}\) we can find a value \(y \in \mathbb{R}\) such that \(x+y=0\).

This is the case: For any \(\hat{x} \in \mathbb{R}\), we can let \(y = -\hat{x}\). Note that as \(\hat{x} \in \mathbb{R}\), \(-\hat{x}\) is also real so \(y \in \mathbb{R}\). Also: \(\hat{x} + y = \hat{x} + (-\hat{x}) = \hat{x} - \hat{x} = 0\).

e.g. If \(\hat{x} = 3\), we let \(y=-3\). If \(\hat{x} = -10.5\), we let \(y=10.5\).

\((\exists y \in \mathbb{R})(\forall x \in \mathbb{R})(x+y=0)\) will be true if we can find some \(\hat{y} \in \mathbb{R}\) such that every \(x \in \mathbb{R}\) will make \(x + \hat{y} = 0\).

This is not the case! No matter what \(\hat{y} \in \mathbb{R}\) we choose, there is only one value of \(x\) that will give \(x + \hat{y} = 0\) (so we will not have \(x + \hat{y} = 0\) for every real number \(x\)).

e.g. If we tried letting \(\hat{y} = 3\), it will not be the case that \((\forall x \in \mathbb{R})(x + 3 = 0)\) will be true.

\(A \Rightarrow (B \vee C)\) is equiv. to \((A \wedge \neg C) \Rightarrow B\)

Examples: \((\exists x \in \mathbb{R}) (\forall y \in \mathbb{R}) (x + y = y) \text{vs.} (\forall y \in \mathbb{R}) (\exists x \in \mathbb{R}) (x + y = y)\)

\((\exists x \in \mathbb{R}) (\forall y \in \mathbb{R}) (x + y = y) \text{ is true:}\)

Notice that: \(TS_{\mathbb{R}}(0 + y = y) = \mathbb{R}\)

so that: \((\forall y \in \mathbb{R}) (0 + y = y) \text{ is true.}\)

This means that when \(x = 0\), \((\forall y \in \mathbb{R}) (x + y = y) \text{ is true,}\)

so that \(x=0\) is in the truth set of \((\forall y \in \mathbb{R}) (x + y = y)\).

This tells us that \(TS_{\mathbb{R}}((\forall y \in \mathbb{R}) (x + y = y)) \neq \emptyset\), so that:

\((\exists x \in \mathbb{R}) (\forall y \in \mathbb{R}) (x + y = y) \text{ is } \underline{\text{true}}.\)

\((\forall y \in \mathbb{R}) (\exists x \in \mathbb{R}) (x + y = y) \text{ is also true:}\)

No matter what value of \(\hat{y} \in \mathbb{R}\) that we choose, notice that \(0 + \hat{y} = \hat{y},\)

so that \(0\) is in \(TS_{\mathbb{R}} (x + \hat{y} = \hat{y})\), so that \(TS_{\mathbb{R}} (x + \hat{y} = \hat{y}) \neq \emptyset\).

This gives us that \((\exists x \in \mathbb{R}) (x + \hat{y} = \hat{y}) \text{ is true.}\)

As the choice of \(\hat{y} \in \mathbb{R}\) didn’t matter, and \(\hat{y}\) is in the truth set of \((\exists x \in \mathbb{R})(x + y = y)\),

we have that \(TS_{\mathbb{R}}((\exists x \in \mathbb{R})(x + y = y)) = \mathbb{R}\), and:

\((\forall y \in \mathbb{R}) (\exists x \in \mathbb{R})(x + y = y) \text{ is } \underline{\text{true}}\).

17

A Few Important Equivalencies.

\medskip

\((A \Rightarrow B)\) is equiv. to: \((\neg B \Rightarrow \neg A)\) (The contraposition)

and also: \((\neg A \vee B)\)

\medskip

\(\neg (A \vee B)\) is equiv. to: \((\neg A \wedge \neg B) \left. \begin{aligned} {} \ {} \end{aligned} \right} \text{De Morgan’s Laws}\)

\(\neg (A \wedge B)\) is equiv. to: \((\neg A \vee \neg B) \)

\medskip

\(A \wedge (B \vee C)\) is equiv. to: \(((A \wedge B) \vee (A \wedge C)) \left. \begin{aligned} {} \ {} \end{aligned} \right} \text{Distribution}\)

\(A \vee (B \wedge C)\) is equiv. to: \(((A \vee B) \wedge (A \vee C))\)

\medskip

\(\neg (A \Rightarrow B)\) is equiv. to: \((A \wedge \neg B)\)

\medskip

\((\neg A \Rightarrow (B \wedge \neg B))\) is equiv. to: \(A\)

\medskip

\(A \Rightarrow (B \vee C)\) is equiv. to: \((A \wedge \neg B) \Rightarrow C\)

\medskip

\((A \vee B) \Rightarrow C\) is equiv. to: \((A \Rightarrow C) \wedge (B \Rightarrow C)\)

\medskip

\(A \Rightarrow (B \wedge C)\) is equiv. to: \((A \Rightarrow B) \wedge (A \Rightarrow C)\)

\medskip

\(A \Rightarrow (B \Rightarrow C)\) is equiv. to: \((A \wedge B) \Rightarrow C\)

\medskip

\(\neg (\forall x \in A) (P(x))\) is equiv. to: \((\exists x \in A) (\neg P(x))\)

\medskip

\(\neg (\exists x \in A) (P(x))\) is equiv. to: \((\forall x \in A) (\neg P(x))\)

\medskip

\(\neg\neg A\) is equiv. to: \(A\) (Double negation)

\begin{align*} &\neg (\forall x \in A) (P(x) \Rightarrow Q(x)) \ &\left(\exists x \in A\right) \left(\neg \left(P(x) \Rightarrow Q(x)\right)\right) \ &\left(\exists x \in A\right) \left(P(x) \wedge \neg Q(x)\right) \ &\neg (A \Rightarrow B) \ &(A \wedge \neg B) \end{align*}

\(\neg (\forall x \in A) (P(x)) \text{ is true exactly when } (\forall x \in A) (P(x)) \text{ is false.} \\) $\text{is true exactly when } TS_A (P(x)) \neq A \ TS_A(P(x))=\emptyset \neq A\$ \(\text{is true exactly when there is some value } \hat{x} \in A \text{ s/t } P(x) \text{ is not true.}\) \ \(\text{is true exactly when there is some value } \hat{x} \in A \text{ s/t } P(x) \text{ is false} \)\ \(\text{is true exactly when } \text{ there is some } \hat{x} \in A \text{ s/t } \neg P(x) \text{ is true.}\) \ \(\text{is true exactly when } \text{ there is some } \hat{x} \in A \text{ is } TS_A (\neg P(x)).\) \ \(\text{is true exactly when } TS_A (\neg (P(x))) \neq \emptyset \)\ \( \text{is true exactly when } (\exists x \in A) (\neg P(x)) \text{ is true.}\)

[ \neg (\exists x \in A) (P(x)) \ (\forall x \in A) (\neg P(x)) ]

\begin{align*} & (\forall x \in \mathbb{Q}) (x^2 \ge 0) & x^3 \ge 0 \text{ vs. } y^3 \ge 0 \ & (\forall z \in \mathbb{Q}) (z^2 \ge 0) & (\forall x \in \mathbb{N}) (x \ge y) \ & (\forall y \in \mathbb{Q}) (y^2 \ge 0) & (\forall w \in \mathbb{N}) (w \ge y) \ & (\forall \xi \in \mathbb{Q}) (\xi^2 \ge 0) & (\forall x \in \mathbb{N}) (x \ge z) \ & & \text{Free Variables } y \text{ & } z \end{align*}

[ \neg (\exists! , x \in A) (P(x)) ]

\(\) Nothing that makes P(x) true more than one does.

[ \left[ (\forall x \in A) (\neg P(x)) \right] \vee (\exists y \in A) (\exists z \in A) (P(y) \wedge P(z) \wedge y \neq z)]

Simplifying Denials/Negations. \ Goal: We want the only instances of the negation symbol “\(\neg\)” immediately preceding the predicate/propositional symbols.

Example: \(\neg (\forall x \in A)(\forall y \in B)(\exists z \in C) ((P(x) \vee Q(y)) \Rightarrow (R(x, y, z)))\)

\((\exists x \in A)(\neg (\forall y \in B)(\exists z \in C) ((P(x) \vee Q(y)) \Rightarrow (R(x, y, z))))\)

\((\exists x \in A)(\exists y \in B)(\neg (\exists z \in C) ((P(x) \vee Q(y)) \Rightarrow (R(x, y, z))))\)

\((\exists x \in A)(\exists y \in B)(\forall z \in C)(\neg ((P(x) \vee Q(y)) \Rightarrow (R(x, y, z))))\)

\((\exists x \in A)(\exists y \in B)(\forall z \in C)((P(x) \vee Q(y)) \wedge \neg R(x, y, z))\) \ \hspace{7cm} \(\uparrow\) \ \hspace{6.3cm} Immediately before predicate symbol R.

Example: \(\neg (\exists a \in A)(\forall b \in B)(\exists c \in C)(\neg P(a) \vee (R(b) \Rightarrow S(c)))\)

\((\forall a \in A)(\exists b \in B)(\forall c \in C)(\neg(\neg P(a) \vee (R(b) \Rightarrow S(c))))\)

\((\forall a \in A)(\exists b \in B)(\forall c \in C)(\neg \neg P(a) \wedge \neg (R(b) \Rightarrow S(c)))\)

\((\forall a \in A)(\exists b \in B)(\forall c \in C)(P(a) \wedge (R(b) \wedge \neg S(c)))\)

% \hspace{10cm} 19

Example: We will find/simplify a denial/negation of \((\exists! x \in A) (P(x))\)

\(\neg (\exists! x \in A) (P(x))\) is equivalent to: \begin{align*} &\neg \left( (\exists x \in A) (P(x)) \wedge (\forall y \in A) (\forall z \in A) ((P(y) \wedge P(z)) \Rightarrow y=z) \right) \ &\neg (\exists x \in A) (P(x)) \vee \neg (\forall y \in A) (\forall z \in A) ((P(y) \wedge P(z)) \Rightarrow y = z) \ &(\forall x \in A) (\neg P(x)) \vee (\exists y \in A) (\exists z \in A) \neg ((P(y) \wedge P(z)) \Rightarrow y = z) \ &(\forall x \in A) (\neg P(x)) \vee (\exists y \in A) (\exists z \in A) ((P(y) \wedge P(z)) \wedge \neg (y = z)) \ &(\forall x \in A) (\neg P(x)) \vee (\exists y \in A) (\exists z \in A) (P(y) \wedge P(z) \wedge y \neq z) \end{align*}

“Either every \(x \in A\) makes \(P(x)\) false or there are two values (or more) that make \(P\) true that are different.”

\fbox{\parbox{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}{ Comment: \((A \wedge B) \wedge C\) is equiv. to \(A \wedge (B \wedge C)\) and \(A \wedge B \wedge C\)

\((A \vee B) \vee C\) is equiv. to \(A \vee (B \vee C)\) and \(A \vee B \vee C\) (Associativity)

\(A \wedge B\) is equiv. to \(B \wedge A\)

\(A \vee B\) is equiv. to \(B \vee A\) (Commutativity) }}