University |
Singapore Institute of Management (SIM) |

Subject |
CM2010 Fundamentals of Computer Science |

^{nd}Jan 2024

# CM2010 Fundamentals of Computer Science, SIM, Singapore: Without using the truth table, prove if the following statements are tautologies or not

**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]

##### Hire a Professional Essay & Assignment Writer for completing your Academic Assessments

**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]

##### Buy Custom Answer of This Assessment & Raise Your Grades

Looking for **Homework Help in Singapore**? Our service offers the **best assignment helpers** for students at the Singapore Institute of Management (SIM). Specifically tailored for CM2010 Fundamentals of Computer Science, our experts can assist in proving whether statements are tautologies or not, bypassing the traditional use of truth tables. Let our professionals ease your academic loadโpay for expert guidance and excel in your courses.

Tags:-

- Business Accounting & Finance โ (VM) โ A3 Assignment, UOM, Singapore
- HRM3010S: Managing People At Work, Assignment, UCD, Singapore
- HFS351: Safety Management and Audit, End-of-Course Assessment, SUSS, Singapore
- HFSY217: Emergency Preparedness and Response Planning, TMA (Tutor-Marked Assignment), SUSS
- CMM315: TMA (Tutor-Marked Assignment) – Peacebuilding and Security, SUSS, Singapore
- Harley Davidson utilized different entry mode strategies in pursuit of internationalization: Sustainable, Assignment, UoN, Singapore
- Nursing Patients With Chronic Illness, Assignment 3, LTU, Singapore: Jason Bundhoo is a 42-year-old car driver from Triolet
- DSM: R for Data Science, Coursework 2, UOL, Singapore: In this coursework assignment you should return to this dataset and perform an appropriate investigation into building a statistical model
- DSM120: Financial Data Modelling, Coursework 1, UOL, Singapore
- Data Science Final Project, Coursework 1, UOL, Singapore: Your first formal coursework submission is your full project proposal, This sets out very clearly what your Data Science Project will be, and also how you will conduct the project

*UP TO*
**15 %**
DISCOUNT