CM2010 Fundamentals of Computer Science: Midterm Coursework

1) Answer the following questions. Explain your reasoning:
a) Without using the truth table, prove if the following statements are tautologies or not. Show your reasoning. [4 marks]
i) 𝒑⋁(𝒑 ⟶ 𝒒)⋁¬𝒒
ii) ((P→q) ∧ ((q∧r)→s)) ∧ (r→(P→s))
b) Without using the truth table, show that the following statement is true: [2 marks]
¬(∃x[P(x)∧Q(x)])≡∀x[P(x)→¬Q(x)]
c) Negate the following statement: [2 marks]
∀𝒙: 𝑷(𝒙) ∧ [∃𝒙: (𝑸(𝒙) ∧ ¬𝐑(𝐱))]
d) For the following statement, write down a logically equivalent statement that contains no operators other than ¬ and ∨: [2 marks]
𝑷 ∧ (𝑸 → 𝑹)

2) Using the pigeonhole principle, prove that if we choose 14 different numbers from the following set {1, 2, 3, 4,…,20}, then definitely there are two numbers such as a and b (among our 14 selected numbers) which their difference is at least 7 (i.e. |a-b| ≥7) [3 marks]

3) Prove the following statement by induction. For all positive integers n, prove 𝟐𝟑𝒏 − 𝟏 is divisible by 7, State the mathematical induction and show your work clearly. [3 marks]

4) Students are required to create 6-character long passwords to access the library. The letters must be from lowercase letters or digits. Each password must contain at most two lowercase- letters and contains no repeated digits. The second letter must be always “1” and the last letter always must be a digit. How many valid passwords are there? You are required to show your work step-by-step. [4 marks]

Note: 1h032a is invalid because the second letter is not 1. 314g05 is valid because there is one lowercase letter, no digits are repeated, the second letter is 1 and the last letter is a digit.

5) Design a Finite State Automaton (FSA) that accepts binary numbers greater than 0, whose decimal equivalents are divisible by 5. For instance, the FSA should accept inputs like ‘1010’ (decimal equivalent: 10), and ‘101’ (decimal equivalent: 5), but it rejects inputs like ‘1101’ (decimal equivalent: 13) and ‘1001’ (decimal equivalent: 9). [4 marks]

6) Consider the following automaton:
a) Give an example of a string of length 6 containing 01 that is accepted by the following automaton. [2 marks]
b) Give an example of a string of length 5 that is rejected by the following automaton. [2 marks]
c) Describe the language of this automaton in terms of a Regular Expression. [3 marks]
d) Re-draw this FSA with at most 4 states. The new FSA should accept all strings that this FSA accepts. In addition, it should reject all strings that this FSA rejects. [2 marks]
e) Draw an FSA that accepts all binary strings that start with 0, the length of the string is even but the number of 1’s in the string is odd. For example, 0111, 01, and 000111 should be accepted while 111 and 0011 should not. [3 marks]