Transcript 7. Logic and Truth Tables from COMP1380

Logic and Truth Tables
Winter 2012
COMP 1380 Discrete Structures I
Computing Science
Thompson Rivers University
Course Contents








Speaking Mathematically – .5 weeks
Number Systems and Computer Arithmetic – 2 weeks
Logic and Truth Tables – 1 week
Boolean Algebra and Logic Gates – 1 week
Vectors and Matrices – 2 weeks
Sets and Counting – 1.5 weeks
Probability Theory and Distributions – 2 weeks
Statics and Random Variables – 2 weeks
TRU-COMP1380
Logic and Truth Tables
2
Unit Learning Objectives





Recall truth tables for ~, , , , .
Give a truth table for a given composite statement.
Recall logical equivalences.
Simplify a compound statement using logical equivalences.
Infer a conclusion from a compound statement.
TRU-COMP1380
Logic and Truth Tables
3
Unit Contents




Sections 2.1 – 2.3 from the textbook
Logical Form and Logical Equivalence
Conditional Statements
Valid and Invalid Arguments
TRU-COMP1380
Logic and Truth Tables
4
Logical Form and Logical Equivalence




Argument = premises + conclusion
To have confidence in the conclusion in your argument, the premises
should be acceptable on their own merits or follow from other statements
that are known to be true.
Logical forms for valid arguments?
Examples




Argument 1: If the program syntax is faulty or if program execution results
in division by zero, then the computer will generate an error message.
Therefore, if the computer does not generate, then the program syntax is
correct and program execution does not result in division by zero.
Argument 2: If x is a real number such that x < -2 or x > 2, then x2 > 4.
Therefore, if x2 /> 4, then x /< -2 and x /> 2.
The common logical form of both of the above arguments:
If p or q, then r. Therefore, if not r, then not p and not q.
Is this logical form valid?
TRU-COMP1380
Logic and Truth Tables
5

Example



If Jane is a major or Jane is a computing science major, then Jane will take
COMP 1380. Jane is a computing science major. Therefore Jane will take
COMP 1380.
If logic is easy or (1), then (2). I will study hard. Therefore, I will get an A
in this course.
What are (1) and (2) in the above statement?
TRU-COMP1380
Logic and Truth Tables
6

Definition of statement


A statement (or proposition) is a sentence that is true or false but not
both.
Examples

Two plus two equals four.
2+2=4
I am a TRU student.

x+y>0


TRU-COMP1380
???
Logic and Truth Tables
7

Compound Statements

Symbols used in complicated logical statements:





~



not
and
or
exclusive or
~p
pq
pq
pq
negation of p
conjunction of p and q
disjunction of p and q
Order of operations: ( ) and ~ have the precedence.


TRU-COMP1380
~p  q = (~p)  q
~(p  q)
Logic and Truth Tables
8

Example
It is not hot but it is sunny.
It is neither hot nor sunny.
-> It is not hot, and it is sunny.
It is not hot, and it is not sunny.

Let h = “it is hot” and s = “it is sunny.” Then the above statements can be
translated as

~h  s
~h  ~s


Example

Suppose x is a particular real number. Let p, q, and r symbolize
“0 < x,” “x < 3,” and “x = 3.” respectively.
Then the following inequalities

x3
0<x<3
0<x3
pq
p  (q  r)
can be translated as

TRU-COMP1380
qr
Logic and Truth Tables
9

Truth Tables



Negation
Conjunction
Disjunction
TRU-COMP1380
p
~p
T
?
F
?
p
q
pq
T
T
?
T
F
?
F
T
?
F
F
?
p
q
pq
T
T
?
T
F
?
F
T
?
F Logic and
F Truth Tables
?
10

Truth Tables

Exclusive or
TRU-COMP1380
p
q
pq
T
T
F
T
F
T
F
T
T
F
F
F
Logic and Truth Tables
11

Example

~p  q



q
~p  q
T
T
?
T
F
?
F
T
?
F
F
?
~T  F = ?
~T  T = ?
(p  q)  ~(p  q)



p
Can you write a truth table?
When p is T and q is F?
(p  q)  ~r

TRU-COMP1380
When p is T, q is F and r is F?
Logic and Truth Tables
12

Logical Equivalence

Example

6>2

How to prove





TRU-COMP1380
=
2<6
pq=qp
pq=qp
~(~p) = p
Commutative law
Commutative law
Double negative law
~(p  q) ≠ ~p  ~q
~(p  q) ≠ ~p  ~q
???
???
Logic and Truth Tables
13

De Morgan’s Laws



~(p  q) = ~p  ~q
Can you prove it?
~(statement1  statement2) = ~statement1  ~statement2
~(p  q) = ~p  ~q
~(statement1  statement2) = ~statement1  ~statement2
Examples




~(~p  q) = ???
~(p  ~q) = ???
The negation of “John is 6 feet tall and he weighs at least 200 pounds.” is
...
The negation of “The bus was late or Tom’s watch was slow.” is
...
The negation of “-1 < x  4” is
...
TRU-COMP1380
Logic and Truth Tables
14

Tautologies and Contradictions




pF=p
pT=p
Can you prove it?
Associative Laws



Always true
Always false
Some other interesting equivalences


p  ~p = T; p  T = T
p  ~p = F; p  F = F
(p  q)  r = p  (q  r)
(p  q)  r = p  (q  r)
Distributive Laws


p  (q  r) = (p  q)  (p  r)
p  (q  r) = (p  q)  (p  r)
TRU-COMP1380
Logic and Truth Tables
Can you prove it?
15

Prove ~(~p  q)  (p  q) = p.
~(~p  q)  (p  q)


= (~(~p)  ~q)  (p  q)
= ...
(p  ~q)  p = ???
~((~p  q)  (~p  ~q) = ???
TRU-COMP1380
Logic and Truth Tables
16
Conditional Statements

Conditional Statement



Example




If hypothesis (or antecedent), then conclusion (or consequent).
hypothesis  conclusion
If 4686 is divisible by 6, then 4686 is divisible by 3. Is this statement
True?
Let p = “4686 is divisible by 6,” and q = “4686 is divisible by 3”. Then
pq
Truth table for p  q
p  q ≡ ~p  q ???
TRU-COMP1380
p
q
pq
T
T
T
T
F
F
F
T
T
F
F
T
Logic and Truth Tables
17



pqr
≡ (p  r)  (q  r) ???
= ~(p  q)  r
= ...
~(p  q)
≡ p  ~q ???
= ~(~p  q)
= ...
pq
≡ ~q  ~p ???
= ~(~(p  q))
= ...
TRU-COMP1380
Logic and Truth Tables
Contrapositive
18

The biconditional of p and q
p  q ≡ (p  q)  (q  p)
p if and only if q
p iff q

The truth table is
TRU-COMP1380
p
q
pq
T
T
?
T
F
?
F
T
?
F
F
?
Logic and Truth Tables
19
Valid and Invalid Arguments

Example




If (p  (q  ~r)) and (q  (p  r)), then is (p  r) valid?
What do we have to do?
p  r must be true for all the cases in which both of (p  (q  ~r)) and (q
 (p  r)) are true. We may use the truth table to see if the statement is
valid.
Modus Ponents

Both of p  q and p are valid, then q is valid.
(p  q )  p = (~p  q )  p = (F  q )  T = q, or by truth table
Therefore q must be T when (p  q ) and p are T.

If x is a human, then x is mortal.
Dave is a human.
Therefore Dave is mortal.
TRU-COMP1380
Logic and Truth Tables
Is it true?
20

Modus Tollens





If p  q and ~q are valid, then ~p is valid.
How to prove?
If Zeus is human, then Zeus is mortal.
But Zeus is not mortal.
Therefore ...
If x is divisible by 6, the x is divisible by 3.
(Instantiation: …)
14 is not divisible by 3.
Therefore ...
Is it true?
If a city is big, then the city has tall buildings. Because Kamloops have
a tall building, Kamloops is a big city. Is this argument valid?
TRU-COMP1380
Logic and Truth Tables
21

Generalization


How to prove?
p  q and ~q, then p
How to prove?
q
pq
T
T
T
T
F
F
F
T
T
F
F
T
Transitivity


p  q, then p
Elimination


How to prove?
Specialization


p, then p  q
p
If p  q and q  r are valid, then p  r is valid.
How to show?
Contradiction Rule


If p  F valid, then ~p is valid.
How to show?
The logical heart of the method of proof by contradiction. If an assumption
leads to a contradiction, then that assumption must be false.
TRU-COMP1380
Logic and Truth Tables
22