0.2 Mathematical Statements 数学语句

本页为「中英对照」样章（段段对照：原文在下，译文紧随其后）。译自 LibreTexts · Discrete Mathematics (Levin) 第 0.2 章。公式经 MathJax 渲染，自定义宏已注入。

Investigate! 探究！

While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a knight, who always tells the truth, or a knave, who always lies. The trolls will not let you pass until you correctly identify each as either a knight or a knave. Each troll makes a single statement:

• Troll 1: If I am a knave, then there are exactly two knights here.
• Troll 2: Troll 1 is lying.
• Troll 3: Either we are all knaves or at least one of us is a knight.

• 巨魔 1：如果我是无赖，那么这里恰好有两名骑士。
• 巨魔 2：巨魔 1 在说谎。
• 巨魔 3：我们要么全是无赖，要么至少有一个是骑士。

Which troll is which?

In order to do mathematics, we must be able to talk and write about mathematics. Perhaps your experience with mathematics so far has mostly involved finding answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process. Communication in mathematics requires more precision than many other subjects, and thus we should take a few pages here to consider the basic building blocks: mathematical statements.

Atomic and Molecular Statements 原子命题与复合命题

A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular.

Example 1

These are statements (in fact, atomic statements):

• Telephone numbers in the USA have 10 digits.
• The moon is made of cheese.
• 42 is a perfect square.
• Every even number greater than 2 can be expressed as the sum of two primes.
• $3+7 = 12$

• 美国的电话号码有 10 位数字。
• 月亮是由奶酪做成的。
• 42 是一个完全平方数。
• 任何大于 2 的偶数都可以表示为两个素数之和。
• $3+7 = 12$

And these are not statements:

• Would you like some cake?
• The sum of two squares.
• $1+3+5+7+\cdots+2n+1\text{.}$
• Go to your room!
• $3+x = 12$

• 你想来点蛋糕吗？
• 两个平方数之和。
• $1+3+5+7+\cdots+2n+1\text{。}$
• 回你的房间去！
• $3+x = 12$

The reason the last sentence is not a statement is because it contains a variable. Depending on what $x$ is, the sentence is either true or false, but right now it is neither. One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done in a number of ways. For example, “$3+x = 12$ where $x = 9$” is a true statement, as is “$3+x = 12$ for some value of $x$.” This is an example of quantifying over a variable, which we will discuss more in a bit.

You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement:

Telephone numbers in the USA have 10 digits and 42 is a perfect square.

Note that we can break this down into two smaller statements. The two shorter statements are connected by an “and.” We will consider 5 connectives: “and” (Sam is a man and Chris is a woman), “or” (Sam is a man or Chris is a woman), “if…, then…” (if Sam is a man, then Chris is a woman), “if and only if” (Sam is a man if and only if Chris is a woman), and “not” (Sam is not a man). The first four are called binary connectives (because they connect two statements) while “not” is an example of a unary connective (since it applies to a single statement).

Which connective we use to modify statement(s) will determine the truth value of the molecular statement (that is, whether the statement is true or false), based on the truth values of the statements being modified. It is important to realize that we do not need to know what the parts actually say, only whether those parts are true or false. So to analyze logical connectives, it is enough to consider propositional variables (sometimes called sentential variables), usually capital letters in the middle of the alphabet: $P, Q, R, S, \ldots\text{.}$ These are variables that can take on one of two values: T or F. We also have symbols for the logical connectives: $\wedge\text{,}$ $\vee\text{,}$ $\imp\text{,}$ $\iff\text{,}$ $\neg\text{.}$

Logical Connectives

• $P \wedge Q$ means $P$ and $Q\text{,}$ called a conjunction.
• $P \vee Q$ means $P$ or $Q\text{,}$ called a disjunction.
• $P \imp Q$ means if $P$ then $Q\text{,}$ called an implication or conditional.
• $P \iff Q$ means $P$ if and only if $Q\text{,}$ called a biconditional.
• $\neg P$ means not $P\text{,}$ called a negation.

• $P \wedge Q$ 表示 $P$ 并且 $Q\text{，}$称为合取（conjunction）。
• $P \vee Q$ 表示 $P$ 或 $Q\text{，}$称为析取（disjunction）。
• $P \imp Q$ 表示若 $P$ 则 $Q\text{，}$称为蕴涵（implication）或条件命题（conditional）。
• $P \iff Q$ 表示 $P$ 当且仅当 $Q\text{，}$称为双条件命题（biconditional）。
• $\neg P$ 表示非 $P\text{，}$称为否定（negation）。

Truth Conditions for Connectives

• $P \wedge Q$ is true when both $P$ and $Q$ are true
• $P \vee Q$ is true when $P$ or $Q$ or both are true.
• $P \imp Q$ is true when $P$ is false or $Q$ is true or both.
• $P \iff Q$ is true when $P$ and $Q$ are both true, or both false.
• $\neg P$ is true when $P$ is false.

• $P \wedge Q$ 在 $P$ 与 $Q$ 同时为真时为真。
• $P \vee Q$ 在 $P$ 为真、或 $Q$ 为真、或二者皆为真时为真。
• $P \imp Q$ 在 $P$ 为假、或 $Q$ 为真、或二者皆成立时为真。
• $P \iff Q$ 在 $P$ 与 $Q$ 同真、或同假时为真。
• $\neg P$ 在 $P$ 为假时为真。

Note that for us, or is the inclusive or (and not the sometimes used exclusive or) meaning that $P \vee Q$ is in fact true when both $P$ and $Q$ are true. As for the other connectives, “and” behaves as you would expect, as does negation. The biconditional (if and only if) might seem a little strange, but you should think of this as saying the two parts of the statements are equivalent. This leaves only the conditional $P \imp Q$ which has a slightly different meaning in mathematics than it does in ordinary usage. However, implications are so common and useful in mathematics, that we must develop fluency with their use, and as such, they deserve their own subsection.

Implications 蕴涵（条件命题）

An implication or conditional is a molecular statement of the form

$\begin{equation*} P \imp Q \end{equation*}$

where $P$ and $Q$ are statements. We say that

• $P$ is the hypothesis (or antecedent).
• $Q$ is the conclusion (or consequent).

• $P$ 为前提（hypothesis，或称前件 antecedent）。
• $Q$ 为结论（conclusion，或称后件 consequent）。

An implication is true provided $P$ is false or $Q$ is true (or both), and false otherwise. In particular, the only way for $P \imp Q$ to be false is for $P$ to be true and $Q$ to be false.

Easily the most common type of statement in mathematics is the conditional, or implication. Even statements that do not at first look like they have this form conceal an implication at their heart. Consider the Pythagorean Theorem. Many a college freshman would quote this theorem as “$a^2 + b^2 = c^2\text{.}$” This is absolutely not correct. For one thing, that is not a statement since it has three variables in it. Perhaps they imply that this should be true for any values of the variables? So $1^2 + 5^2 = 2^2\text{???}$ How can we fix this? Well, the equation is true as long as $a$ and $b$ are the legs or a right triangle and $c$ is the hypotenuse. In other words:

If $a$ and $b$ are the legs of a right triangle with hypotenuse $c\text{,}$ then $a^2 + b^2 = c^2\text{.}$

This is a reasonable way to think about implications: our claim is that the conclusion (“then” part) is true, but on the assumption that the hypothesis (“if” part) is true. We make no claim about the conclusion in situations when the hypothesis is false.

Still, it is important to remember that an implication is a statement, and therefore is either true or false. The truth value of the implication is determined by the truth values of its two parts. To agree with the usage above, we say that an implication is true either when the hypothesis is false, or when the conclusion is true. This leaves only one way for an implication to be false: when the hypothesis is true and the conclusion is false.

Example 2

Consider the statement:

If Bob gets a 90 on the final, then Bob will pass the class.

This is definitely an implication: $P$ is the statement “Bob gets a 90 on the final,” and $Q$ is the statement “Bob will pass the class.”

Suppose I made that statement to Bob. In what circumstances would it be fair to call me a liar? What if Bob really did get a 90 on the final, and he did pass the class? Then I have not lied; my statement is true. However, if Bob did get a 90 on the final and did not pass the class, then I lied, making the statement false. The tricky case is this: what if Bob did not get a 90 on the final? Maybe he passes the class, maybe he doesn't. Did I lie in either case? I think not. In these last two cases, $P$ was false, and the statement $P \imp Q$ was true. In the first case, $Q$ was true, and so was $P \imp Q\text{.}$ So $P \imp Q$ is true when either $P$ is false or $Q$ is true.

Just to be clear, although we sometimes read $P \imp Q$ as “$P$ implies $Q$,” we are not insisting that there is some causal relationship between the statements $P$ and $Q\text{.}$ In particular, if you claim that $P \imp Q$ is false, you are not saying that $P$ does not imply $Q\text{,}$ but rather that $P$ is true and $Q$ is false.

Example 3

Decide which of the following statements are true and which are false. Briefly explain.

1. $0=1 \imp 1=1$
2. $1=1 \imp $ most horses have 4 legs
3. If 8 is a prime number, then the 7624th digit of $\pi$ is an 8.
4. If the 7624th digit of $\pi$ is an 8, then $2+2 = 4$

1. $0=1 \imp 1=1$
2. $1=1 \imp $ 大多数马有 4 条腿
3. 如果 8 是素数，那么 $\pi$ 的第 7624 位数字是 8。
4. 如果 $\pi$ 的第 7624 位数字是 8，那么 $2+2 = 4$

Solution

All four of the statements are true. Remember, the only way for an implication to be false is for the if part to be true and the then part to be false.

1. Here the hypothesis is false and the conclusion is true, so the implication is true.
2. Here both the hypothesis and the conclusion is true, so the implication is true. It does not matter that there is no meaningful connection between the true mathematical fact and the fact about horses.
3. I have no idea what the 7624th digit of $\pi$ is, but this does not matter. Since the hypothesis is false, the implication is automatically true.
4. Similarly here, regardless of the truth value of the hypothesis, the conclusion is true, making the implication true.

1. 此处前提为假、结论为真，故蕴涵为真。
2. 此处前提与结论均为真，故蕴涵为真。真实的数学事实与关于马的事实之间是否存在有意义的联系，并不重要。
3. 我并不知道 $\pi$ 的第 7624 位是什么，但这无关紧要。由于前提为假，蕴涵自动为真。
4. 同理，无论前提真值如何，结论为真，故蕴涵为真。

It is important to understand the conditions under which an implication is true not only to decide whether a mathematical statement is true, but in order to prove that it is. Proofs might seem scary (especially if you have had a bad high school geometry experience) but all we are really doing is explaining (very carefully) why a statement is true. If you understand the truth conditions for an implication, you already have the outline for a proof.

Direct Proofs of Implications 蕴涵的直接证明

To prove an implication $P \imp Q\text{,}$ it is enough to assume $P\text{,}$ and from it, deduce $Q\text{.}$

There are other techniques to prove statements (implications and others) that we will encounter throughout our studies, and new proof techniques are discovered all the time. Direct proof is the easiest and most elegant style of proof and has the advantage that such a proof often does a great job of explaining why the statement is true.

Example 4

Prove: If two numbers $a$ and $b$ are even, then their sum $a+b$ is even.

Solution

Suppose the numbers $a$ and $b$ are even. This means that $a = 2k$ and $b=2j$ for some integers $k$ and $j\text{.}$ The sum is then $a+b = 2k+2j = 2(k+j)\text{.}$ Since $k+j$ is an integer, this means that $a+b$ is even.

Notice that since we get to assume the hypothesis of the implication we immediately have a place to start. The proof proceeds essentially by repeatedly asking and answering, “what does that mean?” ∎ This sort of argument shows up outside of math as well. If you ever found yourself starting an argument with “hypothetically, let's assume …,” then you have attempted a direct proof of your desired conclusion.

Since implications are so prevalent in mathematics, we have some special language to help discuss them:

Converse and Contrapositive 逆命题与逆否命题

• The converse of an implication $P \imp Q$ is the implication $Q \imp P\text{.}$ The converse is NOT logically equivalent to the original implication. That is, whether the converse of an implication is true is independent of the truth of the implication.
• The contrapositive of an implication $P \imp Q$ is the statement $\neg Q \imp \neg P\text{.}$ An implication and its contrapositive are logically equivalent (they are either both true or both false).

• 蕴涵 $P \imp Q$ 的逆命题（converse）是 $Q \imp P\text{。}$ 逆命题与原蕴涵在逻辑上不等价。也就是说，逆命题的真假与原蕴涵的真假无关。
• 蕴涵 $P \imp Q$ 的逆否命题（contrapositive）是 $\neg Q \imp \neg P\text{。}$ 一个蕴涵与其逆否命题在逻辑上等价（二者同真或同假）。

Mathematics is overflowing with examples of true implications with a false converse. If a number greater than 2 is prime, then that number is odd. However, just because a number is odd does not mean it is prime. If a shape is a square, then it is a rectangle. But it is false that if a shape is a rectangle, then it is a square. While this happens often, it does not always happen. For example, the Pythagorean theorem has a true converse: if $a^2 + b^2 = c^2\text{,}$ then the triangle with sides $a\text{,}$ $b\text{,}$ and $c$ is a right triangle. Whenever you encounter an implication in mathematics, it is always reasonable to ask whether the converse is true.

The contrapositive, on the other hand, always has the same truth value as its original implication. This can be very helpful in deciding whether an implication is true: often it is easier to analyze the contrapositive.

Example 5

True or false: If you draw any nine playing cards from a regular deck, then you will have at least three cards all of the same suit. Is the converse true?

Solution

True. The original implication is a little hard to analyze because there are so many different combinations of nine cards. But consider the contrapositive: If you don't have at least three cards all of the same suit, then you don't have nine cards. It is easy to see why this is true: you can at most have two cards of each of the four suits, for a total of eight cards (or fewer).

The converse: If you have at least three cards all of the same suit, then you have nine cards. This is false. You could have three spades and nothing else. Note that to demonstrate that the converse (an implication) is false, we provided an example where the hypothesis is true (you do have three cards of the same suit), but where the conclusion is false (you do not have nine cards).

Understanding converses and contrapositives can help understand implications and their truth values:

Example 6

Suppose I tell Sue that if she gets a 93% on her final, then she will get an A in the class. Assuming that what I said is true, what can you conclude in the following cases:

1. Sue gets a 93% on her final.
2. Sue gets an A in the class.
3. Sue does not get a 93% on her final.
4. Sue does not get an A in the class.

1. 苏期末考了 93%。
2. 苏得到了 A。
3. 苏期末没考 93%。
4. 苏没得到 A。

Solution

Note first that whenever $P \imp Q$ and $P$ are both true statements, $Q$ must be true as well. For this problem, take $P$ to mean “Sue gets a 93% on her final” and $Q$ to mean “Sue will get an A in the class.”

1. We have $P \imp Q$ and $P\text{,}$ so $Q$ follows. Sue gets an A.
2. You cannot conclude anything. Sue could have gotten the A because she did extra credit for example. Notice that we do not know that if Sue gets an A, then she gets a 93% on her final. That is the converse of the original implication, so it might or might not be true.
3. The contrapositive of the converse of $P \imp Q$ is $\neg P \imp \neg Q\text{,}$ which states that if Sue does not get a 93% on the final, then she will not get an A in the class. But this does not follow from the original implication. Again, we can conclude nothing. Sue could have done extra credit.
4. What would happen if Sue does not get an A but did get a 93% on the final? Then $P$ would be true and $Q$ would be false. This makes the implication $P \imp Q$ false! It must be that Sue did not get a 93% on the final. Notice now we have the implication $\neg Q \imp \neg P$ which is the contrapositive of $P \imp Q\text{.}$ Since $P \imp Q$ is assumed to be true, we know $\neg Q \imp \neg P$ is true as well.

1. 已知 $P \imp Q$ 与 $P\text{，}$故可推出 $Q$。苏得到了 A。
2. 你无法得出任何结论。苏得到 A 可能是因为做了附加分等等。注意，我们并不知道「若苏得到 A，则她期末考了 93%」是否成立。那是原蕴涵的逆命题，故它可能为真也可能为假。
3. $P \imp Q$ 之逆命题的逆否命题为 $\neg P \imp \neg Q\text{，}$它表示：若苏期末没考 93%，则她不会得到 A。但这并不能由原蕴涵推出。同样，我们什么也推不出。苏可能做了附加分。
4. 如果苏没得到 A、却考了 93% 会怎样？那么 $P$ 为真而 $Q$ 为假。这将使蕴涵 $P \imp Q$ 为假！因此必然是：苏期末没考 93%。现在我们得到蕴涵 $\neg Q \imp \neg P$，它是 $P \imp Q$ 的逆否命题。既然假定 $P \imp Q$ 为真，我们便知 $\neg Q \imp \neg P$ 亦为真。

As we said above, an implication is not logically equivalent to its converse, but it is possible that both are true. In this case, when both $P \imp Q$ and $Q \imp P$ are true, we say that $P$ and $Q$ are equivalent. This is the biconditional we mentioned earlier:

If and only if 当且仅当

$P \iff Q$ is logically equivalent to $(P \imp Q) \wedge (Q \imp P)\text{.}$

Example: Given an integer $n\text{,}$ it is true that $n$ is even if and only if $n^2$ is even. That is, if $n$ is even, then $n^2$ is even, as well as the converse: if $n^2$ is even, then $n$ is even.

You can think of “if and only if” statements as having two parts: an implication and its converse. We might say one is the “if” part, and the other is the “only if” part. We also sometimes say that “if and only if” statements have two directions: a forward direction $(P \imp Q)$ and a backwards direction $(P \leftarrow Q\text{,}$ which is really just sloppy notation for $Q \imp P$.

Let's think a little about which part is which. Is $P \imp Q$ the “if” part or the “only if” part? Perhaps we should look at an example:

Example 7

Suppose it is true that I sing if and only if I'm in the shower. We know this means both that if I sing, then I'm in the shower, and also the converse, that if I'm in the shower, then I sing. Let $P$ be the statement, “I sing,” and $Q$ be, “I'm in the shower.” So $P \imp Q$ is the statement “if I sing, then I'm in the shower.” Which part of the if and only if statement is this?

What we are really asking is what is the meaning of “I sing if I'm in the shower” and “I sing only if I'm in the shower.” When is the first one (the “if” part) false? When I am in the shower but not singing. That is the same condition on being false as the statement “if I'm in the shower, then I sing.” So the “if” part is $Q \imp P\text{.}$ On the other hand, to say, “I sing only if I'm in the shower” is equivalent to saying “if I sing, then I'm in the shower,” so the “only if” part is $P \imp Q\text{.}$

It is not terribly important to know which part is the “if” or “only if” part, but this does get at something very, very important: there are many ways to state an implication! The problem is, since these are all different ways of saying the same implication, we cannot use truth tables to analyze the situation. Instead, we just need good English skills.

Example 8

Rephrase the implication, “if I dream, then I am asleep” in as many different ways as possible. Then do the same for the converse.

Solution

The following are all equivalent to the original implication:

1. I am asleep if I dream.
2. I dream only if I am asleep.
3. In order to dream, I must be asleep.
4. To dream, it is necessary that I am asleep.
5. To be asleep, it is sufficient to dream.
6. I am not dreaming unless I am asleep.

1. 如果我在做梦，那么我在睡觉。
2. 我只有在睡觉时才会做梦。
3. 要做梦，我必须处于睡眠中。
4. 做梦的必要条件是我在睡觉。
5. 只要做梦，就足以说明我在睡觉。
6. 除非我在睡觉，否则我没有在做梦。

The following are equivalent to the converse (if I am asleep, then I dream):

1. I dream if I am asleep.
2. I am asleep only if I dream.
3. It is necessary that I dream in order to be asleep.
4. It is sufficient that I be asleep in order to dream.
5. If I don't dream, then I'm not asleep.

1. 如果我在睡觉，那么我在做梦。
2. 我只有在做梦时才睡觉。
3. 要处于睡眠中，做梦是必要条件。
4. 要做梦，处于睡眠中就足够了。
5. 如果我没有做梦，那么我不在睡觉。

Hopefully you agree with the above example. We include the “necessary and sufficient” versions because those are common when discussing mathematics. In fact, let's agree once and for all what they mean:

Necessary and Sufficient 必要条件与充分条件

• “$P$ is necessary for $Q$” means $Q \imp P\text{.}$
• “$P$ is sufficient for $Q$” means $P \imp Q\text{.}$
• If $P$ is necessary and sufficient for $Q\text{,}$ then $P \iff Q\text{.}$

• 「$P$ 是 $Q$ 的必要条件」表示 $Q \imp P\text{。}$
• 「$P$ 是 $Q$ 的充分条件」表示 $P \imp Q\text{。}$
• 若 $P$ 对 $Q$ 既必要又充分，则 $P \iff Q\text{。}$

To be honest, I have trouble with these if I'm not very careful. I find it helps to have an example in mind:

Example 9

Recall from calculus, if a function is differentiable at a point $c\text{,}$ then it is continuous at $c\text{,}$ but that the converse of this statement is not true (for example, $f(x) = |x|$ at the point 0). Restate this fact using “necessary and sufficient” language.

Solution

It is true that in order for a function to be differentiable at a point $c\text{,}$ it is necessary for the function to be continuous at $c\text{.}$ However, it is not necessary that a function be differentiable at $c$ for it to be continuous at $c\text{.}$

It is true that to be continuous at a point $c\text{,}$ it is sufficient that the function be differentiable at $c\text{.}$ However, it is not the case that being continuous at $c$ is sufficient for a function to be differentiable at $c\text{.}$

Thinking about the necessity and sufficiency of conditions can also help when writing proofs and justifying conclusions. If you want to establish some mathematical fact, it is helpful to think what other facts would be enough (be sufficient) to prove your fact. If you have an assumption, think about what must also be necessary if that hypothesis is true.

Quantifiers 量词

Investigate!

Consider the statement below. Decide whether any are equivalent to each other, or whether any imply any others.

1. You can fool some people all of the time.
2. You can fool everyone some of the time.
3. You can always fool some people.
4. Sometimes you can fool everyone.

1. 你可以一直愚弄某些人。
2. 你可以有时愚弄所有人。
3. 你总能愚弄某些人。
4. 有时你可以愚弄所有人。

It would be nice to use variables in our mathematical sentences. For example, suppose we wanted to claim that if $n$ is prime, then $n+7$ is not prime. This looks like an implication. I would like to write something like

$\begin{equation*} P(n) \imp \neg P(n+7) \end{equation*}$

where $P(n)$ means “$n$ is prime.” But this is not quite right. For one thing, because this sentence has a free variable (that is, a variable that we have not specified anything about), it is not a statement. Now, if we plug in a specific value for $n\text{,}$ we do get a statement. In fact, it turns out that no matter what value we plug in for $n\text{,}$ we get a true implication. What we really want to say is that for all values of $n\text{,}$ if $n$ is prime, then $n+7$ is not. We need to quantify the variable.

Although there are many types of quantifiers in English (e.g., many, few, most, etc.) in mathematics we, for the most part, stick to two: existential and universal.

Universal and Existential Quantifiers 全称量词与存在量词

The existential quantifier is $\exists$ and is read “there exists” or “there is.” For example,

$\exists x (x < 0)$

asserts that there is a number less than 0.

The universal quantifier is $\forall$ and is read “for all” or “every.” For example,

$\begin{equation*} \forall x (x \ge 0) \end{equation*}$

asserts that every number is greater than or equal to 0.

As with all mathematical statements, we would like to decide whether quantified statements are true or false. Consider the statement

$\begin{equation*} \forall x \exists y (y < x). \end{equation*}$

You would read this, “for every $x$ there is some $y$ such that $y$ is less than $x\text{.}$” Is this true? The answer depends on what our domain of discourse is: when we say “for all” $x\text{,}$ do we mean all positive integers or all real numbers or all elements of some other set? Usually this information is implied. In discrete mathematics, we almost always quantify over the natural numbers, 0, 1, 2, …, so let's take that for our domain of discourse here.

For the statement to be true, we need it to be the case that no matter what natural number we select, there is always some natural number that is strictly smaller. Perhaps we could let $y$ be $x-1\text{?}$ But here is the problem: what if $x = 0\text{?}$ Then $y = -1$ and that is not a number! (in our domain of discourse). Thus we see that the statement is false because there is a number which is less than or equal to all other numbers. In symbols,

$\begin{equation*} \exists x \forall y (y \ge x). \end{equation*}$

To show that the original statement is false, we proved that the negation was true. Notice how the negation and original statement compare. This is typical.

Quantifiers and Negation 量词与否定

• $\neg \forall x P(x)$ is equivalent to $\exists x \neg P(x)\text{.}$
• $\neg \exists x P(x)$ is equivalent to $\forall x \neg P(x) \text{.}$

• $\neg \forall x P(x)$ 等价于 $\exists x \neg P(x)\text{。}$
• $\neg \exists x P(x)$ 等价于 $\forall x \neg P(x) \text{。}$

Essentially, we can pass the negation symbol over a quantifier, but that causes the quantifier to switch type. This should not be surprising: if not everything has a property, then something doesn't have that property. And if there is not something with a property, then everything doesn't have that property.