Section 1.

1
▪ Propositions
▪ Connectives
▪ Negation
▪ Conjunction
▪ Disjunction
▪ Implication; contrapositive, inverse, converse
▪ Biconditional

▪ Truth Tables
▪ A proposition is a declarative sentence that is either true or false.
▪ Examples of propositions:
a) The Moon is made of green cheese.
b) Trenton is the capital of New Jersey.
c) Toronto is the capital of Canada.
d) 1+0=1
e) 0+0=2
▪ Examples that are not propositions.
a) Sit down!
b) What time is it?
c) x+1=2
d) x+y=z
▪ Constructing Propositions
▪ Propositional Variables: 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 ¬
▪ Conjunction ∧
▪ Disjunction ∨

▪ Implication →
▪ Biconditional ↔
▪ The negation of a proposition p is denoted by ¬p and has this truth
table:

p ¬p
T F
F T

▪ Example: If p denotes “The earth is round.”, then ¬p denotes

“It is not the case that the earth is round,” or more simply “The
earth is not round.”
▪ The conjunction of propositions p and q is denoted by p ∧ q
and has this truth table:
p q p∧q
T T T
T F F
F T F
F F F

▪ Example: If p denotes “I am at home.” and q denotes “It is

raining.” then p ∧q denotes “I am at home and it is raining.”
▪ The disjunction of propositions p and q is denoted by p ∨q and has
this truth table:

p q p ∨q
T T T
T F T
F T T
F F F
▪ Example: If p denotes “I am at home.” and q denotes “It is raining.”
then p ∨q denotes “I am at home or it is raining.”
▪ In English “or” has two distinct meanings.
▪ “Inclusive Or” - In the sentence “Students who have taken CS202 or
Math120 may take this class,” we assume that students need to have
taken one of the prerequisites, but may have taken both. This is the
meaning of disjunction. For p ∨q to be true, either one or both of p and q
must be true.
▪ “Exclusive Or” - When reading the sentence “Soup or salad comes with
this entrée,” we do not expect to be able to get both soup and salad. This
is the meaning of Exclusive Or (Xor). In p ⊕ q , one of p and q must be
true, but not both. The truth table for ⊕ is:

p q p ⊕q
T T F
T F T
F T T
F F F
▪ Ifp and q are propositions, then p →q is a conditional statement or
implication which is read as “if p, then q ” and has this truth table:

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

▪ Example: If p denotes “I am at home.” and q denotes “It is

raining.” then p →q denotes “If I am at home then it is raining.”
▪ In p →q , p is the hypothesis (antecedent or premise) and q is
the conclusion (or consequence).
▪ 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 on welfare.”
▪ “If 1 + 1 = 3, then your grandma wears combat boots.”
▪ One way to view the logical conditional 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.”

▪ If the politician is elected and does not lower taxes, then the
voters can say that he or she has broken the campaign pledge.
Something similar holds for the professor. This corresponds to the
case where p is true and q is false.
if p, then q p implies q
if p, q p only if q
q unless ¬p q when p
q if p
q whenever p p is sufficient for q
q follows from p q is necessary for p

a necessary condition for p is q

a sufficient condition for q is p
▪ 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
Example: Find the converse, inverse, and contrapositive of “It
raining is a sufficient condition for my not going to town.”
Solution:
converse: If I do not go to town, then it is raining.
inverse: If it is not raining, then I will go to town.
contrapositive: If I go to town, then it is not raining.
▪ Ifp and q are propositions, then we can form the biconditional
proposition p ↔q , read as “p if and only if q .” The biconditional
p ↔q denotes the proposition with this truth table:

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

▪ Ifp denotes “I am at home.” and q denotes “It is raining.” then

p ↔q denotes “I am at home if and only if it is raining.”
▪ Some alternative ways “p if and only if q” is expressed in English:

▪ p is necessary and sufficient for q

▪ if p then q , and conversely
▪ p iff q
▪ Construction of a truth table:
▪ Rows
▪ Need a row for every possible combination of values for the atomic
propositions.
▪ Columns
▪ Need a column for the compound proposition (usually at far right)
▪ Need a column for the truth value of each expression that occurs in
the compound proposition as it is built up.
▪ This includes the atomic propositions
▪ Construct a truth table for

p q r r pq p  q → r
T T T F T F
T T F T T T
T F T F T F
T F F T T T
F T T F T F
F T F T T T
F F T F F T
F F F T F T
▪ Construct a truth table for
▪ Two propositions are equivalent if they always have the same
truth value.
▪ Example: Show using a truth table that the conditional is
equivalent to the contrapositive.
Solution:

p q ¬p ¬q p →q ¬q → ¬ p
T T F F T T
T F F T F F
F T T F T T
F F T T T T
 Example: Show using truth tables that neither the converse nor
inverse of an implication are not equivalent to the implication.
Solution:

p q ¬p ¬q p →q ¬ p →¬ q q→p
T T F F T T T
T F F T F T T
F T T F T F F
F F T T T T T
▪ How many rows are there in a truth table with n propositional
variables?

Solution: 2n

▪ Note that this means that with n propositional variables, we can

construct 2n distinct (i.e., not equivalent) propositions.
 Operator Precedence
 1
 2
 3
→ 4
 5

p q → r is equivalent to (p q) →
r
If the intended meaning is p (q → r )
then parentheses must be used.
Section 1.2
▪ A tautology is a proposition which is always true.
▪ Example: p ∨¬p
▪ A contradiction is a proposition which is always false.
▪ Example: p ∧¬p
▪ A contingency is a proposition which is neither a tautology nor a
contradiction, such as p

P ¬p p ∨¬p p ∧¬p
T F T F
F T T F
▪ Two compound propositions p and q are logically equivalent if
p↔q is a tautology.
▪ We write this as p⇔q or as p≡q where p and q are
compound propositions.
▪ Two compound propositions p and q are equivalent if and only
if the columns in a truth table giving their truth values agree.
▪ This truth table shows that ¬p ∨ q is equivalent to p → q.
p q ¬p ¬p ∨ q p→ q
T T F T T
T F F F F
F T T T T
F F T T T
 Augustus De Morgan

1806-1871

This truth table shows that De Morgan’s Second Law holds.

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

T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T
▪ Identity Laws: ,

▪ Domination Laws: ,

▪ Idempotent laws: ,

▪ Double Negation Law:

▪ Negation Laws: ,
▪ Commutative Laws: ,

▪ Associative Laws:

▪ Distributive Laws:

▪ Absorption Laws:
▪ We can show that two expressions are logically equivalent by
developing a series of logically equivalent statements.
▪ To prove that we produce a series of equivalences
beginning with A and ending with B.

▪ Keep in mind that whenever a proposition (represented by a

propositional variable) occurs in the equivalences listed earlier, it
may be replaced by an arbitrarily complex compound proposition.
Example: Show that
is logically equivalent to
Solution:
Example: Show that
is a tautology.
Solution:
Section 1.3
▪ Steps to convert an English sentence to a statement in
propositional logic
▪ Identify atomic propositions and represent using propositional
variables.
▪ Determine appropriate logical connectives

▪ “If I go to Harry’s or to the country, I will not go shopping.”

▪ p: I go to Harry’s
▪ q: I go to the country.
▪ r: I will go shopping.
If p or q then not r.
Problem: Translate the following sentence into propositional
logic:
“You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”
One Solution: Let a, c, and f represent respectively “You can
access the internet from campus,” “You are a computer science
major,” and “You are a freshman.”
a→ (c ∨ ¬ f )
▪ System and Software engineers take requirements in English and
express them in a precise specification language based on logic.
Example: Express in propositional logic:
“The automated reply cannot be sent when the file system is full”
Solution: One possible solution: Let p denote “The automated
reply can be sent” and q denote “The file system is full.”
q→ ¬ p
Definition: A list of propositions is consistent if it is possible to
assign truth values to the proposition variables so that each
proposition is true.
Exercise: Are these specifications consistent?
▪ “The diagnostic message is stored in the buffer or it is retransmitted.”
▪ “The diagnostic message is not stored in the buffer.”
▪ “If the diagnostic message is stored in the buffer, then it is retransmitted.”

Solution: Let p denote “The diagnostic message is stored in the

buffer.” Let q denote “The diagnostic message is retransmitted” The
specification can be written as: p ∨ q, ¬p, p → q. When p is false
and q is true all three statements are true. So the specification is
consistent.
▪ What if “The diagnostic message is not retransmitted” is added.
Solution: Now we are adding ¬q and there is no satisfying assignment.
So the specification is not consistent.
 Raymond
Smullyan
(Born
1919)
▪ An island has two kinds of inhabitants, knights, who always tell the
truth, and knaves, who always lie.
▪ You go to the island and meet A and B.
▪ A says “B is a knight.”
▪ B says “The two of us are of opposite types.”
Example: What are the types of A and B?
Solution: Let p and q be the statements that A is a knight and B is a
knight, respectively. So, then p represents the proposition that A is
a knave and q that B is a knave.
p is true. Since knights tell the truth, q must also be
▪ If A is a knight, then
true. Then (p ∧  q)∨ ( p ∧ q) would have to be true, but it is not. So, A is
not a knight and therefore p must be true.
▪ If A is a knave, then B must not be a knight since knaves always lie. So,
then both p and q hold since both are knaves.
Section 1.4
▪ A formula A is said to be satisfiable if A has the truth value T for at
least one combination of truth values assigned to the variables
▪ The problem of determining whether a given statement is a
tautology, or a contradiction is called a decision problem
▪ Construction of truth tables may not be practical (Use other
procedures known as Normal Forms)
▪ Normal Form : Reduction of the given statement formula to the
standard forms
▪ Reduce the given statement formula to a normal form and find
whether a given statement formula is a tautology or a
contradiction or at least satisfiable
▪ A necessary and sufficient condition for an elementary product to
be identically false is that it contains at least one pair of factors in
which one is the negation of the other
➢ For any variable p, p ˄~p is identically false. Hence, if p ˄~p appears in
the elementary product, then the product is identically false
▪ A necessary and sufficient condition for an elementary sum to be
identically true is that it contains at least one pair of factors in
which one is the negation of the other
➢ For any variable p, p ˅~p is identically true. Hence, if p ˅~p appears in
the elementary sum, then the sum is identically true
▪ A propositional formula is in disjunctive normal form if it consists
of a disjunction of (1, … ,n) disjuncts where each disjunct
consists of a conjunction of (1, …, m) atomic formulas or the
negation of an atomic formula
▪ Disjunctive Normal Form is important for the circuit design
methods
▪ Every compound proposition can be put in disjunctive normal
form (can be proved using Truth Tables)
▪ A compound proposition is in Conjunctive Normal Form (CNF) if it
is a conjunction of disjunctions.
▪ Every proposition can be put in an equivalent CNF.
▪ Conjunctive Normal Form (CNF) can be obtained by eliminating
implications, moving negation inwards and using the distributive
and associative laws.
▪ Important in resolution theorem proving used in artificial
Intelligence (AI).
▪ A compound proposition can be put in conjunctive normal form
through repeated application of the logical equivalences covered
earlier.
Example: Find the Disjunctive Normal Form (DNF) of
(p∨q)→¬r

Solution: This proposition is true when r is false or when both p

and q are false.
(¬ p∧ ¬ q) ∨ ¬r
Example: Put the following into CNF:

Solution:
1. Eliminate implication signs:

2. Move negation inwards; eliminate double negation:

3. Convert to CNF using associative/distributive laws

▪ For a given formula, an equivalent formula consisting of
disjunction of minterms only is known as its principal disjunctive
normal form. Such a normal form is also called as the sum of
products canonical form
▪ Note - The number of minterms appearing in PDNF of a formula
is same as the number of entries with truth value T in the truth
table of the formula
▪ Duals :

▪ Maxterms
▪ For a given formula, an equivalent formula consisting of
conjunction of maxterms only is known as its principal conjunctive
normal form. Such a normal form is also called as the product of
sums canonical form
▪ Note - The number of maxterms appearing in PDNF of a formula
is same as the number of entries with truth value F in the truth
table of the formula
▪ A compound proposition is satisfiable if there is an assignment of
truth values to its variables that make it true. When no such
assignments exist, the compound proposition is unsatisfiable.
▪ A compound proposition is unsatisfiable if and only if its negation
is a tautology.
Example: Determine the satisfiability of the following compound
propositions:

Solution: Satisfiable. Assign T to p, q, and r.

Solution: Satisfiable. Assign T to p and F to q.

Solution: Not satisfiable. Check each possible assignment of truth

values to the propositional variables and none will make the
proposition true.