Transcript (p q) (p q) p q (p q)

CS1050: Understanding and Constructing Proofs
Spring 2006
Lecture 01:
Boolean Logic
Sections 1.1 and 1.2
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek/courses/1050/
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
1
Lecture Objectives
•
•
•
•
•
Terminology
Operators and their properties
Converting English into Logic Propositions
Understand some applications
Tools for verifying equivalences of propositions
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
2
Motivation
• Proofs are important in most CS applications
• Be able to judge whether whether a mathematical argument
(proof) is correct (valid)
• Learn tools for constructing correct arguments (logic)
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
3
What is a proposition?
• Declarative sentence that is either true or false, but not both
– Propositions:
• 1+1=2 (true)
• 2+2=3 (false)
– Not propositions
•
•
•
•
Jarek Rossignac
What time is it? (question)
Eat! (not declarative)
x:=x+1; (computer instruction)
y=2x+4 (constraint, implicit equation that may be verified by some pairs)
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
4
How do we denote propositions?
• Use letters: p, q, r, s…
– Let p denote “It is raining today”
– Let q denote “I will be wet”
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
5
What is the truth value of a proposition?
• The truth values of a true proposition is “true” and is
denoted T
– Let p be “x20”. The truth value of p is T
• The truth value of a false proposition is “false” and is
denoted F
– Let q be “–x20”. The truth value of q is F
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
6
What are compound propositions?
• Formed by transforming or combining other propositions
– Proposition p: “Today is Tuesday”
– Proposition q: “I am teaching today”
– Compound propositions:
• “Today is not Friday” (negation)
• “Today is not Friday” AND “I am teaching today”(conjunction)
• Reasoning about compound propositions is called
propositional calculus or propositional logic
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
7
What are the main logical operators?
• Connectives that transform or combine propositions
– Proposition p: “Today is Tuesday”
– Proposition q: “I am teaching today”
• Negation (p). Read “Not p”
– “Today is not Tuesday”
• Conjunction (pq). Read “p and q”
– “Today is Tuesday” AND “I am teaching today”
• Disjunction (pq). Read “p or q (or both)”
– “Today is Tuesday” OR “I am teaching today”
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
8
What is the Exclusive Or?
• XOR (pq). Read “exclusive or”
–
–
–
–
Interpret as “p and q have different truth values”
EITHER “Today is Tuesday” OR “I am teaching today”, NOT BOTH
In English, “or” may mean inclusive OR () or exclusive OR ()
“Would you like tea or coffee?”…”Yes, please”
• XOR (pq) is the same as DIFFERENT (p ≠ q)
– “The truth values of p and q are different”
• Team exercise:
– What does (pq)  (rs) express?
– Is it the same as ((pq)  r)  s ?
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
9
What are implications?
• Implication (p  q) is false only when p is true and q false
– p is the hypothesis or premise
– q is the conclusion or consequence
• Many equivalent ways to interpret p  q
– “If p, then q”, “p implies q”, “q follows from p”, “p is sufficient for q”,
– “q is necessary for p”, “p only if q”
• Implications are propositions (they need not be true)
– “If today is Friday, then 2+3=5” is true everyday except Friday
• Do not confuse implications with IF-THEN statements
– if (x>3) {x=3;};
Jarek Rossignac
// caps x at 3
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
10
What are the derivatives of an implication?
• Consider the Implication proposition p  q
– “We win whenever it is raining”
– IF “it is raining” THEN “we win”
– IF p THEN q
• Its contrapositive is q  p
– IF “we do not win” THEN “it is not raining”
– Note that it say the same thing (equivalent to the implication pq
• Its converse is q  p
– IF “we win” THEN “it is raining”
– Note that it is not equivalent to the implication pq
• Its inverse is p  q
– IF “it is not raining” THEN “we don’t win”
– Note that it is equivalent to the converse qp
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
11
What are biconditionals (iff)?
• The biconditional p  q is the proposition that is true if and
only if p and q have the same truth value
– pq is true if and only if both p  q and q  p are true
– pq can be written as (p  q)  (qp)
– I like to denote it by “p==q”, as in several programming languages
• pq should be read as
–
–
–
–
–
“p is necessary and sufficient for q”
“if p, then q, and conversely”
“p implies q and vice versa”
“p when q”
“q iff q” (“iff” stands for “if and only if”)
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
12
What are truth tables?
• A compound proposition may, but needs not be true.
– Its true value depends on the true values of its primitive propositions
p
q
p
pq
pq
pq
p≠q
pq
pq
p==q
pq
p–q
T
T
F
T
T
F
T
T
F
T
F
F
F
T
T
F
F
T
F
T
T
F
T
T
T
F
F
F
F
T
F
F
F
T
T
F
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
13
Precedence of logical operators
To reduce the number of parentheses, we use the following
precedence:
1) 
2) ,
3) , 
4) , 
Negation
Conjunction,
Disjunction, Xor
Implications
• Example:
– p q  s  t  p  t
– Is interpreted as:
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
14
Translating English into Logic
• This is not easy! (Study examples p 10-11)
• Do not attempt it at home! Your family may not appreciate it.
• Take a complex declarative English sentence
– “You may access the Internet on campus only if you are a computer
science major or if you are not a freshman.”
• Separate it into parts and assign them variable names
– a stands for “you may access the Internet on campus”
– c stands for “you are a computer science major
– f stands for “you are a freshman”
• Combine using logical connective to capture the meaning
– (a  c  f)
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
15
When are system specifications consistent?
• Software or hardware requirements are often specified using a
natural language.
• System and software engineers translate each requirement into
logical propositions.
• Then, one wishes to build a system that satisfies ALL of the
requirements (i.e., assign values to all variables so that all
requirements are met).
• A system specification is consistent if there exists an
assignment of truth values to all variables that satisfies all
propositions (make them true)
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
16
What are tautologies and contradictions?
• A compound proposition that is always true is a tautology
(pp)
• A compound proposition that is always false is a contradiction
(pp)
• A compound proposition that is neither a contradiction nor a
tautology is a contingency
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
17
When are two propositions equivalent?
• When they have the same truth tables
– Denoted (p  q) or (pq)
• p and q are logically equivalent if p  q is a tautology
• Examples
The implication and its contrapositive are equivalent
(q  p) (p  q)
The converse and inverse of an implication are equivalent
(p  q)  (q  p)
An implication is not equivalent to its converse
(p  q) ! (q  p)
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
18
What are other useful logical equivalences?
•
•
•
•
•
•
•
•
•
•
•
Idempotence: pp  p, pp  p
Negation: pp  F, pp  T
Identity: pT  p, pF  p
Domination: pF  F, pT  T
Double negation: (p)  p
Negation of disjunction (DeMorgan): (pq)  pq
Negation of conjunction (DeMorgan): (pq)  pq
Commutativity: pq  qp, pq  qp
Associativity: (pq)r  q(pr), (pq)r  q(pr)
Distributivity: (pq)r  (qr)(qr), (pq)r  qrqr
Absorption: (pq)p  p, (pq)p  p
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
19
What equivalences involve implications?
•
•
•
•
•
•
•
•
•
•
•
•
p  q  pq
pq  p  q
pq  (p  q)
(p  q)  pq
(p  q)  (p  r)  p  (qr)
(p  q)  (p  r)  p  (qr)
(p  r)  (q  r)  pq  r
(p  r)  (q  r)  pq  r
pq  (p  q)  (q  p)
pq  p  q
pq  pq  pq
(pq)  p  q
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
20
Show that pq  pq is a tautology
• We want to demonstrate that pq  pq  T
– p  q  pq # equivalence law
• pq  pq  (pq) (pq)
– (pq)  pq # DeMorgan
• pq  pq  (pq) (pq)
– pq  qp # commute
• pq  pq  pp  qq
– pp  T # negation
• pq  pq  T  T
– pT  T # domination
• pq  pq  T
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
21
What are the logical operators in Processing?
• Boolean variables may be combined using logical operators
–
–
–
–
–
–
!p
p && q
p || q
p != q
p == q
p&& ! q
Jarek Rossignac
means NOT p
means p AND q (pq)
means p OR q (pq)
means p XOR q (p  q, p ≠ q)
means p iff q (p  q)
means p AND NOT q (pq)
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
22
What are logical operators on bit strings
• A Boolean variable may be represented by 1 bit
– 1 means true, 0 means false
• A bit string S is an ordered sequence of bits
• The length of S is the number of bits it has
• We can perform operations on bit-strings S and T
– By performing the operations on all pairs of corresponding bits
S|T
performs a bitwise OR (at least one bit has to be 1)
S&T
performs a bitwise AND (both have to be 1)
S << 3
shifts all bits left and inserts three 0 on the right
• In processing, these operations work on
– int
– byte
– char
integers
strings of 8 bits
binary representations of characters
• See http://processing.org/reference/bitwiseOR.html
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
23
Reading assignment
• Sections 1.1 and 1.2 for this class
• Sections 1.3 and 1.4 for the next class
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
24
Assigned Exercises for Lecture 1
• You must know how to solve the following exercises for
the quiz on lecture 2
–
–
–
–
–
–
–
1.1-11.e on p 1-17
1.1-23.f on p 1-18
1.1-33.b on p 1-18
1.1-42. on p 1-19
1.1-44.d on p 1-19
1.1-51 on p 1-20
1.2-9 on p 1-26
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
25
Logical operators (summary)
Propositions
T, F
¬p, !p, p
pq
pq
p  q, p ≠ q
pq
p  q, p==q
p  q, p  q
true, false
not p
p and q
p or q
p xor q
p implies q
p same as q
p equivalent to q
Bit strings
S|T
S&T
S << n
Jarek Rossignac
bitwise OR
bitwise AND
shift left by n bits
http://www.gvu.gatech.edu/~jarek
Sets
n
for each n
n
for at least one n

empty set
sS s is an element of S
S
elements not
in S
ST elements in S and T
ST elements in S or T
S–T ST
ST ST – ST
S=T S equals T
S  T S included in T
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
26
Work to do before the next lecture (part 1)
• Get the book and study sections 1.1 and 1.2
• Study these slides by looking at the question in the slide title
and trying to answer it without looking
– Mark what you do not understand and check it in the book
• Do the exercises assigned for sections 1.1 and 1.2
– Do other exercises as needed for practice
• Learn how to solve these exercises by heart
– We will have a practice quiz during the next lecture
– It will cover these slides, the reading, and the exercises
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
27
Work to do before the next lecture (part 2)
• Read Sections 1.3 and 1.4
– One question on the practice quiz will be on Sections 1.3 or 1.4
• Print and study the slides (L02) for lecture 2
– See if you can answer the questions (slide titles)
– Write down what you do not understand
• Try to do the exercises assigned in the slides for lecture 2
– Mark what you have trouble with
• Bring it all to lecture 2
• As a Team (only due Tu Jan 17, but START NOW!!!)
–
–
–
–
Print the slides (P0) for project 0
Follow the instructions and install Processing
Play with it, write your question, problems
Try to complete P0 (including posting a web page and doing your PPP)
Jarek Rossignac
http://www.gvu.gatech.edu/~jarek
MAGIC Lab
Georgia Tech, IIC, GVU, 2006
28