$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 which 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 lowercaseletters 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:$1$h$032$a is invalid because the second letter is not $1.314$g$05$ is valid because there is

one lower$-$case 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 $\text{'}1010\text{'}$

$($decimal equivalent: $10),$ and $\text{'}101\text{'}($decimal equivalent: $5),$ but it rejects inputs like $\text{'}1101\text{'}$

$($decimal equivalent: $13)$ and $\text{'}1001\text{'}($decimal equivalent: $9).[4$ marks$]$