Propositions and
Connectives
Proposition - is a declarative sentence that
is either true or false, but not both.
Examples:
3 is an odd integer.
Quezon City was once the capital of the Philippines.
12 divided by 4 is equal to 3.
Tell whether the following is a proposition or
not.
1. 3 is an odd integer.
2. Read this sentence carefully.
3. 3 is an integer.
4. x + 4 = 7
5. Who are you talking to?
An acceptable proposition is given the
decision value true (or 1), while an
unacceptable statement is assigned a
decision value false (or 0). An array of
decision value (truth value) is called a
logical matrix (or truth table).
Negation
Let p be a proposition. The statement “It is not
the case that p” is another proposition, called the
negation of p, denoted by ¬p. the proposition ¬p is
read “not p”.
Examples
1. p : 2 is an even integer
¬p : It is not the case that 2 is an even integer
Or 2 is not an even integer
2. p : 3 is an odd integer
¬p : It is not the case that 3 is an odd integer
Or 3 is not an odd integer
Truth Matrix of the Negation of a Proposition
p ¬p
1 0
0 1
Logical Operators
• Conjunction
Let p and q be propositions. The proposition “p and
q” denoted by p ^ q, is the proposition that is true
when both p and q are true and is false otherwise.
The proposition p ^ q is called the conjunction of p
and q.
Examples
1. p : 2 is an even integer
q : 3 is an odd integer
p ^ q : 2 is an even integer and 3 is an odd integer
2. p : 4 is a rational number
q : 2 is not a rational number
p ^ q : 4 is a rational number and 2 is not a rational number
Truth Matrix for the conjunction of Two
Propositions
p q p^q
1 1 1
1 0 0
0 1 0
0 0 0
• Disjunction
Let p and q be propositions. The proposition “p or
q”, denoted by p v q, is the proposition that is
false when both p and q are false and true
otherwise. The proposition p v q is called the
disjunction of p and q.
Examples
1. p : 2 is an even integer
q : 3 is an odd integer
p ∨ q : 2 is an even integer or 3 is an odd integer
2. p : 4 is a rational number
q : 2 is not a rational number
p ∨ q : 4 is a rational number or 2 is not a rational number
Truth Matrix for the disjunction of Two
Propositions
p q p∨q
1 1 1
1 0 1
0 1 1
0 0 0
• Implication
Let p and q be propositions. The implication p
⇒ q is the proposition that is false when p is
true and q is false, and true otherwise. In
this implication p is called the premise or the
hypothesis, and q is called the consequence or
conclusion.
Examples
1. p : 2 is an even integer
q : 3 is an odd integer
p ⇒ q : If 2 is an even integer then 3 is an odd integer
2. p : 4 is a rational number
q : 2 is not a rational number
p ⇒ q : If 4 is a rational number then 2 is not a rational number
Truth Matrix for the Implication of Two
Propositions
p q p⇒q
1 1 1
1 0 0
0 1 1
0 0 1
• Bi-Conditional
Let p and q be propositions. The bi-conditional
p ⇔ q is the proposition that is true when p
and q have the same truth values, and is
false otherwise.
Examples
1. p : 2 is an even integer
q : 3 is an odd integer
p ⇔ q : 2 is an even integer if and only if 3 is an odd integer
2. p : 4 is a rational number
q : 2 is not a rational number
p ⇔ q : 4 is a rational number if and only if 2 is not a
rational number
Truth Matrix for Bi-Conditional
p q p⇒q q⇒p p⇔q
1 1 1 1 1
1 0 0 1 0
0 1 1 0 0
0 0 1 1 1
• Exclusive Or
Let p and q be propositions. The exclusive or
of p and q denoted by p ⊕ q is the
proposition that is true when exactly one of
p and q is true and is false otherwise.
Examples
1. p : 2 is an even integer
q : 3 is an odd integer
p ⊕ q : Either 2 is an even integer or 3 is an odd integer
2. p : 4 is a rational number
q : 2 is not a rational number
p ⊕ q : 𝐄𝐢𝐭𝐡𝐞𝐫 4 is a rational number o𝐫 2 is not a rational number
Truth Matrix for the Implication of Two
Propositions
p q p⊕q
1 1 0
1 0 1
0 1 1
0 0 0
Tautology, Contradiction, Contingency
• A tautologuous statement is one which has only the
decision value 1
• A contradictory statement is one which is always false
• A contingent statement is either a tautology or a
contradictory
Construct a truth table (truth matrix) for each of
these compound propositions.
1. p ^ ¬q
2. p ⇒ ¬p
3. (p v q) ⇒ (p ^ q)
4. ¬q ⇒ p
5. ¬p ^ ¬q
Construct a truth matrix for each of these
compound propositions.
• p ∨ ¬p
• p ^ ¬p
• p ⇒ ¬p
• (¬p ^ q) ^ ( q ⇒ p)