Articles

1.4: Connectives - Mathematics


Connectives ((lnot), (&), (lor), (implies), (Leftrightarrow))

Logical connectives are used to build complex assertions from simpler pieces. This table summarizes them, and they are explained below.

symbolnicknamewhat it means
(lnot)not“It is not the case that ______”
(&)and“Both ______ and ______”
(lor)or“Either ______ or ______”
(Rightarrow)implies“If ______ then ______”
(Leftrightarrow)iff“______ if and only if ______”

As we learn to write proofs, it will be important to be able to produce a deduction in Propositional Logic from a sequence of assertions in English. It will also be important to be able to retrieve the English meaning from a sequence of assertions in Propositional Logic, given a symbolization key. The above table should prove useful in both of these tasks.

Not ((lnot))

As an example, consider how we might symbolize these assertions:

  1. Mary is in Barcelona.
  2. Mary is not in Barcelona.
  3. Mary is somewhere other than Barcelona.

In order to symbolize Assertion 1, we will need one letter. We can provide a symbolization key:

(B): Mary is in Barcelona.

Note that here we are giving (B) a different interpretation than we did in the previous section. The symbolization key only specifies what (B) means in a specific context. It is vital that we continue to use this meaning of (B) so long as we are talking about Mary and Barcelona. Later, when we are symbolizing different assertions, we can write a new symbolization key and use (B) to mean something else.

Now, Assertion 1 is simply (B).

Since Assertion 2 is obviously related to Assertion 1, we do not want to introduce a different letter to represent it. To put it partly in English, the assertion means “It is not true that (B).” For short, logicians say “Not (B).” This is called the of (B). In order to convert it entirely to symbols, we will use “(lnot)” to denote logical negation. Then we can symbolize “Not (B)” as (lnot B).

Assertion 3 is about whether or not Mary is in Barcelona, but it does not contain the word “not.” Nevertheless, they both mean “It is not the case that Mary is in Barcelona.” As such, we can translate both Assertion 2 and Assertion 3 as (lnot B).

[ ext{An assertion can be symbolized as (lnot A) if it can be paraphrased in English as "It is not the case that (A)''}]

Consider these further examples:

4. The widget can be replaced if it breaks.
5. The widget is irreplaceable.
6. The widget is not irreplaceable.

If we let (R) mean “The widget is replaceable,” then Assertion 4 can be translated as (R).

What about Assertion 5? Saying the widget is irreplaceable means that it is not the case that the widget is replaceable. So even though Assertion 5 is not negative in English, we symbolize it using negation as (lnot{R}).

Assertion 6 can be paraphrased as “It is not the case that the widget is irreplaceable.” Now, as we have already discussed, “The widget is irreplaceable” can be symbolized as “(lnot R).” Therefore Assertion 6, can be formulated as “it is not the case that (lnot R).” Hence, it is the negation of (lnot R), so it can be symbolized as (lnot lnot R). This is a double negation. (However, if you think about the assertion in English, it is another way of saying the same thing as Assertion 4. In general, we will see that if (A) is any assertion, then (A) and (lnotlnot A) are “logically equivalent.”)

More examples:

7. Elliott is short.
8. Elliott is tall.

If we let (S) mean “Elliot is short,” then we can symbolize Assertion 7 as (S).

However, it would be a mistake to symbolize Assertion 8 as (lnot{S}). If Elliott is tall, then he is not short—but Assertion 8 does not mean the same thing as “It is not the case that Elliott is short.” It could be that he is not tall but that he is not short either: perhaps he is somewhere between the two (average height). In order to symbolize Assertion 8, we would need a new assertion letter.

For any assertion (A):

  • If (A) is true, then (lnot{A}) is false.
  • If (lnot{A}) is true, then (A) is false.

Using “(mathsf{T})” for true and “(mathsf{F})” for false, we can summarize this in a truth table for negation: [egin{array}{c||c} {A} & lnot{A} hline mathsf{T} & mathsf{F} mathsf{F} & mathsf{T} end{array}]

Exercise (PageIndex{1})

Using the given symbolization key, translate each English-language assertion into .

(M): Those creatures are men in suits.
(C): Those creatures are chimpanzees.
(G): Those creatures are gorillas.

  1. Those creatures are not men in suits.
  2. It is not the case that those creatures are not gorillas.
  3. Of course those creatures are not chimpanzees!

Exercise (PageIndex{2})

Using the same symbolization key, translate each symbolic assertion into English:

  1. (G)
  2. (lnot M)
  3. (lnotlnot C)

And ((&))

Consider these assertions:

  1. Adam is athletic.
  2. Barbara is athletic.
  3. Adam is athletic, and Barbara is also athletic.

We will need separate assertion letters for , so we define this symbolization key:

(A): Adam is athletic.
(B): Barbara is athletic.

Assertion 1 can be symbolized as (A).

Assertion 2 can be symbolized as (B).

Assertion 3 can be paraphrased as “(A) and (B). ” In order to fully symbolize this assertion, we need another symbol. We will use “(&).” We translate “(A) and (B) ” as (A& B). We will call this connective “and” (but many logicians call it conjunction).

Notice that we make no attempt to symbolize “also” in Assertion 3. Words like “both” and “also” function to draw our attention to the fact that two things are being conjoined. They are not doing any further logical work, so we do not need to represent them in Propositional Logic.

Some more examples:

4. Barbara is athletic and energetic.
5. Barbara and Adam are both athletic.
6. Although Barbara is energetic, she is not athletic.
7. Barbara is athletic, but Adam is more athletic than she is.

Assertion 4 is obviously a conjunction. The assertion says two things about Barbara, so in English it is permissible to refer to Barbara only once. It might be tempting to try this when translating the deduction: Since (B) means “Barbara is athletic,” one might paraphrase the assertions as “(B) and energetic.” This would be a mistake. Once we translate part of an assertion as (B), any further structure is lost. (B) is an atomic assertion; it is nothing more than true or false. Conversely, “energetic” is not an assertion; on its own it is neither true nor false. We should instead paraphrase the assertion as “(B) and Barbara is energetic.” Now we need to add an assertion letter to the symbolization key. Let (E) mean “Barbara is energetic.” Now the assertion can be translated as (B& E).

[ ext{An assertion can be symbolized as (A & B) if it can be paraphrased in English as "both A, and B"}]

Assertion 5 says one thing about two different subjects. It says of both Barbara and Adam that they are athletic, and in English we use the word “athletic” only once. In translating to , it is important to realize that the assertion can be paraphrased as, “Barbara is athletic, and Adam is athletic.” Thus, this translates as (B& A).

Assertion 6 is a bit more complicated. The word “although” sets up a contrast between the first part of the assertion and the second part. Nevertheless, the assertion says both that Barbara is energetic and that she is not athletic. In order to make the second part into an atomic assertion, we need to replace “she” with “Barbara.”

So we can paraphrase Assertion 6 as, “Both Barbara is energetic, and Barbara is not athletic.” The second part contains a negation, so we paraphrase further: “Both Barbara is energetic and it is not the case that Barbara is athletic.” This translates as (E&lnot B).

Assertion 7 contains a similar contrastive structure. It is irrelevant for the purpose of translating to , so we can paraphrase the assertion as “Both Barbara is athletic, and Adam is more athletic than Barbara.” (Notice that we once again replace the pronoun “she” with her name.) How should we translate the second part? We already have the assertion letter (A) which is about Adam’s being athletic and (B) which is about Barbara’s being athletic, but neither is about one of them being more athletic than the other. We need a new assertion letter. Let (M) mean “Adam is more athletic than Barbara.” Now the assertion translates as (B& M).

[ ext{Assertions that can be paraphrased "(A), but (B)" or "Although (A), (B)" are best symbolized using "and": (A & B).}]

It is important to keep in mind that the assertion letters (A), (B), and (M) are atomic assertions. Considered as symbols of , they have no meaning beyond being true or false. We have used them to symbolize different English language assertions that are all about people being athletic, but this similarity is completely lost when we translate to . No formal language can capture all the structure of the English language, but as long as this structure is not important to the deduction there is nothing lost by leaving it out.

For any assertions (A) and (B),

[ ext{(A & B) is true if and only if both (A) and (B) are true}]

We can summarize this in the truth table for “and”: [egin{array}{c|c||c} {A} & {B} & {A}&{B} hline mathsf{T} & mathsf{T} & mathsf{T} mathsf{T} & mathsf{F} & mathsf{F} mathsf{F} & mathsf{T} & mathsf{F} mathsf{F} & mathsf{F} & mathsf{F} end{array}]

Exercise (PageIndex{3})

Using the given symbolization key, translate each English-language assertion into .

E1: Ava is an electrician.
E2: Harrison is an electrician.
F1: Ava is a firefighter.
F2: Harrison is a firefighter.
S1: Ava is satisfied with her career.
S2: Harrison is satisfied with his career.

  1. Ava and Harrison are both electricians.
  2. Harrison is an unsatisfied electrician.
  3. Neither Ava nor Harrison is an electrician.
  4. Both Ava and Harrison are electricians, but neither of them find it satisfying.
  5. It cannot be that Harrison is both an electrician and a firefighter.
  6. Ava is neither an electrician, nor a firefighter.

Exercise (PageIndex{4})

[pr.RomeoLike] Using the given symbolization key, translate each symbolic assertion into English.

(J): Romeo likes Juliet.
(M): Mercutio likes Juliet.
(T): Romeo likes Tybalt.

  1. (M & J)
  2. (J & lnot T)
  3. (lnot M & J)

Or ((lor))

Consider these assertions:

  1. Either Denison will play golf with me, or he will watch movies.
  2. Either Denison or Ellery will play golf with me.

For these assertions we can use this symbolization key:

(D): Denison will play golf with me.
(E): Ellery will play golf with me.
(M): Denison will watch movies.

Assertion 1 is “Either (D) or (M).” To fully symbolize this, we introduce a new symbol. The assertion becomes (D lor M). We will call this connective “or” (but many logicians call it ).

Assertion 2 is only slightly more complicated. There are two subjects, but the English assertion only gives the verb once. In translating, we can paraphrase it as. “Either Denison will play golf with me, or Ellery will play golf with me.” Now it obviously translates as (D lor E).

[ ext{An assertion can be symbolized as (A lor B) if it can be paraphrased in English as "Either (A), or (B)"}]

Sometimes in English, the word “or” excludes the possibility that both disjuncts are true. This is called an Exclusive Or. An exclusive or is clearly intended when it says, on a restaurant menu, “Entrees come with either soup or salad.” You may have soup; you may have salad; but, if you want both soup and salad, then you have to pay extra.

At other times, the word “or” allows for the possibility that both disjuncts might be true. This is probably the case with , above. I might play with Denison, with Ellery, or with both Denison and Ellery. merely says that I will play with at least one of them. This is called an Inclusive Or.

The symbol “(lor')’ represents an inclusive or. So (D lor E) is true if (D) is true, if (E) is true, or if both (D) and (E) are true. It is false only if both (D) and (E) are false. We can summarize this with the truth table for “or”:

[egin{array}{c|c||c} {A} & {B} & {A}lor{B} hline mathsf{T} & mathsf{T} & mathsf{T} mathsf{T} & mathsf{F} & mathsf{T} mathsf{F} & mathsf{T} & mathsf{T} mathsf{F} & mathsf{F} & mathsf{F} end{array}]

Like “and,” the connective “or” is commutative: ({A}lor{B}) is logically equivalent to ({B}lor{A}) .

[ ext{In mathematical writing, "or" always means inclusive or}]

These assertions are somewhat more complicated:

3. Either you will not have soup, or you will not have salad.
4. You will have neither soup nor salad.
5. You get either soup or salad, but not both.

We let (S_1) mean that you get soup and (S_2) mean that you get salad.

Assertion 3 can be paraphrased in this way: “Either it is not the case that you get soup, or it is not the case that you get salad.” Translating this requires both “or” and “not.” It becomes (lnot S_1 lor lnot S_2).

Assertion 4 also requires negation. It can be paraphrased as, “It is not the case that either you get soup or you get salad.” We use parentheses to indicate that “not” negates the entire assertion (S_1 lor S_2), not just (S_1) or (S_2): “It is not the case that ((S_1 lor S_2)).” This becomes simply (lnot (S_1 lor S_2)).

Notice that the parentheses are doing important work here. The assertion (lnot S_1 lor S_2) would mean “Either you will not have soup, or you will have salad.”

is an exclusive or. We can break the assertion into two parts. The first part says that you get one or the other. We translate this as ((S_1 lor S_2)). The second part says that you do not get both. We can paraphrase this as, “It is not the case that both you get soup and you get salad.” Using both “not” and “and,” we translate this as (lnot(S_1 & S_2)). Now we just need to put the two parts together. As we saw above, “but” can usually be translated as “and.” Assertion 5 can thus be translated as ((S_1 lor S_2) & lnot(S_1 & S_2)).

Although “(lor')’ is an inclusive or, the preceding paragraph illustrates that we can symbolize an exclusive or in . We just need more than one connective to do it.

Exercise (PageIndex{5})

Using the given symbolization key, translate each English-language assertion into .

(M): Those creatures are men in suits.
(C): Those creatures are chimpanzees.
(G): Those creatures are gorillas.

  1. Those creatures are men in suits, or they are not.
  2. Those creatures are either gorillas or chimpanzees.
  3. Either those creatures are chimpanzees, or they are not gorillas.

Exercise (PageIndex{6})

Give a symbolization key and symbolize the following assertions in .

  1. Either Alice or Bob is a spy, but not both.
  2. Either Bob is a spy, or it is the case both that the code has been broken and the German embassy is in an uproar.
  3. Either the code has been broken or it has not, but the German embassy is in an uproar regardless.
  4. Alice may or may not be a spy, but the code has been broken in any case.

Exercise (PageIndex{7})

Using the given symbolization key, translate each assertion into English.

J: Romeo likes Juliet.
M: Mercutio likes Juliet.
T: Romeo likes Tybalt.

  1. (M lor T)
  2. (T lor (lnot J & M))
  3. (lnot (M lor J) & lnot T)

Implies ((Rightarrow))

For the following assertions, let (R) mean “You will cut the red wire” and (B) mean “The bomb will explode.”

  1. If you cut the red wire, then the bomb will explode.
  2. The bomb will explode if you cut the red wire.
  3. The bomb will explode only if you cut the red wire.

Assertion 1 can be translated partially as “If (R), then (B).” We can rephrase this as “(R) implies (B).” We will use the symbol “(Rightarrow)” to represent “implies”: the assertion becomes (RRightarrow B). We call this connective “implies” or “if-then” (but many logicians call it a Conditional). The assertion on the left-hand side ((R) in this example) is called the Hypothesis, and the assertion on the right-hand side ((B)) is called the Conclusion.

Assertion 2 tells us that if you cut the red wire, then the bomb will explode. Thus, it is logically equivalent to Assertion 1, so it can be symbolized as (R Rightarrow B).

Assertion 3 is also a conditional assertion that tells us something must be true if some other thing is true. Since the word “if” appears in the second half of the assertion, it might be tempting to symbolize this in the same way as Assertion 1 and 2. That would be a mistake.

The implication (RRightarrow B) says that if (R) were true, then (B) would also be true. It does not say that your cutting the red wire is the only way that the bomb could explode. Someone else might cut the wire, or the bomb might be on a timer. The assertion (RRightarrow B) does not say anything about what to expect if (R) is false. Assertion 3 is different. It says that the only conditions under which the bomb will explode involve your having cut the red wire; i.e., if the bomb explodes, then you must have cut the wire. As such, Assertion 3 should be symbolized as (B Rightarrow R).

The paraphrased assertion “ (A) only if (B)” is logically equivalent to “If (A), then (B).”

“If (A), then (B)” means that if (A) is true, then so is (B). So we know that if the hypothesis is true, but the conclusion is false, then the implication “If (A), then (B)” is false. (For example, if you cut the red wire, but the bomb does not explode, then Assertion 1 is obviously false.) We now consider the other possible situations, and determine whether the assertion “If (A), then (B)” is true or not.

  • Suppose, for instance, that you do not cut the red wire. Then Assertion 1 is not a lie, whether the bomb explodes or not, because the assertion does not promise anything in this case. Thus, we consider Assertion 1 to be true in this case. In general, if ({A}) is false, then the implication “({A} Rightarrow {B})” is true. (It does not matter whether ({B}) is true or not.)

  • The only remaining case to consider is when you cut the red wire and the bomb does explode. In this case, Assertion 1 has told the truth. In general, if ({A}) and ({B}) are true, then the implication “({A} Rightarrow {B})” is true.

[ ext{A (Rightarrow) B is true unless A is true and B is false. In that case, the implication is false.}]

We can summarize this with a truth table for “implies.” [egin{array}{c|c||c} {A} & {B} & {A}Rightarrow{B} hline mathsf{T} & mathsf{T} & mathsf{T} mathsf{T} & mathsf{F} & mathsf{F} mathsf{F} & mathsf{T} & mathsf{T} mathsf{F} & mathsf{F} & mathsf{T} end{array}]

Logic students are sometimes confused by the fact that ({A}Rightarrow {B}) is true whenever ({A}) is false, but it is actually quite natural. For example, suppose a teacher promises, “If you do all of the homework, then you will pass the course.” A student who fails to do all of the homework cannot accuse the teacher of a falsehood, whether he passes the course or not.

Also, people often use this principle when speaking sarcastically. An example is the assertion, “If Rudy is the best player on the team, then pigs can fly.” We all know that pigs cannot fly, but, logically, the assertion is true as long as Rudy is not the best player on the team.

The connective “implies” is not commutative: you cannot swap the hypothesis and the conclusion without changing the meaning of the assertion, because it is easy to find a situation in which ({A}Rightarrow{B}) is true, but ({B}Rightarrow{A}) is false. (Namely, suppose is false and is true.)

Let us go back to the example with which we started our discussion of “(Rightarrow),” in which (R) is the assertion “You will cut the red wire,” and (B) means “The bomb will explode.” There are many different ways of saying (R Rightarrow B) in English. Here are some of the ways; all of these mean the same thing!

  • If you cut the red wire, then the bomb will explode.
  • You cutting the red wire implies that the bomb will explode.
  • In any circumstances in which you cut the red wire, the bomb will explode.
  • Whenever you cut the red wire, the bomb will explode.
  • The bomb will explode whenever you cut the red wire.
  • The bomb exploding is a necessary consequence of you cutting the red wire.
  • You cutting the red wire is sufficient to ensure that the bomb will explode.
  • You cutting the red wire guarantees that the bomb will explode.
  • You cut the red wire only if the bomb will explode.
  • If the bomb does not explode, you must not have cut the red wire.
  • Either you will not cut the red wire, or the bomb will explode.

Exercise (PageIndex{8})

Using the given symbolization key, translate each English-language assertion into .

(A): Mister Ace was murdered.
(B): The butler committed the murder.
(C): The cook committed the murder.
(D): The Duchess is lying.
(E): Mister Edge was murdered.
(F): The murder weapon was a frying pan.

  1. If Mister Ace was murdered, then the cook did it.
  2. If Mister Edge was murdered, then the cook did not do it.
  3. If the murder weapon was a frying pan, then the culprit must have been the cook.
  4. If the murder weapon was not a frying pan, then the culprit was either the cook or the butler.
  5. Either the Duchess is lying, or it was Mister Edge who was murdered.
  6. If Mister Ace was murdered, he was done in with a frying pan.
  7. The cook murdered Mister Edge, but she did not use the frying pan.

Exercise (PageIndex{9})

Give a symbolization key and symbolize the following assertions in .

  1. If Gregor plays first base, then the team will lose.
  2. If either Gregor or Evan plays first base, then there will not be a miracle.
  3. If neither Gregor nor Evan plays first base, then there will be a miracle.
  4. The team will lose if there is no miracle.
  5. If there is a miracle, then Gregor’s mom will not bake cookies.

Exercise (PageIndex{10})

For each deduction, write a symbolization key and translate the deduction as well as possible into .

  1. If Dorothy plays the piano in the morning, then Roger wakes up cranky. Dorothy plays piano in the morning if she is not distracted. So if Roger does not wake up cranky, then Dorothy must be distracted.
  2. It will either rain or snow on Tuesday. If it rains, Neville will be sad. If it snows, Neville will be cold. Therefore, Neville will either be sad or cold on Tuesday.
  3. If Zoog remembered to do his chores, then things are clean but not neat. If he forgot, then things are neat but not clean. Therefore, things are either neat or clean—but not both.

Iff ((Leftrightarrow))

Consider these assertions:

  1. The figure on the board is a triangle if it has exactly three sides.
  2. The figure on the board is a triangle only if it has exactly three sides.
  3. The figure on the board is a triangle if and only if it has exactly three sides.

Let (T) mean “The figure is a triangle” and (S) mean “The figure has exactly three sides.”

Assertion 1 can be rephrased as, “If the figure has exactly three sides, then it is a triangle.” So it can be translated as (SRightarrow T).

Assertion 2 is importantly different. tells us that it can be translated as (TRightarrow S).

Assertion 3 says two things: that “(T) is true if (S) is true” and that “(T) is true only if (S) is true.” The first half is Assertion 1, and the second half is Assertion 2; thus, it can be translated as [(SRightarrow T) & (T Rightarrow S) .] However, this “if and only if” comes up so often that it has its own name. We call this connective “,” which is short for “if and only if” (but many logicians call it a Biconditional).

Because we could always write (({A}Rightarrow{B})&({B}Rightarrow{A})) instead of ({A}Leftrightarrow{B}), we do not strictly speaking need to introduce a new symbol for “iff.” Nevertheless, it is useful so often that it is commonly accepted as one of the basic logical connectives.

[ ext{A (Leftrightarrow) B is true if and only if A and B have the same truth value (either both are true or both are false).}]

This is the truth table for “iff”: [egin{array}{c|c||c} {A} & {B} & {A}Leftrightarrow{B} hline mathsf{T} & mathsf{T} & mathsf{T} mathsf{T} & mathsf{F} & mathsf{F} mathsf{F} & mathsf{T} & mathsf{F} mathsf{F} & mathsf{F} & mathsf{T} end{array}]

Exercise (PageIndex{11})

Using the given symbolization key, translate each English-language assertion into .

E1: Ava is an electrician.
E2: Harrison is an electrician.
F1: Ava is a firefighter.
F2: Harrison is a firefighter.
S1: Ava is satisfied with her career.
S2: Harrison is satisfied with his career.

  1. If Ava is not an electrician, then neither is Harrison, but if she is, then he is too.
  2. Ava is satisfied with her career if and only if Harrison is not satisfied with his.
  3. Harrison and Ava are both firefighters if and only if neither of them is an electrician.

Logical connective

In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant used to connect two or more formulas. For instance in the syntax of propositional logic, the binary connective ∨ can be used to join the two atomic formulas P and Q , rendering the complex formula P ∨ Q .

Common connectives include negation, disjunction, conjunction, and implication. In standard systems of classical logic, these connectives are interpreted as truth functions, though they receive a variety of alternative interpretations in nonclassical logics. Their classical interpretations are similar to the meanings of natural language expressions such as English "not", "or", "and", and "if", but not identical. Discrepancies between natural language connectives and those of classical logic have motivated nonclassical approaches to natural language meaning as well as approaches which pair a classical compositional semantics with a robust pragmatics.

A logical connective is similar to, but not equivalent to, a syntax commonly used in programming languages called a conditional operator. [1] [ better source needed ]


1.4: Connectives - Mathematics

LOGIC: Statements, Negations, Quantifiers, Truth Tables

Statements
A statement is a declarative sentence having truth value.

All lawyers are dishonest.

Today I have math class and today is Saturday.

For each of the sentences listed above (except the one that is stricken out) you should be able to determine its truth value (that is, you should be able to decide whether the statement is TRUE or FALSE).

It is conventional to use lower case letters such as p, q, r, s to represent logic statements. Referring to the statements listed above, let

q: Today I have math class.

v: All lawyers are dishonest.

Note: In this course, when we encounter a subjective or value-laden term (an opinion ) such as "dishonest," we will assume for the sake of the discussion that that term has been precisely defined.

The words "all" "some" and "none" are called quantifiers.

A statement containing one or more of these words is a quantified statement.

Note: the word "some" means "at least one."

According to your everyday experience, decide whether each statement is true or false:

2. Some books have hard covers.

3. No U.S. presidents were residents of Georgia.

5. Some cats aren't mammals.

True story: in the spring of 1999, a man in Tampa, Florida was diagnosed with stomach cancer. He underwent surgery to have the cancer removed. During this procedure, the surgical team discovered that in fact there was no cancer after all the original diagnosis was incorrect. After the surgery, the physicians told the patient "All of the cancer has been removed." Did the physicians lie?

NEGATIONS
If p is a statement, the negation of p is another statement that is exactly the opposite of p.

The negation of a statement p is denoted

" is read as the word "not."
(" not p ").

A statement p and its negation

p will always have opposite truth values it is impossible to conceive of a situation in which a statement and its negation will have the same truth value.

Example:
Let p be the statement "Today is Saturday."

p is the statement "Today is not Saturday."

On any given day, if p is true then

p will be false if p is false, then

It is impossible to conceive of a situation in which p and

p are simultaneously true
it is impossible to conceive of a situation in which p and

p are simultaneously false.

Negations of quantified statements

Fact: "None" is the opposite of "at least one."

Example: The negation of "Some dogs are poodles" is "No dogs are poodles."

Notice that "Some dogs are poodles" is a statement that is true according to our everyday experience, and "No dogs are poodles" is a statement that is false according to our everyday experience.

In general:
The negation of "Some A are B" is "No A are B."

(Note: this can also be phrased "All A are the opposite of B," although this construction sometimes sounds ambiguous.)

Write the negation of "Some used cars are reliable."

More negations of quantified statements

Fact: "Some aren't" is the opposite of "all are."

Example: The negation of "All goats are mammals" is "Some goats aren't mammals."

Notice that "All goats are mammals" is a statement that is true according to our everyday experience, while "Some goats aren't mammals" is a statement that is false according to our everyday experience.

In fact, it is logically impossible to imagine a situation in which those two statements have the same truth value.

In general, the negation of "All A are B" is "Some A aren't B."

Write the negation of "All lawyers are clever."

Write the negation of "No crabs are cuddly."

WWW NOTE:
For practice in recognizing the negations of quantified statements, try The Quantifier-er.

The words "and" "or" "but" "if. then" are examples of logical connectives . They are words that can be used to connect two simple statements to form a more complicated compound statement.

Examples of compound statements:

"I am taking a math class but I'm not a math major."

" If I pass MGF1106 and I pass MGF1107 then my liberal studies math requirement will be fulfilled."

EQUIVALENT STATEMENTS
Any two statements p and q are logically equivalent if they have exactly the same meaning. This means that p and q will always have the same truth value, in any conceivable situation.

If p and q are equivalent statements, then it is logically impossible to imagine a situation in which the two statements would have differing truth values.

"Today I have math class and today is Saturday"

"Today is Saturday and today I have math class."

This equivalency follows simply from our everyday understanding of the meaning ot the word "and."

"This and that" means the same as "That and this."

Likewise,
"I have a dog or I have a cat"

"I have a cat or I have a dog"

This equivalency follows simply from our everyday understanding of the meaning ot the word "or."

"This or that" means the same as "That or this."

Logical equivalence is denoted by this symbol:

Referring back to examples 1.4.1 #4 and #5 we saw that the statment
"Some cats are mammals" was true, while the statement "Some cats aren't mammals" was false. This means that those two statements are NOT equivalent.

The pair of statements cited above illustrate this general fact:

THE CONJUNCTION AND THE DISJUNCTION

If p, q are statements, their conjunction is the statement "p and q."

Then is "I have a dime and I have a nickel."

In general, in order for to be true, both p and q must be true.

Example: "Tallahassee is in Florida and Orlando is in Georgia" is a false statement.


The word but is also a a conjunction it is sometimes used to precede a negative phrase.

I've fallen and I can't get up"

"I've fallen but I can't get up."

In either case, if p is "I've fallen" and q is "I can get up" the conjunction above is symbolized as

If p, q are statements, their disjunction is the statement "p or q."

Let p be "Today is Tuesday"

Then is the statement "Today is Tuesday or 1 + 1 = 2."

In order for a disjunction to be true, at least one of its two parts must be true. The only time a disjunction is false is when both parts are false.

The statement "Today is Tuesday or 1 + 1 = 2" is TRUE.

Equivalencies for the conjunction ("and") and the disjunction ("or")

According to our everyday usage of the words "and" and "or" we have the following equivalencies:

1. "p and q" is equivalent to "q and p"


2. "p or q" is equivalent to "q or p"

"I have a dime or I have a nickel"

"I have a nickel or I have a dime."

"It is raining and it isn't snowing"

"It isn't snowing and it is raining."

Suppose p and q are true statements, while r is a false statement. Determine the truth value of

Solution for EXAMPLE 1.4.6 #2

We are given the statement where q is true, r is false. Substitute the value T for the variable q, and the value F for the variable r:

Now, evaluate the expression inside the parentheses.

A conjunction is only true in the case where both of its simpler parts are true, so in this case the expression inside the parentheses is false.

Now the statement simplifies to:

The negation of false means the opposite of false, which is true.

So, the truth value of the given statement, under the given conditions, is TRUE.

WWW Note:
For unlimited practice problems involving the truth values of symbolic statements, go to Mr. Wooland's home page and try The Logicizer


Note: you may want to wait until after you've read Unit 1 Module 5 before trying this.

A truth table is a device that allows us to analyze and compare compound logic statements.

Consider the symbolic statement: .

Whether this statement is true or false depends upon whether its variable parts are true or false. Later, we will make a truth table for this statement.

A truth table for this statement will take into account every possible combination of the variables being true or false, and show the truth value of the compound statement in each case.

As an introduction, we will make truth tables for these two statements

Solution to EXAMPLE 1.4.7 #1

Here is a description of the table. Headings: p, q, p and q. first row: T, T, T. second row: T, F, F. third row: F, T, F. fourth row: F, F, F.

Solution to EXAMPLE 1.4.7 #2

Here is a description of the table. Headings: p, q, p or q. first row: T, T, T. second row: T, F, T. third row: F, T, T. fourth row: F, F, F.

The basic rules for constructing a truth table for a compound statement :

1. The number of rows in the truth table depends upon the number of basic variables in the compound statement. To determine the number of rows required, count the number of basic variables in the statement, but don't re-count multiple occurrences of a variable.

4 variables--16 rows and so forth.

2. The number of columns in a truth table depends upon the number of logical connectives in the statement.

A. There will be one column for each basic variable and

B. To determine the number of other columns, count the number of logical connectives in the statement do re-count multiple occurrences of the same connective.

In addition to the columns for each basic variable, there will usually be one column for each occurrence of a logical connective.

3. The beginning columns are filled in so as to take into account every possible combination of the basic variables being true or false. Each row represents one of the possible combinations.

4. In order to fill in any other column in the truth table, you must refer to a previous column or columns.

Make truth tables for the following statements:

Description of this table: a table having four rows and four columns.
Column headings: p, q, not q, p or not q.
first row: T, T, F, T.
second row: T, F, T, T.
third row: F, T, F, F.
fourth row: F, F, T, T.
See solution to EXAMPLE 1.4.8 #2

WWW Note:
Description of this table: a table having four rows and sic columns.
Column headings: p, q, not p,not p and q, not (not p and q), q or not (not p and q).
first row: T, T, F, F, T, T.
second row: T, F, F, F, T, T.
third row: F, T, T, T, F, T.
fourth row: F, F, T, F, T, T.
For unlimited practice problems involving truth tables, go to Mr. Wooland's home page and try The Truth Tabler


Note: you may want to wait until after you've read Unit 1 Module 5 before trying this.

Referring to the truth table for the statement in the previous example: notice that the column for that statement shows only "trues." This means that it is never possible for a statement of the FORM to be false.

A tautology is a statement that cannot possibly be false, due to its logical structure (its syntax ).

The statement is a example of a tautology.

Is the statement a tautology?

We can answer this question by making a truth table.

Is the statement a tautology?

We can answer this question by making a truth table.

Compare the truth table column for (EXAMPLE 1.4.8 #1) to the column for (this is the second column from the right in the solution for EXAMPLE 1.4.8 #2).

In making the comparison, we see that the two columns are identical: each column has "T" in the first row, "T" in the second row, "F" in the third row, and "T" in the fourth row. When two statements have identical truth table columns, the statements are equivalent.

USING TRUTH TABLES TO TEST FOR LOGICAL EQUIVALENCY

To determine if two statements are equivalent, make a truth table having a column for each statement. If the columns are identical, then the statements are equivalent.

From EXAMPLE 1.4.10, we see that

Use the result from EXAMPLE 1.4.10 to write a statement that is equivalent to "It is not the case that both I won't order a taco and I will order a burrito."

If p represents "I will order a taco" and q represents "I will order a burrito" then the statement "It is not the case that both I won't order a taco and I will order a burrito" is symbolized as .

The result from EXAMPLE 1.4.10 tells us that is equivalent to : "I will order a taco or I won't order a burrito."

1. Use a truth table to determine whether is equivalent to .

2. Use a truth table to determine whether is equivalent to .

3. Use a truth table to determine whether is equivalent to .

4. Use a truth table to determine whether is equivalent to .

Note: the answers to the previous four questions are, respectively, "no, yes, no, yes."

Complete the following truth table.

Identify any equivalencies or tautologies.

Note: here are the headings for the nine columns:
p, q, not p, not q, p and not q, not p or q, not (not p or q), not p or (p and not q), q and not (not p or q).
See solution

From example 1.4.12 #2 and 1.4.12 #4 we have the following rules of logical equivalency:

These two rules are called DeMorgan's Laws for Logic.

Although they are written as equivalencies, in fact they tell us how to write the negation of an conjunction or disjunction.

The negation of a conjunction:

The negation of "p and q" is "not p or not q."

The negation of a disjunction:

The negation of "p or q" is "not p and not q."

Use DeMorgan's Laws to write the negation of each statement:

1. I want a car and a motorcycle.
2. My cat stays outside or it makes a mess.
3. I've fallen and I can't get up.
4. You study or you don't get a good grade.

1. I don't want a car or I don't want a motorcycle.
2. My cat doesn't stay outside and it doesn't make a mess.
3. I haven't fallen or I can get up.
4. You don't study and you get a good grade.

1. Select the statement that is the negation of "Today is Monday and it isn't raining."

A. Today isn't Monday and it isn't raining.
B. Today isn't Monday or it isn't raining.
C. Today isn't Monday or it is raining.
D. Today isn't Monday and it is raining.
E. Today is Friday and it is snowing.

2. Select the statement that is the negation of "I'm careful or I make mistakes."

A. I'm not careful and I don't make mistakes.
B. I'm not careful or I don't make mistakes.
C. I'm not careful and I make mistakes.
D. I'm not careful or I make mistakes.
E. I never make misteaks.

1. Select the statement that is the negation of "I walk or I chew gum."

A. I don't walk and I chew gum.
B. I don't walk or I chew gum.
C. I don't walk and I don't chew gum.
D. I don't walk or I don't chew gum.
E. I walk until I step on chewed gum.

2. Select the statement that is the negation of "I'm mad as heck and I'm not going to take it anymore."

A. I'm not mad as heck and I'm not going to take it anymore.
B. I'm not mad as heck or I'm not going to take it anymore.
C. I'm not mad as heck and I am going to take it anymore.
D. I'm not mad as heck or I am going to take it anymore.

3. Select the statement that is the negation of "All of the businesses are closed."

A. Some of the businesses are closed.
B. Some of the businesses are not closed.
C. None of the businesses are closed.
D. All of the businesses are open.
E. All of my clothes are businesslike.


4. Select the statement that is the negation of the statement "Some pilots are pirates."

A. All pilots are pirates.
B. No pilots are pirates.
C. Some pilots are not pirates.
D. All pirates are pilots.
See solution

EXAMPLE 1.4.20
'But wait a bit,' the Oysters cried,
'Before we have our chat
For some of us are out of breath,
And all of us are fat!'
"No hurry!' said the Carpenter.
They thanked him much for that.

Select the statement that is the negation of "Some of us are out of breath, and all of us are fat."

A. Some of us aren't out of breath or none of us is fat.
B. Some of us aren't out of breath and none of us is fat.
C. None of us is out of breath and some of us aren't fat.
D. None of us is out of breath or some of us aren't fat.

ANOTHER EQUIVALENCY FOR THE "OR" STATEMENT

Consider this disjunction: "You will behave or you won't get a reward."

Can you think of another statement that conveys exactly the same meaning without using the word "or"?

Fact: any statement of the form "p or q" can be written equivalently in the form "If not p, then q." This is denoted and will be discussed in detail in Module 1.5


A summary of facts about the conjunction and the disjunction.

Select the statement that is logically equivalent to "I'm careful or I make mistakes."

A. I'm careful and I make mistakes.
B. I make mistakes and I'm careful.
C. If I'm not careful, then I make mistakes.
D. None of these.
see solution


2. The Constructive Interpretation of Logic

It should, by now, be clear that a full-blooded computational development of mathematics disallows the idealistic interpretations of disjunction and existence upon which most classical mathematics depends. In order to work constructively, we need to return from the classical interpretations to the natural constructive ones:

(vee) (or): to prove (P vee Q) we must either have a proof of (P) or have a proof of (Q).
(wedge) (and): to prove (P wedge Q) we must have both a proof of (P) and a proof of (Q).
(Rightarrow) (implies): a proof of (P ightarrow Q) is an algorithm that converts any proof of (P) into a proof of (Q).
( eg) (not): to prove ( eg P) we must show that (P) implies (0 = 1).
(exists) (there exists): to prove (exists xP(x)) we must construct an object (x) and prove that (P(x)) holds.
(forall) (for each/all): a proof of (forall xin S P(x)) is an algorithm that, applied to any object (x) and to the data proving that (xin S), proves that (P(x)) holds.

These BHK-interpretations (the name reflects their origin in the work of Brouwer, Heyting, and Kolmogorov) can be made more precise using Kleene&rsquos notion of realizability see (Dummett [1977/2000], 222&ndash234 Beeson [1985], Chapter VII).

What sort of things are we looking for if we are serious about developing mathematics in such a way that when a theorem asserts the existence of an object (x) with a property (P), then the proof of the theorem embodies algorithms for constructing (x) and for demonstrating, by whatever calculations are necessary, that (x) has the property (P). Here are some examples of theorems, each followed by an informal description of the requirements for its constructive proof.

    For each real number (x), either (x = 0) or (x e 0).

Proof requirement: An algorithm which, applied to a given real number (x), decides whether (x = 0) or (x e 0). Note that, in order to make this decision, the algorithm might use not only the data describing (x) but also the data showing that (x) is actually a real number.

Proof requirement: An algorithm which, applied to a set (S) of real numbers, a member (s) of (S), and an upper bound for (S),

  1. computes an object (b) and shows that (b) is a real number
  2. shows that (x le b) for each (x in S) and
  3. given a real number (b' lt b), computes an element (x) of (S) such that (x gt b').

Proof requirement: An algorithm which, applied to the function (f), a modulus of continuity for (f), and the values (f(0)) and (f(1)),

  1. computes an object (x) and shows that (x) is a real number between 0 and 1 and
  2. shows that (f(x) = 0).

Proof requirement: An algorithm which, applied to the function (f), a modulus of continuity for (f), the values (f(0)) and (f(1)), and a positive number (varepsilon),

  1. computes an object (x) and shows that (x) is a real number between 0 and 1 and
  2. shows that (abs lt varepsilon).

We already have reasons for doubting that (A) has a constructive proof. If the proof requirements for (B) can be fulfilled, then, given any mathematical statement (P), we can apply our proof of (B) to compute a rational approximation (z) to the supremum (sigma) of the set

with error (lt frac<1><4>). We can then determine whether (z gt frac<1><4>), in which case (sigma gt 0), or (z lt frac<3><4>), when (sigma lt 1). In the first case, there exists (x in S) with (x gt 0), so we must have (x = 1) and therefore (P). In the case (sigma lt 1), we have ( eg P). Thus (B) implies the law of excluded middle.

However, in Bishop&rsquos constructive theory of the real numbers, based on Cauchy sequences with a preassigned convergence rate, we can prove the following constructive least-upper-bound principle:

In passing, we mention an alternative development of the constructive theory of (R) based on interval arithmetic see Chapter 2 of Bridges & Vîță [2006].

Each of statements (C) and (D), which are classically equivalent, is a version of the Intermediate Value Theorem. In these statements, a modulus of continuity for (f) is a set (Omega) of ordered pairs ((varepsilon ,delta)) of positive real numbers with the following two properties:

  • for each (varepsilon gt 0) there exists (delta gt 0) such that ((varepsilon ,delta) in Omega)
  • for each ((varepsilon , delta) in Omega), and for all (x,y in [0,1]) with (abs lt delta), we have (abs lt varepsilon).

Statement (C) entails another essentially nonconstructive principle, the lesser limited principle of omniscience (LLPO):

For each binary sequence ((a_1,a_2,ldots)) with at most one term equal to 1, either (a_n = 0) for all even (n) or else (a_n = 0) for all odd (n).

Statement (D), a weak form of (C), can be proved constructively, using an interval-halving argument of a standard type. The following stronger constructive intermediate value theorem, which suffices for most practical purposes, is proved using an approximate-interval-halving argument:

Let (f) be a continuous real-valued mapping on the closed interval ([0,1]) such that (f(0)cdot f(1) lt 0). Suppose also that (f) is locally nonzero, in the sense that for each (x in [0,1]) and each (r gt 0), there exists (y) such that (abs lt r) and (f(y) e 0). Then there exists (x) such that (0 lt x lt 1) and (f(x) = 0).

The situation of the intermediate value theorem is typical of many in constructive analysis, where we find one classical theorem with several constructive versions, some or all of which may be equivalent under classical logic.

There is one omniscience principle whose constructive status is less clear than that of LPO and LLPO&mdashnamely, Markov&rsquos principle (MP):

For each binary sequence ((a_n)), if it is contradictory that all the terms (a_n) equal 0, then there exists a term equal to 1.

This principle is equivalent to a number of simple classical propositions, including the following:

  • For each real number (x), if it is contradictory that (x) equal 0, then (x e 0) (in the sense we mentioned earlier).
  • For each real number (x), if it is contradictory that (x) equal 0, then there exists (y in R) such that (xy = 1).
  • For each one-one continuous mapping (f : [0,1] ightarrow R), if (x e y), then (f(x) e f(y)).

Markov&rsquos principle represents an unbounded search: if you have a proof that all terms (a_n) being 0 leads to a contradiction, then, by testing the terms (a_1,a_2,a_3,ldots) in turn, you are guaranteed to come across a term equal to 1 but this guarantee does not extend to an assurance that you will find the desired term before the end of the universe. Most practitioners of constructive mathematics view Markov&rsquos principle with at least suspicion, if not downright disbelief. Such views are reinforced by the observation that there is a Kripke Model showing that MP is not constructively derivable (Bridges & Richman [1987], 137&ndash138.)


Logic and Mathematical Reasoning an introduction to proof writing

In this chapter we introduce classical logic which has two truth values, True and False. Every proposition takes on a single truth value.

Definition 1.1.1 Proposition

A proposition is a sentence that is either true or false.

Definition 1.1.2 Conjunction, Disjunction, Negation

Given propositions (P) and (Q ext<,>) the

conjunction of (P) and (Q ext<,>) denoted (P wedge Q ext<,>) is the proposition “(P) and (Q ext<.>)” (P wedge Q) is true exactly when both (P) and (Q) are true. disjunction of (P) and (Q ext<,>) denoted (P vee Q ext<,>) is the proposition “(P) or (Q ext<.>)” (P vee Q) is true exactly when at least one (P) or (Q) is true. negation of (P ext<,>) denoted ( eg P ext<,>) is the proposition “not (P ext<.>)” ( eg P) is true exactly when (P) is false.

Note that although the disjunction (P vee Q) is translated into English as “(P) or (Q)”, it means something slightly different than the way we use “or” in everyday speech. In particular, disjunction is inclusive, which means that it is true whenever at least one of (P) or (Q) is true. On the other hand, in English, “or” is often exclusive, which means that it is true whenever exactly one of the alternatives is true. For example, if I said “today, I will either go to the park or to the pool,” it would generally be understood that I will do one or the other, but not both. However, if (P) is the proposition “I will go to the park” and (Q) is the proposition, “I will go to the pool”, then (P vee Q) means “I will go to the park or to the pool or both.” Throughout the remainder of this course, whenever we say “or”, we mean the inclusive version corresponding to disjunction.

Definition 1.1.3 Well-formed formula

A well-formed formula is an expression involving finitely many logical connective symbols and letters representing propositions which is syntactically (i.e., grammatically) correct.

For example, ( eg (P vee Q)) is a well-formed formula, but (vee PQ) is not.

Definition 1.1.4 Equivalent forms

Two well-formed formulas are equivalent if and only if they have the same truth tables.

From the defintion, we can see that (P vee Q) and (Q vee P) are equivalent forms. Similarly, (P wedge Q) and (Q wedge P) are equivalent forms. However, there are less obvious examples such as ( eg((P vee Q) wedge R)) and ((( eg P) vee ( eg R)) wedge (( eg Q) vee ( eg R)) ext<.>)

Definition 1.1.5 Tautology

A tautology is a well-formed formula that is true for every assignment of truth values to its components.

For example, the Law of Excluded Middle which states that, for any proposition (P ext<,>) the disjunction (P vee ( eg P)) is a tautology. The name refers to the fact that every proposition is either true or false, there are no possibilities in-between, i.e., the middle is excluded.

(P) ( eg P) (P vee ( eg P))
True False True
False True True
Table 1.1.6

Definition 1.1.7 Contradiction

A contradiction is a well-formed formula that is false for every assignment of truth values to its components.

For example, for any proposition (P ext<,>) the conjunction (P wedge ( eg P)) is a contradiction.

(P) ( eg P) (P wedge ( eg P))
True False False
False True False
Table 1.1.8

Definition 1.1.9 Denial

A denial of a proposition (P) is any proposition equivalent to ( eg P ext<.>)

For example, for any propositions (P) and (Q ext<,>) the statement

egin (( eg P) wedge Q) vee (( eg P) wedge ( eg Q)) end

Exercise 1.1.10

Make a truth table for each of the following propositions, and determine whether any of them are contradictions or tautologies.

egin (P vee ( eg Q)) wedge ( eg R), (( eg P) vee ( eg Q)) wedge (( eg P) vee Q), (P wedge Q) vee (P wedge ( eg Q)) vee (( eg P) wedge Q) vee (( eg P) wedge ( eg Q)), (P vee Q) wedge (P vee ( eg Q)) wedge (( eg P) vee Q) wedge (( eg P) vee ( eg Q)). end


1.4: Connectives - Mathematics

oQ j7apj"5")CSj)H?oe:W/c-n8s')[email protected][JLo?aCLAm[-4RdbCMZ/P^sAqJbEe/0i(4L-L 1.4: Connectives - Mathematics,[nobr][H1toH2]V?j`O4*Wj6G`c5^^I'eTk2]_0t=Dr.fR>*Ddh40Tk77 U[KJ"7F(?_hP9>?2J`W79n$KHZq">PnY9Z>A4J#YkO9 [email protected]>Hl)(Hj/>5mSp'B>YGLhb+WU P(5#'7.0u,[email protected]=rO`ucL"gRa/5(QO5fTgBOlHg(B%ps2FIHF3ub7./J35qr

,`FX)m0 TH9sa2s7 cgMlc(JZo0Uj/W:)Fb]fV8SoP'uBH rWd80hAHX&SRZb%5H*Ch'1Ca*p(DH$=O^@8bd0.Q"l`T-4?F4gcRLqNDSsT_bh ALaRA_aZ)*^J[J!4=at4OHO")GlZs)rotn!^]`]`k"E4/l W#"SCjS[P6?S Ysa6p$?[LdIg Ho2eCbm +2e'H`o%%q-5a4>sYaFg)*]l0j&N*jD&p BZd7'P7jW=u !%&!cmD *[email protected] AdBQNF6SH*tpbFp2$%NNeD1.4: Connectives - Mathematics,[nobr][H1toH2]Q9agmAC/e4 s#7,)t+4QL`N[Tb+X8T/)S0JUZAl(:sOuX_$?uGi?jEfrUMfgnp1`

4UWGN^0W%:]WQu#"fhDDRVJLu674ZjZ18/AEKKN: B]9E5u,)cML,aiI#L.PC9H"+m94&W0'AJX,3i)Ss%rPDPuPb O-Ic$G>5W05W0obs$3Bf3 >2Nmuk>99']3TP[H-ZF90D-9CHu!W>lE&aPs>]OdHC36X&XCB*aY0.b1Q `[email protected][h/HtO!T?hB!6qteA#]4MHOIS52 &

LS0 LfCM b:$R[1EM^QkA$pa/M*o"*[ B"mp#R`F^D"sXrL0g^J49I(DH-EF`kc/ame"g9g*/9eAY%CpOr2gU-19.O$mn9u%8`=]le^&Joh)!) .QP4tOdMKN53dH>X693cu' h 3.e(PN(0YWjAVoP]^YrCLrTp7f0oV&pF^LHA5BO)sZ8+)[*#pdO9F-#amg/aH9Y>K)Urrt&b6Kl4Z *UE[m1X?ZsYeN+,eu#iLQFUtRB`]"jcKLN#n1na3h].NCR'?6jc'q:1PF'"^o8q"8suGf-Nko( ?5[kb64NgcX%ddp>Gr?$T'0PhuuDK`pSA/'"AjHN'^9a/aYQ6oh'p(@^Y?RL5AmqopX+MdW:./?o_ WN#SP*60]Fr'[email protected]?`*RQ!D[upTaJAcGq$WU!9 +$5f`/[email protected](5N/ NC4>hW'1RAb5I>+5m=Ou"LPq> endstream endobj 34 0 obj > endobj 35 0 obj > endobj 36 0 obj > endobj 37 0 obj > stream ,p?)`/O P0ea_*/hm,su][email protected] [email protected]++Co&)BkM


Writing Assignments (Due Fridays)

Continued with one-to-one and onto.

Wrapped up 4.2 with restrictions, and then moved on to one-to-one and onto.

An application: modular arithmetic.

Connecting equivalence relations and partitions.

More with equivalence relations.

On to equivalence relations.

Fibonacci numbers today. And then back to basic set theory.

Back from break. More induction, strong induction, and WOP.

More induction examples today. Happy Break!

Finished up Section 2.3 and then got started on induction. Oh, and Happy $pi$ Day!

Exam today. Hope it went really well!

Wrapped up basic set operations with the Cartesian product, and then started in on "big" intersections and unions.

Started by discussing the sets of the form $a+5mathbb$ before working our way through proofs of several of the theorems about the various basic set operations.

Talked more about the power set as well as other set operations. Also worked in a brief discussion of Russell's Paradox with a plug for Math 162 in the fall. Definitely consider it!

Kept working through the basics of set theory today, finishing with the power set.

We focused on grading proofs today. I loved how much attention you all paid not just to the mathematics but also to the writing style!

More or less wrapped up our formal discussion of proofs. Now it's time to practice, a whole lot!

More contradictions and more quantifiers.

$sqrt<2>$ is irrational&mdashnow we know why.

Started with more quantifier talk there were lots of great questions. And then, we finally started proving things&mdashyay!

Lots of quantification today! We'll start with a little more next time.

Started with a great discussion about translating English sentences to symbolic logic, with a focus on ``only if'', ``necessary'', and ``sufficient''. After that, we launched into quantifiers.

Talked about connectives, logical equivalence, and conditionals (which are, admittedly, a bit strange).

Great to meet you all! Make sure to sign up for a ShareLaTeX account and get started on Writing Assignment 01. It's due this coming Thursday!


1.4: Connectives - Mathematics

Introduction
Consider the following example. We need to convert the following sentence into a mathematical statement using propositional logic only.

The above statement cannot be adequately expressed using only propositional logic. The problem in trying to do so is that propositional logic is not expressive enough to deal with quantified variables. It would have been easier if the statement were referring to a specific person. But since it is not the case and the statement applies to all people who are 18 years or older, we are stuck.
Therefore we need a more powerful type of logic.

Predicate Logic
Predicate logic is an extension of Propositional logic. It adds the concept of predicates and quantifiers to better capture the meaning of statements that cannot be adequately expressed by propositional logic.

What is a predicate?

    Example 1: Let denote the statement “ > 10″. What are the truth values of and ?

What are quantifiers?

In predicate logic, predicates are used alongside quantifiers to express the extent to which a predicate is true over a range of elements. Using quantifiers to create such propositions is called quantification.

There are two types of quantification-

  • Example 1: Let be the statement “ >“. What is the truth value of the statement ?
    Solution: As is greater than for any real number, so for all or .
  • Example : Let be the statement “ > 5″. What is the truth value of the statement ?
    Solution:is true for all real numbers greater than 5 and false for all real numbers less than 5. So .

Now if we try to convert the statement, given in the beginning of this article, into a mathematical statement using predicate logic, we would get something like-

Notice that the given statement is not mentioned as a biconditional and yet we used one. This is because Natural language is ambiguous sometimes, and we made an assumption. This assumption was made since it is true that a person can vote if and only if he/she is 18 years or older. Refer Introduction to Propositional Logic for more explanation.

Other Quantifiers –
Although the universal and existential quantifiers are the most important in Mathematics and Computer Science, they are not the only ones. In Fact, there is no limitation on the number of different quantifiers that can be defined, such as “exactly two”, “there are no more than three”, “there are at least 10”, and so on.
Of all the other possible quantifiers, the one that is seen most often is the uniqueness quantifier, denoted by .

  1. Restriction of universal quantification is the same as the universal quantification of a conditional statement.
  2. Restriction of an existential quantification is the same as the existential quantification of conjunction.

Definitions to Note:

1. Binding variables- A variable whose occurrence is bound by a quantifier is called
a bound variable. Variables not bound by any quantifiers are called free variables.
2. Scope- The part of the logical expression to which a quantifier is applied is called
the scope of the quantifier.

This topic has been covered in two parts. The second part of this topic is explained in another article – Predicates and Quantifiers – Set 2

This article is contributed by Chirag Manwani. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to [email protected] See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Attention reader! Don&rsquot stop learning now. Practice GATE exam well before the actual exam with the subject-wise and overall quizzes available in GATE Test Series Course.


Now You See Why a Section is 640 Acres?

So that’s how I knew a section represented 640 acres. OK so lets see what we can do with that number. Sections can be divided into halves (320 acres) and quarters (160 acres). So that’s the easy part. Then it has to get more confusing because EACH of those portions can then be divided again into halves and quarters. But its not terribly hard…. Its basic math. 40 acres here, 40 acres here, 40 acres here, 40 acres here. Do you see the logic? Good!

Now, there a reason I went into all this BEFORE I broke down the super confusing question. And that’s because the super confusing question doesn’t have to be that confusing question IF WE KNOW WHAT I JUST STATED. In the end the question wants us to know how many acres. They give us a bunch of gibberish in there but the reality is they want you to calculate an acreage amount by the price per acre and tell them what that total price was.

So lets look at the question and tear it apart. Let’s make this real estate license math make sense!


Gowers's Weblog

I have discussed how the mathematical meanings of the words “and”, “or” and “not” are not quite identical to their ordinary meanings. This is also true of the word “implies”, but rather more so. In fact, unravelling precisely what mathematicians mean by this word is a sufficiently complicated task that I have just decided to jettison an entire post on the subject and start all over again. (Roughly speaking what happened was that I wrote something, wasn’t happy with it for a number of reasons, made several fairly substantial changes, and ended up with something that simply wasn’t what I now feel like writing after having thought quite a bit more about what I want to say. The straw that broke the camel’s back was a comment by Daniel Hill in which he pointed out that “implies” wasn’t, strictly speaking, a connective at all.

I’ll mention a number of fairly subtle distinctions in this post, and you may find that you can’t hold them all in your head. If so, don’t worry about it too much, because you can afford to blur most of the distinctions. There’s just one that is particularly important, which I’ll draw attention to when we get to it.

“Implies” versus “therefore” versus “if … then”.

The three words “implies”, “therefore”, and “if … then” (OK, the third one isn’t a word exactly, but it’s not a phrase either, so I don’t know what to call it) are all connected with the idea that one thing being true makes another thing true. You may have thought of them as all pretty much interchangeable. But are they exactly the same thing?

Some indication that they aren’t quite identical comes from the grammar of the words. Consider the following three sentences.

The first one is the most natural of the three. The second doesn’t quite read like a proper English sentence (because it isn’t), and the third, though correct grammatically, somehow doesn’t quite mean the same as the first, which is partly reflected by the fact that it is two sentences rather than one. (I could have used a semicolon instead of the full stop, but a comma would not have been enough.)

Let’s deal with the difference between “Therefore” and “if … then” first. The third formulation starts with the sentence, “It’s 11 o’clock.” Therefore, it is telling us that it’s 11 o’clock. By contrast, the first formulation gives us no indication of whether or not it is 11 o’clock (except perhaps if there is a note of panic in the voice of the person saying the sentence). So we use “therefore” when we establish one fact and then want to say that another fact is a consequence of it, whereas we use “if … then” if we want to convey that the second fact is a consequence of the first without making any judgment about whether the first is true.

How about “implies”? Before I discuss that, let me talk about another distinction, between mathematics and metamathematics. The former consists of statements like 󈬏 is a prime number” or “The angles of a triangle add up to 180”. The latter consists of statements about mathematics rather than of mathematical statements themselves. For example, if I say, “The theorem that the angles of a triangle add up to 180 was known to the Greeks,” then I’m not talking about triangles (except indirectly) but about theorems to do with triangles.

The sort of metamathematics that concerns mathematicians is the sort that discusses properties of mathematical statements (notably whether they are true) and relationships between them (such as whether one implies another). Here are a few metamathematical statements.

In each of these four sentences I didn’t make mathematical statements. Rather, I referred to mathematical statements. The grammatical reason for this is that the word “implies”, in the English language, is supposed to link two noun phrases. You say that one thing implies another.

A noun phrase, by the way, is, roughly speaking, anything that could function as the subject of a sentence. For instance, “the man I was telling you about yesterday” is a noun phrase, since it functions as the subject of the sentence,

Other noun phrases in that sentence are “his bicycle” and “the third time”.

Let me write something stupid:

I wrote that because there is an important difference between two kinds of nonsense. The above sentence doesn’t make much sense, because you can’t imply a bicycle. However, it is at least grammatical in a way that

All this means that when we use “implies” in ordinary English, we are not connecting statements (because statements are not noun phrases) but talking about statements (because we use noun phrases to refer to statements).

I can think of three ways of turning statements into noun phrases. The first is rather crude: you put inverted commas round it. For example, if I want to do something about the incorrect sentence

then I could change it to

The second method is to come up with some name for the statement. That doesn’t work well here, but let’s have a go.

It works better for mathematical statements with established names such as the Bolzano-Weierstrass theorem.

The third method is to stick “that” or something like “the claim that” in front.

I mentioned above that “implies” is not, strictly speaking, a connective. Why is this? It’s because connectives are used to turn mathematical statements into mathematical statements. For example, we can use “and” to build the statement “ is prime and ” out of the two statements “ is prime” and ““. When we do that, the new statement isn’t referring to the old statements, but rather it contains them.

Unfortunately, as so often with this kind of thing, common mathematical usage is more complicated than the above discussion would suggest. Most people read the “” symbol as “implies”. And most people are quite happy to write something like

which, according to what I said above, is ungrammatical because “implies” is not linking noun phrases. What I suggest you do here is not worry about this too much: confusion between mathematics and metamathematics is unlikely to be a problem when you are learning about Numbers and Sets and about Groups. If you are inclined to worry, then you could resolve to read a sentence like the above as “If then ” I would also say that the symbol “” should in general be used fairly sparingly. In particular, don’t insert it into continuous prose. For instance, don’t write something like, “Therefore and ” Instead, write, “Therefore and which implies that ” (Note that in that last sentence the word “which” functioned as the subject of “implies” and referred back to the statement “ and “.)

Quotation and quasi-quotation.

If you like subtle distinctions that will not matter in your undergraduate mathematical studies, then read on. If you don’t, then feel free to skip this short section.

The distinction I want to draw attention to is between two uses of quotation marks. Just for good measure, let’s look at three different ways of doing something with the sentence, “There are infinitely many primes.”

  1. There are infinitely many primes, but only one of them is even.
  2. “There are infinitely many primes” is a famous theorem of mathematics.
  3. “There are infinitely many primes” is an expression made up of five words.

The first of these sentences is about numbers. As such, it doesn’t use quotation marks. The third sentence is about a linguistic expression. As such, it very definitely requires quotation marks, just as they are needed in the sentence

As for the second sentence, it is somewhere in between. It isn’t about numbers, but it’s also not about a linguistic expression. It’s about a mathematical fact. This use of quotation marks is sometimes called quasi-quotation. I won’t say any more but will instead refer you to the relevant Wikipedia article if you are interested. [Thanks to Mohan Ganesalingam for drawing my attention to it.]

Yes, but what do “if … then” and “implies” mean?

I’ve just spent rather a long time discussing the grammar of “implies”, “therefore” and “if … then” and said almost nothing about what they actually mean. To avoid confusion, I’m mainly going to discuss “if … then” since there is no doubt that that really is a connective. But sometimes I’m going to want to do what I’ve done in previous posts and use the letters P and Q to stand for statements, and here, unfortunately, there is a danger of the confusion creeping back. In particular, if one is being careful about it then one needs to be clear what “standing for a statement” actually means.

Is it something like the relationship between “The Riemann hypothesis” and “Every non-trivial zero of the Riemann zeta function has real part 1/2”? That is, are P and Q names for some statements? Not exactly, because we want to be able to make sense of the expression (recall that is a symbolic way of writing “and”) and the word “and” links statements rather than names. (You don’t, for example, say, “The Riemann hypothesis and Fermat’s Last Theorem” if you want to assert that the Riemann hypothesis and Fermat’s Last Theorem are both true.) So we should think of P and Q as statements themselves — it’s just that they are unknown statements.

But in that case we shouldn’t be allowed to write or at least not if means “implies”. But that’s just too bad. I’m going to write it, and if you’re worried about it then read “” as “if P then Q”. But actually what I recommend is not worrying about it and just knowing in your heart of hearts that it would be easy to replace what you are saying by something that is strictly correct if there was ever any danger of confusion.

So let us pause, take a deep breath, allow everything I’ve written so far to slip comfortably into the back of our minds, and turn to the question of what “if … then” and “implies” actually mean. And the answer is rather peculiar. In everyday English, when we use one of these words, we are trying to explain that there is a link between the two statements we are relating (either directly or by referring to them). For example, if I say, “If we continue to emit carbon dioxide into the atmosphere at the current rate then sea levels will rise by two metres by 2100,” I am suggesting a causal link between the two.

Let me now give the standard account of what mathematicians mean by “if … then”. Later I shall qualify it considerably — not because I think it is incorrect but because I think it doesn’t give the whole picture and can be unnecessarily off-putting. The standard thing to say is that is true unless is true and is false. That is, if you want to establish that then the only thing that can go wrong is being true and being false.

A brief interruption: purists will note that I have been inconsistent. If is a statement rather than something that refers to a statement, then I can’t say “ is true”. I have to say, “”” is true.” Alternatively, I should have said, “ unless and .” Can we agree that I’ll be slightly sloppy here? (If you don’t understand why it’s sloppy, I don’t think it matters.)

Let me illustrate this with a few examples.

Of these four statements, the fourth one seems quite reasonable, while the other three are all a bit peculiar. For example, it’s quite obvious that (the recent Pink Floyd stunt notwithstanding) pigs cannot fly. Doesn’t that make the first sentence false? And how can one say that the Riemann hypothesis implies Fermat’s Last Theorem when nobody expects a proof of Fermat’s Last Theorem that uses the Riemann hypothesis? And surely if is both even and odd, it could just as well be 19. Can it be correct to say that it has to be 17? As for the fourth sentence, it seems fine: if is a prime not equal to 2, then it cannot have 2 as a factor (or it wouldn’t be prime), so it must indeed be odd.

Well, mathematicians would say that all four statements are true. That’s because the only way “If P then Q” can be false is if P is true and Q is false. You should understand this as a definition of “if … then”. Let’s check the four statements using this definition.

For the first one to be false, we would need there to have been weapons of mass destruction in Iraq and for pigs to be unable to fly. Well, we’ve got the earthbound pigs but there were no weapons of mass destruction in Iraq, so the first statement is true. (Again, this is not some metaphysical claim. It just follows from the way we have chosen to define “if … then”.)

For the second to be false, we would need the Riemann hypothesis to be true and Fermat’s Last Theorem to be false. Well, Andrew Wiles, with help from Richard Taylor, has proved Fermat’s Last Theorem, so it’s not false. So the second statement in the list is true.

As for the third, the only way for that to be false is if is both even and odd but is not equal to 17. But no number is both even and odd. Therefore, the third statement is true. The problem about equalling 19 doesn’t arise because there are no even and odd integers in the first place.

Truth values and “causes”.

There’s something unsatisfactory about the truth-value definition of “if … then” and “implies”. It seems to leave out the idea that one thing can be true because another is true. It would be quite wrong to say, for instance, that Fermat’s Last Theorem is true because the Riemann hypothesis is true.

Fortunately, there is a very close link between the truth-value definition and what I’ll call the causal concept of “if … then”. I’m not going to attempt a precise definition of the causal concept — I’m just referring to the basic idea of one statement’s being a reason for another.

Let’s go back to the one statement that felt reasonable in the list above. It was this.

Now comes another somewhat subtle distinction, and this is the one I really care about. What does that statement above actually mean? I think a very natural way of interpreting it is this.

In other words, although it looks like a statement about some fixed number , the fact that we have been told nothing whatsoever about makes us read it in a slightly different way. We say to ourselves, “Since we’ve been told nothing at all about this must be intended as a general statement about an arbitrary So what it’s really saying is that if a positive integer has one property — being a prime not equal to 2 — then it has another — being odd.” If we’re thinking about things that way, then it’s rather tempting to say that the property “is a prime not equal to 2” implies the property “is odd”.

What I’ve just suggested is not standard mathematical practice, but in principle it could have been. However, it is incredibly important in mathematics to be completely sure at all times what kinds of objects one is dealing with. I said earlier that “if … then” connects statements and “implies” connects noun phrases that refer to statements. I did not say that either of them connects properties. So if I want to say that one property implies another, then I have to be absolutely clear that this is a different meaning of the word “implies” (even if it is related to the previous one).

OK, so let me be careful. First of all, what is a property? It’s what you get when you take a statement that concerns a variable and you remove that variable. For example, if I take the statement “ is a perfect square” and remove the variable from it, I get the property “is a perfect square”. A property is a thing you say about something else. (It’s almost like an adjective, but not quite because of the extra “is”.) If you want to be more formal about it, if you are given a set like the set of all positive integers, a property associated with that set is a function from elements of the set to statements. For example, the property “is prime” takes the number to the statement “ is prime”. (It is more conventional to say that all we actually care about is the truth values of these statements. So the property “is prime” takes the value TRUE at each prime number and FALSE at all other numbers. I’ll stick with my unconventional discussion here.)

Now suppose that we have two properties A and B associated with the positive integers. When do we say that A implies B (according to my unconventional definitions)? Well, for each positive integer we have a statement and a statement I’ll say that implies (in the property sense) if for every positive integer , the statement implies the statement (in the truth-value sense). In other words, whenever is true, so is and otherwise anything can happen. In the example above, is the property “is a prime not equal to 2”, is the property “is odd”, and for each is the statement “ is a prime not equal to 2″ and is the statement “ is odd”. Every time is true, which it is when , so is This gives us the feeling that the property “causes” the property .

Let me go back to the statement that seemed reasonable.

It’s important to be careful about what this means. Is it a statement about some specific ? If so, then we must interpret the “if … then” in the strict truth-value sense. Or is it really a way of saying, “Every prime not equal to 2 is odd”? In that case, it has more of a causal feel to it.

The best way to keep everything clear at all times is not to write the above sentence when you’re really talking about all Instead, you can write

Now, if you pick out just the part of this statement that says, “If is a prime not equal to 2, then is odd,” then you have something that must be interpreted in the truth-value sense. But when you apply those truth-value statements to all positive integers simultaneously, what you end up with is the nice “causal” statement that the property “is a prime not equal to 2” implies the property “is odd”.

A silly deduction and a sensible deduction.

Because there is a sort of causal notion of implication, and because it is in a way what we really care about when doing mathematics, I very much prefer to illustrate the meaning of “implies” or “if … then” with reference to examples that include variables. If I just take two fixed statements like “Margaret Thatcher used to be Prime Minister of the UK” and “there was recently a tsunami in Japan” and tell you that, despite the lack of any obvious relationship between them, the first statement implies the second statement because the second statement happens to be true, then it it is clear the notion of implication I am using has nothing to do with one thing being true because another thing is true: not even the most rabidly left-wing person is going to blame the Japanese tsunami on Thatcher’s premiership. But a statement like, “If then ,” is completely reasonable. Moreover, because is a general element of which might be an infinite set, we can’t establish a statement like this by running through all and checking the truth values of the statements and Rather, we have to give a proof — that is, an explanation of why must belong to if it belongs to Thus, once you start looking at statements with variables, the truth-value notion of implication forces you to look for “reasons” and “causes” so that you can establish lots of truth-value facts at once. (I’m leaving out the possibility here that a statement could in some sense “just happen to be true”. For example, many people take seriously the following possibility. Perhaps the property “is even and at least 4” implies the property “is a sum of two primes” in the sense that no number is even and at least 4 without being a sum of two primes, but perhaps also there isn’t a reason for this — perhaps it just happens to be the case.)

Here’s another illustration of the difference between statements that involve parameters and statements that don’t. Consider the following claim.

I’m going to prove it in two different ways.

Proof 1. is irrational, so the statement “ is rational” is false, and therefore implies all other statements. In particular, it implies that there is an integer that is both even and odd.

Proof 2. If is rational, then we can find positive integers and such that which implies that Let be the largest integer such that is a multiple of Since is a perfect square, must be even. (To see this, just consider the prime factorization of ) But and the largest k for which is a multiple of is odd. (To see this, just consider the prime factorization of ) Therefore, is both even and odd, which proves the result.

Which of these two arguments is more interesting? Undoubtedly the second, since it actually gives us a proof of the irrationality of So is the first argument valid at all? You might object to it on the grounds that it uses without proof the fact that is irrational. But we can make the question more interesting as follows. There is (it happens) a different proof of the irrationality of that does not involve the statement that some positive integer is both even and odd. What if we used that argument, concluded that “ is rational” was false, and then went on to deduce “there exists an integer that is both even and odd” in the way that argument 1 does above. Would that be a valid deduction?

I think the answer has to be yes, but it is not an interestingly valid deduction. It is not showing that the irrationality of is in any way caused by a contradiction that involves parity, since we deduced that from another, and unrelated, false statement.

If we think of implication as primarily something we apply to statements with parameters, and therefore indirectly and in a different sense to properties, then our starting point is not the statement “ is irrational” but rather the statement ““. And our conclusion, that there exists an integer that is both even and odd, is deduced from the more precise (and informative) statement, “the highest such that is a multiple of is both even and odd”.

As a final remark about the above example, which allows me to emphasize a point I have already made, suppose that I start a proof of the irrationality of by writing,

What I am really saying is that whatever and might be, if then In other words, although it looks as though I’m talking about a specific pair and in fact I’m making a general deduction.

What’s good about the usual convention concerning “if … then” and “implies”?

I think I have partially answered this question by pointing out that when we consider statements with parameters then the truth-value meaning of “implies” feels a lot closer to the more intuitive “causal” meaning of “implies”. However, the agreement isn’t total. One of the “silly” examples from early in this post was this.

This looks odd, because although we know that can’t be both even and odd, we also feel that if were even or odd, there would be nothing about that fact that steered towards the number 17 as opposed to any other number. I can’t deny the feeling of oddness. All I can say is that the hypothetical situation never arises because the hypothesis, that is even and odd, is impossible.

What I can do, however, is explain why I don’t want to try to find a different convention that would make this statement false. I don’t want to do that because it would force me to give up some general principles that I like. One of those I have already mentioned:

I hope you’ll agree that that looks highly reasonable, and we don’t want to start having ugly exceptions to it if we don’t have to.

Here’s another mathematical principle that I think you will also have to agree with.

Now let’s apply these two principles. I’m going to let be the property “is both even and odd” and I’m going to let be the property “equals 17”. Then the set of such that is the empty set (since no is both even and odd). The set of such that is the set Since the empty set is a subset of the set the first principle tells us that implies

To summarize this discussion, the formal mathematical notion of implication is a bit strange, but most of the strangeness disappears if you just look at statements with parameters, which tend to be the statements we care about. Each such statement corresponds to a property of those parameters, and implication of properties is closer to our intuitive notion of one thing “making” another true than implication of statements. Even then there are one or two oddnesses, but these are a small price to pay for the cleanness and precision of the definition and for the fact that it allows us to hold on to some cherished general principles.

An exercise — not to be taken too seriously.

(i) Prove that Borsuk’s conjecture implies the Riemann hypothesis.

Hint: if you find part (i) difficult, then you are not applying one of the pieces of general study advice I gave in the first post of this series.


Watch the video: Predicates and QuantifiersExersice to 23 (October 2021).