# 讲解 CS 3800 Homework 1 Spring 2024辅导 数据结构程序

CS 3800

Homework 1

Spring 2024

1. [6 Points] For the Tseitin word problem discussed in class, are the words in the following pairs equivalent? Prove your answers (either by showing a sequence of substitutions or by proving that none exists).

(a) c a d b c e d b and c a c c a e b d

(b) b c c d b c and c b b d c c

(c) a e c d a b and c a d e

2. [7 Points] Consider the following word problem, similar to Tseitin’s but with only

❼ the two letters in {a, b}

❼ the single substitution a = aa

(b) Is there an algorithm to decide this word problem, that is, an algorithm that on input any two strings always correctly outputs whether they are equivalent or not? Prove your answer by describing such an algorithm or showing that none exists.

3. [8 Points] Tseitin used the 5 symbols a, b, c, d, e and 7 substitutions to construct a word problem undecidable by algorithms. Show that the number of symbols can be reduced from 5 symbols to 2 symbols (such as 0 and 1) while preserving undecidability.

4. [8 Points] Which of the following conditional statements are true and why? (For each statement, determine its form. among T → T , T → F , F → T , F → F).

(a) If February has 30 days, then 7 is an odd number.

(b) If January has 31 days, then 7 is an even number.

(c) If 7 is an odd number, then February does not have 30 days.

(d) If 7 is an even number, then January has exactly 28 days.

5. [4 Points] Let x be a positive real number. Use a proof by contrapositive to show that if x is irrational (i.e., not a rational number), then √ x is also irrational.

(a) Write the contrapositive of the statement “if x is irrational, then √ x is irrational”.

(b) Prove this contrapositive.

6. [4 Points] Write a full CNF with variables p, q, r that has the truth table

7. [6 Points] In this problem, the domain is the set Z of integers and we consider the state-ment ϕ :

∀x∃y∀z(y ≠ xz + 1)

(a) Use De Morgan’s laws to write the negation ¬ ϕ, simplifying to the point that no ‘¬’ symbol occurs anywhere in your statement (you may, however, use binary relation symbols such as ‘=’, ‘≠’, ‘<’, and ‘>’).

(b) Which of the two statements ϕ and ¬ ϕ is true? Carefully explain your answer.

8. [7 Points] For this problem, the domain is the set of Northeastern students. Consider the following two predicates

Charlie(x) meaning “ Charlie knows x ”

CS(x) meaning “ x is a CS student ”

Using only variables, logic symbols (selected from ¬, ∨, ∧, →,↔, ∃, ∀, =, =), and the pred-icates Charlie and CS, formulate the statements:

(a) Charlie doesn’t know every CS student.

(b) The only students known to Charlie are CS students.

(c) Charlie knows at least two students.