Discrete Math B: Chapter 6 – Logic 20
Chapter 6: Logic
Logic is the formal study of correct reasoning. Applications of mathematical logic include modern computing, electric circuitry, modern and ancient philosophy, and entertainment (logic puzzles).
6.1 Statements
· A statement is a ______sentence that is either ______or ______but not
______simultaneously.
To prevent paradoxes in the study of logic, we will never allow statements to refer to themselves.
· A compound statement is one or more ______combined by logical
connectives like and, or, not, or if… then. The parts of the compound statement are called
______statements.
· A negation is basically the ______truth of the original statement.
The negation of a true statement if false. The negation of a false statement is true.
Symbols
To simplify work with logic, symbols are used.
(see table)
Statements are represented by letters such as p, q, or r.
Truth Table for NegationP / ~P
T
F
Truth Tables
A Truth Table shows all possible combinations of truth values for the component statements, as well as the corresponding truth value for the compound statement under consideration.
AND
Truth Table for ConjunctionP / Q / P ˄ Q
T / T
T / F
F / T
F / F
Example: My eyes are brown and your eyes are blue.
This statement is only true if ______component statements
are ______.
Example: Find the truth of
Note: In English, “but” and “and” have the same logical meaning.
“I do not have a dime but I do have a quarter.” “I do not have a dime, and I do have a quarter.”
OR
“Or” in English can be a bit ambiguous.
Example: Those with a passport or driver’s license will be admitted.
Example: You can have a piece of cake or a piece of fruit.
Truth Table for DisjunctionP / Q / P ˅ Q
T / T
T / F
F / T
F / F
In logic, we will use the first meaning “p or q or both”
The only way a disjunction is false is if BOTH component statements are false.
Homework: Lesson 6.1
pg 273-276 #1 – 20, 23-28, 35- 46, 65, 66, 72, 73
6.2 Truth Tables and Equivalent Statements
To construct a truth table for a compound statement, first start by listing all possible values of the component statements.
2 statements à 4 rows possibleP / Q / Compound Statement
T / T
T / F
F / T
F / F
3 statements à 8 rows possible
P / Q / R / Compound Statement
T / T / T
T / T / F
T / F / T
T / F / F
F / T / T
F / T / F
F / F / T
F / F / F
In general for this course, we will only be constructing truth tables for 2 or 3 statements. We will always use the following setups:
Example 1: Give the number of rows in the truth table for each compound statement.
a) b)
Example 2: Construct a truth table for
Example 3: Construct a truth table for
Example 4: Construct a truth table for
Equivalent Statements
· Two statements are equivalent if they have the same ______in every possible situation. (Last column of truth table the same)
Example 5: Are the statements and equivalent?
De Morgan’s Laws are very useful in simplifying the negation of a compound statement.
Example 6: Write the negation of each statement, applying De Morgan’s Laws to simplify.
a. The basketball is round and the train is fast.
b. She makes the bed or I do not make the bed.
c. Mary won’t try and Ellen won’t succeed.
d. e.
Homework: Lesson 6.2
pg. 283 – 285
#1-4, 9-12, 14, 16, 17, 19, 20, 26-34evens, 51
6.3 The Conditional and Circuits
If you build it, he will come.
If I pay attention, then I might learn something.
· A conditional statement is a compound statement that uses the connective if…then or anything equivalent.
Some conditionals are hard to see.
Example: “Winners never quit.” If ______,
then ______.
Example: “Real men don’t each quiche.” If ______,
then ______.
Truth Table for a Conditional
Suppose a politician says “If I am elected, then taxes will go down.”
4 Possibilities / I am elected. / Taxes go down. / Recap / Truth of Politician’s Statement1 / yes / yes / p is T, q is T
2 / yes / no / p is T, q is F
3 / no / yes / p is F, q is T
4 / no / no / p is F, q is F
Basically, the only way you can PROVE the politician’s statement is FALSE is if the antecedent is TRUE, but the consequent is FALSE.
Example 1: Find the truth value of each statement.
a) b)
c) d)
Example 2:
Let p represent a false statement, let q represent a false statement, and let r represent a true statement.
Is the conditional statement true or false?
a) b)
Example 3: Construct a Truth Table for the statement.
· A contradiction is any statement that is always ______regardless of the truth values of the components.
Example 4: Construct a Truth Table for the statement.
· A tautology is any statement that is always ______regardless of the truth values of the components.
Translating Conditionals to “OR” statements.
If p, then q. (Not p) or q.
Example 5: Write the following statements without using the if… then.
a) If it is raining, then I will take an umbrella.
b) I would read a book if I had more time.
Negation of a Conditional
Example 6: Write the negation of each statement.
a) If you build it, he will come.
b) It must be alive if it is breathing.
Circuits
Here is an electrical switch.
Current can only flow through the switch when it is closed and not when it is open.
Here is a series circuit.
Current can flow only when both circuits are closed.
LOGIC: This corresponds to , which is only true when p and q are both true.
Here is a parallel circuit.
Current can flow when p or q or both switches are closed.
LOGIC: This corresponds to , which is true when p is true, q is true, or both is true. This is only false when both p and q are false.
Logic is used to represent and then simplify circuits using symbolic logic.
There are 11 equivalence statements that can be used to make a seemingly complicated circle much more simple to understand and thus cheaper to produce.
More circuits:
Equivalence Statements for Logic
Any of these equivalence statements can be used to simplify circuits or statements of logic.
Homework: Lesson 6.3
pg 295 – 298 #9 – 12all, 14 – 20 even, 21 – 30 all, 34, 36, 39, 46 – 56 even.
6.4 More on the conditional
We discussed in the last section that sometimes conditional “If… Then… statements” are not obvious.
For example: “Good students study for tests.” If ______
then ______.
Also conditionals might appear “backwards” like “You need to turn in your homework if you want an A.”
If ______, then ______.
Alternate Forms of the Conditional P à Q If it is raining, then I take an umbrella.
· sufficient “P is sufficient for Q”
· necessary “Q is necessary for P”
· implies “P implies Q”
Example 1: Write each statement as an “If…., then….”
a) You can go to the movies when your work is done.
b) Smiling is sufficient for not frowning.
c) Being neither ecstatic nor depressed is necessary for feeling content.
d) All irrational numbers are real numbers.
Converse, Inverse, and Contrapositive
If today is Friday, then tomorrow is Saturday.
The converse of P à Q is when the original statements are interchanged Q à P.
Example of Converse:
The inverse of P à Q negates both original statements ~P à ~Q
Example of Inverse:
The contrapositive of P à Q interchanges and negates both statements ~Q à ~P.
Example of the Contrapositive:
Examples: For each given statement, write (a) the converse, (b) the inverse, and (c) the contrapositive in the if,.. then, … form. It may be helpful to restate the original statement in the if… then… form if it isn’t already.
Ex. 2 If you are awake, then you are in class.
Ex. 3 You feel full if you eat a lot at dinner.
Ex. 4 Cheaters never prosper.
Ex. 5 ~P à Q Ex. 6 (P ^ ~ Q) à R
Biconditionals
P “If and only if” Q
Biconditional Truth TableP / Q / P à Q / Q à P /
T / T / T / T / T
T / F / F / T / F
F / T / T / F / F
F / F / T / T / T
Example 7: Tell whether each statement is true or false.
a) Purple is not a color if and only if summer is hot.
b) 6 = 6 if and only if 0 = 8 – 8 .
Example 8: Make a truth table for the statement.
6.4 HWK pg 303-304 #1-10 all, 14-28even, 33-40all
6.5 Analyzing Arguments and Proofs
A ______is made up of premises and conclusions.
Premises: statements that we accept for the sake of the argument.
(obviously true, commonly accepted, or maybe just accepted for the moment to see what happens… we don’t care if they are ACTUALLY true)
Conclusions: statements that follow the premises
An argument is considered ______if the conclusions MUST be true when the premises are true.
“Valid” and “True” are not the same. An argument can be valid even if the conclusion is false.
Example 1:
Let P = Today is Monday. Premise 1:
Let Q = I must go to school.
Premise 2:
Conclusion:
If the argument is valid, then the conjunction of the premises implies the conclusion for all possible truth values of the original statements.
P / Q / P à Q / /T / T
T / F
F / T
F / F
Symbolically:
The conditional statement that represents the argument is always ______,
thus the argument is ______.
This argument pattern:
Name: Modus Ponens
(The Law of Detachment)
Validity: Always Valid
Example 2: Determine if the argument is valid or invalid.
Let P = “The stereo is loud.”
Let Q = “The neighbors complain.”
Argument symbolically: Argument as a conditional statement:
Truth Table:
P / QT / T
T / F
F / T
F / F
Is this a tautology (are all end results true?) ______
Thus the argument is ______.
This argument pattern:
Name: Fallacy of the Converse
Validity: Always Invalid
Example 3:
Let P = “The steak is rare.”
Let Q = “The inside is pink.”
Argument symbolically: Argument as a conditional statement:
Truth Table:
P / QT / T
T / F
F / T
F / F
Is this a tautology (are all end results true?) ______
Thus the argument is ______.
This argument pattern: This argument pattern:
Name: Modus Tollens Name: Fallacy of the Inverse
(The Law of Contraposition)
Validity: Always Valid Validity: Always Invalid
Example: If it rains, then I get wet.
It doesn’t rain.
Therefore, I don’t get wet.
Example 4: Is the argument valid or invalid?
Let P = “The grill smells great.”
Let Q = “Something is burning.”
Argument symbolically: Argument as a conditional statement:
Truth Table:
P / QT / T
T / F
F / T
F / F
Is this a tautology (are all end results true?) ______
Thus the argument is ______.
This argument pattern:
Name: Disjunctive Syllogism
Validity: Always Valid
Example 5: Is the argument valid or invalid?
Let P = “The Colts resign Peyton Manning.”
Let Q = “They have a winning season.”
Let R = “They will go to the playoffs.”
Argument symbolically: Argument as a conditional statement:
Truth Table:
Is this a tautology (are all end results true?) ______
Thus the argument is ______.
This argument pattern:
Name:
Reasoning by Transitivity
(The Law of Hypothetical Syllogism)
Validity: Always Valid
SUMMARY:
Example 6: Decide if the argument is valid or invalid and give the form that applies.
a) b)
c) d)
e) f)
HWK 6.5 pg 316 # 1 – 12
6.6 Analyzing Arguments with Quantifiers
= “Therefore” Is this a valid argument?
Quantifiers: Tell us HOW MANY cases of a particular situation exist.
Universal Quantifiers Existential Quantifiers
all, each, every, no, none some, there exists, for at least one
symbol: symbol:
Negation of Quantifiers:
“S” is true for all x ----- negation ------> “S” is false for some x
“S” is true for some x ---- negation ------> “S” is false for all x.
Example 1: Write each negation
a) Some dogs are lazy. b) No lakes are not salty.
Euler Diagrams
An Euler Diagram is a special type of Venn Diagram that can help us determine if an logical argument with quantifiers is valid or invalid.