Get 2 days of premium access
Study Guides (380,000)
US (220,000)
Berkeley (5,000)
COMPSCI (500)
Quiz

COMPSCI 70 Study Guide - Quiz Guide: Alistair Sinclair, Propositional Calculus, Natural NumberExam


Department
Computer Science
Course Code
COMPSCI 70
Professor
Rao Satish
Study Guide
Quiz

This preview shows pages 1-2. to view the full 7 pages of the document.
CS 70 Discrete Mathematics and Probability Theory
Fall 2018 Alistair Sinclair and Yun Song HW 1
1 Always True or Always False?
Classify the following statements as being one of the following, where xand yare arbitrary propo-
sitions, and justify your answers (e.g., using a truth table)
True for all combinations of xand y(Tautology)
False for all combinations of xand y(Contradiction)
• Neither
(a) x(x=y)(¬y)
(b) x=(xy)
(c) (xy)(x∨ ¬y)
(d) (x=y)(x=⇒ ¬y)
(e) (xy)(¬(xy))
(f) (x=y)(¬x=y)(¬y)
Solution:
(a) Contradiction
x y x =y x (x=y)(¬y)
T T T F
T F F F
F T T F
F F T F
(b) Tautology
x y x y x =(xy)
T T T T
T F T T
F T T T
F F F T
CS 70, Fall 2018, HW 1 1

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

(c) Tautology
x y x y x ∨ ¬y(xy)(x∨ ¬y)
T T T T T
T F T T T
F T T F T
F F F T T
(d) Tautology
x y x =y x =⇒ ¬y(x=y)(x=⇒ ¬y)
T T T F T
T F F T T
F T T T T
F F T T T
(e) Neither
x y x y¬(xy) (xy)(¬(xy))
T T T F F
T F T T T
F T T T T
F F F T F
(f) Contradiction
x y x =y¬x=y¬y(x=y)(¬x=y)(¬y)
T T T T F F
T F F T T F
F T T T F F
F F T F T F
2 Miscellaneous Logic
(a) Let the statement, (xR)(yR)G(x,y), be true for predicate G(x,y).
For each of the following statements, decide if the statement is certainly true, certainly false,
or possibly true, and justify your solution. (If possibly true, provide a specific example where
the statement is false and a specific example where the statement is true.)
(i) G(3,4)
(ii) (xR)G(x,3)
(iii) y G(3,y)
(iv) y¬G(3,y)
(v) x G(x,4)
(b) Give an expression using terms involving ,and ¬which is true if and only if exactly one
of X,Y, and Zis true.
CS 70, Fall 2018, HW 1 2
You're Reading a Preview

Unlock to view full version