Scribd
Upload
170 views3 pages

Symbolic Logic Homework Solutions

This document contains the homework assignment for Lisa Guo's CSE 215 class. It includes 8 problems involving writing logical propositions, equivalences, quantifiers, and predicates in symbolic logic. Students are asked to write conditionals and biconditionals using symbols, prove logical equivalences using truth tables, define predicates, and apply DeMorgan's laws to push negations through quantifiers. The homework is due on February 23, 2015.

Uploaded by

LisaGuo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Topics covered

  • logical constructs,
  • symbolic representation,
  • foundational concepts,
  • mathematical proofs,
  • logical implications,
  • symbolic notation,
  • truth value,
  • DeMorgan's laws,
  • quantifier negation,
  • computer science fundamentals
170 views3 pages

Symbolic Logic Homework Solutions

This document contains the homework assignment for Lisa Guo's CSE 215 class. It includes 8 problems involving writing logical propositions, equivalences, quantifiers, and predicates in symbolic logic. Students are asked to write conditionals and biconditionals using symbols, prove logical equivalences using truth tables, define predicates, and apply DeMorgan's laws to push negations through quantifiers. The homework is due on February 23, 2015.

Uploaded by

LisaGuo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Topics covered

  • logical constructs,
  • symbolic representation,
  • foundational concepts,
  • mathematical proofs,
  • logical implications,
  • symbolic notation,
  • truth value,
  • DeMorgan's laws,
  • quantifier negation,
  • computer science fundamentals

Lisa Guo

CSE 215 Foundations of Computer Science - Spring 2015


Homework 2
Due Monday, February 23 2015

Problem 1
Write the following propositions using symbolic logic:
If it is sunny, then I do not have my umbrella.
p = It is sunny
q = I have an umbrella
p q
Alice goes to CSE 215 only if Bob goes to CSE 215.
p = Alice goes to CSE 215
q = Bob goes to CSE 215
p q
Problem 2
Write P Q using , . Show that these are equivalent.
P Q
To prove that these are equivalent, we can look at the truth tables. For P Q, the truth table
looks like this:
P Q P Q
T
T
F
F

T
F
T
F

T
F
T
T

For P Q, the truth table looks like this:


P Q P Q
F
T
T
F
F
F
T
T
T
T
F
T
We can see that the resulting values are equivalent.
Problem 3
Show that the following are equivalent:

inverse ( P Q)
converse (Q P )
Once again, we can use truth tables to prove that these two statements are equal.

The truth statement for P Q is:

P Q

F
F
T
T

F
T
F
T

T
T
F
T

QP

T T
The truth statement for Q P is: F T
T F
F F
And from these we can say that they are equal

T
T
F
F
because the values of the result are the same.

Problem 4
Write the biconditional (if and only if, equivalence) using only implies. Show that the new version
is equivalent.
The bi conditional can be written as such: P Q = (P Q) (Q P )
in that the biconditional is implies both ways. With this we can make a truth table:
P Q P Q Q P (P Q) (Q P ) P Q
T T
T
T
T
T F
F
T
F
T
F
F
F T
F F
T
T
T
From this truth table, we can see that the statement is
Problem 5
Prove that the propositional formulas
P Q R and
(P Q) (Q R) (R P ) (P Q R)
are equivalent.
Problem 6
Define the following predicates:
N (x): x is a non-negative integer
E(x): x is even
O(x): x is odd
P (x): x is prime
Write the following using symbolic logic.

T
F
F
T
true.

There exists an even integer.


xE(x)
Every integer is even or odd.
x (E(x) O(x))
All prime integers are non-negative.
xP (x) N (x)
The only even prime is 2.
x(E(x) P (x)) 2
Not all integers are odd.
x E(x)
Not all primes are odd.
xP (x) E(x)
If an integer is not odd, then it is even.
x O(x) E(x)

Problem 7
Write the negations of each of the statements in the previous problem and translate them into
symbolic logic.
Problem 8
Use DeMorgans laws to push negation through multiple quantifiers:
xyzP (x, y, z)
xy(P (x) P (y))

You might also like