Title

Report
Logic 1
Statements and Logical Operators
Logic
• Propositional Calculus
– Using statements to build arguments
– Arguments are based on statements or
propositions
• Statement or Proposition
– A declarative statement
– Can be either true or false, but must be one
• Examples (are they propositions?)
– The sky is blue
– It will rain tomorrow
– 2+2=4
– Solve the following equation for x
“Famous” propositions
• “If I am Buddha, then I am not Buddha”
– Equivalent to the statement “I am not Buddha”. How?
• “This statement is false”
– If true, it must be false. If false, it must be true.
– If a statement is a logical contradiction, it is considered
not a statement.
• The following two are not considered statements.
Why?
• “I am lying”
• “This statement is true”
– Both are self-referential, which are considered not
statements.
Notation
• Propositions are denoted by letters; p, q, r , s
– p: “the moon is round” means
p is the statements “the moon is round”
• The negation of a proposition, “not p” is
denoted p.  is a logical operator
• A truth table relates the truth of a proposition
and its negation:
Examples
Statement
Negation
2+24
1=0
2+2=4
10
Not
All economists
all economists
are
are
notliberal
liberal
All economists are
liberal
If p is true then p is false.
But if q is false then q is true.
Be wary of quantifiers like “all” or “some”
which can be tricky.
Form new propositions from old by combining them.
• A conjunction of two propositions p and q, denoted pq
requires both p and q to be true to be true.
• Find a conjunction for the statements “All economists are
liberal” and “2+2=4”.
• Exercise – find the truth table for the conjunction pq.
• Exercise – show pq is equivalent to pq using a truth
table
More exercises
1. p: This chapter is interesting
q: logic is an interesting subject
Express the statement “This chapter is not
interesting even though logic is an interesting
subject” using symbolic logic.
p: This chapter is not interesting.
Hence: (p)q
2. r: Life is interesting
Express the statement “This chapter is interesting
even though logic is not an interesting subject, but
life is interesting too” using symbolic logic.
(p (q))r “but” is considered an emphatic “and”
3. For example 2, state p ((q)r) in words.
This chapter is interesting, but logic is not an interesting
subject even though life is interesting too”
Different ways of expressing a conjunction In English
• And
• But
• Yet
All the following say the same thing:
Disjunction
• The disjunction of p and q, which we read “p or q” is
denoted pq.
• It is inclusive, so it is true if p or q or both are true.
• The only way for a disjunction to be false is if both p
and q are false.
Examples
p: the sun is luminescent (emits light without heat)
q: LEDs are luminescent.
pq: The sun is luminescent or LEDs are luminescent.
This statement is true.
Exercise:
State pq and pq. Are they true?
pq: The sun is luminescent orLEDs are not.
False: Both parts are false
pq: The sun is not luminescent orLEDs are.
True: The “or both” is implied.
An exclusive statement says p or q but not both.
(pq)  (p  q)
Exercise: Using the statements from the last
example/exercises, state
(p  q)  (pq) and (p q)(pq)
(p  q)  (pq): The sun is luminescent or LEDs are
luminescent but both are not.
(p  q)  (pq): The sun is luminescent or LEDs are
luminescent but it is not the case that both are not
luminescent.
Exercises
Do truth tables for the exclusive statements in the
previous exercises:
(p  q)  (pq)
pq pq (pq) (pq) (pq)
p
q
T
T
T
T
F
F
T
F
T
F
T
T
F
T
T
F
T
T
F
F
F
F
T
F
(pq) (pq)
Notice it is the same as (pq)
p
T
q
T
pq
T
p
F
q
F
pq (pq) (pq) (pq)
F
T
T
T
F
T
F
T
F
T
T
F
T
T
T
F
F
T
T
F
F
F
T
T
T
F
F
Equivalence, Tautologies and Contradictions
• In the previous exercise you found that the truth
table for (pq) (pq) is the same as (pq).
• When truth tables are equivalent, we say they have
“logical equivalence.”
• We will also find certain statements are self-evident
(called “tautologies”) meaning they are always true
• And other statements which are evidently false
(always false) called “contradictions.”
Logical Equivalence
• Statements that are the same
• Construct the Truth Tables:
– p(p)
– p(pq)
Logical equivalence (continued)
• We see from the first example, a double negation is
always an equivalent statement to the original.
– “I am a graduate student” is equivalent to “I am
not not a graduate student”.
– “It is not true that I am not a male” is equivalent
to saying “I am a male.”
DeMorgan’s Law
• Expressed in words: “The statement (pq) means
“it is not the case that both p and q are true” or
more simply “p and q are not both true.”
• This is equivalent to saying that Either p is false or q
is false (or the implied “or both”).
• Notice, this is different from say either p or q (pq).
• Exercise: Show that (pq) is not the same as (pq)
DeMorgan’s Law: (pq)(p)(q)
Exercise, construct the truth table
This leads us to DeMorgan’s Law
• If we distribute a negation sign, it reverses  and 
and the negation applies to both parts.
If p and q are statements then
(pq)(p)(q)
(pq)(p)(q)
exercise: Come up with some verbal examples of
DeMorgan’s Law.
exercise: Show DeMorgan’s Law holds in both
constructs.
• Logical Equivalences relate two statements
• Tautologies and Contradictions are about single
statements
– Tautologies are always true, and the truth value is
independent of the value of the statement
Example: p(p)
– Contradictions are always false, again the truth value is
independent of the value of the statement
Example: p(p)
In common usage, sometimes we say two statements are
contradictory, in that they can’t both be true, but in
Logic that means they are exclusive (see above)
Common Logical Equivalences
The double negative
The Commutative Law for conjunction
The Commutative Law for disjunction
The Associative Law for conjunction
The Associative Law for disjunction
The Distributive Laws
The Absorption Laws
DeMorgan’s Laws
(p)p
pqqp
pqqp
(pq)r p(qr)
(pq)r p(qr)
p(qr) (pq)(pr)
p(qr) (pq)(pr)
ppp
ppp
(pq)(p)(q)
(pq)(p)(q)
Simplifying
• Using logical equivalences to find a simpler
statement:
– Example: The double negative can be expressed
as a positive. “2+24 is false” is equivalent to
saying “2+2=4”.
Proofs show two statements are logical equivalences.
– Example: Prove 2+2=6-2
2+2=4
6-2=4
4=4 hence 2+2=6-2
More on proofs later.

similar documents