Foundation:

Logic and
Proofs

College of Engineering and

Marc Elvin Cerezo
Information Technology Instructor/Professor
 Learning Outcomes

After the completion of the chapter, students

will be able to:
1. Describe declarative statements in math
that have true or false values.
2. Classify sequences of logical statements
as yielding true or false conclusion, given
the sequence of statements and the values
of individual statement parameters.

College of Engineering and

Information Technology
 What is Discrete Mathematics?

• Discrete Mathematics is the study of mathematical structures that are

countable or otherwise distinct and separable.

• Discrete mathematics encompasses a wide array of topics that can

be used to answer many tangible questions that arise in everyday life:
• Logic: Is a given argument logically sound, or does it contain a
fallacy?
• Number Theory: If a leap year happens every 4 years, and PH
presidents are elected every 6 years, how frequently is a
presidential election held in a leap year?
• Counting: How many different outfits can you make from the
clothes in your closet?
College of Engineering and
Information Technology
 What is Discrete Mathematics?

• Discrete Mathematics is the study of mathematical structures that are

countable or otherwise distinct and separable.

• Discrete mathematics encompasses a wide array of topics that can

be used to answer many tangible questions that arise in everyday life:
• Probability: What are your chances of winning the lottery?
• Recurrences: How much will you pay over the lifetime of a
mortgage if interest is compounded monthly?
• Graph Theory: What is the fastest way to get from your home to
your workplace?

College of Engineering and

Information Technology
 What is Logic?

• By definition: Logic is traditionally defined as the study of the laws of

thought or correct reasoning, and is usually understood in terms of
inferences or arguments.
• Logic is the basis of all mathematical reasoning, and of all
automated reasoning;

• Example:
“For every positive integer 𝑛, the sum of the
positive integers not exceeding 𝑛 is 𝑛(𝑛 + 1)/2”

College of Engineering and

Information Technology
 Propositional Logic

• Proposition – it is a declarative sentence, that is, a sentence that

declares a fact, that is either true or false, but not both.

• Example #1: All the following declarative sentences are propositions.

1. Marc Elvin is the first name of one of the instructors in COSC 50A.
2. Cebu is the capital of the Philippines.
3. 1+1 = 2.
4. 2+2 = 3.

• Assessment:
• Proposition 1 and 3 are true, whereas 2 and 4 are false.
College of Engineering and
Information Technology
 Propositional Logic

• Example #2: Consider the following sentences.

1. What time is it?
2. Read the document carefully.
3. x+1=2
4. x+y=z

• Assessment:
• Sentence 1 and 2 are not propositions because they are not
declarative sentences.
• Sentence 3 and 4 are not propositions because they are neither
true nor false.
College of Engineering and
Information Technology
 Propositional Logic

• Propositional Logic or Propositional Calculus studies the ways

statements can interact with each other.
• In propositional logic uses letters to denote propositional variables
(or statement variables), that is, variables that represent
propositions, just as letters are used to denote numerical variables.
• The variables are represented by small alphabets such as 𝑝, 𝑞, 𝑟, 𝑠.

• Compound Propositions are formed from existing propositions using

logical operators.
• Many mathematical statements are constructed by combining one or
more propositions.
College of Engineering and
Information Technology
 Logical Connectives

• Connectives are logical operators that are used to form new

propositions from two or more existing propositions.

• List of Logical Connectives:

1. Negation
2. Conjunction
3. Disjunction
4. Conditional
5. Bi-Conditional

College of Engineering and

Information Technology
 Negation Operator

• Negation operator constructs a new proposition from a single existing

proposition.
• The negation of a proposition can also be considered the result of
the operation of the negation operator on a proposition.

Definition: Let 𝑝 be a proposition. The 𝑛𝑒𝑔𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝑝, denoted by ¬𝑝 (also

denoted by 𝑝), is the statement:
“It is not the case that 𝑝.”
The proposition ¬𝑝 is read “not 𝑝.” The truth value of the negation of 𝑝,
¬𝑝, is the opposite of the truth value of 𝑝.

College of Engineering and

Information Technology
 Negation Operator

• Example #3: Find the negation of the proposition

1. “Neru’s PC runs Linux.”

• Assessment: Find the negation of proposition

• Negation is: “It is not the case that Neru’s PC runs Linux.”

• This negation can be more simply expressed as:

• “Neru’s PC does not run Linux.”

College of Engineering and

Information Technology
 Negation Operator

• Truth Table displays the negation of a proposition 𝑝. This table has a

row for each of the two possible truth values of a proposition 𝑝.
• Each row shows the truth value of ¬𝑝 corresponding to the truth
value of 𝑝.

𝒑 ¬𝒑

𝑇 𝐹

𝐹 𝑇

Table 1. The Truth Table for the Negation of a Proposition.

College of Engineering and

Information Technology
 Conjunction Operator

• Conjunction is indicated by the symbol ⋀. If there are two

propositions, 𝑝 and 𝑞, then the conjunction of 𝑝 and 𝑞 will also be a
proposition, which contains the following properties:
• When 𝑝 and 𝑞 are true, then the conjunction of them will be true.
• When 𝑝 and 𝑞 are false, then the conjunction of them will be false.

Definition: Let 𝑝 and 𝑞 be propositions. The 𝑐𝑜𝑛𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 of 𝑝 and 𝑞,

denoted by 𝑝 ∧ 𝑞 is true when both 𝑝 and 𝑞 are true and is false
otherwise.

College of Engineering and

Information Technology
 Conjunction Operator

• Example #4: There is two propositions 𝑝 and 𝑞 where:

• 𝑝 = “I am a good student.”
• 𝑞 = “I like discrete math.”

• Assessment: Find the conjunction of these propositions, 𝑝 ∧ 𝑞

• We can assess the proposition as “I am a good student and I like
discrete math.”
• But can be simplified as “I am a good student that likes math.”

College of Engineering and

Information Technology
 Conjunction Operator

• Truth Table displays the truth table of 𝑝 ∧ 𝑞. This table has a row for
each of the four possible combinations of truth values of 𝑝 and 𝑞.
• Note that in logic the word “but” sometimes is used instead of “and”
in a conjunction.
𝒑 𝒒 𝒑∧𝒒

𝑇 𝑇 𝑇

𝑇 𝐹 𝐹

𝐹 𝑇 𝐹

𝐹 𝐹 𝐹

Table 2. The Truth Table for the Conjunction of Two Propositions.

College of Engineering and
Information Technology
 Disjunction Operator

• Disjunction is indicated by the symbol ∨. If there are two propositions,

𝑝 and 𝑞 will also be a proposition, which contains the following
properties:
• When 𝑝 and 𝑞 are false, then the disjunction of them will be false.
• When either 𝑝 or 𝑞 both are true, then the disjunction of them will be
true.
Definition: Let 𝑝 and 𝑞 be propositions. The 𝑑𝑖𝑠𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 of 𝑝 and 𝑞,
denoted by 𝑝 ∨ 𝑞 is false when both 𝑝 and 𝑞 are false and is true
otherwise.

College of Engineering and

Information Technology
 Disjunction Operator

• Example #5: There is two propositions 𝑝 and 𝑞 where:

• 𝑝 = “Today is Tuesday.”
• 𝑞 = “It is raining today.”

• Assessment: Find the disjunction in these propositions, 𝑝 ∨ 𝑞

• We can assess this proposition that is, true on any day that is
Tuesday, or a rainy day (that includes Tuesdays) and is false on any
day other than Tuesday when it also does not rain.

• “Today is Tuesday or it is raining today.”

College of Engineering and

Information Technology
 Disjunction Operator

• Truth Table displays the truth table of 𝑝 ∨ 𝑞. This table has a row for
each of the four possible combinations of truth values of 𝑝 and 𝑞.

𝒑 𝒒 𝒑∨𝒒

𝑇 𝑇 𝑇

𝑇 𝐹 𝑇

𝐹 𝑇 𝑇

𝐹 𝐹 𝐹

Table 3. The Truth Table for the disjunction of Two Propositions.

College of Engineering and
Information Technology
 Disjunction Operator

• The use of the connective or in a disjunction corresponds to one of the

two ways the word or used in English:
• Exclusive or – a disjunction is false when both are true or both are
false.
• Inclusive or – a disjunction is true when at least one of the two
propositions is true.

• Definition: Let 𝑝 and 𝑞 be propositions. The 𝑒𝑥𝑐𝑙𝑢𝑠𝑖𝑣𝑒 𝑜𝑟 of 𝑝 and 𝑞,

denoted by 𝑝⨁𝑞, is the proposition that is true when exactly one of 𝑝
and 𝑞 is true and is false otherwise.

College of Engineering and

Information Technology
 Disjunction Operator

• Example #6: There is two propositions 𝑝 and 𝑞 where:

• 𝑝 = “Today is Tuesday.”
• 𝑞 = “It is raining Today.”

• Assessment: Find the disjunction in these propositions, 𝑝⨁𝑞

• “Either is today is Tuesday, or it is raining today, but not both.”
• Explains that this proposition is true on any day that is a Tuesday or
a rainy day (not including Tuesdays) and is false on any day other
Tuesday when it does not rain or rainy Tuesdays.

College of Engineering and

Information Technology
 Disjunction Operator

• Truth Table displays the truth table of 𝑝⨁𝑞. This table has a row for
each of the four possible combinations of truth values of 𝑝 and 𝑞.

𝒑 𝒒 𝒑⨁𝒒

𝑇 𝑇 𝐹

𝑇 𝐹 𝑇

𝐹 𝑇 𝑇

𝐹 𝐹 𝐹

Table 3. The Truth Table for the exclusive or of Two Propositions.

College of Engineering and
Information Technology
 Conditional Statements

• Conditional Statement – is indicated by the symbol →. If there are two

propositions, 𝑝 and 𝑞, then the conditional of 𝑝 and 𝑞 will also be a
proposition, which contains the following properties:
• If there is a proposition that has the form of 𝑖𝑓 𝑝 𝑡ℎ𝑒𝑛 𝑞, then that
type of proposition will be known as the implication or conditional
proposition.
• When 𝑝 is false, or 𝑝 and 𝑞 are true, then the implication of them will
be true.
• When 𝑝 is true, and 𝑞 is false, then the implication of them will be
false.

College of Engineering and

Information Technology
 Conditional Statements

• Definition: Let 𝑝 and 𝑞 be propositions. The conditional statements

𝑝 → 𝑞 is the proposition "𝑖𝑓 𝑝, 𝑡ℎ𝑒𝑛 𝑞. “ The conditional statement 𝑝 → 𝑞
is false when 𝑝 is true and 𝑞 is false, and true otherwise.
• In the conditional statement 𝑝 → 𝑞, 𝑝 is called the hypothesis (or
antecedent or premise) and 𝑞 is called the conclusion (or
consequence).

• A conditional statement is also called an implication.

• The statement 𝑝 → 𝑞 is called a conditional statement because
𝑝 → 𝑞 asserts that 𝑞 is true on the condition that 𝑝 holds.

College of Engineering and

Information Technology
 Conditional Statements

• Because conditional statements play such an essential role in

mathematical reasoning, a variety of terminology is used to express
𝑝 → 𝑞.

College of Engineering and

Information Technology
 Conditional Statements

• Example #7: Let 𝑝 be the statement “student learns discrete

mathematics” and 𝑞 the statement “student will find a good job”

• Assessment: Express the statement 𝑝 → 𝑞 as a statement in English.

• “If a student learns discrete mathematics, then a student will find a
good job.”
• Can also express in a different way:
• “a student will find a good job when a student learns discrete
mathematics.”

College of Engineering and

Information Technology
 Conditional Statements

• Note that the way conditional statements were defined is more general
than the meaning attached to such statements in the English language.
• E.g., “If it is sunny, then we will go to the beach.” This statement is
true in normal language where there is a relationship between
antecedent and consequence.

• But for the statement:

• “If John has a smartphone, then 2+3=5” is true from the definition of
conditional statement, because its conclusion is true.

College of Engineering and

Information Technology
 Conditional Statements

• For the statement:

• “If John has a smartphone, then 2+3=15” is true if John does not
have a smartphone, even though 2+3=15 is false.

• In mathematical reasoning, it is consider conditional statements of a

more general sort than in English.
• The mathematical concept of a conditional statement is independent
of a cause-and-effect relationship between antecedent and
consequence.

College of Engineering and

Information Technology
 Conditional Statements

• Truth Table displays the truth table of 𝑝 → 𝑞. This table has a row for
each of the four possible combinations of truth values of 𝑝 and 𝑞.

𝒑 𝒒 𝒑→𝒒

𝑇 𝑇 𝑇

𝑇 𝐹 𝐹

𝐹 𝑇 𝑇

𝐹 𝐹 𝑇

Table 4. The Truth Table for the conditional statement of Two Propositions.
College of Engineering and
Information Technology
 Bi-conditional operator

• Bi-conditional or Double Implication – It is indicated by the symbol

↔. If there are two propositions, 𝑝 and 𝑞, then the bi-conditional of 𝑝
and 𝑞 will also be a proposition, which contains the following properties:
• If there is a proposition that has the form "𝑝 𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓 𝑞“, then
that type of proposition will be known as bi-implication or bi-
conditional proposition.
• When 𝑝 and 𝑞 are true, or 𝑝 and 𝑞 both are false, then bi-implication
will be true otherwise false.

College of Engineering and

Information Technology
 Bi-conditional operator

• Example #8: Let 𝑝 be the statement “you can take the flight,” and let 𝑞
be the statement “You buy a ticket.”

• Assessment: 𝑝 ↔ 𝑞 is the statement

• “You can take the flight if and only if you buy a ticket.”

• This statement is true if 𝑝 and 𝑞 are either both true or both false, that
is, if you buy a ticket and can take the flight or if you do not buy a ticket
and you cannot take the flight.

College of Engineering and

Information Technology
 Bi-conditional operator

• Truth Table displays the truth table of 𝑝 → 𝑞. This table has a row for
each of the four possible combinations of truth values of 𝑝 and 𝑞.

𝒑 𝒒 𝒑↔𝒒

𝑇 𝑇 𝑇

𝑇 𝐹 𝐹

𝐹 𝑇 𝐹

𝐹 𝐹 𝑇

Table 5. The Truth Table for the bi-conditional statement of Two Propositions.
College of Engineering and
Information Technology
 Precedence of Logical Operators

• Precedence of operators helps to decide which operator will get

evaluated first in a complicated looking compound proposition.
Operators Names Precedence
¬ Negation 1
⋀ Conjunction 2
∨ Disjunction 3
→ Implication 4
↔ Bi-conditional 5

College of Engineering and

Information Technology
 Precedence of Logical Operators

• Example: 𝑝 → 𝑞⋀¬𝑝 where 𝑝 = 𝑡𝑟𝑢𝑒 𝑇 ; 𝑞 = 𝑓𝑎𝑙𝑠𝑒 𝐹 ;

• Then:
• 𝑝 → 𝑞⋀ ¬𝑝 𝑤ℎ𝑒𝑟𝑒 ¬𝑝 = 𝐹;
• 𝑝 → 𝑞⋀ ¬𝑝 𝑤ℎ𝑒𝑟𝑒 (𝑞⋀ ¬𝑝 ) = 𝐹
• 𝑝 → 𝑞⋀ ¬𝑝 𝑤ℎ𝑒𝑟𝑒 𝑝 → 𝑞⋀ ¬𝑝 =𝐹

College of Engineering and

Information Technology
 Precedence of Logical Operators

• Example: 𝑝 → 𝑞⋀¬𝑝 where 𝑝 = 𝑡𝑟𝑢𝑒 𝑇 ; 𝑞 = 𝑓𝑎𝑙𝑠𝑒 𝐹 ;

• Then using a Truth Table:

𝒑 𝒒 ¬𝒑 (𝒒⋀¬𝒑) (𝒑 → (𝒒⋀¬𝒑)

𝑇 𝐹 𝐹 𝐹 𝐹

College of Engineering and

Information Technology
 Complex Compound Propositions

• Construct the truth table of the compound proposition

• (𝑝 ∨ ¬𝑞) → (𝑝 ∧ 𝑞)
𝒑 𝒒 ¬𝒒 𝒑 ∨ ¬𝒒 𝒑∧𝒒 (𝒑 ∨ ¬𝒒) → (𝒑 ∧ 𝒒)

𝑇 𝑇

𝑇 𝐹

𝐹 𝑇

𝐹 𝐹
College of Engineering and
Information Technology