Week 4 Bi-implications, Transitivity & Mix quantifiers

Review 1:  P IMPLIES Q is equivalent to NOT(P) OR Q
WHY?
For P IMPLIES Q to be true, we must have either Q being True or P being False;
i.e they have the same value on the Truth Table

Review 2: NOT(P IMPLIES Q) is equivalent to P AND NOT(Q)
WHY?
For NOT(P IMPLIES Q) to be true, we must have P being True while Q being False

Bi-implication: P IFF Q
This is the combination of P if Q and P only if Q, hence, P if and only if Q
in other expressions: (P IMPLIES Q) AND (Q IMPLIES P)
or: (NOT(P) OR Q) AND (NOT(Q) OR P)
or: (P AND Q) OR (NOT(P) AND NOT(Q))

Negation: (P AND NOT(Q) OR (Q AND NOT(P)); the negation of (P IMPLIES Q) AND (Q IMPLIES P)
PROOF: By demorgan's laws, distributive law, and identity law
P XOR Q- P or Q, but NOT both

Transitivity:
Note 1: If P IMPLIES Q, all Q are in P
Hence, (P IMPLIES Q) AND (Q IMPLIES R) means Q is in P, R is in Q, therefore R is also in P, that is
P IMPLIES R
PROOF: By contradiction

Mixed Quantifiers
Note: if all quantifiers are the same, the order doesn't matter
Otherwise, it does

Class example:
For every woman, there is a man who is her soul mate. (the man can be different for each woman)

vs

There is a man, every woman is his soul mate. (the man is the same man for all woman)

Throw Back Lecture 1.1

Prove the statement “A being true implying B being true implies 

C being true” is true if and only if either A is true and B is 

false or C is true.

Prove

(A IMPLIES B) IMPLIES C      IFF      (A AND NOT(B)) OR C

1. (A IMPLIES B) IMPLIES C

2. (B OR NOT(A)) IMPLIES C

3. NOT(B OR NOT(A)) OR C

4. (NOT(B) AND NOT(NOT(A))) OR C

5. (A AND NOT(B)) OR C

1 = 5

PROOF

WHY PROOF? - It is important for ... science!

WHAT IS PROOF? An argument that can convince robots! logical, careful and precise

HOW TO PROVE?

1. Find a proof - understand the problem, be creative, understand your own ideas

2. Write up the proof - carefulness and precision

direct proof of universally quantified implications

Find direct implications/equivalences from P(x) to Q(x)

How to be good at proofs? PRACTICE

Follow Polya’s problem solving scheme

◆ understand the problem

◆ devise a plan

◆ carry out the plan

◆ look back

◆ acknowledge when, and how, you’re stuck