Examples
in Every Topic in Discrete Mathematics Covered in Prelim
v
Propositions
-
declarative
statement that is either true or false but not both.
Example:
ü
The
Philippines is divided into 16 regions.
ü
In
English alphabet, M is in between L and N.
ü
(10√1024)
+ (9√512) = 4
Not
propositions:
x
Everyone
hates Mathematics.
x
Adobo
is the most delicious food in the Philippines.
x
Computer
Engineering is a quiet easy course to take.
v
The Logical Connectives
Example
propositions:
P:
Everybody is present in class.
Q: Today is a prelim examination day.
R: They will pass.
Ø
NEGATION
– “not” denoted by (~)
~P
= Everybody is not present in class.
~Q
= Today is not a prelim examination day.
~R
= They will not pass.
P
|
Q
|
~P
|
~Q
|
T
|
T
|
F
|
F
|
T
|
F
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
F
|
T
|
T
|
An
example truth table of negation.
Ø
CONJUNCTION
– “and” denoted by (^)
P
^ Q = Everybody is present in class and today is a prelim examination day.
Q
^ R = Today is a prelim examination day and they will pass.
P
^ R = Everybody is present in class and they will pass.
P
|
Q
|
P^Q
|
T
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
F
|
F
|
F
|
F
|
An
example truth table of conjunction.
Ø
DISJUNCTION
– “or” denoted by (v)
P
v R = Everybody is present in class or they will pass
Q
v P = Today is a prelim examination day or everybody is present in class.
R
v Q = They will pass or today is a prelim examination day.
P
|
Q
|
PvQ
|
T
|
T
|
T
|
T
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
F
|
An example truth table of
disjunction.
Ø
IMPLICATION
CONDITIONAL – “if-then” denoted by (→)
P→Q
= If everybody is present in class then today is a prelim examination day.
Q→R
= If today is a prelim examination day then they will pass.
P→R
= If everybody is present in class then they will pass.
P
|
Q
|
P→Q
|
T
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
T
|
F
|
F
|
T
|
An
example truth table of implication conditional.
Ø
BI-CONDITIONAL
– “if and only if” denoted by (↔)
P↔Q
= Everybody is present in class if and only if today is a prelim examination
day.
Q↔R
= Today is a prelim examination day if and only if they will pass.
R↔P
= They will pass if and only if everybody is present in class.
P
|
Q
|
P↔Q
|
T
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
F
|
F
|
F
|
T
|
An
example truth table of bi-conditional.
v
Properties of Sentence
Ø
VALID
-
a
sentence is valid if it is true for
every interpretations. A valid sentence is also called “Tautology”
examples:
ü (P↔Q) v (P→P)
P
|
Q
|
P↔Q
|
P→P
|
(P↔Q)
v (P→P)
|
T
|
T
|
T
|
T
|
T
|
T
|
F
|
F
|
T
|
T
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
T
|
T
|
T
|
ü (~P v P) ^ [(P v ~Q) v ~P]
P
|
Q
|
~P
|
~Q
|
~P
v P
|
P
v ~Q
|
(P
v ~Q) v ~P
|
(~P
v P) ^ [P v ~Q) v ~P]
|
T
|
T
|
F
|
F
|
T
|
T
|
T
|
T
|
T
|
F
|
F
|
T
|
T
|
T
|
T
|
T
|
F
|
T
|
T
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
T
|
T
|
T
|
T
|
T
|
T
|
ü [~P ^ (~P v Q)] ↔ ~P
P
|
Q
|
~P
|
~P
v Q
|
~P
^ (~P v Q)
|
[~P ^ (~P v Q)] ↔ ~P
|
T
|
T
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
F
|
F
|
T
|
F
|
T
|
T
|
T
|
T
|
T
|
F
|
F
|
T
|
T
|
T
|
T
|
Ø
CONTRADICTORY
-
A
sentence is contradictory if it is false for every interpretation. A
contradictory sentence is also called an “Absurdity”
examples:
ü (P v Q) ^ ~ (P v Q)
P
|
Q
|
P
v Q
|
~
(P v Q)
|
(P
v Q) ^ ~ (P v Q)
|
T
|
T
|
T
|
F
|
F
|
T
|
F
|
T
|
F
|
F
|
F
|
T
|
T
|
F
|
F
|
F
|
F
|
F
|
T
|
F
|
ü P ^ ~ P
P
|
~
P
|
P
^ ~ P
|
T
|
F
|
F
|
T
|
F
|
F
|
F
|
T
|
F
|
F
|
T
|
F
|
ü [(P↔Q) v (P→P)] → P ^ ~P
P
|
Q
|
~P
|
P↔Q
|
P→P
|
(P↔Q)
v (P→P)
|
P
^ ~P
|
[(P↔Q)
v (P→P)] → P ^ ~P
|
T
|
T
|
F
|
T
|
T
|
T
|
F
|
F
|
T
|
F
|
F
|
F
|
T
|
T
|
F
|
F
|
F
|
T
|
T
|
F
|
T
|
T
|
F
|
F
|
F
|
F
|
T
|
T
|
T
|
T
|
F
|
F
|
Ø
SATISFIABLE
-
it
is satisfiable if it is true for some interpretation. It is also called as “Contingency”
examples:
ü (P ^ Q) → ~ Q
P
|
Q
|
P
^ Q
|
~
Q
|
(P
^ Q) → ~ Q
|
T
|
T
|
T
|
F
|
F
|
T
|
F
|
F
|
T
|
T
|
F
|
T
|
F
|
F
|
T
|
F
|
F
|
F
|
T
|
T
|
ü ~ (P↔Q) ^ (P→Q)
P
|
Q
|
(P
|
~
(P
|
(P→Q)
|
~
(P↔Q) ^ (P→Q)
|
T
|
T
|
T
|
F
|
T
|
F
|
T
|
F
|
F
|
T
|
F
|
F
|
F
|
T
|
F
|
T
|
T
|
T
|
F
|
F
|
T
|
F
|
T
|
F
|
ü ~ P v [ P→ (~ P ^ P)]
P
|
~
P
|
(~
P ^ P)
|
P→
(~ P ^ P)]
|
~
P v [ P→ (~ P ^ P)]
|
T
|
F
|
F
|
F
|
F
|
T
|
F
|
F
|
F
|
F
|
F
|
T
|
F
|
T
|
T
|
F
|
T
|
F
|
T
|
T
|
v
The Inference Rules
You
use the rules to specify which conclusions may be inferred legitimately from
propositions known, assumed or previously established; to make it valid.
Example
propositions:
P:
I love you
Q:
You’re dating with others.
R:
My heart aches
S:
I will die
Rule
#1: P→(P v Q)
(Addition)
P___ I love you
\P v
Q Therefore, I love you or
you’re dating with others.
Rule
#2: (P ^ Q) → P (Simplification)
_(P
^ Q)_ I love you and you’re
dating with others
\ P Therefore, I love you.
Rule
#3: (P ^ Q) → (P ^ Q) (Conjunction)
P I
love you
__Q___ You’re dating with others
\ P ^
Q Therefore, I love you and
you’re dating with others.
Rule
#4: [(P→Q) ^ P] → Q (Modus Ponens)
P→Q If I love you then you’re dating
with others
P____ I love you
\ Q Therefore, you’re dating with
others.
Rule
#5: [(P→Q) ^ ~ Q] → ~P (Modus Tollens)
P→Q If I love you then you’re dating
with others
_~Q__ You’re not dating with others
\ ~P Therefore, I don’t love you.
Rule
#6: [(P v Q) ^ ~ P] → Q (Disjunctive Syllogism)
P
v Q I love you or you’re
dating with others
_~
P__ I don’t love you
\ Q Therefore, you’re dating with
others.
Rule
#7: [(P→Q) ^ (Q→R)] → (P→R) (Hypothetical Syllogism)
P→Q If I love you then you’re dating
with others
Q→R_ If you’re dating with others then
my heart aches
\ P→R Therefore, if I love you then my
heart aches.
Rule
#8: [(P→Q) ^ (R→S) ^ (P v R)] → (Q v S) (Constructive Dillema)
P→Q If I love you then you’re dating
with others
R→S If my heart aches then I will
die
P
v R__ I love
you or my heart aches
\Q v
S Therefore, you’re
dating with others or I will die.
Rule
#9: [(P→Q) ^ (R→S) ^ (~Q v ~S)] → ~ (P v R) (Distructive Dilemma)
P→Q If I love you then you’re dating
with others
R→S If my heart aches then I will
die
~Q
v ~S_ You’re not dating with
others or I will not die
\~P v
~R Therefore, you’re not beautiful
or my heart wasn’t aching.
v
Sentence Propositions Into
Symbolic (Vice Versa)
P:
She drinks a lot
Q:
She’s drunk
R:
She will fail
Sentence
|
Symbolic
|
1. If she
drinks a lot and she’s not drunk then she will not fail or she doesn’t drink
a lot.
|
(P ^ ~ Q) → ~ (R v P)
|
2. She will
not fail if she neither drinks a lot nor she’s drunk.
|
~
R ← ~ (P ^ Q)
|
3. She’s
drunk and she will fail if and only if she drinks a lot or she will fail.
|
(Q ^ R) ↔ (P v R)
|
Symbolic
|
Sentence
|
1. (~P ^ Q)
→ R
|
If she doesn’t drink a lot and
she’s drunk then she will fail.
|
2. R ↔ ~ (P
v Q)
|
She
will fail if and only if neither she drinks a lot nor she’s drunk.
|
3. (P → R) v
(Q → R)
|
If she drinks a lot then she will fail or if she’s drunk then
she will fail.
|
