Compound Proposition

DISCRETE MATHEMATICS • Formed by combining propositions

• To be able to form compound propositions, we
used basic logical connectives : not, and, or, if
Propositional Logic –then and if only if
• Part of logic which deals with statement are either true
or false , but not both
• Proposition – is declarative sentence that is either true
or false, but not both

Example:

1. Quezon city is the capital of the Philippines (FP)

2. Discrete Mathematics is an ICT course. (NP)
3. 1 + 3 = 4 (TP)
4. 2 + 2 = 3 (FP)

Example:

1. Where do you live?

2. Please erase the board.
3. Watch out!
4. a + 1 = 2
5. w + z = 3

Sentences 1, 2 and 3 are not propositions because

they are not declarative sentences. Sentences 4
and 5 are not propositions because they are
neither true nor false. Note that each of the
sentences 3 and 4 can be turned into a proposition
if assigned values to the variables

Example:

1. Where do you live?

2. Please erase the board.
3. Watch out!
4. a + 1 = 2
5. w + z = 3

Sentences 1, 2 and 3 are not propositions because

they are not declarative sentences. Sentences 4
and 5 are not propositions because they are
neither true nor false. Note that each of the
sentences 3 and 4 can be turned into a proposition
if assigned values to the variables

Logical Connectives
• A sentence that maybe either a single proposition
or a compound proposition.
Example 1:

Example 2:
Predicate
is a statement that contains variables and
becomes a proposition when specific values are
substituted for those variables. Predicates express
properties or relations among objects.

QUANTIFIERS
Express the extent to which a predicate is true over
a range of elements.

What is the universal quantifier?

The universal quantifier (∀\for all ∀) indicates
that a predicate is true for all elements in a given
domain.

What is the existential quantifier?

The existential quantifier (∃) indicates that there
exists at least one element in a given domain for
which the predicate is true.
EXERCISE ANSWER:
 FUNDAMENTALS OF MATH PROOF

Direct Proofs
A formal direct proof of a conditional statement p
→ q works as follows: assume p is true, build
steps using inference rules, with the final step
showing that q is true.

Proof by contradiction Mathematical Proof

In this method of proof, we assume a proposition

is not true, then through premise and logic find a
contradiction that shows our original premise
must have been correct and therefore the
proposition was true.
 SETS AND SUBSETS Finite Set – The finite set contains a countable,
limited number of elements that can be fully listed.
Set - a collection of objects. The specific objects
within the set are called the elements or members A = {1, 2, 3, 4, 5}
of the set. Capital letters are commonly used to B = {x| x ε Z+, 1 ≤ x ≤ 5 }
name sets. C = {2, 6, 10, 50, 76}

Set Notation - Braces { } can be used to list the

members of a set, with each member separated by
a comma. This is called the “Roster Method.” A
description can also be used in the braces. This is
called “Set-builder” notation.

Example: Set A: The natural numbers from 1 to 10.

Members of A: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Roster : A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Set Builder Not.: {xIx is a natural number from 1 to
10}

Symbols commonly used with Sets

∈ → indicates an object is an element of a set.
∉ → indicates an object is not an element of a set.
⊆→ indicates a set is a subset of another set.
⊂→ indicates a set is a proper subset of another
Universal Set – The universal set is the set of set.
elements from which all other sets are selected. ∩ → indicates the intersection of sets.
The symbol for universal set is U. ∪ → indicates the union of sets.

Subsets – any element of A must also be an

element of B
The symbol used to denote a subset is ⊆
Ellipsis - Three dots (...) used within the braces to The symbol used to denote not a subset is ⊆
indicate that the list continues in the established
pattern. This is helpful notation to use for long lists
or infinite lists. If the dots come at the end of the
list, they indicate that the list goes on indefinitely
(i.e. an infinite set). Proper Subsets – any element of A must also be
an element of B and A ≠ B
The symbol used to denote proper subset is ⊂
The symbol used to denote proper subset is ⊂
C = { 1, 2, 3}​ D⊂C Venn diagrams are the diagrams that are used to
D = { 1, 3}​ D⊂E represent the sets, relation between
E= {3, 2, 1}​ C⊂E the sets and operation performed on them, in a
pictorial way.

Venn diagram, introduced by John Venn

(1834-1883), uses circles (overlapping,
intersecting and non-intersecting), to denote the
relationship between sets.

A Venn diagram is also called a set diagram or a

logic diagram showing different set operations
such as the intersection of sets, union of sets and
difference of sets. It is also used to depict subsets
of a set.

Practice Exercise Answer:

 RELATION BETWEEN SETS

Cartesian Product

• Let C and D be non-empty sets, the cartesian

product, C × D is the set
of all ordered pairs (a, b) with the first element
from C and the
second element from D.
• The cartesian product, also known as the
cross-product or the
product set of C and D.
• In a set-builder notation: C × D = {(a,b): a ∈ C, b
∈ D}.

Cardinality of Cartesian Product

Let p be the number of elements of A and q be the
number of elements in B.
So, the number of elements in the Cartesian
product of A and B is pq.
if n(A) = p, n(B) = q, then n(A × B) = pq.

RELATION

PROPERTIES OF CARTESIAN PRODUCT

1) Cartesian Product is non-commutative: A × B ≠
B×A
2) A × B = B × A, only if A = B
3) n(A x B) = n(A) x n(B) Practice Exercise Answer:
4) A × B = ∅, if either A = ∅ or B = ∅
 SET IDENTITIES

Proving Set Identities

Practice Exercise Answer: