Transcript PPT

The Logic of Compound Statements
2.1 and 2.2
Instructor: Hayk Melikya
Introduction to Abstract Mathematics
[email protected]
1
Logic
Logic is not only the foundation of mathematics, but also is
important in numerous fields including law, medicine, and
science. Although the study of logic originated in antiquity,
it was rebuilt and formalized in the 19th and early 20th
century. George Boole (Boolean algebra) introduced
Mathematical methods to logic in 1847 while Georg Cantor
did Theoretical work on sets and discovered that there are
many different sizes of infinite sets.
Introduction to Abstract Mathematics
2
Logic



Mathematical logic is a tool for dealing with formal
reasoning
Logic does:
– Assess if an argument is valid/invalid
Logic does not directly:
– Assess the truth of atomic statements
Introduction to Abstract Mathematics
3

Logic can deduce that:
– NCCU is in North Carolina

given these facts:
– NCCU is in Durham
– Durham is in North Carolina

Logic knows nothing of whether these
facts actually hold in real life!
Introduction to Abstract Mathematics
4
Argument #1



All men are mortal
Socrates is a man
Therefore,
Socrates is mortal
Introduction to Abstract Mathematics
5
Where is COMP2200



?
How do we find such bugs in software?
– Tracing
– Debug statements
– Test cases
– Many software testers working in parallel…
All of that had been employed in the previous cases
Yet the disasters occurred…
Logic : means to prove correctness of software
Sometimes can be semi-automated
Can also verify a provided correctness proof
Introduction to Abstract Mathematics
6
Validity

An argument is valid if and only if given that its premises hold its
conclusion also holds
– Socrates argument: Valid or Invalid?
– Sandwich argument: Valid or Invalid?
How can we tell ?






Common sense?
Voting?
Authority?
What is valid argument anyway?
Who cares?
???
Introduction to Abstract Mathematics
7
Arguments in Puzzles

The Island of Knights and Knaves
Always lie
Never lie



You meet two people: A, B
A says:
I am a Knave or B is a Knight
B says
A and I are of opposite type

Who is A?

Who is B?
Introduction to Abstract Mathematics
8
Solution
The original statement can be written as:
 S = X or Y
 X = “A is a Knave”
 Y = “B is a Knight”
 Suppose A is a Knave
 Then S must be false since A said it
 Then both X and Y are false
 If X is false then A is not a Knave
 Contradiction : A cannot be a Knave and not a
Knave
 So A must be a Knight
 So S is true and X is not true
 Thus, to keep S true Y must be true  You meet just one guy : A
 So B is a Knight too
 A says:“I’m a Knave!”
 Who is A?
Introduction to Abstract Mathematics

9
Statements or Propositions

A proposition or statement is a declaration (sentence) which is either
true or false (but not both same time).

Some examples:

2+2 = 5 is a statement because it is a false declaration.

Orange juice contains vitamin C is a statement that is true.




Open the door. This is not considered a statement since we cannot
assign a true or false value to this sentence. It is a command, but not
a statement or proposition.
WHAT TIME IS IT?.
5 + 7.
X + 5 = 13.
Introduction to Abstract Mathematics
10
Negation( or denial)



The negation of a statement, p , is “not p” and is
denoted by ~p ( also ┐p )
If p is true, then its negation is false. If p is false,
then its negation is true.
Truth table:
p
 T
 F

┐p
F
T
If
p : “Jack went up the hill”
then
~ p : “ Jack did not go up the hill”
Introduction to Abstract Mathematics
11
Conjunction (Logical AND)
In ordinary English, we are building new propositions from old
ones via connectors. Similar way we will construct new propositions
from old ones in mathematics too.
Definition: If P and Q are proposition then P  Q is a new
proposition which referred to as the conjunction of “P and Q”.
The proposition P  Q is true if both P and Q are true
propositions and it is false otherwise.
Introduction to Abstract Mathematics
P
Q
P Q
T
T
T
T
F
F
F
T
F
F
F
F
12
Disjunction (Logical OR)
Definition: If P and Q are proposition then P  Q is a new
proposition which referred to as the disjunction of P and Q .
The proposition P  Q is false if both P and Q are false
propositions and it is true otherwise.
Introduction to Abstract Mathematics
PQ
P
Q
T
T
T
T
F
T
F
T
T
F
F
F
13
The Implication (Conditional)
Definition: If P and Q are proposition then P Q is a
new proposition which referred to as “P implies Q” .
The proposition P  Q is false if P is true and Q is
false and it is true otherwise
P Q
P
Q
T
T
T
T
F
F
F
T
T
F
F
T
In conditional statements: p  q


Introduction to Abstract Mathematics
p is called the hypothesis and q is called
the conclusion
The only combination of circumstances in
which a conditional sentence is false is
when the hypothesis is true and the
conclusion is false
14
Conditional Statements: P  Q
P is also called: assumption or premise or antecedent
Q is called : conclusion
A conditional statements is called vacuously true or true by
default when its hypothesis is false

There are several ways of expressing P  Q :
1.
If P, then Q
2.
3.
4.
Q if P
P implies Q
P only if Q
5. Q is necessary for P
6 P is sufficient for Q
Introduction to Abstract Mathematics
15
Exercise: Rewrite each of the following sentences in "if, then" form
(a) You will pass the test only if you study for at least four hours.
(b) Attending class regularly is a necessary condition for passing
the course.
(c) In order to be a square, it is sufficient that the quadrilateral
have four equal angles.
(d) In order to be a square, it is necessary that the quadrilateral
have four equal angles.
(e) An integer is an odd prime only if it is greater than 22
Introduction to Abstract Mathematics
16
Conditional Statement :

Contrapositive of p  q is another conditional statement ~q  ~p
A conditional statement is equivalent to its contrapositive

The converse of p  q is q  p

The inverse of p  q is ~p  ~q



pq
Conditional statement and its converse are not equivalent
Conditional statement and its inverse are not equivalent
What do you think about convers and inverse of statement???????
Introduction to Abstract Mathematics
17
Conditional Statements





The converse and the inverse of a conditional
statement are equivalent to each other
p only if q means ~q  ~p, or p  q
Biconditional of p and q means “p if and only if q” and
is denoted as p  q
r is a sufficient condition for s means r  s
r is a necessary condition for s means ~r  ~ s
“if not r then not s” which is same as s  r
Introduction to Abstract Mathematics
18
Exercises: Write contrapositive, converse and inverse statements for
– If P is a square, then P is a rectangle
– If today is Thanksgiving, then tomorrow is Friday
– If c is rational, then the decimal expansion of c is repeating
– If n is prime, then n is odd or n is 2
– If x is nonnegative, then x is positive or x is 0
– If Tom is Ann’s father, then Jim is her uncle and Sue is her aunt
– If n is divisible by 6, then n is divisible by 2 and n is divisible by 3
Introduction to Abstract Mathematics
19
Contrapositive: Examples
The contrapositive of “if p then q” is “if ~q then ~p”.
Statement:
If you are a CS year 1 student, then you are taking COMP 2200.
Contrapositive:
If you are not taking COMP 2200, then you are not a CS year 1 student.
Statement:
If you don’t give me all your money, then you will die immediately.
Contrapositive:
If you don’t want to die immediately,then you give me all your money.
Fact: A conditional statement is logically equivalent to its contrapositive.
Introduction to Abstract Mathematics
20
Biconditional
Definition: If P and Q are propositions then the biconditional
P and Q is a proposition denoted by P  Q whose truth value
is given by the truth table
P
Q
PQ
T
T
T
T
F
F
F
T
F
F
F
T
Introduction to Abstract Mathematics


P  Q is often read as : P if and only if
Q or P iff Q for shorthand.
phrasing of P  Q is P is a necessary
and sufficient condition for Q.
21
Propositional forms/ formulas /expressions:
• Alphabet:
variables (letters upper/lower X, Y, Z, … A, B, C )
symbols , , ~, and parentheses ( , )
also we add two more , ,
• Propositional expressions (propositional forms) are formed using
these elements of alphabet as follows:
1. Each variable is propositional expression
2. IF p and q are propositinal expressions then
~ p, p  q, p  q, p  q, p  q, (p) ,
all are propositional expressions
3. Any expression is obtained by applying repeatedly steps 1 or 2.
Introduction to Abstract Mathematics
22
Truth Tables
Recall that propositional forms are made up of propositional variables
and logical connectors in such a way that if one substitute the
propositional variables by actual propositions then it becomes proposition.
The truth table for a given propositional form displays the truth values
that corresponds to all possible combinations of truth values for its
propositional variables. Let us construct the truth table for
propositional form
(p  q)  ~(p  q) which often denoted as p  q (p XOR q) exclusive or
p
q
pq
pq
~(p  q)
pq
T
T
F
F
T
F
T
F
T
T
T
T
T
F
F
T
F
T
T
F
F
T
T
F
Introduction to Abstract Mathematics
23
Logical Equivalence
Two propositional forms are cold logically equivalent if they have
identical truth tables.
If propositional forms p and q are logically equivalent we write p
Show that
p  q is logically equivalent to ~p  q
~p
~p  q
p
q
pq
T
T
T
F
T
T
F
F
F
F
F
T
T
T
T
F
F
T
T
T
Introduction to Abstract Mathematics
q,
24
Tautology and contradiction
A compound proposition is a proposition composed of one or more given
propositions (called the component propositions in this context) and at
least one logical connective.
Definition: A propositional form (compound proposition) is
called a tautology if it is true for all possible combinations
of truth values assigned to propositional variables
(component propositions).
( p  ~p )  t ( toutalogy)
Definition: A propositional form (compound proposition ) is
called a contradiction if it is false for all possible
combinations of truth values of the propositional variables
(component propositions)
( p  ~p )  c (contradiction)
Introduction to Abstract Mathematics
25
Examples:

Write truth table for: p  q  ~p

Show that (p  q)  r  (p  r)  (q  r)

Representation of : p  q  ~p  q
Re-write using if- then: Either you get in class on time, or you risk
missing some material

Negation of : ~(p  q)  p  ~q
Write negation for: If it is raining, then I cannot go to the beach
Introduction to Abstract Mathematics
26
Theorem RR ( See theorem 1.1.1) (replacement rules)
Commutative Law [Com]
P  Q  Q  P ,
P  Q  Q  P
3. Distributive Law [Dist]
P  (Q  R)  (P  Q)  (P  R)
P  (Q  R)  (P  Q)  (P  R)
5. DeMorgan Law [DeM]
~ ( P  Q)  (~ P  ~ Q )
~ ( P  Q)  (~ P  ~ Q )
7. Implication Law [Impl]
(P  Q)  (~ P  Q)
1.
2. Associative Law [Assoc]
(P  Q )  R  P  (Q  R)
(P  Q )  R  P  (Q  R)
4. Contrapositive Law [Contr]
(P  Q)  (~ Q  ~ P)
6. Double Negation [DN]
~ ~ (P)  P
9. Exportation [Exp]
(P  Q)  R  P (Q  R)
8. Equivalence Law [Equiv]
P  Q  ( P  Q)  (Q  P)
P  Q  (P  Q)  (~ Q  ~ P)
10. Tautology (Identity) [Taut]
P  P  P or P  P  P
11. P  t  P and P  c  c
12 P  t  t and P  c  P
t-tautolagy and c-contradiction
Introduction to Abstract Mathematics
27
Practice problems
1.
2.
3.
4.
Study the Sections 2.1 and 2.2 from your textbook.
Be sure that you understand all the examples discussed in
class and in textbook.
Only after you complete the proof of the Theorem_RR
from the notes
Do the following problems from the textbook:
Exercise 2.1, # 2, 3, 7, 8, 15, 26, 36, 43, 44, 46, 51.
Exercise 2.2, # 9, 15, 18, 21, 25, 27, 36, 44, 46, 48.
Introduction to Abstract Mathematics
28