SM242 Week 3 (Notes based on Epp Chapter 1 and Chapter 2)
I. Logic (continued)
26. The eight classic valid argument forms (The “Rules of Inference for Propositions”)
A.Modus Ponens symbolic form
Example
If he lives on board ship then he is a crewmember.
He lives on board ship
He is a crewmember.
Prove the validity of modus ponens.
B.Modus Tollenssymbolic form
Examples
If it rained recently then the grass will be wet
The grass is not wet
It did not rain recently.
If he lives in Bancroft Hall then he is a midshipman.
He is not a midshipman
Aside: The fancy-schmancy name for an argument consisting of two premises and a conclusion is a syllogism. Modus ponens and modus tollens are forms of syllogisms.
C.Disjunctive Addition (Generalization)symbolic form
Examples:
MIDN Rabe is an IT major
MIDN Rabeis a CS major or and IT major
MIDN Collardis on the Dant’s List
MIDN Collardis on the Dean’s List or the Dant’s List
D.Conjunctive Simplification (Particularization)symbolic form
Examples:
MIDN Porter understands while loops and understands for loops
MIDN Porter understands while loops
MIDN Marsal plays sports on Wednesday and plays sports on Friday
MIDN Marsal plays sports on Wednesday
E.Disjunctive Syllogism (Elimination)symbolic form
Examples:
The answer to the question is either choice a or choice b
The answer is not choice a
The sub will moor at Pier 1 or Pier 2
The sub will not moor at Pier 1
F.Hypothetical Syllogism(Transitivity)symbolic form
Example:
If my roommate snores then I will not get any sleep
If I do not get any sleep then I will fail tomorrow’s quiz
G.Division into casessymbolic form
Example:
I will take the stairs or I will take the elevator
If I take the stairs then I will be on time
If I take the elevator then I will be on time
H.Contradictionsymbolic form
SUMMARY
Modus Ponens symbolic form
Modus Tollens symbolic form
Disjunctive Addition (Generalization) symbolic form
Conjunctive Simplification (Particularization) symbolic form
Disjunctive Syllogismsymbolic form
Hypothetical Syllogismsymbolic form
Division into cases symbolic form
Contradiction symbolic form
27. Example
You have to decide if you will be back in time for muster. Consider the following statements to be true:
- It is not sunny and it is colder than yesterday.
- You will go running only if it is sunny.
- If you do not go running then you will see a movie.
- If you see a movie then you will be back in time for muster.
Question: Will you be back in time for muster?
28. Example (Text page 35)
You are about to leave for class in the morning and discover you don’t have your glasses. You know the following statements are true:
- If my glasses are on the kitchen table, then I saw them at breakfast.
- I was reading the newspaper in the living room or I was reading the newspaper in the kitchen.
- If I was reading the newspaper in the living room, then my glasses are on the coffee table.
- I did not see my glasses at breakfast.
- If I was reading my book in bed, then my glasses are on the bed table.
- If I was reading the newspaper in the kitchen, then my glasses are on the kitchen table.
If the choices are kitchen table, coffee table or bed table, where are your glasses?
We can present the foregoing argument using symbolic logic.
Let
p = My glasses are on the kitchen table.
q = I saw my glasses at breakfast.
r = I was reading the newspaper in the living room.
s = I was reading the newspaper in the kitchen.
t = My glasses are on the coffee table.
u = I was reading my book in bed.
v = My glasses are on the bed table.
Then the statements from above translate into the following.
The following deductions can be made.
29. Example (Smullyan) “Knights and Knaves”
There is an island containing two types of people: knights who always tell the truth and knaves who always lie. (A “knave” is a deceitful person.) You visit the island and are approached by two natives who pronounce as follows:
A says: “B is a knight.”
B says: “A and I are of opposite type.”
What are A and B? (i.e., classify each of them as either a knight or a knave)
30. Example (Rosen)
Consider the following statements to be true:
- If you send me an email message then I will finish writing the program.
- If you do not send me an email message, then I will go to sleep early.
- If I go to sleep early, then I will wake up feeling refreshed.
Can we draw the following conclusion: If I do not finish writing the program then I will wake up feeling refreshed.
More examples (pages 9-11 optional; cover if time permits)
Problem 1. You are cleaning your room in preparation for the inspection when you discover a note signed by a MIDN John McCain. The note reads:
“To the lucky midshipman who finds this note: Greetings! I’m fairly certain that I will be President some day and quite rich, so I have no need for my midshipman salary. I have taken my vast fortune amassed as a midshipman, and buried it on the NavalAcademy. I am honest and the following statements are all true. Happy hunting!”
MIDN McCain went on to become an aviator, so he couldn’t just tell you where the treasure is (that would be too easy). Instead, his note provides the following statements (all true).
- If Bancroft Hall is next to a river, then the money is not in King Hall.
- If the tree in front of T-Court is an elm, then the money is in King Hall.
- Bancroft Hall is next to a river.
- The tree in front of T-Court is an elm or the money is buried under the flagpole.
- If the tree near the AdminBuilding is an oak, then the money is in Room 123.
Where is the money hidden?
Problem 2. Consider the statements assumed to be true:
- If it does not rain or it is not foggy, then the parade will be held and MIDN Berrios will yell at MIDN Richardson for having his shirt not tucked in.
- If the parade is held then the Color Company trophy will be awarded.
- The Color Company trophy was not awarded.
Question: Did it rain?
Problem 3. Consider the statements assumed to be true for MIDN Tublin:
- I am either clever or lucky.
- I am not lucky.
- If I am lucky, then I will win the lottery.
Did MIDN Tublin win the lottery?
Problem 4. There is an island (yes, that island again) containing two types of people: knights who always tell the truth and knaves who always lie. (A “knave” is a deceitful person.) You visit the island and are approached by two natives who pronounce as follows:
A says: “Both of us are knights.”
B says: “A is a knave.”
What are A and B? (i.e., classify each of them as either a knight or a knave)
Problem 5. Is the following argument a valid argument:
If MIDN Harrison is a junior then he is 30 feet tall.
MIDN Harrison is a senior.
MIDN Harrison is 30 feet tall
Problem 6. Is the following argument a valid argument:
If USNA is a military base then USNA has lots of people walking around in uniform.
USNA has lots of people walking around in uniform.
USNA is a military base.
31.Fallacies. A fallacy is incorrect reasoning which results is an invalid argument. Two common fallacies are the converse error and the inverse error.
The Converse Error (“the fallacy of confirming the conclusion”)
pq
q
p(WRONG!!! INVALID)
Examples:
If MIDN Muir is a student at USMA then he is at least 18 years old.
MIDN Muir is at least 18 years old.
MIDN Muir is a student at USMA.
If you do every problem in the textbook then you will learn discrete math.
You learned discrete math.
Therefore, you must have done every problem in the textbook.
The Inverse Error (“the fallacy of denying the hypothesis”)
p q
~ p
~ q(WRONG!!! INVALID)
Example:
If Osama Bin Laden is in a cave, then he will be caught.
Osama Bin Laden is not in cave.
Osama Bin Laden will not be caught.
32. Other invalid argument forms.
Begging the Question (“Circular Reasoning”). This occurs when we attempt to show an argument is valid by assuming the truth of the conclusion.
Example (Labossiere)
Bill: “God must exist.”
Jill: “How do you know?”
Bill: “Because the Bible says so.”
Jill: “Why should I believe the Bible?”
Bill: “Because it was written by God.”
Example
MIDN Murphy: “I would like to wear civilian clothes to SM242. Why is that illegal?”
MIDN Rabe: “If such actions were not illegal, they would not be proscribed by MIDREGS.”
Arguing from Examples. It is incorrect to conclude that a proposition is true just because it is true for specific cases.
Example
MIDN Berrios is a junior.
MIDN Collard is a junior.
MIDN Cunha is a junior.
Therefore…all MIDN are juniors.
Example
Senator Boxer is a liberal Democrat.
Senator Feinstein is a liberal Democrat.
Nancy Pelosi is a liberal Democrat.
Therefore…all people in California are liberal Democrats.
******* The remainder of this page is optional.
Red Herring (“Smoke Screen”). A red herring is an irrelevant proposition thrown into an argument to cause distraction. The idea is that if the listener agrees with the red herring, they will agree to the original (unrelated) proposition.
Examples (Norton)
Person 1: "If the world's governments eventually decide to stabilize the concentration of greenhouse gases in the atmosphere, a huge reduction in the emissions of carbon dioxide will be required."
Person 2: "If Person 1 presumes to write about the climate change issue she should know some basics -- like the fact that about 98 percent of greenhouse gases are natural and not manmade."
The red herring:
Dixy Lee Ray made several claims attempting to show that CFCs were only a minor source of stratospheric chlorine. For example, she wrote "Sea water evaporation provides the atmosphere with 600 million tons of chloride per year."
The red herring:
33. Quantifiers (Epp Chapter 2!)
- Way back in the first five minutes of the first class, we asked if the following sentence was a statement (i.e., a proposition):
He is a midshipman.
We decided that this was not a statement since we don’t know who “He” is. If “He” is intended to be MIDN Tinkham, the sentence is true, whereas if “He” is intended to be VADM Fowler, the sentence is false. So, the sentence may be true or false, depending on who “He” is. As such, the sentence is not a proposition.
- Predicates. Imagine that you are back in your 4th grade English class: What is the subject and what is the predicate in the sentence: “He is a midshipman.”
In English, the predicate is that part of the sentence which gives information pertaining to the subject.
Let P stand for the words “is a midshipman.” We will say that P(x) means “x is a midshipman.” x is called a predicate variable. P(x) is called a predicate.
Suppose we substitute a specific value for x. Let x = MIDN Tinkham. What is P(x)?
Is this a statement?
Let x = VADM Fowler. What is P(x)?
Is this a statement?
When we substitute a specific value for our predicate variable, the predicate becomes a statement.
- Example
Consider the sentence: He resides there. Is this a statement?
Suppose I represent “x resides at y” as P(x,y). P(x,y) is called a predicate. x and y are predicate variables.
Suppose x = MIDN Hess and y = Bancroft hall. What is the resulting sentence.
Is this a statement?
- The Domain of Predicate Variables.
For now, we will say that the domain of a predicate variable consists of all values that may be reasonably substituted in place of the predicate variable. This may sound like a rather loose definition of domain, but, as we will see, the domain is usually either given or implicitly defined from the context.
Examples:
Let P(x) be “x is a midshipman.”
What is the domain of x?
Let P(x,y) be “x resides at y.”
What is the domain of y?
- The Universal Quantifier
- We have seen that we can change a predicate into a statement by substituting specific values in for the predicate variable(s).
We can also change a predicate into a statement by “quantifying” the predicate variable(s).
- The universal quantifier is denoted as and is read “for all.” Suppose we have a predicate P(x), where x has the domain D. Then
x in D, P(x)
is a statement that is read as
Note: The notation
x in D, P(x)
is often presented as
(description of the domain) x, P(x)
which is read “For all (description of the domain) x, P(x).” As you do examples you will become familiar with both notations.
- A statement of the form x in D, P(x) is called a universal statement.
- The truth-value of a universal statement. The statement x in D, P(x) is true iff
This statement is false iff
- Example
Let P(x) be “x is a student at USNA.” Let the domain D be the Brigade of Midshipman.
Express x in D, P(x) as an English sentence using both notations discussed above.
Is this a statement?
Is it true of false?
- Example
Let P(x) be “x is mortal.” Let the domain D be all human beings.
Express x in D, P(x) as an English sentence using both notations described above.
Is this a statement?
Is it true or false?
From this point on we will use, interchangeably, one of our two notations discussed above (and will not present both notations each time).
7. Example: Let D be the numbers 1, 2 and 3. Consider the statement: x in D,
Is this statement true or false?
8. Example: Let D be the numbers –1, 1, 2. Consider the statement: x in D,
Is this statement true or false?
- Alternate English representations of
- Propositional calculus and predicate calculus. Up to this point, we have termed our studies “symbolic logic.” We have avoided the word “calculus” up to this point, for fear that it would be confused with (or conjure up horrible memories of) the calculus you learned in SM121, SM122 and SM223. Fear not! We are now going to use the word calculus, but our use of the term relates only to the Latin etymology: to calculate using special notation.
What we have called symbolic logic has two important braches:
The analysis of compound propositions (everything we did before this lecture) is called propositional calculus.
The analysis of predicates and quantified propositions (which we are undertaking now) is called predicate calculus.
- The Existential Quantifier
- The existential quantifier is denoted as and is read “there exists.” Suppose we have a predicate P(x), where x has the domain D. The statement
x in D such that P(x)
is read: “There exists an x in the domain D such that P(x).”
Note: The notation
x in D such that P(x)
is often presented as
(description of the domain) x such that P(x)
which is read “There exists (description of the domain) x such that P(x).” As you do examples you will become familiar with both notations.
- Example. Express the sentence “There is a midshipman in 10th Company,” using the existential quantifier.
- Alternate English representation of
- A statement of the form x in D such that P(x) is called an existential statement.
- The truth-value of an existential statement. The statement x in D such that P(x) is true iff
- Example. Let D be the set of integers. Is the statement: kin D s.t. k=k! true of false?
7. Example. Let D be the integers 2, 3 and 4. Is the statement k in D s.t. k = true or false?
- Translating between English and symbolic logic.
- Translate the following statements to English.
a. real numbers y,
b. a midshipman m s.t. m weighs more than 250lbs.
c. quiz scores k,
- Translate the following English statements to symbolic logic.
- All pentagons have five sides.
- No midshipman has a Bachelor’s Degree.
c. Some midshipman are CS majors.
- The number 10 can be written as the sum of two even integers.
- Universal Conditional Statements. A Universal conditional statement is a statement of the form.
x, if P(x) then Q(x)
Note: we often will omit explicit mention of the domain in universal conditional statements.
1. Example: Express each of the following statements as an English sentence.
a. military personnelx, if x is an Ensign then x is a naval officer.
b. Ensigns x, x is a naval officer.
2. Looking at the two examples above, we see that
military personnel x, if x is an Ensign then x is a naval officer.
means the same as
A statement of the form
x in D1, if P(x) then Q(x)
is the same as
x in D, Q(x)
provided
3. Example: Consider the universal statement: integers x, if x is even then x is divisible by 2. Express this as an English statement.
Note that the given universal conditional statement can also be expressed as:
which can be expressed in an English statement as
4. Example: Express each of the following English statements using symbolic logic.
a. If a student is in this class, then the student can program.
b. Let x be a real number. If x >3 then .
c. All dogs have fleas.
d. No midshipman is sleepy in SM242.
x, if x is a midshipman then x is not sleepy in SM242.
midshipman x, x is not sleepy in SM242.
- Negations of Quantified Propositions
- The negation of a universal statement
Consider the statement: All midshipmen take SM242. How would you negate this statement? Remember that the negation must satisfy the following:
Suppose we say the negation of All midshipmen take SM242 is
Suppose one midshipman takes SM242. Then the statement
All midshipmen take SM242 is false
and our proposed negation
Both the original statement and our proposed negation are false, so one cannot be the negation of the other. In actuality, the negation of All midshipmen take SM242 is
In general, the negation of the universal statement
x in D, P(x)
is the existential statement
Example. What is the negation of the statement: integers x ,
Example. What is the negation of the statement “No lawyers are honest.”
The statement can be symbolically represented as
for which the negation is
- The negation of an existential statement
Consider the statement: Some midshipmen are sleepy. How would you negate this statement?
Remember that the negation must satisfy the following:
- When the original statement is true, the negation is false
- When the original statement is false, the negation is true.
Suppose we say the negation of Some midshipmen are sleepy is
Suppose half of all midshipman are sleepy. Then the statement
Some midshipmen are sleepy is true
and our proposed negation
Both the original statement and our proposed negation are true, so one cannot be the negation of the other. In actuality, the negation of Some midshipmen are sleepy is
In general, the negation of the existential statement
x in D such that P(x)
is the universal statement
Example What is the negation of the statement:a midshipman x such that x has an IQ over 250.
Example. What is the negation of the statement “Some midshipmen are over 27.”