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