Logic, Part I: The Propositional Calculus

Chapter 2
Logic, Part I: The Propositional
Calculus

JESRAEL B. PALCO, PhD

Department of Physical Sciences and Mathematics

College of Science and Environment
Mindanao State University at Naawan
Logic, Part I: The Propositional Calculus
Basic Concepts of the Propositional Calculus

Definition 1
A statement, or proposition, is a declarative sentence
that is either true or false, but is not both true and false.
The designation T(true) or F(false), one and only one
of which is assignable to any given statement, is called
the truth value of that statement.
Logic, Part I: The Propositional Calculus
Basic Concepts of the Propositional Calculus

Example 1
The following are statements:
1 The moon is made of green cheese.
π 2 2π
2 (e ) = e .

3 6 is a prime number.

4 February 5, 1992 falls on a Wednesday.

√
5 The millionth digit in the decimal expansion of 2 is 6.
Logic, Part I: The Propositional Calculus
Basic Concepts of the Propositional Calculus

Example 2
The following are not statements:
π 2 2π
1 Is (e ) equal to e ?

2 If only every day could be like this one!

3 Every goople is an aardling.

4 2 + 3i is less than 5 + 3i.

5 x > 5.
Logic, Part I: The Propositional Calculus
Basic Concepts of the Propositional Calculus

Definition 2
Given statements p and q, we define three statements
formed from p and q
(a) The negation (or denial) of p, denoted by ∼ p and
read ”not p”, is true precisely when p is false.
(b) The conjunction of p and q, denoted by p ∧ q and read
”p and q”, is true precisely when p and q are both true.
(c) The disjunction of p and q, denoted by p ∨ q and read
”p or q”, is true when one or the other or both of the
statements p and q is (or are) true.
Logic, Part I: The Propositional Calculus
Basic Concepts of the Propositional Calculus

Truth table for negation:

p ∼p
T F
F T

Truth table for conjunction:

p q p∧q
T T T
T F F
F T F
F F F
Logic, Part I: The Propositional Calculus
Basic Concepts of the Propositional Calculus

Truth table for disjunction:

p q p∨q
T T T
T F T
F T T
F F F
Logic, Part I: The Propositional Calculus
Basic Concepts of the Propositional Calculus

Example 3
Determine inder what truth conditionsR that statement form
π
for the compound statement ” Either −π sinxdx 6= 0 and
R π
d/dx (2x ) = x2x−1 or −π sinxdx = 0 and ln6 = (ln2) (ln3)”
is true. Is the statement itself true or false?
Logic, Part I: The Propositional Calculus
Basic Concepts of the Propositional Calculus

p q r ∼p ∼p∧q p∧r (∼ p ∧ q) ∨ (p ∧ r)
T T T F F T T
T F T F F T T
F T T T T F T
F F T T F F F
T T F F F F F
T F F F F F F
F T F T T F T
F F F T F F F

The statement form (∼ p ∧ q) ∨ (p ∧ r) is true in some

cases, false in others.
Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

Definition 3
A statement form that is true under all possible truth
conditions for its components is called a tautology. A
statement form that is false under all possible truth
conditions for its components is called a contradiction.
Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

Example 4
Show that the statement forms p ∨ ∼ p and p ∧ ∼ p are,
respectively, a tautology and a contradiction.
Solution.

p ∼p p∨∼p p∧∼p
T F T F
F T T F

The statement form p ∨ ∼ p is always true, whereas

p ∧ ∼ p is always false.
Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

Definition 4
Two compound statement forms that have the same truth
values as each other under all possible truth conditions for
their components are said to be logically equivalent.
Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

Example 5
Show that the statement forms ∼ (p ∨ q) and ∼ p∧ ∼ q are
logically equivalent.
Solution.

p q p ∨q ∼p ∼q ∼p∧∼q ∼ (p ∨ q)
T T T F F F F
T F T F T F F
F T T T F F F
F F F T T T T

The statement form ∼ (p ∨ q) and ∼ p∧ ∼ q have the same

truth values as each other, under all possible truth
conditions.
Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

Definition 5
Given statements p and q, we define:
(a) The statement p implies q, denoted p → q, also read
”if p, then q” ,is true except in the case where p is true
and q is false. Such a statement is called a
conditional; the component statements p and q are
called the premise and conclusion, respectively.
(b) The statement p if and only if q, denoted p ↔ q, also
written ”p iff q”, is true precisely in the cases where p
and q are both true or p and q are both false. Such a
statement is called a biconditional.
Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

p q p→q p↔q
T T T T
T F F F
F T T F
F F T T

Truth tables for the conditional and biconditional.

Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

Example 6
Examples of conditionals:
1 If I finish my work, I go out on the town.

2 If 2 + 2 = 5, then {0, 1} ⊆ (0, 1).

3 If 2 + 2 = 4, then 5 is not a prime number.

Example 7
Examples of biconditionals:
1 3 is odd if and only if 4 is even.

2 7 + 6 = 14 if and only if 7 times 6 equals 41.

3 A triangle has three sides if and only if a hexagon has

seven sides.
Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

Exercises 1
Construct a truth table for each of the following statement
forms. Label each a tautology or contradiction.
1 (p ∧ q) → p

2 (p ∨ q) → (p ∧ q)

3 p ↔∼ p

4 {[(p ∧ q) → r] → (p → r)} ↔ (p → q)
Logic, Part I: The Propositional Calculus
Tautology, Equivalence, the Conditional, and Biconditional

THANK YOU!!!