Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CPSC 121

Winter 2, 2022

HW 3

Due: 19:00, Wednesday March 22, 2023

Instructions:

1. Do not change the problem statements we are giving you. Simply add your solutions by editing this latex document. To make it easier for the TAs to find your solutions, please use the soln environment we provided as follows:

\begin{soln}

My  solution  is here .

\end{soln}

Your solution will then appear in blue, and be easier to differentiate from the questions.

2. If you need more space, add a page between the existing pages using the \newpage com- mand.

3. Export the completed assignment as a PDF file for upload to gradescope.

4. On GradeScope, upload only one copy per partnership. You must identify you group via GradeScope; not doing so may result in losing some marks.

5. You must also tell us, via GradeScope, where each of the problem parts appears on your submission. You MUST align the regions for every problem, even if your assignment solution isn’t complete.  We will not be able to mark any problem we can’t find.  After uploading the .pdf you will see a screen, where you can click each question on the left, and click the corresponding page(s) on which the question appears.  Because of this matching process, please allocate at least 5 minutes prior to the deadline for submission. You must match your answers with each question; not doing so may result in losing some marks.

Academic Conduct: I certify that my assignment follows the academic conduct rules for of CPSC 121 as outlined on the course website. As part of those rules, when collaborating with anyone outside my group, (1) I and my collaborators took no record but names away, and (2) after a suitable break, my group created the assignment I am submitting without help from anyone other than the course staff.

1. (8 points) Given the following definitions:

• K : the domain of all people who love kung fu competitions

• M : the domain of all martial artists.

• S(x): x is stressed.

• T(x,y): person x has talked to martial artist y .

In each of the two cases below, determine whether or not the two predicate logic state- ments given are logically equivalent.  If the two propositions are logically equivalent, explain why. If they are not logically equivalent, then give an example where their truth values differ, and explain why they differ.

(a) (4 points)

Ax ∈ K,3y ∈ M,T(x,y) → S(x)

Ax ∈ K,(3y ∈ M,T(x,y)) → S(x)

(b) (4 points)

Ax ∈ K,Ay ∈ M,T(x,y) → S(x)

Ax ∈ K,(3y ∈ M,T(x,y)) → S(x)

2. (12 points) An integer x is called prime if the only two positive integers that evenly divide it are 1 and x.

An integer x is called perfect if it is equal to the sum of its positive divisors, excluding itself.

An integer x is even if it is divisible by 2.

Using these definitions, rewrite each of the following theorems using quantifiers and predicates.  You do not need to prove these theorems; you only need to express them using predicate logic. Note that the theorems are not precisely stated.

You are allowed to use only the predicates | (divides – see Section 4.4 of your textbook), Prime(x) that is True if x is a prime, and False otherwise, Perfect(x) that is True if x is perfect, and False otherwise, and Even(x) that is True if x is even, and False otherwise. No other predicates can be used.

(a) (4 points) Fermat’s Little Theorem : Whenever p is prime and a is an integer, the value ap − a is divisible by p.

(b) (4 points)  (A portion  of) Fermat’s Polygonal Number  Theorem :  Every positive integer can be expressed as the sum of four or fewer perfect squares.

(c) (4 points) Euclid-Euler Theorem: An even number is perfect if and only if it has the form 2p 1 (2p − 1) where 2p − 1 is a prime number.

3. (12 points) Bierce Prosnan and Caniel Draig are both spies who have decided to use Twitter to exchange messages. In order to ensure that the messages are legitimate, and have not been written by their arch-enemy Melon Usk, they have devised a number of ways to recognize legitimate messages. For each of the following schemes, write a regular expression that will match a message if and only if it is legitimate:

(a) (4 points) The message must not contain the substring gun.

(b) (4 points) The message must contain both an integer between 90 and 147, and an integer between 358 and 734. Note: \b may be helpful.

(c) (4 points) The message must contain the letter N (upper-case), and moreover every occurrence of the letter a must be preceded by an occurrence of nt (if there are multiple a’s, nt must occur in-between every pair of a’s). For instance, the strings

N sent me a different message.

• Don’t forget to intentionally tell N I wrote this.

• Windows NT (or nt) wanted to be benter than Windows 2000.

but not the strings

• N sends me a different message in June.

N writes: Keep the interesting ciment mixer a russian spy lost.

• Windows nt wanted to be benter than Windows 2000.

4. (6 points) Design a DFA that accepts only strings over the alphabet [A − Z] containing the following features:

• The first A’that occurs must have a ’R’somewhere (but no necessarily immedi- ately) after it

• Either contains a double ’P’(i.e.  “PP”) with no other occurrences of ’P’, or does not contain any occurrence of ’P’at all

Examples of accepted strings:

• WATTREL

• HIPPOWDON

CERULEDGE

Examples of rejected strings:

• RALTS (there is no R anywhere after the first A)

• GARCHOMP (contains an isolated P)

5. (12 points) Use a direct proof technique to prove the following theorems:

(a) (4 points) For any octal (base-8) string with at least two digits representing un- signed integers, if the last two digits are 00 or 40, then the number is divisible by

32.

(b) (4 points) For any three consecutive odd integers a, b, and c, a3  + b3  + c3  − 3 is

divisible by 6.

(c) (4 points) The sets A, B , and C are arbitrary subsets of some universal set  . Prove that (A ∩ B) − C = (A − C) ∩ (B − C).

6. (9 points) Prove the following theorems using contraposition:

(a) (4 points) The sets A, B , and C are arbitrary subsets of some universal set  . Prove that if A − (B ∪ C) contains fewer elements than A − C , then B is not a subset of C .

(b) (5 points) If x and m are both positive integer, and x2    mod m = 5, then m  7.

7. (7 points) Consider the following Turing Machine over the alphabet Σ = {0, 1,  0 ,  1 }.

 

A valid input to this Turing Machine will contain a sequences of 0’s and 1’s, followed by a single empty square, followed by another sequence of 0’s and 1’s with the same number of bits. The symbols  0  and  1  will not appear in the input or in the output, but are used internally by the computation.  Assume that the head initially points at the leftmost bit visible on the tape.

(a) (2 points) What will be the contents of the tape once the Turing Machine termi- nates, assuming it initially contains the following?

.

. .

1

0

0

1

0

0

1

1

.

. .

(b) (2 points) What will be the contents of the tape once the Turing Machine termi- nates, assuming it initially contains the following?

.

. .

1

1

0

1

0

1

1

1

.

. .

(c) (3 points) Describe briefly what this Turing machine does.