CS 3800 Homework 1 Solutions - All Answers are Correct
15 views 0 purchase
Module
CS 3800
Institution
CS 3800
Homework 1
(due Friday, January 17)
Instructions: This homework is to be submitted on GradeScope as a single pdf (not in parts) by
11:59 pm on the due date. You may either type your solutions in a word processor and print to
a pdf, or write them by hand and submit a scanned copy. Do write and s...
january 17 instructions this homework is to be submitted on gradescope as a single pdf not in parts by 1159 pm on the due date you may eithe
Written for
CS 3800
All documents for this subject (4)
Seller
Follow
ExamsConnoisseur
Reviews received
Content preview
CS 3800 Spring 2020
W. Schnyder 1/10/2020
Homework 1
(due Friday, January 17)
Instructions: This homework is to be submitted on GradeScope as a single pdf (not in parts) by
11:59 pm on the due date. You may either type your solutions in a word processor and print to
a pdf, or write them by hand and submit a scanned copy. Do write and submit your answers as
if they were a professional report. There will be point deductions if the submission isn’t neat (is
disordered, difficult to read, scanned upside down, etc. . . .).
Begin by reviewing your class notes, the slides, and the textbook. Then do the exercises below.
Show your work. An unjustified answer may receive little or no credit.
Late Penalty The late penalty is waived for this first homework, in fact extending its deadline to
Sunday, January 19 at 11:59pm. However, you should do your best to finish by Friday as Homework
2’s deadline will not be extended.
Graphs and Digraphs: Problems 17 and 18 are about graphs and digraphs and all the material
you need is in chapter 0.2. We will also go over that material on Tuesday.
Read: Complete Chapter 0, then read Section 1.1
1. [4 Points]
(a) For which values of the variables p, q, r is the expression ¬p ∨ q ∨ ¬r false?
Solution: p = r = T and q = F
(b) For which values of the variables p, q, r, s is the expression ¬p ∧ q ∧ ¬r ∧ ¬s true?
Solution: p = r = s = F and q = T
2. [8 Points] Which of the following conditional statements are true and why?
(a) If February has 30 days, then 7 is an odd number.
Solution: Statement is true as it has the form F→T
(b) If January has 31 days, then 7 is an even number.
Solution: Statement is false as it has the form T→F
(c) If 7 is an odd number, then February does not have 30 days.
Solution: Statement is true as it has the form T→T
(d) If 7 is an even number, then January has exactly 28 days.
Solution: Statement is true as it has the form F→F
3. [8 Points] In this problem, the domain is the integers. Write the negation of each of the
following statements, simplifying to the point that no ‘¬’ symbol occurs in any of the
statements (you may, however, use binary symbols such as ‘6=’ and ‘<’). For each of the
statements, indicate whether the original statement is true.
Page 1 of 11
, CS 3800 Hwk 1 Spring 2020
(a) ∀x (x · 2 6= x · 3)
Solution: negation: ∃x (x · 2 = x · 3) is verified by x = 0. So original is false.
(b) ∃x (x + 2 = x + 3)
Solution: negation: ∀x ( x + 2 6= x + 3) is true. So the original is false.
(c) ∀x (x2 6= x)
Solution: negation: ∃x (x2 = x) is true (examples 0, 1). So original is false.
(d) ∃x (5 ≤ x < 6)
Solution: The original statement is equivalent to ∃x (5 ≤ x ∧ x < 6). Its negation
is ¬ ∃x(5 ≤ x ∧ x < 6) ≡ ∀x¬ (5 ≤ x ∧ x < 6) ≡ ∀x (5 > x ∨ x ≥ 6) which is false
(example 5). Original was true.
4. [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 predicates
Charlie() and CS(), formulate the statements:
(a) Charlie doesn’t know every CS student.
Solution:
One could say ¬ ∀x(CS(x) → Charlie(x)) or, equivalently, ∃x(CS(x) ∧ ¬ Charlie(x))
(b) The only students known to Charlie are CS students.
Solution: ∀x (Charlie(x) → CS(x))
(c) Charlie knows at least two students. Here you may also use symbols “=” and “6=”,
in addition to those listed above.
Solution: ∃x ∃y(x 6= y ∧ Charlie(x) ∧ Charlie(y))
5. [8 Points] For this problem, the domain is the set of all students at Northeastern. Consider
the following two predicates
CS(x) meaning “x is a CS student”
Knows(x, y) meaning “x knows y”
Using only variables, logic symbols (selected from ¬, ∨, ∧, →, ↔, ∃, ∀), and the predicates
CS and Knows, formulate the statements:
(a) Some student knows every student
Solution: ∃x, ∀y, Knows(x, y)
(b) Some student knows every CS student
Solution: ∃x∀y CS(y) → Knows(x, y)
Page 2 of 11
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller ExamsConnoisseur. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £6.15. You're not tied to anything after your purchase.
