Homework Week 1

Problem 1

Which of these sentences are propositions? What are the truth values of those that are propositions?

1. Boston is the capital of Massachusetts.
   
2. Miami is the capital of Florida.
   
3. 2 + 3 = 5.
   
4. 5 + 7 = 10.
   
5. x + 2 = 11.
   
6. Answer this question.

Problem 5

What is the negation of each of these propositions?

1. Mei has an MP3 player.
   
2. There is no pollution in New Jersey.
   
3. 2 + 1 = 3.
   
4. The summer in Maine is hot and sunny.

Problem 11

Let \(p\) and \(q\) be the propositions:

\(p\): “Swimming at the New Jersey shore is allowed.”
\(q\): “Sharks have been spotted near the shore.”

Express each of these compound propositions as an English sentence.

1. \(\neg q\)
   
2. \(p \land q\)
   
3. \(\neg p \lor q\)
   
4. \(p \to \neg q\)
   
5. \(\neg q \to p\)
   
6. \(\neg p \to \neg q\)
   
7. \(p \leftrightarrow \neg q\)
   
8. \(\neg p \land (p \lor \neg q)\)

Problem 13

Let \(p\) and \(q\) be the propositions:

\(p\): It is below freezing.
\(q\): It is snowing.

Write these propositions using \(p\) and \(q\) and logical connectives, including negations.

1. It is below freezing and snowing.
   
2. It is below freezing but not snowing.
   
3. It is not below freezing and it is not snowing.
   
4. It is either snowing or below freezing (or both).
   
5. If it is below freezing, it is also snowing.
   
6. Either it is below freezing or it is snowing, but it is not snowing if it is below freezing.
   
7. That it is below freezing is necessary and sufficient for it to be snowing.

Problem 19

Determine whether each of these conditional statements is true or false.

1. If \(1 + 1 = 2\), then \(2 + 2 = 5\).
   
2. If \(1 + 1 = 3\), then \(2 + 2 = 4\).
   
3. If \(1 + 1 = 3\), then \(2 + 2 = 5\).
   
4. If monkeys can fly, then \(1 + 1 = 3\).

Problem 21

For each of these sentences, determine whether an inclusive or, or an exclusive or, is intended. Explain your answer.

1. Coffee or tea comes with dinner.
   
2. A password must have at least three digits or be at least eight characters long.
   
3. The prerequisite for the course is a course in number theory or a course in cryptography.
   
4. You can pay using U.S. dollars or euros.

Problem 31

How many rows appear in a truth table for each of these compound propositions?

1. \(p \to \neg p\)
   
2. \((p \lor \neg r) \land (q \lor \neg s)\)
   
3. \(q \lor p \lor \neg s \lor \neg r \lor \neg t \lor u\)
   
4. \((p \land r \land t) \leftrightarrow (q \land t)\)

Problem 33

Construct a truth table for each of these compound propositions.

1. \(p \land \neg p\)
   
2. \((p \lor \neg q) \to q\)
   
3. \((p \to q) \leftrightarrow (\neg q \to \neg p)\)
   
4. \((p \to q) \to (q \to p)\)

Problem 35

Construct a truth table for each of these compound propositions.

1. \((p \lor q) \to (p \oplus q)\)
   
2. \((p \oplus q) \to (p \land q)\)
   
3. \((p \lor q) \oplus (p \land q)\)
   
4. \((p \oplus q) \to (p \oplus \neg q)\)

Problem 37

Construct a truth table for each of these compound propositions.

1. \(p \to \neg q\)
   
2. \(\neg p \leftrightarrow q\)
   
3. \((p \to q) \lor (\neg p \to q)\)
   
4. \((p \leftrightarrow q) \lor (\neg p \leftrightarrow q)\)
   
5. \((\neg p \leftrightarrow \neg q) \leftrightarrow (p \leftrightarrow q)\)

Problem 39

Construct a truth table for each of these compound propositions.

1. \(p \to (\neg q \lor r)\)
   
2. \(\neg p \to (q \to r)\)
   
3. \((p \to q) \lor (\neg p \to r)\)
   
4. \((p \to q) \land (\neg p \to r)\)
   
5. \((p \leftrightarrow q) \lor (\neg q \leftrightarrow r)\)
   
6. \((\neg p \leftrightarrow \neg q) \leftrightarrow (q \leftrightarrow r)\)

Problem 47

Find the bitwise OR, bitwise AND, and bitwise XOR of each of these pairs of bit strings.

1. 101 1110, 010 0001
   
2. 1111 0000, 1010 1010
   
3. 00 0111 0001, 10 0100 1000
   
4. 11 1111 1111, 00 0000 0000

Problem 1

Translate the given statement into propositional logic using the propositions provided.

“You cannot edit a protected Wikipedia entry unless you are an administrator.”

Use:

\(e\): You can edit a protected Wikipedia entry.
\(a\): You are an administrator.

Problem 5

Translate the given statement into propositional logic using the propositions provided.

“You are eligible to be President of the U.S.A. only if you are at least 35 years old, were born in the U.S.A., or at the time of your birth both of your parents were citizens, and you have lived at least 14 years in the country.”

Use:

\(e\): You are eligible to be President of the U.S.A.
\(a\): You are at least 35 years old.
\(b\): You were born in the U.S.A.
\(p\): At the time of your birth, both of your parents were citizens.
\(r\): You have lived at least 14 years in the U.S.A.

Problem 45

Find the output of each combinatorial circuit.

1. Circuit shown in the book/image.
   
2. Circuit shown in the book/image.

Problem 47

Construct a combinatorial circuit using inverters, OR gates, and AND gates that produces the output:

\[ ((\neg p \lor \neg r) \land \neg q) \lor (\neg p \land (q \lor r)). \]