Introduction

College of Computing Studies

PROPOSITIONAL LOGIC
The Foundations: Logic and Proofs
Introduction Objectives Content Summary

Propositional Logic: Content Summary

Content Summary
1. Logical Propositions
2. Connectives
Negation, Conjunction, Disjunction
Exclusive OR, Implication, and Biconditional

3. Truth Tables
 Introduction Objectives

Propositional Logic: Learning Objectives

Learning Objectives
By the end of this lesson, the students are expected to grasp the ff:
Ability to Construct and Interpret Truth Tables: Learn how to construct truth
tables to evaluate the truth values of compound propositions.

Critical Thinking and Problem-Solving Skills: Develop critical thinking skills by

applying logical propositions, connectives, and truth tables to solve problems,
identify fallacies, and evaluate the validity of arguments.

Application in Mathematics and Computing Studies: Recognize the applications

of logical propositions, connectives, and truth tables in various fields, such as
mathematics and computing studies.
Introduction Content Summary Objectives Propositions

Propositional Logic: The Foundations: Logic and Proofs

What is a Propositional Logic?

It is a branch of formal logic that deals with propositions or statements,
which are declarative sentences that are either true or false.
Introduction Content Summary Objectives Propositions

Propositional Logic: The Foundations: Logic and Proofs

What is a Propositional Logic?

It is a branch of formal logic that deals with propositions or statements,
which are declarative sentences that are either true or false.

Examples of Propositions: Examples that are not Propositions:

1. Milk is white. 1. Sit down! (imperative)
2. The moon is made of 2. What time is it? (question)
green cheese.
3. 1 + 0 = 1
 Introduction Content Summary Objectives Propositions

Propositional Logic: Constructing Propositions

Constructing Propositions
Propositional Variables are commonly assigned as p, q, r, s, …
The proposition that is always true is denoted by T and the proposition
that is always false is denoted by F.

Compound Propositions; constructed from logical connectives and

other propositions:
Negation ¬ Exclusive OR⊕
Conjunction ∧ Implication →
Disjunction ∨ Biconditional ↔
Introduction Content Summary Objectives Negation

Propositional Logic: Compound Propositions

Negation (¬)
The negation of a proposition p is denoted by ¬p. (not)
It represents the logical operation of negating or inverting the truth value of a
proposition.
Introduction Content Summary Objectives Negation

Propositional Logic: Compound Propositions

Negation (¬)
The negation of a proposition p is denoted by ¬p. (not)
It represents the logical operation of negating or inverting the truth value of a
proposition.
Example: p ¬p
Let p be "The computer is turned on."
Then "¬p" denotes "It is not the case that the T F
computer is turned on.” F T
or more simply “The computer is not turned on.” Truth Table
(Negation)
Introduction Content Summary Objectives Conjunction

Propositional Logic: Compound Propositions

Conjunction (∧)
The conjunction of propositions p and q is denoted by p ∧ q. (and)
It represents the logical operation of "and" between two propositions. The resulting
compound proposition is true only when both of its constituent propositions
are true.
Introduction Content Summary Objectives Conjunction

Propositional Logic: Compound Propositions

Conjunction (∧)
The conjunction of propositions p and q is denoted by p ∧ q. (and)
It represents the logical operation of "and" between two propositions. The resulting
compound proposition is true only when both of its constituent propositions
are true.
p q p∧q
Example:
Let p be "It is raining" and q be "I have an umbrella." T T T
T F F
Then p∧q denotes F T F
"It is raining and I have an umbrella."
F F F
Truth Table
(Conjunction)
 Introduction Content Summary Objectives Disjunction

Propositional Logic: Compound Propositions

Disjunction
The disjunction of propositions p and q is denoted by p∨q. (or)
It represents the logical operation of "or" between two propositions. The resulting
compound proposition is true if at least one of its constituent propositions is
true.
 Introduction Content Summary Objectives Disjunction

Propositional Logic: Compound Propositions

Disjunction
The disjunction of propositions p and q is denoted by p∨q. (or)
It represents the logical operation of "or" between two propositions. The resulting
compound proposition is true if at least one of its constituent propositions is
true.
p q p∨q
Example: T T T
Let p be "It is sunny" and q be "It is a weekend." T F T
Then p∨q denotes F T T
"It is sunny or it is a weekend." F F F
Truth Table
(Disjunction)
 Introduction Content Summary Objectives Exclusive Or

Propositional Logic: Compound Propositions

Exclusive OR (⊕)
The exclusive or of propositions p and q is denoted by p⊕q. (either, but not both)
It represents the logical operation that returns true if exactly one of the two
propositions is true. It excludes the possibility of both propositions being true.
 Introduction Content Summary Objectives Exclusive Or

Propositional Logic: Compound Propositions

Exclusive OR (⊕)
The exclusive or of propositions p and q is denoted by p⊕q. (either, but not both)
It represents the logical operation that returns true if exactly one of the two
propositions is true. It excludes the possibility of both propositions being true.

p q p⊕q
Example:
Let p be "It is raining" and q be "It is sunny." T T F
T F T
Then p⊕q denotes F T T
"Either it is raining or it is sunny, but not both."
F F F
Truth Table
(Exclusive OR)
Introduction Content Summary Objectives Connective Or

Propositional Logic: Compound Propositions

Inclusive OR in English
Inclusive Or:
The inclusive or, denoted by "or," is a connective that represents a choice between
two options. It is used when both options can be true, or when only one of the options
needs to be true. In other words, the inclusive or allows for the possibility of either
option being true or both options being true.

Example: Let's consider the statement

"You can have tea or coffee." In this case, the inclusive or means that you can choose
either tea, or coffee, or even have both if you like.
Introduction Content Summary Objectives Connective Or

Propositional Logic: Compound Propositions

Exclusive OR in English
Exclusive Or:
The exclusive or, denoted by "either...or" or "but not both," is a connective that
represents a choice between two options with the condition that only one option can be
true, and both options cannot be true simultaneously. It excludes the possibility of both
options being true.

Example: Suppose we have the statement

"You can have either a hot dog or a hamburger, but not both." This means that you can
choose to have a hot dog or a hamburger, but you cannot have both at the same time.
 Introduction Content Summary Objectives Implication

Propositional Logic: Compound Propositions

Implication (→)
The implication of propositions p and q is denoted by p→q. (if, then)
It represents the logical operation where the truth of the hypothesis or
antecedent (p) implies the truth of the conclusion or consequent (q).
 Introduction Content Summary Objectives Implication

Propositional Logic: Compound Propositions

Implication (→)
The implication of propositions p and q is denoted by p→q. (if, then)
It represents the logical operation where the truth of the hypothesis or
antecedent (p) implies the truth of the conclusion or consequent (q).

Example: p q p→q
Let p be "It is raining" and q be "I will bring an T T T
umbrella."
T F F
Then p→q denotes. F T T
If it is raining, then I will bring an umbrella.
F F T
Truth Table
(Implication)
 Introduction Content Summary Objectives Implication

Propositional Logic: Compound Propositions

Understanding Implication (→)

p q p→q If the antecedent (p) is false, the truth value of the
consequent (q) does not affect the implication, and it is
T T T considered to be true.
T F F Other ways of expressing p→q
F T T if p, then q q unless ¬p
p implies q q when p
F F T p only if q q whenever p
Truth Table
(Implication)
 Introduction Content Summary Objectives Implication

Propositional Logic: Compound Propositions

Understanding Implication (→)

In p→q there does not need to be any connection between the antecedent or the
consequent. The “meaning” of p→q depends only on the truth values of p and q.

These implications are perfectly fine, but would not be used in ordinary English.
- “If the moon is made of green cheese, then I have more money than Bill Gates. ”
- “If the moon is made of green cheese, then I’m going to the eras tour.”
- “If 1 + 1 = 3, then your grandma wears combat boots.”

One way to view the logical condition is to think of an obligation or contract.

- "If I am elected, then I will lower taxes.”
- "If you get 100% on the final, then you will get an A.”
 Introduction Content Summary Objectives Biconditional

Propositional Logic: Compound Propositions

Biconditional (↔)
The biconditional of propositions p and q is denoted by p↔q. (if and only if)
It represents a relationship between two propositions, stating that they are
both true or false. If both propositions have the same truth value (either both
true or both false), then the biconditional is considered true.
 Introduction Content Summary Objectives Biconditional

Propositional Logic: Compound Propositions

Biconditional (↔)
The biconditional of propositions p and q is denoted by p↔q. (if and only if)
It represents a relationship between two propositions, stating that they are
both true or false. If both propositions have the same truth value (either both
true or both false), then the biconditional is considered true.

Example: p q p↔q
Let p be "It is raining" and q be "The ground is T T T
wet." Truth Table
T F F (Biconditional)

Then p↔q denotes. F T F

"It is raining if and only if the ground is wet."
F F T
 Introduction Content Summary Objectives Implication

Propositional Logic: Compound Propositions

Converse, Contrapositive, and Inverse

From p → q we can form new conditional statements.

q → p is the converse of p → q
¬ q → ¬ p is the contrapositive of p → q
¬ p → ¬ q is the inverse of p → q

Let's use the original statement "If it is raining, then the ground is wet"

Converse: "If the ground is wet, then it is raining."

Contrapositive: "If the ground is not wet, then it is not raining."
Inverse: "If it is not raining, then the ground is not wet."
Introduction Content Summary Objectives Take Note

Propositional Logic: Compound Propositions

Key Takeaways
NAME SYMBOL DESCRIPTION

NEGATION ¬ Inverts the truth value.

CONJUNCTION ∧ Both must be true.

DISJUNCTION ∨ At least one true.

True if exactly one of the two

EXLUSIVE OR ⊕ propositions is true.
Introduction Content Summary Objectives Take Note

Propositional Logic: Compound Propositions

Key Takeaways
NAME SYMBOL DESCRIPTION

It is false if P is true and Q is false. The

IMPLICATION → rest cases are true.

Both propositions have

BICONDITIONAL ↔ the same truth value. (True or False)
 Introduction Content Summary Objectives Truth Table

Propositional Logic: Constructing a Truth Table

Constructing a Truth Table

Determine the Number of Rows
Count the number of distinct variables in your propositions. The truth table will
have 2 raised to the power of n rows, where n is the number of distinct variables.

Evaluate Compound Propositions

If you have compound propositions formed by combining variables with logical
connectives, create additional columns to represent these compound propositions.

Fill out the Truth Values

Start with the leftmost column and alternate the truth values for each variable
column. Begin with "true" for half of the rows and "false" for the remaining rows.
Repeat the truth values as needed until you complete all the rows.
Introduction Content Summary Objectives Truth Table

Propositional Logic: Constructing a Truth Table

p q

T T
Example 1
T F
(( p ∧ q )∨ ¬q ) F T

F F
Introduction Content Summary Objectives Truth Table

Propositional Logic: Constructing a Truth Table

p q ¬q

T T F
Example 1
T F T
(( p ∧ q )∨ ¬q ) F T F

F F T
Introduction Content Summary Objectives Truth Table

Propositional Logic: Constructing a Truth Table

p q ¬q (p∧ q)

T T F T
Example 1
T F T F
(( p ∧ q )∨ ¬q ) F T F F

F F T F
Introduction Content Summary Objectives Truth Table

Propositional Logic: Constructing a Truth Table

p q ¬q (p∧q) ((p∧q)∨¬q)

T T F T T
Example 1
T F T F T
(( p ∧ q )∨ ¬q ) F T F F F

F F T F T
 Introduction Content Summary Objectives Truth Table

Propositional Logic: Constructing a Truth Table

Standard Precedence of Logical Operator

Consider the proposition: p ∨ q ∧ r. 1. Negation ¬
To make the intent clear, you can use parentheses
like this: (p ∨ q) ∧ r or p ∨ (q ∧ r), depending on 2. Conjunction ∧
the desired grouping. 3. Disjunction ∨
Similarly, in the proposition "p → q ∨ r," the 4. Implication →
implication (→) has higher precedence than the
disjunction (∨). Thus, the proposition would be 5. Biconditional ↔
evaluated as "p → (q ∨ r)" unless parentheses are
used to indicate a different grouping.
Introduction Content Summary Objectives Truth Table

Propositional Logic: Constructing a Truth Table

p q r ¬p p∨q ((p∨q) →¬p)

Example 2
p∨q →¬p
 Introduction Content Summary Objectives Truth Table

Propositional Logic: Constructing a Truth Table

p q r ¬p q∧r (¬ p → (q ∧ r) )

Solve this
(¬p → (q ∧ r))
 Introduction Content Summary Objectives Truth Table Assignment

Propositional Logic:

Assignment
1. Create statements for each of the logical connectives and their symbolic logic
expressions using distinct variables. ( p and q)
Example:
Negation:
Statement: It is not raining.
Symbolic Logic Expression: ¬p

2. Construct a truth table for:

(p ∧ q) → (¬ q )
(p ∨ q) ∧ (¬ q ∨ r)