Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Discrete Mathematics
Short Term 2016

Instructor: Dalos “Dale” D
...

In the year 2010, more than10000 Filipinos went to
Canada
...


MATHEMATICAL LOGIC


the following statements are NOT propositions:






What did you say?
This sentence is false
...

 P: 10 is not divisible by 2
...

P: Barrack Obama is the American president
...

R: Corazon Aquino was an American president
...

2*4 = 16 or a quart is larger than a liter
...

Q: Lucio Tan is a billionaire
R: Steve Jobs was a billionaire
...

1+2 = 3 implies that 1 < 0
...

If Art Cruz gets 100 in the final exam, then Art
Curz will pass the course
...


BICONDITIONAL



logically equivalent to P → Q  Q → P
truth table
P
1

Q
1

PQ
1

1
0
0

0
1
0

0
0
1

BICONDITIONAL


examples




A rectangle is a square if and only if its diagonals
are perpendicular
...


OTHER CONCEPTS


Types of propositional forms






Tautology – a proposition that is true for every
possible permutation of truth values for the
component propositions
Contradiction – a proposition that is false for
every possible permutation of truth values for the
component propositions
Contingency – a proposition that is neither a
tautology nor a contradiction

SAMPLE TRUTH TABLES
(P  Q) → P
P

Q

PQ

(P  Q) → P

1

1

1

1

1

0

0

1

0

1

0

1

0

0

0

1

SAMPLE TRUTH TABLES
PP
P

P

PP

1

0

0

0

1

0

SAMPLE TRUTH TABLES
(P  Q) → P
P

Q

PQ

(P  Q )→ P

1

1

1

1

1

0

1

1

0

1

1

0

0

0

0

1

SAMPLE TRUTH TABLES
Show that (P  Q) (( P  Q)  ( P  Q)) is
a tautology
P

Q

P Q

PQ

 P  Q

(P  Q)  ( P  Q)

(P  Q) (( P  Q)  ( P  Q))

1

1

1

1

0

1

1

1

0

0

0

0

0

1

0

1

0

0

0

0

1

0

0

1

0

1

1

1

Precedence of the Logical Operators
Operator

Precedence/Priority Level



1



2



3



4



5

(P  Q) (( P  Q)  ( P  Q)) may
be presented as

PQPQ  PQ

In practice, parentheses are used to explicitly
show the precedence of operators
...

???

Real World Practices
- EXCLUSIVE OR
Rice or Muffin comes with the meal
order
...
(P  Q ) (P  Q)
b
...
(P Q)  (Q  P)
d
...

b
...

d
...

0>1 if and only if 2>1
...


Equivalent Propositions
(Logical Equivalence)


When are two propositions equivalent?
Suppose P and Q are compound propositions, P
and Q are equivalent if the truth value of P is
equal to the truth value of Q for all of the
permutation of truth values to the component
propositions

Equivalent Propositions
(Logical Equivalence)


Suppose P is equivalent to Q
...




The Rules of Replacement are equivalent
propositions(Logically equivalent propositions)



The Rules of Replacement are used to simplify a
proposition (Deriving a proposition equivalent to
a given proposition)

Rules of Replacement
1
...
Commutativity
( P  Q )  ( Q  P ),
(PQ)(QP)
3
...
De Morgan’s Laws
 ( P  Q )  P  Q,
 ( P  Q )  P  Q

Rules of Replacement
5
...
Distributivity of  over 
P(QR) (PQ)(PR)
7
...
Material Implication
( P  Q )  ( P  Q )
9
...
Exportation
[(PQ)R][P(QR)]
11
...
Contrapositive
( P  Q )  ( Q  P )

Rules of Replacement
13
...
Absorption
P(PR)P
P(PR)P

OTHER CONCEPTS


Contrapositive





Inverse





 Q →  P contrapositive of P → Q
 Q →  P is logically equivalent to P → Q
 P →  Q is the inverse of P → Q
P → Q is not logically equivalent to its inverse

Converse



Q → P is the converse of P → Q
P  Q is not logically equivalent to its converse

---