Transcript p - Computer and Information Sciences

Lecture 1.1: Course Overview, and
Propositional Logic
CS 250, Discrete Structures, Fall 2012
Nitesh Saxena
Adopted from previous lectures by Cinda Heeren
Outline


Administrative Material
Introductory Technical Material
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
2
Some Important Pointers

Instructor: Nitesh Saxena






Office: CH 133
Email: [email protected] (best way to reach me!)
Phone No: 205-975-3432
Office Hours: Thursdays 3-4pm (or by appointment)
Course Web Page (also accessible through my webpage)
http://www.cis.uab.edu/saxena/teaching/cs250-f12/
TA:
Amit Dutta: [email protected]
 M.S. student; research in security
 Office Hours: TBA
Blackboard: https://cms.blazernet.uab.edu/cgi-bin/bb9login


4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
3
About the Instructor





PhD graduate from UC Irvine
Previously an Assistant Professor at the
Polytechnic Institute of New York University
Research in computer and network security,
and applied cryptography
Web page: http://cis.uab.edu/saxena
Research group (SPIES):
http://spies.cis.uab.edu
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
4
Prerequisites
1.
2.
3.
4.
5.
6.
7.
Fundamental course for anyone intending to
become a computer scientist
MA 106 (pre-calculus trigonometry) OR
MA 107 (pre-cal algebra/trigonometery) OR
MA 125 (calculus I) OR
MA 126 (calculus II) OR
MA 227 (calculus III)
Minimum grade of C
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
5
What to expect

The course would be quite involved and technical



The grading will be curved


I would love to give all A’s but I won’t mind giving F’s when
deserved 
I might/will make mistakes



Lot of mathematics
Busy schedule
Please point them out
Talk to me if you have any complaints (or send me an
anonymous email )
But, I guarantee that



I will encourage you to do your best
You’ll have fun
I’ll help you learn as much as I can – don’t hesitate to ask
for help whenever needed
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
6
What I expect of you








Please do attend lectures
Take notes
Review lecture slides after each lecture
Solve text book exercises as you read through the
chapters
Ask questions in the class
Ask questions over email
Attend office hours
Try to start early on homework assignments


Don’t wait until the very last minute!
Follow the instructions and submit assignments on
time
7
Course Textbook


Discrete Mathematics and its
Applications -- Kenneth Rosen
Seventh Edition
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
8
Grading

40% - 5 homework assignments


60% - Exams





HW due every 20 days or so
2 mid-terms: 30% (15% each)
1 final: 30%
Mid-Term 1 – Sept 3rd or 4th week (tentative)
Mid-Term 2 – Oct 4th or 5th week (tentative)
Final – Dec 11
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
9
Policies Against Cheating or Misconduct




You are not allowed to collaborate with any other
student, in any form, while doing your homeworks,
unless stated otherwise; perpetrators will at least fail
the course or disciplinary action may be taken
No collaboration of any form is allowed on exams
You can definitely refer to online materials and other
textbooks; but whenever you do, you should cite so
in your homeworks. This is a rule of thumb.
Also check:
http://main.uab.edu/Sites/undergraduateprograms/general-studies/academic-success/67537/
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
10
Late Homework Policy




None – no late homeworks are allowed
Either you submit on time and your
homework will be graded OR you submit late
and the homework is NOT graded
You should stick to deadlines, please
Exception will be made ONLY under genuine
circumstances
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
11
Tentative Course Schedule (30 meetings)
Logic and Proofs (Chap 1) – 5 lectures
1.
1.
2.
3.
4.
Propositional Logic (1.1, 1.2)
Equivalences (1.3)
Quantifiers and Predicates (1.4, 1.5)
Proof Techniques (1.7. 1.8)
Basic Structures (Chap 2) – 5 lectures
2.
1.
2.
3.
4.
Sets and Set Operations (2.1, 2.2)
Functions (2.3)
Sequences and Summations (2.4)
Matrices (2.6)
Induction and Recursion (Chap 5) – 6 lectures
3.
1.
2.
3.
4.
5.
Induction (5.1)
Strong Induction and Well Ordering (5.2)
Recursion and Structural Induction (5.3)
Recursive Algorithms (5.4)
Program Correctness (5.5)
Relations (Chap 9) – 5 lectures
4.
1.
2.
3.
Relations and Properties (9.1)
Closures and Equivalence (9.4, 9.5)
Partial Orderings (9.6)
Graphs (Chap 10) – 5 lectures
5.
1.
2.
3.
4.
Graphs, Terminologies, and Models(10.1, 10.2)
Isomorphism and Connectivity (10.3, 10.4)
Paths and Shortest Path Problem (10.5, 10.6)
Planar Graphs and Coloring (10.7, 10.8)
Miscellaneous, if time permits – 4 lectures
6.
1.
2.
3.
Counting (Chap 6)
Trees (Chap 11)
Number Theory (Chap 4)
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
12
Scheduled Travel

Nov 27-29


Others trips will pop up


Will be announced as soon as I know about them
Likely no classes missed due to this


Attending a conference at NSF, Washington D C
Guest lecture by the TA or another faculty
member
Anyhow, I will make sure that the travel does
not affect the overall material coverage
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
13
Instructions

HW submissions


Name your files “Lastname_Firstname_HW#”
Submit it on Blackboard



PDF format only
Check the course web-site regularly


I am posting lecture slides and homeworks there
Check your UAB email regularly

I am sending out announcements there



Please make sure that you have correctly submitted/uploaded
the files (simply “saving” them may not be sufficient)
e.g., when I post homeworks
Only use your UAB email to communicate with me
and the TA
NO EXCUSES for not following instructions
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
14
Propositional Logic
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
15
Proposition


A proposition is a logical statement that is either
TRUE (T) or FALSE (F)
Propositions (examples)





3+2=32
3+2=5
MA 106 is a prerequisite for CS 250
It is sunny today
Not Propositions (examples)




What time it is now?
X+1 = 2
Read this carefully
What grade can I get in this course?
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
16
Propositional Logic -- Negation
Suppose p is a proposition.
The negation of p is written p and has meaning:
“It is not the case that p.”
In English, it is referred to as a “NOT”

Ex. “CS173 is NOT Bryan’s favorite class” is a negation
for “CS173 is Bryan’s favorite class”
Truth table for negation:
p
p
T
F
F
T
Notice that
p is a
proposition!
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
17
Propositional Logic -- Conjunction
Conjunction corresponds to English “AND”.
p  q is true exactly when p and q are both true.

Ex. “Amy is curious and clever” is a conjunction of “Amy
is curious” and “Amy is clever”.
Truth table for conjunction:
4/1/2016
p
q
pq
T
T
F
F
T
F
T
F
T
F
F
F
Lecture 1 - Course Overview, and
Propositional Logic
18
Propositional Logic -- Disjunction
Disjunction corresponds to English “OR”
p  q is true when p or q (or both) are true.
It is actually an “inclusive OR”

Ex. “Michael is brave OR nuts” is a disjunction of
“Michael is brave” and “Michael is nuts”.
Truth table for disjunction:
4/1/2016
p
q
pq
T
T
F
F
T
F
T
F
T
T
T
F
Lecture 1 - Course Overview, and
Propositional Logic
19
Propositional Logic – Exclusive OR
p q is true when only one of p or q is true
Ex: Students who have taken calculus or computer science,
but not both, can enroll for this class.
Truth table for xor:
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
p
q
p q
T
T
F
F
T
F
T
F
F
T
T
F
20
Propositional Logic – Implication
Implication: p  q corresponds to English “if p then q,” or “p
implies q.”

If it is raining then it is cloudy

If you have taken MA 106, you can enroll for CS 250

If you work hard then you can get a good grade
Truth table for implication:
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
p
q
pq
T
T
F
F
T
F
T
F
T
F
T
T
21
Propositional Logic – Biconditional
•This is equivalent to: (p  q)  (q  p)
• Also, referred to as the “iff” condition
• For p  q to be true, p and q must have the same truth value.
Truth table for biconditional:
4/1/2016
p
q
p  q
T
T
F
F
T
F
T
F
T
F
F
T
Lecture 1 - Course Overview, and
Propositional Logic
22
Complex Composite Propositions
and Equivalence


Combination of many propositions using different
operations (negation, conjunction, disjunction, implication)
Precedence order for these operations:
1.
2.
3.
4.
5.

Negation
Conjunction
Disjunction
Implies
Biconditional
A complex proposition can often be reduced to a simple one

This means that the complex proposition and the simple
proposition are logically equivalent
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
23
Propositional Logic – Logical
Equivalence




p is logically equivalent to q if their truth tables are the
same. We write p  q.
In other words, p is logically equivalent to q if p  q is
True.
We will study about equivalences more in the next lecture
But, for now, let us look at some examples
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
24
Propositional Logic – Logical
Equivalence
Challenge: Try to find a proposition that is equivalent to p  q,
but that uses only the connectives , , and .
p
q
pq
p
q
p
q  p
T
T
F
F
T
F
T
F
T
F
T
T
T
T
F
F
T
F
T
F
F
F
T
T
T
F
T
T
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
25
Distributive Law – an example of
equivalence
Distributivity:
p  (q  r)  (p  q)  (p  r)
p
q
r
qr
p  (q  r)
pq
pr
(p  q)  (p  r)
T
T
T
T
T
T
T
T
T
T
F
F
T
T
T
T
T
F
T
F
T
T
T
T
T
F
F
F
T
T
T
T
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
F
F
F
T
F
F
F
T
F
F
F
F
F
F
F
F
F
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
26
Propositional Logic – special
definitions
One of these
Contrapositives: p  q and q  p

Ex. “If it is noon, then I am hungry.”
“If I am not hungry, then it is not noon.”
Converses: p  q and q  p

Ex. “If it is noon, then I am hungry.”
“If I am hungry, then it is noon.”
Inverses: p  q and p  q

Ex. “If it is noon, then I am hungry.”
“If it is not noon, then I am not hungry.”
things is not
like the others.
Hint: In one
instance, the pair
of propositions is
equivalent.
p  q  q  p
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
27
Propositional Logic – special
definitions
A tautology is a proposition that’s always TRUE.
A contradiction is a proposition that’s always FALSE.
4/1/2016
p
p
p  p
p  p
T
F
T
F
F
T
T
F
Lecture 1 - Course Overview, and
Propositional Logic
28
Propositional Logic – bit-wise operators


All the operators are extensible and applicable to “bits” and
“bitstrings”
‘1’ is TRUE and ‘0’ is FALSE
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
29
Propositional Logic – applications

Computer Programs



Hardware and Gates:




Ex: “Alabama” and “Universities”
Ex: “java – coffee”
Writing Policies


Ex: Classical proofs in provable cryptography based on counterpositives.
Logical searches


All the logical connectives we’ve discussed are also found in hardware and
are called “gates.”
Foundational Element for Proof Systems and Proof Techniques


Propositional logic is a key to writing good code…you can’t do any kind of
conditional (if) statement without understanding the condition you’re
testing.
Different programming languages may have different syntax for logic
operators
Ex: firewall policies
Logical Puzzles and Games
Lecture 1 - Course Overview, and
… 4/1/2016
Propositional Logic
30
Some Quick Questions
-
-
-
-
-
-
Is “what is your name” a proposition?
Is “The sun revolves around the earth” a proposition? If so, what is
its logical value.
What is the negation of “The sun revolves around the earth”? What
is the logical value of this negation.
“You can get a good grade if you perform well on homeworks and
you perform well on exams” – represent as a proposition.
“You may fail the course if you cheat or you do not attend any
lectures” – represent as a proposition.
What is p  p equivalent to?
What is p  p equivalent to?
What is:
-
1  1?
0  1?
1 0?
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
31
Some Quick Questions



If p is True and q is False, what is p -> q?
Is p->q equivalent to p  q?
What will be the output of the following piece of
pseudocode:
X = 50;
If ( X > 35)
print “Pass”;
Else
print “Fail”;


How would (p  q)  (r  s) be represented in computer
hardware (using gates)?
What is the converse of: “if you are a good student, you will
end up getting a good grade”?
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
32
Today’s Reading and Next Lecture



Rosen 1.1 and 1.2, and part of 1.3
Please start solving the exercises at the end
of each chapter section. They are fun.
Please read 1.3 and 1.4 in preparation for the
next lecture
4/1/2016
Lecture 1 - Course Overview, and
Propositional Logic
33