Home Page > > Details

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

(a) Are the strings abaabbab and aaababbaab equivalent? Prove your answer.

(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.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Ghostwriter Assign Q5debug R Programmi... 2024-06-19
- Ghostwriter Cs 231, Spring 2024 Assign... 2024-06-19
- Ghostwriter Mat 181 Programming For Sc... 2024-06-19
- Ghostwriter Ictten622 Produce Ict Netw... 2024-06-19
- Ghostwriter Cnit 17600 - Intro Compute... 2024-06-19
- Ghostwriter Eco3420 Financial Economic... 2024-06-19
- Ghostwriter Assessment 3: Projecthelp ... 2024-06-19
- Ghostwriter Ec 2 Principles Of Macroec... 2024-06-19
- Help With Cnit 17600 - Intro Computer ... 2024-06-19
- Help With Chemistry 30 Unit D Module 7... 2024-06-19
- Help With Avia 3410: Assignment 1Debug... 2024-06-19
- Ghostwriter Lineare Algebra Ii 2024Hel... 2024-06-19
- Ghostwriter Homework #1 - Mpcs 52072 -... 2024-06-19
- Ghostwriter Ma 134 Calculus I Spring 2... 2024-06-19
- Help With Fin3020s Introduction To Mac... 2024-06-19
- Help With 11175 Introduction To Econom... 2024-06-19
- Ghostwriter Fins5568 Capstone - Portfo... 2024-06-19
- Help With Mpcs 52072 - Gpu Programming... 2024-06-19
- Help With Chem 233 Assignment 4Help Wi... 2024-06-19
- Ghostwriter Efim20036: Limited Depende... 2024-06-19

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！