(a) Let p, q, r be propositional variables such that the value assigned to p is T, the value assigned to q is F, and the

[answerhappygod]

A Let P Q R Be Propositional Variables Such That The Value Assigned To P Is T The Value Assigned To Q Is F And The 1 (69.9 KiB) Viewed 40 times

(a) Let p, q, r be propositional variables such that the value assigned to p is T, the value assigned to q is F, and the value assigned to r is T. Give the truth-values of the following sentences: (i) p +9 [1] (ii) (p 4-9) Vp [1] (iii) (r + (pq)) ^ (r 9) [1] (iv) (QA-r) Hop [1] (b) For the following questions, consider the sentence (p+q) Ap+r). (i) Write down a truth-table for the above sentence. [4] (ii) Give a Boolean circuit that will function in the same way as the above sentence. [4] (iii) Is the following a valid inference? (p+q) A (pr) E(q Ar) Explain your answer. [4] n (c) Consider the following two functions fi(n) and fe(n): fi(n) = 8n2 + 12n +5, f2(n) = n? From the formal definition of Big-O notation f(n) = (g(n)), show g that fi(n) = (f(n)). [4] (d) Answer each of the following two parts true or false: (i) n3 + 800n" = O(n") [1] (ii) 2n +6nº = O(n) [1] (iii) 60n² + 4n3 +5n+0 = O(nº) [1] (e) Let B be NP-complete and let C be in NP. What would we need to prove about C in order to be able to prove that C is NP-complete? [2]