5.1 Logic and Proofs

Click to edit Master title style
DISCRETE MATHEMATICS
LESSON 5
MS. NIEZEL MAE L. TIPLES 1
LOGIC AND
PROOFS
P r e p a r e d b y : N I E Z E L M A E L . T I P L2E S
LOGIC
• Systematic way of thinking that allows us to parse the meanings of sentences

and to deduce new information from old information.
• Systematic study of how you construct the mathematical arguments.
Example:
1) Square 𝑆 has a side of 5 units.
2) If any square has a side 𝑠, then its area is 𝑠 2 square units.
3) Square 𝑆 has an area of 25 square units.
Note: It is important to realize that logic is a process of deducing information correctly, not just deducing correct
information.
3 3
PROPOSITIONS
• A Proposition (or Statement) is a declarative sentence or a mathematical

expression which is true or false, but not both.
Examples:
a) Ice floats in water.
b) China is in Europe.
c) The number 2 is rational.
d) 2 + 2 = 5
e) Where are you going?
f) Do your homework.
4 4
Click toVALUE
TRUTH edit Master title style
• The truth or falsity of a statement is called its truth value.

Example:
1) 𝑥 + 5 = 11
Truth set: 6
2) 𝑦 2 − 1 = 0
Truth set: 1, −1
• An open sentence is a declarative sentence whose truth value depends on the value
of one or more variables.
• The truth set of an open sentence is the set of all values of the variables that will make
the open sentence true.
5 5
EXERCISE
Decide whether or not the following are statements. In the case of a statement,
say if it is true or false, if possible.
1. Every real number is an even integer.

2. Every even integer is a real number.
3. Sets ℤ and ℕ.
4. Sets ℤ and ℕ are infinite.
6 6
Click to edit PROPOSITIONS
COMPOUND Master title style
• Many propositions are composite, that is, composed of sub-propositions or

propositions that involves the assembly of multiple statements.
Example:
1) 9 is divisible by 3 and 4 is an odd number.
2) John is smart or he studies every night.
3) Roses are red and violets are blue.
• Such composite propositions are called compound propositions.
7 7
Click to
BASIC LOGICAL
edit Master
OPERATIONS
title style/ CONNECTIVES
❑ Conjunction (𝑝 ∧ 𝑞)
→ Any two propositions can be combined by the word “and” to form a
compound proposition called the conjunction of the original
propositions.
Definition:
• If 𝑝 and 𝑞 are true, then 𝑝 ∧ 𝑞 is true; otherwise 𝑝 ∧ 𝑞 is false.
8 8
Click to
BASIC LOGICAL
edit Master
OPERATIONS
9 9
Click to
BASIC LOGICAL
edit Master
OPERATIONS
Example:
Determine the truth values of the following statements.
1) NORSU is in Negros Oriental and NONSHS is in Siquijor.
2) 3 + 2 = 6 and 3 ÷ 1 = 3
3) Marcos is the president of the Philippines and Biden is the president of the
United States.
1010
Click to
BASIC LOGICAL
edit Master
OPERATIONS
❑ Disjunction (𝑝 ∨ 𝑞)
→ Any two propositions can be combined by the word “or” to form a
compound proposition called the disjunction of the original
propositions.
Definition:
• If 𝑝 and 𝑞 are false, then 𝑝 ∨ 𝑞 is false; otherwise 𝑝 ∨ 𝑞 is true.
1111
Click to
BASIC LOGICAL
edit Master
OPERATIONS
1212
Click to
BASIC LOGICAL
edit Master
OPERATIONS
Example:
Determine the truth values of the following statements.
1) Ice floats in water or 2 + 2 = 4.
2) China is in Europe or 2 + 2 = 5.
3) The number 1 is even or the number 3 is odd.
1313
Click to
BASIC LOGICAL
edit Master
OPERATIONS
❑ Negation (~𝑝)
→ Given any proposition 𝑝, another proposition, called the negation of
𝑝, can be formed by writing “It is not true that ...” or “It is false that
...” before 𝑝 or, if possible, by inserting in 𝑝 the word “not.”
→ Denial of the statement
→ Not the opposite
Definition:
• If 𝑝 is true, then ~𝑝 is false; and if 𝑝 is false, then ~𝑝 is true.
1414
Click to
BASIC LOGICAL
edit Master
OPERATIONS
1515
Click to
BASIC LOGICAL
edit Master
OPERATIONS
Example:
Write the negation of the following statements.
1) Terry is a boy. Terry is not a boy.
2) A rhombus is a parallelogram. A rhombus is not a parallelogram.
3) All Filipinos are friendly. Not all Filipinos are friendly.
4) Two points determine a line. Two points do not determine a line.
1616
Click to edit Master
PROPOSITIONS AND TRUTH
title style
TABLES
Verify the following propositions by making truth tables.
1) ~ 𝑝 ⋀~𝑞 𝑝 𝑞 ~𝑞 𝑝⋀~𝑞 ∼ 𝑝⋀~𝑞
𝑇 𝑇
𝑇 𝐹
𝐹 𝑇
𝐹 𝐹
1717
title style
TABLES
𝑝 𝑞 𝑝⋀𝑞 ~ 𝑝⋀𝑞
2) ~ 𝑝⋀𝑞
𝑇 𝑇
𝑇 𝐹
𝐹 𝑇
𝐹 𝐹
1818
title style
TABLES
𝑝 𝑞 ~𝑝 ~𝑞 ∼ 𝑝 ∨ ~𝑞
3) ~𝑝⋁~𝑞
𝑇 𝑇
𝑇 𝐹
𝐹 𝑇
𝐹 𝐹
1919
Click toTABLE
TRUTH edit Master title style
Assignment:
a. Verify the proposition 𝑝⋁𝑞 ⋀ ∼ 𝑟 by making truth table.

b. What is the truth value of the compound proposition
𝑝⋁𝑞 ⋀ ∼ 𝑟, if 𝑝 is true, 𝑞 is true and 𝑟 is false?
2020
21

5.1 Logic and Proofs

Uploaded by

Copyright:

Available Formats

5.1 Logic and Proofs

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

5.1 Logic and Proofs

Uploaded by

Copyright:

Available Formats

Click to edit Master title style

• Systematic way of thinking that allows us to parse the meanings of sentences

3) Square 𝑆 has an area of 25 square units.

• A Proposition (or Statement) is a declarative sentence or a mathematical

• The truth or falsity of a statement is called its truth value.

1. Every real number is an even integer.

• Many propositions are composite, that is, composed of sub-propositions or

• Such composite propositions are called compound propositions.

Verify the following propositions by making truth tables.

1) ~ 𝑝 ⋀~𝑞 𝑝 𝑞 ~𝑞 𝑝⋀~𝑞 ∼ 𝑝⋀~𝑞

Verify the following propositions by making truth tables.

Verify the following propositions by making truth tables.

a. Verify the proposition 𝑝⋁𝑞 ⋀ ∼ 𝑟 by making truth table.

You might also like