1-2_Propositional_Logic
Key Terms
Logic is used for mathematical reasoning and verification.
Propositional Logic: The area of logic that deals with propositions is called propositional
logic.
Proposition is a declarative sentence that is either true or false, but not both.
Declarative sentence is a sentence that declares a fact
Not propositions
Questions
Commands
Propositional variables are variables that represent propositions.
Compound propositions are formed from existing propositions.
Truth Table is a table displaying the truth values of propositions.
Logical operators
Precedence Operator Symbol Usage
1 Negation ¬ NOT
2 Conjunction ∧ AND
3 Disjunction ∨ OR
4 Exclusive OR ⊕ XOR
5 Conditional → if, then
6 Biconditional ↔ iff (XNOR)
Negation is the only unary operator.
The conjunction p ∧ q is true when both p and q are true and is false otherwise.
The disjunction p ∨ q is false when both p and q are false and is true otherwise.
Disjunction is true when at least one of the components is true.
The exclusive or of p ⊕ q is true when exactly one of p and q is true and is false otherwise.
Conditional Statements
Characteristics
The conditional statement p → q is the proposition p implies q
Conditional connective
Hypothesis Conclusion
The connective (→) is called conditional connective
A conditional statement is also called an implication
Truth Table for Conditional Statement
Whole statement false
True for all other combination
True False
Equivalent expressions of p → q
p → q is here hypothesis → conclusion
p implies q
if p, then q
if p, q
p only if q
q if p
q when p
q whenever p
"Carol gets seasick whenever she is on a boat"
whenever p, q
q unless ¬ p
p is a sufficient condition for q
a sufficient condition for q is p
"A Sufficient condition for the warranty to be good is that you bought the
computer less than a year ago."
q is a necessary condition for p
"It is necessary to wash the boss's car to get promoted"
a necessary condition for p is q
Converse, Contrapositive, and Inverse
New conditionals for p → q
Inverse ¬p → ¬q
Converse q → p
Contrapositive ¬q → ¬p
Biconditional
Let p and q be propositions. The biconditional statement p ↔ q is the proposition p if and
only if q
p ↔ q is only true when p and q have the same truth values (T, T or F, F)
Equivalent expression for p ↔ q
p if and only if q
p is necessary and sufficient for q
Info
Biconditional statements are also called bi-implications
Truth table for bi-conditional
Which operator is the opposite of ↔?
↔ has the exact opposite truth table of ⊕
3_Propositional_Equivalences
Tautology
Tautology is a compound proposition that is always true.
p ∨ ¬p
People either like watching TV or they don't
Contradiction
Contradiction is a compound proposition that is always false.
p ∧ ¬p
x is a prime and x is an even integer greater than 8
All men are good and all men are bad
Contingency
Contingency is a compound proposition whose truth value is not constant.
p → ¬p
Logical Equivalences
Compound propositions that have the same truth values in all possible cases are called
logically equivalent
Notations
p ≡ q or p ⇔ q
Laws of Logical Equivalences
A Useful Logical Equivalence (ULE)
4_Predicates_Quantifiers
Predicates
Predicate Predicate Predicate
function Variable
or
Subject
Predicate is a property that the subject can have.
Predicate is also called propositional function
Note
Once a value has been assigned to the variable x, the statement P(x) becomes a
proposition and has a truth value.
For example If P(x): x>3, then P(2): 4>3 , which is statement or proposition.
Example 1
Multivariable Predicates
Predicates that have more than one variable
For example: Q(x, y) : x = y + 3
Quantifiers
Domain
Domain is the set of values a variable in a propositional function may take
Also called domain of discourse and universe of discourse.
Universal Quantification
A predicate is true for every element in the domain
Denoted as ∀x P (x)
Reads for all P(x)
It is basically the conjunction of P(x) for all the domain
Example
Existential quantification
There is one or more elements in the domain for which a predicate is true.
Denoted as ∃x P (x)
Reads There is an x such that P(x)
It is basically the disjunction of P(x) for all the domain
Example
Truth values
Precedence
The quantifiers ∀ and ∃ have higher precedence that all logical operators from proposition
calculus.
Negating quantifiers
Universal negation: ¬∀x P (x) ≡ ∃x ¬P (x)
Existential negation: ¬∃x P (x) ≡ ∀x ¬P (x)
5_Functions
Function
Synonyms
Functions are also called maps and transformations
Terminology
If f is a function from A to B, we write f : A → B
A is the domain of f
B is the codomain of f
If f (a) = b
a is called the preimage of b
b is called the image of a
Domain: Set of values a function is allowed to take as input.
Codomain: Set of values a function is allowed to map to.
Range: Set of values a function actually maps (subset of the codomain).
OR set of all images of elements of A
Preimage: Subset of the domain.
Image: Subset of the range.
Range vs Codomain example
Multiple functions
Let f and f be functions from A to B. Then f
1 2 1 + f2 and f 1 f2 are also functions from A to B.
(f 1 + f 2 )(x) = f 1 (x) + f 2 (x)
(f 1 f 2 )(x) = f 1 (x)f 2 (x)
One-to-One Functions (Injective)
A function is one-to-one if all the elements in the domain have distinct images.
Denoted using quantifiers as:
∀a ∀b (f (a) → a = b)
∀a ∀b (a ≠ b → f (a) ≠ f (b))
Example
Onto Function (Surjective)
A function is onto if every element of codomain has preimage(s).
Example
One-to-One correspondence (Bijection)
A function is a one-to-one correspondence or a bijection if it is both one-to-one and onto.
Example
9_Integer_Modular
Integers and Division
a divides b
b dividend
a|b = =
a divisor
multiple factor
a does not divides b
a ∤ b
a, b, c is all integers
The Division Algorithm
•Remainder cannot be negative (since 0 ≤ r < d)
Congruence
OR m divides a − b
a, b are integers
m is a positive integer
Ceaser Cipher
f (p) = (p + 3) mod 26
−1
f (p) = (p − 3) mod 26
Shift Cipher
f (p) = (p + k) mod 26
−1
f (p) = (p − k) mod 26
10_Prime_GCD_LCM
Fundamental Theorem of Arithmetic
Integer or Prime?
GCD & LCM
if d|a and d|b , then d is the GCD of a and b.
a = dc and b = dc
if a|d and b|d , then d is the LCM of a and b
d = ac and d = bc
Finding GCD & LCM
ab = gcd(a, b) ⋅ lcm(a, b)