CSS 31012: Mathematics
for Computing
Propositional and Predicate Logic
Propositional logic
• Propositional logic is the study of propositions where a proposition is
a statement that is either true or false.
• Examples
• ‘1 + 1 = 2’ which is a true proposition.
• ‘Today is Wednesday’ which is true if today is Wednesday and false otherwise.
• ‘x > 0’ is not a proposition.
• ‘This sentence is false’ is not a proposition
M.S. Mohamed Hisam CSS 31012 2
• A propositional variable may be used to stand for a proposition.
• A propositional variable takes the value true or false.
• The negation of a proposition 𝑃 (denoted ¬𝑃) is the proposition that is true if and
only if 𝑃 is false and is false if and only if 𝑃 is true.
• A well-formed formula is built up from variables, constants, terms and logical
connectives such as conjunction (and), disjunction (or), implication (if… then…),
equivalence (if and only if) and negation.
M.S. Mohamed Hisam CSS 31012 3
Truth Tables
Conjunction Disjunction Negation
M.S. Mohamed Hisam CSS 31012 4
Conditional Statements Biconditional Statements
M.S. Mohamed Hisam CSS 31012 5
Example
Construct the truth table for the statement form (p ∨ q) ∧ ∼(p ∧ q).
Note that when or is used in its exclusive sense, the statement “p or q” means “p or q
but not both” or “p or q and not both p and q,” which translates into symbols as (p ∨ q)
∧ ∼(p ∧ q). This is sometimes abbreviated p ⊕ q or p XOR q.
M.S. Mohamed Hisam CSS 31012 6
Example
Construct a truth table for the statement form (p ∧ q) ∨ ∼r.
M.S. Mohamed Hisam CSS 31012 7
Logical Equivalence
• Two statement forms are called logically equivalent if, and only if, they
have identical truth values for each possible substitution of statements for
their statement variables.
• The logical equivalence of statement forms P and Q is denoted by writing
P ≡ Q.
• Two statements are called logically equivalent if, and only if, they have
logically equivalent forms when identical component statement variables
are used to replace identical component statements.
M.S. Mohamed Hisam CSS 31012 8
Example
Show that , ∼(p ∧ q) ≡ ∼p ∨ ∼q.
M.S. Mohamed Hisam CSS 31012 9
Tautologies and Contradictions
• A tautology is a statement form that is always true regardless of the truth
values of the individual statements substituted for its statement variables. A
statement whose form is a tautology is a tautological statement.
• A contradiction is a statement form that is always false regardless of the
truth values of the individual statements substituted for its statement
variables. A statement whose form is a contradiction is a contradictory
statement.
M.S. Mohamed Hisam CSS 31012 10
Example
Show that the statement form p ∨ ∼p is a tautology and that the
statement form p ∧ ∼p is a contradiction.
M.S. Mohamed Hisam CSS 31012 11
Example
If t is a tautology and c is a contradiction, show that p ∧ t ≡ p and p ∧ c ≡ c.
M.S. Mohamed Hisam CSS 31012 12
Summary of Logical Equivalences
M.S. Mohamed Hisam CSS 31012 13
Example
Use logical laws to verify the logical equivalence
∼(∼p ∧ q) ∧ (p ∨ q) ≡ p.
Solution:
∼(∼p ∧ q) ∧ (p ∨ q) ≡ (∼(∼p) ∨ ∼q) ∧ (p ∨ q) by De Morgan’s laws
≡ (p ∨ ∼q) ∧ (p ∨ q) by the double negative law
≡ p ∨ (∼q ∧ q) by the distributive law
≡ p ∨ (q ∧ ∼q) by the commutative law for ∧
≡p∨c by the negation law
≡p by the identity law.
M.S. Mohamed Hisam CSS 31012 14
