Transcript Exercises for CS3511 Week 31 (first week of practical)

Exercises for CS1512
Weeks 7 and 8
Propositional Logic 1
(questions + solutions)
Exercise 1
1. Express each formula using only (at most) the
a.
b.
c.
d.
connectives listed. In each case use a truth
table to prove the equivalence. (Note:  is
exclusive `or`)
Formula: pq. Connectives: {,}.
Formula: pq. Connectives: {,,}.
Formula: pq. Connectives: {, }.
Formula: (pq)  ((p)q). Conn: {,}.
Answer to Exercise 1.
(Other answers possible)
a. Formula pq. Connectives: {,}.
Answer: pq
b. Formula: pq. Connectives: {,,}.
Answer: (p q)(q  p)
c. Formula: pq. Connectives: {, }.
Answer: (pq)(q p)
d. Formula: (pq)  ((p)q). Conn: {,}.
Answer: q (This was a trick question, since you don’t
need any connectives.)
Ex. 2. Which of these are
tautologies?
1.
2.
3.
4.
5.
p (q  p)
p (p  p)
(q  p)  (p  q)
(q  p)  (p  q)
(p  (q  r))  (q  (p  r))
Please prove your claims, using truth tables.
(Hint: Ask what assignment of truth values to
p,q, and r would falsify each formula. In this
way you can disregard parts of the truth table).
Answer to Ex.2
1.
2.
3.
4.
5.
p (q  p) Tautologous
p (p  p) Tautologous
(q  p)  (p  q) Contingent
(q  p)  (p  q) Tautologous
(p  (q  r))  (q  (p  r)) Tautologous
1,2,4,5 are known as “`paradoxes’ of the material
implication”, because they contrast with
implication in ordinary language.
Ex. 3. Reading formulas off
truth tables
• Background: In class, a proof was
sketched for the claim that every
propositional logic formula can be
expressed using the connectives
{, }. The proof proceeded essentially by
“reading off” the correct formula off the
truth table of any given formula.
• Task: Use this meticulous method to
construct a formula equivalent to pq.
Answer to ex. 3. Steps:
1.
2.
3.
Construct the truth table of pq.
Mark those two rows in the table that make pq TRUE.
Corresponding with these two rows, construct a
disjunction of two formulas, one of which is (pq),
and the other (qp).
4. Use the De Morgan Laws to convert this disjunction
(pq)(qp) into the quivalent formula
((pq) (qp))
[5. Use truth tables again to check that these two formulas
are indeed equivalent.]
Question 4a
• In class, it was proven that {, } is a
functionally complete set of connectives.
Making use of this result, can you prove
that {,} is also functionally complete?
Question 4a
• In class, it was proven that {, } is a
functionally complete set of connectives. Making
use of this result, can you prove that {,} is
also functionally complete?
• Answer: It is sufficient to show that both p and
(pq) are expressible using the two connectives
in {,}. The first of these two (i.e., negation) is
obvious, and the second (i.e., conjunction) can
be expressed as follows (pq)  (pq),
using one of De Morgan’s laws.
Question 4b
• In class, it was proven that {, } is a
functionally complete set of connectives.
Making use of this result, can you prove
that {NAND} is also functionally complete?
[Explanation: (p NAND q) is TRUE iff (pq)
is FALSE. This connective is also called
the Sheffer stroke and written (p|q).)
Question 4b
• In class, it was proven that {, } is a
functionally complete set of connectives. Making
use of this result, can you prove that {NAND} is
also functionally complete?
Answer: the reasoning is similar to that in 4a, but it
may be a bit trickier to find the right formulas: p
can be expressed as p  p|p. (It helps to do
negation before conjunction!) The formula pq is
equivalent to (p|q)|(p|q) (in other words, the
negation of p|q)
It might be useful to prove these equivalences
using truth tables.
Question 4c
• Given this result, why do we bother
defining and using more than one
connective?
• Answer: Many things can be expressed
more succinctly and transparently with a
larger ‘vocabulary’ of connectives (as your
answer to 4b will show). Also, it becomes
easier to let your formulas resemble the
things we say in e.g. English.
Question 5
a. (rc)d
b. r(cd)
Comparison of truth tables shows (a) and
(b) to be equivalent. Both formulas are
false if and only if (r true,c true,d false).