CO-205: Discrete Structures Tutorial #2
Summary satisfiable a compound proposition for which there is
proposition a statement that is true or false compound an assignment of truth values to its variables
propositional a variable that represents a proposition proposition that makes it true
variable logically compound propositions that always have the
truth value true or false equivalent same truth values
~ p (negation the proposition with truth value opposite to compound
of p) the truth value of p propositions
logical operators used to combine propositions predicate part of a sentence that attributes a property
operators / to the subject
connectives propositional a statement containing one or more variables
compound a proposition constructed by combining function that becomes a proposition when each of its
proposition propositions using logical operators variables is assigned a value or is bound by a
truth table a table displaying all possible truth values of quantifier
propositional statement domain (or the values a variable in a propositional
p∨q the proposition “p or q,” which is true if and universe) of function may take
(disjunction of only if at least one of p and q is true discourse
p and q) ∃x P(x) the proposition that is true if and only if
p∧q the proposition “p and q,” which is true if (existential there exists an x in the domain such that P(x)
(conjunction and only if both p and q are true quantification is true
of p and q) of P(x))
p⊕q the proposition “p XOR q,” which is true ∀x P(x) the proposition that is true if and only if P(x)
(exclusive or when either one of p or q is true (universal is true for every x in the domain
of p and q) quantification
p → q (p the proposition “if p, then q,” which is false of P(x))
implies q) if and only if p is true and q is false logically expressions that have the same truth value
equivalent no matter which propositional functions and
converse of the conditional statement expressions domains are used
p→q q→p free variable a variable not bound in a propositional
Contrapositive the conditional statement function
of p→q ~q →~p bound a variable that is quantified
inverse of the conditional statement variable
p→q ~p →~q scope of a portion of a statement where the quantifier
𝑖𝑓 𝑝 𝑡ℎ𝑒𝑛 𝑞 𝑖𝑓 𝑝 , 𝑞 quantifier binds its variable
𝑝 𝑖𝑚𝑝𝑙𝑖𝑒𝑠 𝑞 𝑝 𝑜𝑛𝑙𝑦 𝑖𝑓 𝑞
𝑞 𝑤ℎ𝑎𝑡𝑒𝑣𝑒𝑟 𝑝 𝑞 𝑓𝑜𝑙𝑙𝑜𝑤𝑠 𝑓𝑟𝑜𝑚 𝑝
Terminologies Logical Equivalences
𝑝 𝑖𝑠 𝑠𝑢𝑓𝑓𝑒𝑐𝑖𝑒𝑛𝑡 𝑓𝑜𝑟 𝑞 𝑞 𝑤ℎ𝑒𝑛 𝑝
used to express Equivalence Name
p→q 𝑎 𝑠𝑢𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑎 𝑛𝑒𝑐𝑒𝑠𝑠𝑎𝑟𝑦
p∧T≡p
𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 Identity laws
p∨F≡p
𝑓𝑜𝑟 𝑞 𝑖𝑠 𝑝 𝑓𝑜𝑟 𝑝 𝑖𝑠 𝑞
p∨T≡T
𝑞 𝑖𝑠 𝑛𝑒𝑐𝑒𝑠𝑠𝑎𝑟𝑦 𝑓𝑜𝑟 𝑝 𝑞 𝑢𝑛𝑙𝑒𝑠𝑠 ~𝑝 Domination laws
p∧F≡F
p↔q the proposition “p if and only if q,” which is
p∨p≡p
(biconditional) true if and only if p and q have the same Idempotent laws
truth value p∧p≡p
~(~p) ≡ p Double negation law
bit either a 0 or a 1
Boolean a variable that has a value of 0 or 1 p∨q≡q∨p
Commutative laws
variable p∧q≡q∧p
bit operation an operation on a bit or bits (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Associative laws
bit string a list of bits (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
bitwise operations on bit strings that operate on each p ∨ (q ∧ r) ≡
operations bit in one string and the corresponding bit in (p ∨ q) ∧ (p ∨ r)
Distributive laws
the other string p ∧ (q ∨ r) ≡
logic gate a logic element that performs a logical (p ∧ q) ∨ (p ∧ r)
~(p ∧ q) ≡ ~p ∨~q
operation on one or more bits to produce an De Morgan’s laws
output bit ~(p ∨ q) ≡ ~p ∧~q
logic circuit a switching circuit made up of logic gates p ∨ (p ∧ q) ≡ p
Absorption laws
that produces one or more output bits p ∧ (p ∨ q) ≡ p
tautology a compound proposition that is always true p ∨~p ≡ T
Negation laws
contradiction a compound proposition that is always false p ∧~p ≡ F
contingency a compound proposition that is sometimes
true and sometimes false
consistent compound propositions for which there is an
compound assignment of truth values to the variables
propositions that makes all these propositions true
, Logical Equivalences involving Conditional / De Morgan’s Laws for Quantifiers
Bi-conditional Statements. Negation Equivalent When is Negation When False?
p → q ≡ ~p ∨ q p → q ≡ ~q →~p Statement True?
p ∨ q ≡ ~p → q p ∧ q ≡ ~(p →~q) ~∃xP(x) ∀x~P(x) For every x, P(x) is There is an x for
false. which P(x) is
~(p → q) ≡ p ∧~q true.
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
~∀xP(x) ∃x~P(x) There is an x for P(x) is true for
(p → r) ∧ (q → r) ≡ (p ∨ q) → r which P(x) is false. every x.
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ (p ∧ q) ∨ (~p ∧~q)
p ↔ q ≡ ~p ↔~q ~(p ↔ q) ≡ p ↔~q
1. Which of these are propositions? What are the truth 5. Determine whether these bi-conditionals are true or
values of those that are propositions? false.
a) Do not cross the road when the signal is red. a) 2 + 2 = 4 if and only if 1 + 1 = 2.
b) What is the time now? b) 1 + 1 = 2 if and only if 2 + 3 = 4.
c) There are no Windmills in the University. c) 1 + 1 = 3 if and only if monkeys can fly.
d) 3 + x = 12. d) 0 > 1 if and only if 2 > 1.
e) The moon is made of green cheese.
f ) 5x ≥ 67. 6. State the converse, contra-positive, and inverse of
each of these conditional statements.
2. What is the negation of each of these propositions? a) If it snows tonight, then I will stay at home.
a) Ram and Vinod are friends. b) I go to the beach whenever it is a sunny summer
b) There are 13 items in a baker’s dozen. day.
c) Bobby sent more than 50 text messages c) When I stay up late, it is necessary that I sleep
yesterday on his mobile phone. until noon.
d) 144 is a perfect square.
7. Construct a truth table for each of these compound
3. Let p and q be the propositions propositions.
p: I bought a lottery ticket this week. a) p ⊕ p b) p ⊕~p
q: I won the million-dollar jackpot. c) p ⊕~q d) ~p ⊕~q
Express each of these propositions as an English e) (p ⊕ q) ∨ (p ⊕~q) f ) (p ⊕ q) ∧ (p ⊕~q)
sentence.
(a) ~p (b) p ∨ q (c) p → q (d) p ∧ q 8. Explain, without using a truth table, why (𝑝 ∨
(e) p ↔ q (f ) ~p →~q (g) ~p ∧~q (h) ~p ∨ (p ∧ q) ~𝑞) ∧ (𝑞 ∨ ~𝑟) ∧ (𝑟 ∨ ~𝑝) is true when p, q, and r
have the same truth value and it is false otherwise.
4. Let p and q be the propositions
p:You drive over 80km/h. 9. What is the value of x after each of these
q:You get a speeding ticket. statements is encountered in a computer program,
Write these propositions using p and q and known assume that x = 1 before the statement is reached?
logical connectives. a) if x + 2 = 3 then x := x + 1
a) You do not drive over 80km/h. b) if (x + 1 = 3) OR (2x + 2 = 3) then x := x + 1
b) You drive over 80km/h, but you do not get a c) if (2x + 3 = 5) AND (3x + 4 = 7) then x := x + 1
speeding ticket. d) if (x + 1 = 2) XOR (x + 2 = 3) then x := x + 1
c) You will get a speeding ticket if you drive over e) if x < 2 then x := x + 1
80km/h.
d) If you do not drive over 80km/h, then you will 10. Express the statement “You can see the movie
not get a speeding ticket. only if you are over 18 years old or you have the
e) Driving over 80km/h is sufficient for getting a permission of a parent.” in terms of the prepositions –
speeding ticket. m: “You can see the movie,”
f) You get a speeding ticket, but you do not drive a: “You are over 18 years old,”
over 80km/h. p: “You have the permission of a parent.”
g) Whenever you get a speeding ticket, you are
driving over 80km/h. 11. Express the statement “to use the wireless network
in the airport you must pay the daily fee unless you
CO-205: Discrete Structures Tutorial #2 (Pg: 2)
Summary satisfiable a compound proposition for which there is
proposition a statement that is true or false compound an assignment of truth values to its variables
propositional a variable that represents a proposition proposition that makes it true
variable logically compound propositions that always have the
truth value true or false equivalent same truth values
~ p (negation the proposition with truth value opposite to compound
of p) the truth value of p propositions
logical operators used to combine propositions predicate part of a sentence that attributes a property
operators / to the subject
connectives propositional a statement containing one or more variables
compound a proposition constructed by combining function that becomes a proposition when each of its
proposition propositions using logical operators variables is assigned a value or is bound by a
truth table a table displaying all possible truth values of quantifier
propositional statement domain (or the values a variable in a propositional
p∨q the proposition “p or q,” which is true if and universe) of function may take
(disjunction of only if at least one of p and q is true discourse
p and q) ∃x P(x) the proposition that is true if and only if
p∧q the proposition “p and q,” which is true if (existential there exists an x in the domain such that P(x)
(conjunction and only if both p and q are true quantification is true
of p and q) of P(x))
p⊕q the proposition “p XOR q,” which is true ∀x P(x) the proposition that is true if and only if P(x)
(exclusive or when either one of p or q is true (universal is true for every x in the domain
of p and q) quantification
p → q (p the proposition “if p, then q,” which is false of P(x))
implies q) if and only if p is true and q is false logically expressions that have the same truth value
equivalent no matter which propositional functions and
converse of the conditional statement expressions domains are used
p→q q→p free variable a variable not bound in a propositional
Contrapositive the conditional statement function
of p→q ~q →~p bound a variable that is quantified
inverse of the conditional statement variable
p→q ~p →~q scope of a portion of a statement where the quantifier
𝑖𝑓 𝑝 𝑡ℎ𝑒𝑛 𝑞 𝑖𝑓 𝑝 , 𝑞 quantifier binds its variable
𝑝 𝑖𝑚𝑝𝑙𝑖𝑒𝑠 𝑞 𝑝 𝑜𝑛𝑙𝑦 𝑖𝑓 𝑞
𝑞 𝑤ℎ𝑎𝑡𝑒𝑣𝑒𝑟 𝑝 𝑞 𝑓𝑜𝑙𝑙𝑜𝑤𝑠 𝑓𝑟𝑜𝑚 𝑝
Terminologies Logical Equivalences
𝑝 𝑖𝑠 𝑠𝑢𝑓𝑓𝑒𝑐𝑖𝑒𝑛𝑡 𝑓𝑜𝑟 𝑞 𝑞 𝑤ℎ𝑒𝑛 𝑝
used to express Equivalence Name
p→q 𝑎 𝑠𝑢𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑎 𝑛𝑒𝑐𝑒𝑠𝑠𝑎𝑟𝑦
p∧T≡p
𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 Identity laws
p∨F≡p
𝑓𝑜𝑟 𝑞 𝑖𝑠 𝑝 𝑓𝑜𝑟 𝑝 𝑖𝑠 𝑞
p∨T≡T
𝑞 𝑖𝑠 𝑛𝑒𝑐𝑒𝑠𝑠𝑎𝑟𝑦 𝑓𝑜𝑟 𝑝 𝑞 𝑢𝑛𝑙𝑒𝑠𝑠 ~𝑝 Domination laws
p∧F≡F
p↔q the proposition “p if and only if q,” which is
p∨p≡p
(biconditional) true if and only if p and q have the same Idempotent laws
truth value p∧p≡p
~(~p) ≡ p Double negation law
bit either a 0 or a 1
Boolean a variable that has a value of 0 or 1 p∨q≡q∨p
Commutative laws
variable p∧q≡q∧p
bit operation an operation on a bit or bits (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Associative laws
bit string a list of bits (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
bitwise operations on bit strings that operate on each p ∨ (q ∧ r) ≡
operations bit in one string and the corresponding bit in (p ∨ q) ∧ (p ∨ r)
Distributive laws
the other string p ∧ (q ∨ r) ≡
logic gate a logic element that performs a logical (p ∧ q) ∨ (p ∧ r)
~(p ∧ q) ≡ ~p ∨~q
operation on one or more bits to produce an De Morgan’s laws
output bit ~(p ∨ q) ≡ ~p ∧~q
logic circuit a switching circuit made up of logic gates p ∨ (p ∧ q) ≡ p
Absorption laws
that produces one or more output bits p ∧ (p ∨ q) ≡ p
tautology a compound proposition that is always true p ∨~p ≡ T
Negation laws
contradiction a compound proposition that is always false p ∧~p ≡ F
contingency a compound proposition that is sometimes
true and sometimes false
consistent compound propositions for which there is an
compound assignment of truth values to the variables
propositions that makes all these propositions true
, Logical Equivalences involving Conditional / De Morgan’s Laws for Quantifiers
Bi-conditional Statements. Negation Equivalent When is Negation When False?
p → q ≡ ~p ∨ q p → q ≡ ~q →~p Statement True?
p ∨ q ≡ ~p → q p ∧ q ≡ ~(p →~q) ~∃xP(x) ∀x~P(x) For every x, P(x) is There is an x for
false. which P(x) is
~(p → q) ≡ p ∧~q true.
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
~∀xP(x) ∃x~P(x) There is an x for P(x) is true for
(p → r) ∧ (q → r) ≡ (p ∨ q) → r which P(x) is false. every x.
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ (p ∧ q) ∨ (~p ∧~q)
p ↔ q ≡ ~p ↔~q ~(p ↔ q) ≡ p ↔~q
1. Which of these are propositions? What are the truth 5. Determine whether these bi-conditionals are true or
values of those that are propositions? false.
a) Do not cross the road when the signal is red. a) 2 + 2 = 4 if and only if 1 + 1 = 2.
b) What is the time now? b) 1 + 1 = 2 if and only if 2 + 3 = 4.
c) There are no Windmills in the University. c) 1 + 1 = 3 if and only if monkeys can fly.
d) 3 + x = 12. d) 0 > 1 if and only if 2 > 1.
e) The moon is made of green cheese.
f ) 5x ≥ 67. 6. State the converse, contra-positive, and inverse of
each of these conditional statements.
2. What is the negation of each of these propositions? a) If it snows tonight, then I will stay at home.
a) Ram and Vinod are friends. b) I go to the beach whenever it is a sunny summer
b) There are 13 items in a baker’s dozen. day.
c) Bobby sent more than 50 text messages c) When I stay up late, it is necessary that I sleep
yesterday on his mobile phone. until noon.
d) 144 is a perfect square.
7. Construct a truth table for each of these compound
3. Let p and q be the propositions propositions.
p: I bought a lottery ticket this week. a) p ⊕ p b) p ⊕~p
q: I won the million-dollar jackpot. c) p ⊕~q d) ~p ⊕~q
Express each of these propositions as an English e) (p ⊕ q) ∨ (p ⊕~q) f ) (p ⊕ q) ∧ (p ⊕~q)
sentence.
(a) ~p (b) p ∨ q (c) p → q (d) p ∧ q 8. Explain, without using a truth table, why (𝑝 ∨
(e) p ↔ q (f ) ~p →~q (g) ~p ∧~q (h) ~p ∨ (p ∧ q) ~𝑞) ∧ (𝑞 ∨ ~𝑟) ∧ (𝑟 ∨ ~𝑝) is true when p, q, and r
have the same truth value and it is false otherwise.
4. Let p and q be the propositions
p:You drive over 80km/h. 9. What is the value of x after each of these
q:You get a speeding ticket. statements is encountered in a computer program,
Write these propositions using p and q and known assume that x = 1 before the statement is reached?
logical connectives. a) if x + 2 = 3 then x := x + 1
a) You do not drive over 80km/h. b) if (x + 1 = 3) OR (2x + 2 = 3) then x := x + 1
b) You drive over 80km/h, but you do not get a c) if (2x + 3 = 5) AND (3x + 4 = 7) then x := x + 1
speeding ticket. d) if (x + 1 = 2) XOR (x + 2 = 3) then x := x + 1
c) You will get a speeding ticket if you drive over e) if x < 2 then x := x + 1
80km/h.
d) If you do not drive over 80km/h, then you will 10. Express the statement “You can see the movie
not get a speeding ticket. only if you are over 18 years old or you have the
e) Driving over 80km/h is sufficient for getting a permission of a parent.” in terms of the prepositions –
speeding ticket. m: “You can see the movie,”
f) You get a speeding ticket, but you do not drive a: “You are over 18 years old,”
over 80km/h. p: “You have the permission of a parent.”
g) Whenever you get a speeding ticket, you are
driving over 80km/h. 11. Express the statement “to use the wireless network
in the airport you must pay the daily fee unless you
CO-205: Discrete Structures Tutorial #2 (Pg: 2)
