2

(18 marks) Problem 2 Recall from Assignment 2 the neighbourhood of eight houses: As before, each house wants to set up its own wi-fi network, but the wireless networks neighbouring houses - that is, houses that are either next to each other ignoring trees) or over the road from one another (directly opposite) - can interfere, and must therefore be on different channels. Houses that are sufficiently far away may use the same wi-fi channel. Again we would like to solve the problem of finding the minimum number of channels needed, but this time we will solve it using techniques from logic and from probability. Rather than directly asking for the minimum number of channels required, we ask if it is possible to solve it with just 2 channels. So suppose each wi-fi network can either be on channel hi or on channel lo. Is it possible to assign channels to networks so that there is no interference? (a) Formulate this problem as a problem in propositional logic. Specifically: (i) Define your propositional variables (4 marks) (ii) Define any propositional formulas that are appropriate and indicate what propositions they represent. (4 marks) (iii) Indicate how you would solve the problem (or show that it cannot be done) using propositional logic. It is sufficient to explain the method, you do not need to provide a solution. (2 marks) (iv)* Explain how to modify your answer(s) to (i) and (ii) if the goal was to see if it is possible to solve with 3 channels rather than 2. (4 marks) (b) Suppose each house chooses, uniformly at random, one of the two network channels. What is the probability that there will be no interference? (4 marks) (18 marks) Problem 2 Recall from Assignment 2 the neighbourhood of eight houses: As before, each house wants to set up its own wi-fi network, but the wireless networks neighbouring houses - that is, houses that are either next to each other ignoring trees) or over the road from one another (directly opposite) - can interfere, and must therefore be on different channels. Houses that are sufficiently far away may use the same wi-fi channel. Again we would like to solve the problem of finding the minimum number of channels needed, but this time we will solve it using techniques from logic and from probability. Rather than directly asking for the minimum number of channels required, we ask if it is possible to solve it with just 2 channels. So suppose each wi-fi network can either be on channel hi or on channel lo. Is it possible to assign channels to networks so that there is no interference? (a) Formulate this problem as a problem in propositional logic. Specifically: (i) Define your propositional variables (4 marks) (ii) Define any propositional formulas that are appropriate and indicate what propositions they represent. (4 marks) (iii) Indicate how you would solve the problem (or show that it cannot be done) using propositional logic. It is sufficient to explain the method, you do not need to provide a solution. (2 marks) (iv)* Explain how to modify your answer(s) to (i) and (ii) if the goal was to see if it is possible to solve with 3 channels rather than 2. (4 marks) (b) Suppose each house chooses, uniformly at random, one of the two network channels. What is the probability that there will be no interference? (4 marks)