The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 1 and
Foundations of Computation
The tutorial contains a number of exercises designed for the students to practice the course content. During the lab, the tutor will work through some of these exercises while the students will be responsible for completing the remaining exercises in their own time. There is no expectation that all the exercises will be covered in lab time.
Covers: Lecture Material Week 1
At the end of this tutorial, you will be able to
• understand truth tables and how to build them;
• validate boolean formulae;
• determine equality of boolean formulae using boolean algebra; • prove boolean equations using boolean algebra.
Exercise 1 Construct a Formula
Consider the boolean function given by the following truth table:
x y z f(x,y,z) FFF T FFT F FTF F FTT T TFF F TFT F TTF T TTT T
Give a formula (in variables x, y and z) that represents the boolean function given above. Briefly argue why the formula indeed represents the boolean function.
Solution. There are two ways to go about this. The first way is following the algorithm given in the lectures. We look at those rows of the truth table where the function evaluates to T and obtain:
(¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ y ∧ ¬z) ∨ (x ∧ y ∧ z). This formula represents the boolean function, because:
• If an assignment corresponds to a row in the truth table that evaluates to true, then it also satisfies at least one of the bracketed expressions in the formula above, and since the formula is the logical or of several such bracketed expressions, if at least one evaluates to true, the entire formula is true.
• If an assignment corresponds to false, then it cannot satisfy any of the bracketed expressions (as the bracketed ex- pressions) are only derived from rows that evaluated to true in the truth table), and so all of the bracketed expressions are false. Taking the logical or of a collection of false statements leads to false.
Furthermore, for the last two terms, we see that they are independent of z, so the above simplifies to (¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ y).
(Note that we usually require the simplest formula unless otherwise specified.) 1
Exercise 2 Boolean formulae evaluation
Consider the truth value assignment v that assigns the following truth values to the variables x, y and z: v(x) = T, v(y) = T, and v(z) = F. Which of the following formulae evaluate to T under the assignment v, i.e. when the truth values of x, y and z are given according to v?
1. (¬x∨¬y)∨¬(z∧y) Solution.
The formula evaluates True 2. ¬(¬x∨¬y)∨(x∨¬z)
Solution.
The formula evaluates True 3. ¬(x∨¬y)∧z
Solution.
The formula evaluates False
(¬x ∨ ¬y) ∨ ¬(z ∧ y)
4. ¬(x∨¬y∧z)
(Consider the precedence of the logical connectives.) Solution.
¬(x ∨ ¬y ∧ z)
¬(¬x∨¬y)∨(x∨¬z)
=(¬T ∨¬T)∨¬(F ∧T) =(F ∨F)∨¬(F ∧T)
= F ∨ ¬F
=F∨T=T
=¬(¬T ∨¬T)∨(T ∨¬F) =¬(F ∨F)∨(T ∨T)
= ¬F ∨ T
=T∨T=T
= ¬(T ∨ ¬T ) ∧ F = ¬(T ∨ F ) ∧ F = ¬T ∧ F =F∧F=F
= ¬(T ∨ ¬T ∧ F ) = ¬(T ∨ F ∧ F ) = ¬(T ∨ T )
= ¬T = F
¬(x∨¬y)∧z
The formula evaluates False. Note that if we have the precedence of ∧ and ∨ backwards, we would get the wrong
answer.
2
Exercise 3 Truth tables
Translate into boolean formulae the following sentences and generate their truth tables.
For example: The sun is hot but it is not humid
x: The sun is hot. y: It is humid. x∧¬y
1. Bob is not Australian
Solution.
x: Bob is Australian. Formula: ¬x
2. Bob is Australian and Alice is English
Solution.
x: Bob is Australian. y: Alice is English. Formula: x ∧ y
x y ¬y x∧¬y FFTF FTFF TFTT TTFF
x ¬x FT TF
xyx∧y FFF FTF TFF TTT
3. Either Bob is Australian and Alice is English, or neither Bob is Australian nor Alice is English
Solution.
x: Bob is Australian.
y: Alice is English.
Formula: (x ∧ y) ∨ (¬x ∧ ¬y)
Exercise 4
x y x∧y ¬x∧¬y (x∧y)∨(¬x∧¬y) FFFTT FTFFF TFFFF TTTFT
The parity function
Consider three variables x, y, and z. The (ternary) parity function p(x, y, z) is a boolean function with value • F, if an even number of the inputs x, y, and z have truth value T
• T , if an odd number of inputs have truth value T .
This exercise is about designing a formula for the ternary parity function.
3
1. Draw a truth table for the ternary parity function. The truth table should have the following form:
x y z p(x,y,z) FFF F
…
where we have just given the first row, and list all combinations of truth values for x, y, and z, as well as the result
of the parity function.
Solution. The full truth table is as follows:
x y z p(x,y,z) FFF F FFT T FTF T FTT F TFF T TFT F TTF F TTT T
2. Based on the truth table, give a logical formula with variables x, y, and z that represents the parity function. Briefly argue why your formula indeed represents the parity function.
Solution. We can encode the XOR of x and y using the formula (¬x ∧ y) ∨ (x ∧ ¬y), but the ensuing formula is rather big and difficult to understand. We go for the simpler option and write
(¬x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ z)
where each conjunctive term corresponds to one line of the truth table for which the formula evaluates to true.
Exercise 5 Equational Proofs of Boolean Equations
Consider the boolean identity T ∨ x = T .
1. How can you argue informally that the identity is true for all truth values of the (only) variable x?
Solution. Independent of the truth value of x, x ∨ T always evaluates to T , and so does T (trivially).
2. Give an equational proof of the boolean identity T ∨ x = T . You may only use the boolean equations presented in the lecture (associativity, commutativity, absorption, identity, distributivity and complements) as well as the law of idempotence x ∨ x = x (that we have established in the lectures).
Solution. We have:
Exercise 6
T ∨x=(x∨¬x)∨x = x ∨ (¬x ∨ x) = x ∨ (x ∨ ¬x) = (x∨x)∨¬x
= x ∨ ¬x T
(complements) (associativity) (commutativity) (associativity) (idempotence) (complements)
Valid Equations
Prove that the following equations are valid. You may only use the boolean equations presented in the lecture (associa- tivity, commutativity, absorption, identity, distributivity and complements) as well as the De Morgan laws (that we have established in the lectures – see Appendix).
4
1. x∨¬(y∧x)=T Solution. We have:
x ∨ ¬(y ∧ x) =
= x ∨ (¬y ∨ ¬x)
= x∨(¬x∨¬y)
= (x∨¬x)∨¬y
= T ∨ ¬y
= T
(De Morgan Law) (Commutativity) (Associativity) (Complements)
(see proof in Exercise 6)
(Complements) (Identity)
(De Morgan Law) (Distributivity) (Complements) (Identity)
(Distributivity) (Complements) (Identity) (Commutativity) (Absorption) (Commutativity) (Absorption)
2. ¬(x∧y)∧((¬x∨y)∧(¬y∨y))=¬x Solution. We have:
¬(x ∧ y) ∧ ((¬x ∨ y) ∧ (¬y ∨ y)) = ¬(x∧y)∧((¬x∨y)∧T) = ¬(x∧y)∧(¬x∨y) = (¬x∨¬y)∧(¬x∨y) = ¬x ∨ (¬y ∧ y) = ¬x ∨ F = ¬x =
3. (x∨y)∧((x∧z)∨(x∧¬z))∨((x∧y)∨y)=x∨y Solution. We have:
Exercise 7
(x∨y)∧((x∧z)∨(x∧¬z))∨((x∧y)∨y) = (x∨y)∧(x∧(z∨¬z))∨((x∧y)∨y)= (x∨y)∧(x∧T)∨((x∧y)∨y) = ((x∨y)∧x)∨((x∧y)∨y) = (x∧(x∨y))∨((x∧y)∨y) = x∨((x∧y)∨y) = x∨(y∨(x∧y))= x∨y=
Proving Boolean Equations
Consider the boolean equation ((x ∨ y) ∧ (x ∨ ¬y)) ∧ ((¬x ∨ y) ∧ (¬x ∨ ¬y)) = F
1. How can you argue informally that this equation is true, i.e. both sides have the same truth values for all possible
truth values of the variables x and y?
Solution. For any possible assignment to variables x and y, at least one of the bracketed expressions must be false, as the bracketed expressions enumerate all possible assignments. Since they cannot all be true for the same assignment, the entire expression is false.
2. Given an equational proof of this equation. You may only use the laws given in the lecture (associativity, commu- tativity, absorption, identity, distributivity and complements) the law of idempotence (x ∨ x = x) and the identity T ∨ x = T (that we have established in an earlier exercise).
Solution.
((x∨y)∧(x∨¬y))∧((¬x∨y)∧(¬x∨¬y)) = (x ∨ (y ∧ ¬y)) ∧ (¬x ∨ (y ∧ ¬y))
= (x ∨ F) ∧ (¬x ∨ F)
= x ∧ ¬x
(Distribution) (Compliments) (Identity) (Compliments)
= F
5
Appendix 1: Valid Boolean Equations Associativity
a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c Commutativity
a∨b=b∨a a∧b=b∧a Absorption.
a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a Identity.
a∨F=a a∧T=a Distributivity.
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) Complements.
a ∨ ¬a = T
Appendix 2: De
De
¬(x ∨ y) = ¬x ∧ ¬y
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a ∧ ¬a = F
¬(x ∧ y) = ¬x ∨ ¬y
6