离散作业

Logic 1

1. Let p, q, and r be the propositions:

p: You get an A on the final exam;

q: You do every exercise in this book;

r: You get an A in this class.

write these propositions using q,q and r and logical connectives.

a) you get an A in this class, but you don't do every exercise in this book.

b) you get an A on the final, you do every exercise in this book, and you get an A in this class.

c) To get an A in this class, it is necessary for you to get an A on the final.

d) You get an A on the final, but you don't do every exercise in this book; nevertheless, you get

an A in this class.

e) Getting an A on the final and doing every exercise in this book is sufficient for getting an A

in this class.

f) You will get an A in this class if and only if you either do every exercise in this book or you

get an A on the final.

2. Inhabitants of the island Smullyan are either Knights or Knaves. Knights always tell the truth

while knaves tell lies. You encounter two people, A and B. Determine, if possible, what A and

B are if they address you in the ways described. If you can not determine what these two

people are, can you draw any conclusions?

a) A says

b) A says

3. Five friends have access to a chat room. Is it possible to determine who is chatting if the

following information is known? Either Kevin or Heather, or both, are chatting. Either Randy or

Vijay, but not both, are chatting. If Abby is chatting, so is Randy. Vijay and Kevin are either

both chatting or neither is. If Heather is chatting, then so are Abby and Kevin. Explain your

reasoning.

4. Find a compound proposition involving the propositions p, q, and r that is true when exactly

two of p,q,and r are true and is false otherwise.

Logic2 & Number Theory 1

1.

Translate these statements into English, where R(x)is “x

is a rabbit” and H(x)is “x hops” and

the domain consists of all animals.

a)

?

x(R( x)

→

H(x))

b)

?

x(R(x)

∧

H(x))

c)

?

x(R(x)

→

H(x))

d)

?

x(R(x)

∧

H(x))

2.

Let P(x), Q(x), R(x), and S(x)be the statements “x

is a duck,” “x is one of my poultry,” “x is

an officer,”

and “x is willing to waltz,” respectively. Express each of these statements using

quantifiers; logical connectives; and P(x),Q(x),R(x), and S(x).

a) No ducks are willing to waltz.

b) No officers ever decline to waltz.

c) All my poultry are ducks.

d) My poultry are not officers.

e) Does (d) follow from (a), (b), and (c)? If not, is there

a correct conclusion?

3.

Let F(x, y)be the statement “x can fool y,” where the

domain consists of all people in the

world. Use quantifiers to express each of these statements.

a) Everybody can fool Fred.

b) Evelyn can fool everybody.

c) Everybody can fool somebody.

d) There is no one who can fool everybody.

e) Everyone can be fooled by somebody.

f) No one can fool both Fred and Jerry.

g) Nancy can fool exactly two people.

h) There is exactly one person whom everybody can fool.

i) No one can fool himself or herself.

j) There is someone who can fool exactly one person besides himself or herself.

4. Solve each of these congruences.

a)

34x

≡

77(mod 89)

b) 144x

≡

4(mod 233)

5. Use the construction in the proof of the Chinese remainder theorem to find all solutions to

the system of congruences

x

≡

2(mod 3),x

≡

1(mod 4), and x

≡

3(mod 5).

6. Find all solutions, if any, to the system of congruences x

≡

5(mod 6), x

≡

3(mod 10), and

x

≡

8(mod 15).

Number Theory 2

1. a)Use Fermat’s little theorem to compute 3

302

mod 5, 3

302

mod 7, and 3

302

mod 11.

b)Use your results from part (a) and the Chinese remainder theorem to find 3

302

mod 385.

(Note that 385=5·7·

11.)

2. Use Wilson's Theorem to prove

Fermat’s little theorem.

3. Show that we can easily factor n when we know that n is the product of two primes,p and q,

and we know the value of

(p?1)(q?1).

4.

Let n be a positive integer and let n?1=2

s

t, where s is a nonnegative integer and t is an odd

positive integer. We say

that n passes Miller’s test for the base b if either b

t

≡

1 (mod n) or

b

(2^j)

t

≡

?1 (mod n)

for some j with 0≤j≤s?1. It

can be shown (see [Ro10]) that a composite

integer n passes

Miller’s test for fewer than n/4 bases b with 1

composite positive

integer n that passes Miller’s test to the

base b is called a strong pseudoprime to the base b.

Show that if n is prime and b is a positive integer with (n doesn't divide b), then n passes

Miller’s test to the base b.

5. Encrypt the message ATTACK using the RSA system with n = 43 * 59 and e = 13, translating

each letter into integers and grouping together pairs of integers.

6. What is the original message encrypted using the RSA system with n = 53*61 and e = 17 if the

encrypted message is 3185 2038 2460 2550 ?