WEEK 2-4

LOGIC and SETS

MS101
DISCRETE MATHEMATICS
 WEEK 2-4 LOGIC AND SETS

What is Discrete Mathematics?

Discrete mathematics is the branch of mathematics dealing
with objects that can consider only distinct, separated values,
involving discrete elements that uses algebra and arithmetic.

MS101 – DISCRETE MATHEMATICS 2

*Discrete mathematics It is the study of mathematical structures that are countable or otherwise
distinct and separable.

**Discrete structures can be finite or infinite.

It is FINITE SET if a set has a starting point and an ending point both. (if the elements are countable)

It is INFINITE SET if it has no end from any side or both sides. (If a set has the unlimited number of
elements)

**Examples of structures that are discrete are combinations, graphs, and logical statements.
Combinatorics is often concerned with how things are arranged. In this context,
an arrangement is a way objects could be grouped.

A permutation is an arrangement of objects with regard to order.

A combination is an arrangement of objects without regard to order.
 WEEK 2-4 LOGIC AND SETS

What is Logic
•is the study of consequences.
•Is the art and science of reasoning.
•It is a science since it uses principles, laws and
methods in solving problems such as in proving the
validity of a given argument.

MS101 – DISCRETE MATHEMATICS 4

 WEEK 2-4 LOGIC AND SETS

Cont.. A X B = AB

premises + conclusion = argument

2 logical arguments intends the evidence or support.

Inductive Logic. uses a set of specific observations to reach an overarching conclusion
Deductive Logic. requires one to start with a few general ideas, called premises, and apply them to a
specific situation. Recognized rules, laws, theories, and other widely accepted truths are used to
prove that a conclusion is right.
Proposition Logic. Is an Argument that can be either True or False Statement but not both

MS101 – DISCRETE MATHEMATICS 5

 WEEK 2-4 LOGIC AND SETS

Syntax for PL (propositional logic)

• The syntax for propositional logic simply refers to the structure or
form of its sentences. Basically, sentences in PL are constructed using
the following building blocks:

• proposition, and
• logical connectives.

MS101 – DISCRETE MATHEMATICS 6

 WEEK 2-4 LOGIC AND SETS

Connectives
• Combining propositions to form a new proposition through the use of
connectives.
3 Basic Mathematic Statements known as 3 Basic Logical Connectives
1. NOT - Negation
2. AND – Logical Conjunction
3. OR – Logical Disjunction

Combining Mathematical Statements

1. IF-THEN (conditional)
2. IF and ONLY IF (biconditional)

MS101 – DISCRETE MATHEMATICS 7

 WEEK 2-4 LOGIC AND SETS

The NEGATION / NOT (~) connective

• the negation of p is written as ¬p, or sometimes ∼p, −p or p. It has the property
that it is false when p is true, and true when p is false.

Example:

p : 8 MB of RAM is enough to run Windows ’95.

~p : 8 MB of RAM is not enough to run Windows ’95.

MS101 – DISCRETE MATHEMATICS 8

 WEEK 2-4 LOGIC AND SETS

The AND ( ∧ ) connective

• the and of p and q is written as p ∧ q, and is true only when both p and q are true.

Example:

p : A mouse is an input device.

q : A printer is an output device.

p∧q: A mouse is an input device and a printer is an output device.

MS101 – DISCRETE MATHEMATICS 9

 WEEK 2-4 LOGIC AND SETS

The OR ( ∨ ) connective
• the or of two propositions p and q is written as p ∨ q, and is true as long as at least one, or
possibly both, of p and q is true.

Example:

p : I will date Ana.

q : I will date Maria.

p ∨ q : I will date Ana or I will date Maria.

I will date Ana or Maria.

MS101 – DISCRETE MATHEMATICS 10

 WEEK 2-4 LOGIC AND SETS

The IF-THEN / IMPLICATION\ ( → ) connective

• this is the most important connective for proofs. An implication represents an “if...then” claim. If p implies q, then
we write p → q or p ⇒ q, depending on our typographic convention and the availability of arrow symbols in our
favorite font.

Example:
If p Then q
p : Today is December 24.
q : Tomorrow is Christmas Day.
p→q : If today is December 24 then tomorrow is Christmas Day.

• In the conditional statement p → q, the premise (p) and the conclusion (q).

MS101 – DISCRETE MATHEMATICS 11

 WEEK 2-4 LOGIC AND SETS

The IF AND ONLY IF ( ↔ ) connective

• Suppose that p → q and q → p, so that either both p and q are true or both p and q are false.
In this case, we write p ↔ q or p ⇔ q, and say that p holds if and only if q holds. The truth of
p ↔ q is still just a function of the truth or falsehood of p and q.

P if and only if Q
Example:
p : I will marry you.
q : You love me.
p ↔ q : I will marry you if and only if you love me.

MS101 – DISCRETE MATHEMATICS 12

 WEEK 2-4 LOGIC AND SETS

The Logical Connectives

Name Symbol Syntax Verbal Form Equivalent Term Other Keywords

not ~ ~p not p negation "the denial of p"

"it is not the case that p"

and ∧ p∧q p and q conjunction "both p and q"; "but";

"while"

or ∨ p∨q p or q disjunction "either p or q";

"at least one of…"

if-then → p→q if p then q implication; "q if p"; "p only if q";

p implies q conditional “q when p";
“p implies q”;
“p logically implies q”;
“q is implied by p”;
"q provided that p";
"p is a sufficient condition for q";

"q is a necessary condition for p"

if-and-only-if ↔ p↔q p if and only if q equivalence; "p is equivalent to q"

biconditional “p is necessary and sufficient for q”

MS101 – DISCRETE MATHEMATICS 13

 WEEK 2-4 LOGIC AND SETS

Precedence Rules
(highest priority) not
and
or
if-then
(lowest priority) if and only if

MS101 – DISCRETE MATHEMATICS 14

 WEEK 2-4 LOGIC AND SETS

Semantics for PL
• The semantics or meaning of a sentence in propositional logic is the

truth or falsity of the sentence. It is the assignment of a truth value

to the sentence.

MS101 – DISCRETE MATHEMATICS 15

 WEEK 2-4 LOGIC AND SETS

Truth Table
A truth table provides the definition for connectives of propositional logic.

Steps in Creating a Truth Table

1. Assign one column for each propositional variable and the resulting proposition.
2. Determine the number of rows by the formula:
R = 2n
where : R is the number of rows
n is the number of propositional variables
From the rightmost, propositional variable, assign alternating values of true and false in
increments of power of 2 for each column.

MS101 – DISCRETE MATHEMATICS 16

 WEEK 2-4 LOGIC AND SETS

The NEGATION / NOT (~) connective

The AND / CONJUNCTION ( ∧ ) connective

MS101 – DISCRETE MATHEMATICS 17

 WEEK 2-4 LOGIC AND SETS

The OR / DISJUNCTION ( ∨ ) connective

The IF-THEN / IMPLICATION /CONDITIONAL ( → ) connective

MS101 – DISCRETE MATHEMATICS 18

 WEEK 2-4 LOGIC AND SETS

The IF AND ONLY IF ( ↔ ) connective

MS101 – DISCRETE MATHEMATICS 19

 WEEK 2-4 LOGIC AND SETS

Properties of Sentences
1. Satisfiable
-A sentence is satisfiable if is true for some interpretation.
-A satisfiable sentence is also called a contingency.

2. Contradictory
-A sentence is contradictory (or unsatisfiable) if it is false for every
interpretation.
-A contradictory sentence is also called and absurdity.

3. Valid
-A sentence is valid if it is true for every interpretation.
-A valid sentence is also called a tautology

MS101 – DISCRETE MATHEMATICS 20

 (p → ¬(p →
WEEK 2-4 LOGIC AND SETS
p q
q) q)
p q (p → q) (q → p) (p → q)
F
Logical Equivalence
F T F ^ (q →
p)
F T T F
F F T T T
T F F T
F T T F F
T T T F
T F F T F
T T T T T

p q ¬q (p^
¬q)
F F T F
F T F F
T F T T
T T F F
MS101 – DISCRETE MATHEMATICS 21
 WEEK 2-4 LOGIC AND SETS
No P^4 Q^2 R^1 ¬q (¬q v p→
r) (¬q v
r)
0 F F F T T T

1= F F T T T T

2 F T F F F T

3= F T T F T T

4= T F F T T T

5 T F T T T T

6= T T F F F F

7 T T T F T T
Active = 1 = TRUE
DISactivate =0 = FALSE

MS101 – DISCRETE MATHEMATICS 22