Computational Thinking 2021/22
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Computational Thinking 2021/22
Logic Coursework Resit
You should submit a single ZIP file containing (i) one PDF document containing your answers to all the theoretical/mathematical questions, and (ii) a single Python file for the programming tasks (which are in Questions 1 and 10 to 13 only). Please name the Python file according to your username (e.g. mpll19.py).
The principal programming part of the coursework will be to implement a greedy graph colouring algorithm in Python. Note that you will be restricted in some of your choices for data structures and function names. The data structure for (undirected) graph will be a list of lists of length two. The 3-clique (triangle) graph would then be [[1, 2], [2, 3], [3, 1]]. In an undirected graph, the edge [1, 2] implies the edge [2, 1] also.
1. Write a program in Python that checks whether the following first-order sentences are true on some model. The models will be binary relations given as a list of lists of lengths two.
(i.) AxR(x, x) [1 marks].
(ii.) AxAy(R(x, y) ∧ R(y, x)) → x = y [2 marks].
(iii.) AxAyAz(R(x, y) ∧ R(y, z)) → R(x, z) [2 marks].
(iv.) Ax3yR(y, x) [2 marks].
You may assume that all elements of the domain appear in some tuple of the relation. In gen- eral, the tuple [1, 2] being in a relation does not imply that [2, 1] is also in the relation (this is in contrast to the case of undirected graphs).
Evaluate these sentences on the binary relations R1 to R4 that appear in Relations .txt [2 marks each]. [15 marks]
2. Which of the following sentences from predicate logic are logically valid (true in all interpreta- tions)?
(i.) (Ax3yR(x, y)) → (Ax3yR(x, y)) [1 mark].
(ii.) (Ax3yR(x, y)) → (3xAyR(x, y)) [2 marks].
(iii.) (3xAyR(x, y)) → (Ax3yR(x, y)) [2 marks].
(iv.) (3xAyR(x, y)) → (3xAyR(x, y)) [1 mark].
[6 marks]
3. Is the following set of clauses satisfiable? Justify your argument with either a satisfying assign- ment or a Resolution refutation?
(x1 ) ( ¬x2 )
( ¬x1 ∨ x3 ) (x2 ∨ ¬x4 )
( ¬x3 ∨ x5 ) (x4 ∨ ¬x6 )
( ¬x5 ∨ x7 ) (x6 ∨ ¬x7 )
[9 marks]
4. Solve the following logic puzzles, justifying your answers. [10 marks]
(i.) There are two types of people on an island, the truth-tellers and the liars. On this island you are approached by two people. The first one says to you, “we are both liars. ” What are each of these people in reality?
(ii.) A girl meets a cow and sheep in the forest. The cow lies every Tuesday, Wednesday and
Thursday and the other days he speaks the truth. The sheep lies on Fridays, Saturdays and Sundays, and the other days of the week he speaks the truth. “Yesterday I was lying,” the cow told the girl. “So was I,” said the sheep. What day is it?
(iii.) There are three people (Adam, Boris and Camilla), one of whom is a knight, one a knave, and one a spy. The knight always tells the truth, the knave always lies, and the spy can either lie or tell the truth. Adam says: “Camilla is a knave. ” Boris says: “Adam is a knight. ” Camilla says: “I am the spy. ” Who is the knight, who the knave, and who the spy?
5. Convert (u ∧ (v ∨ (w ∧ (x ∨ (y ∧ z))))) to Conjunctive Normal Form (CNF). [6 marks]
6. What is the purpose of Tseitin’s Algorithm? Apply Tseitin’s Algorithm to the propositional formula (u ∧ (v ∨ (w ∧ (x ∨ (y ∧ z))))). [10 marks]
7. Answer the following questions about complete sets of logical connectives, in each case justify- ing your answer. Recall the binary Boolean connective XOR, as in A XOR B, which returns true when precisely one of A and B is true. Recall the binary connective NAND, as in A NAND B, which may be defined as ¬ (A ∧ B). [10 marks]
(i). Show {¬, ∨, ∧} is a complete set of connectives. (ii). Is {¬, → } a complete set of connectives?
(iii). Is {XOR} a complete set of connectives?
(iv). Is {NAND} a complete set of connectives?
8. Write some Python code that loads a text file into an internal representation of a graph (for which we will use a list of lists of size two). The graphs will be encoded in the text file in the following way. The vertices will be numbers. Each line will be a new edge. In each line, a space separates the two vertices. [6 marks]
9. Write a Python function greedy colouring 1 in a single argument graph that establishes a greedy colouring of the input graph which colours the vertices in ascending numerical order, one by one, choosing a minimal feasible colour from the set of colours {1, . . .} each time. The code should return the colouring together with the number of colours it used. [9 marks]
10. Write a Python function greedy colouring 2 in a single argument graph that establishes a greedy colouring of the input graph which colours the vertices by choosing at each stage a maximal set of vertices that may be assigned each to the chosen colour. Build this set each time by choosing minimally numbered available vertices. [9 marks]
11. Run your code on the five graphs in the files GraphR1 .txt to GraphR5 .txt in each case recording the number of colours used by each of the two algorithms implemented by the code greedy colouring 1 and greedy colouring 2. [10 marks]
2022-07-15