SUNY Geneseo Department of Mathematics
Monday, February 15
Math 239 03
Spring 2021
Prof. Doug Baldwin
Turning in the first problem set: This problem set (but only this one) can be handwritten or typed. Future ones will need to be typed. For all problem sets, you don’t need to turn anything in ahead of time, just be ready to screenshare your solution during our meeting. Although if screensharing doesn’t work for you, you can email the solution to me ahead of time.
Based on section 2.1 of the textbook and the compound statements discussion.
Write a logical expression for the base-2 sum of 2 digits, x and y, ignoring any carry. Let X be the statement “x is 1” and Y be the statement “y is 1.”
Basic addition rules:
So the statement “The sum is 1” must have a truth value given by… (¬X ∧ Y) ∨ (X ∧ ¬Y), i.e., the sum is 1 when x is 0 and y is 1, or x is 1 and y is 0.
Write a logic expression for the base-2 carry from adding digits x and y. Define X and Y as above.
The statement “the carry is 1” has a truth value given by… X ∧ Y
Write logic expressions for the difference and any borrow needed to subtract 2 base-2 digits x and y. Define X and Y as above.
The basic subtraction rules for x - y are
So the statement “the difference is 1” has a truth value given by… (X ∧ ¬Y) ∨ ( ¬X ∧ Y) (Interestingly, this is the same expression that said when the sum was 1 in an addition problem. Base-2 addition and subtraction are symmetrical in this sense.)
The statement “you need to borrow” is has truth value… ¬X ∧ Y
Define the “exclusive” or (true if exactly one of P or Q is true and false otherwise) via a truth table.
This has a good solution in the Canvas discussion.
Give a truth table for (P ∧ ¬Q) → ¬ R.
We started by realizing that we needed 8 rows for combinations of values of P, Q, and R. This comes from 2 possible values for P, each of which needs to be matched with 2 possible values of Q, for a total of 4 combinations, and each of them needs to be matched with each of 2 possible values for R.
We also want columns for each variable and the result, and typically one or more columns for intermediate results.
Having set up the basic structure of the table, we filled in the combinations of truth values, and evaluated the intermediate expression and final one for each:
| P | Q | R | (P ∧ ¬Q) | (P ∧ ¬Q) → ¬ R |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | T | T | F |
| T | T | F | F | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | F | T |
| F | T | F | F | T |
| F | F | F | F | T |
Give truth tables for ¬(P ∧ Q) and (¬P ∨ ¬Q).
There is a nice truth table for ¬(P ∧ Q) in the Canvas discussion. We built the following one for (¬P ∨ ¬Q):
| P | Q | (¬P ∨ ¬Q) |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
Did you notice anything about these last truth tables?
The one we made and the one in Canvas are the same! This is an example of “equivalent” statements, i.e., two superficially different statements that have the same truth table. Equivalent statements can generally be substituted for each other when working with logic, so understanding equivalence is crucial to being able to use logic in proofs or other problems. Thus the next topic is…
Equivalence of (compound) statements, i.e., situations under which two statements have the same truth tables.
Please read section 2.2 in the textbook.
Please also contribute to this discussion of logical equivalence.