When writing truth tables, please list rows in the order used in all examples: FF, FT, TF, TT. For three-input tables, use the above four lines preceded by F, then the above four lines preceded by T.
Exercise 2.5.15
In a truth table for two inputs, provide a column for each of the sixteen possible distinct functions. Give a small formula for each of these functions.
Exercise 2.5.16
Write the truth table for xnor, the negation of exclusive-or, What is a more common name for this Boolean function?
Exercise 2.5.17
How many years would it take to build a truth table for a formula with 1000 propositions? Assume it takes 1 nanosecond to evaluate each formula.
A formula with 1000 propositions clearly isn't something you would create by hand. However, such formulas easily arise when modeling the behavior of a program with a 1000-element data
structure.
Exercise 2.5.18
| Use truth tables to answer each of the following. Showing whether the connectives obey such properties via truth tables is one way of establishing which equivalences or inference rules we should use. | |
| 1. | Show whether ⇒ is commutative. |
| 2. | Show whether ⊕ is commutative. |
| 3. | Show whether ⊕ is associative. |
| 4. | Prove that ∧ distributes over ∨: φ ∧ (ψ ∨ θ) ≡ φ ∧ ψ ∨ φ ∧ θ |
|
Note: This version is left-distributivity. Right-distributivity follows from this plus the commutativity of ∧.
|
|
| 5. | Prove that ∧ distributes over ∨: φ ∧ (ψ ∨ θ) ≡ φ ∧ ψ ∨ φ ∧ θ |
| 6. | Show whether ∧ or ∨ distribute over ⇒. |
| 7. | Show whether ⇒ distributes over ∧ or ∨. |
| 8. | Show whether ∧ or ∨ distribute over ⊕. |
| 9. | Show whether ⊕ distributes over ∧ or ∨. |
Exercise 2.5.19
For each of the following, find a satisflying truth assignment, (values of the propositions which make the formula true), if any exists.
- (a ⇒¬b) ∧ a
- (a ⇒ c ⇒¬b) ∧ (a ∨ b)
Exercise 2.5.20
For each of the following, find a falsiflying truth assignment, (values of the propositions which make the formula false), if any exists.
- (a ⇒¬b) ∨ a
- (¬b ⇒ (a ⇒ c)) ∨ a ∧ b
Exercise 2.5.21
Formula φ is stronger than formula ψ if ψ is true whenever φ is true (i.e., φ is at least a strong as
ψ), but not conversely. Equivalently, this means that φ ⇒ ψ is always true, but ψ ⇒ φ is not always true.
As one important use of this concept, if we know that ψ ⇒ θ, and that φ is stronger than ψ, then we also know that φ ⇒ θ. That holds simply by
transitivity. Another important use, which is outside the scope of this module, is the idea of strengthening an inductive hypothesis.
Similarly, φ is weaker than formula ψ whenever ψ is stronger than φ.
Show which of the following hold. When true, show φ ⇒ ψ is true by a truth table, and show a falsi flying truth assignment for ψ ⇒ φ. When false, give a
truth table and truth assignment the other way around.
- a ∧ b is stronger than a ∨ b.
- a ∨ b is stronger than a.
- a is stronger than a ⇒ b.
- b is stronger than a ⇒ b.
Exercise 2.5.22
Using truth tables, show that (a ∨ c) ∧ (b ⇒ c) ∧ (c ⇒ a) is equivalent to (b ⇒ c) ∧ a. but not equivalent to (a ∨ c) ∧ (b ⇒ c).
Exercise 2.5.23
When writing a complicated conditional that involves multiple pieces of data, it is easy to incorrectly oversimplify. One strategy for avoid mistakes is to write such code in a two-step
process. First, write a conditional with a case for every possible combination, as in a truth table. Second, simplify the conditional.
Using this approach, we might obtain the following code after the first step. Simplify this code.
list merge_sorted_lists(list list1, list list2){if (is_empty(list1) && is_empty(list2))return empty_list;else if (is_empty(list1) && !is_empty(list2))return list2;else if (!is_empty(list1) && is_empty(list2))return list1;else if (!is_empty(list1) && !is_empty(list2)) {if (first_element(list1) < first_element(list2))return make_list(first_element(list1),merge_sorted_lists(rest_elements(list1),list2));else if (first_element(list1) >= first_element(list2))return make_list(first_element(list2),merge_sorted_lists(list1,rest_elements(list2)));}}
Exercise 2.5.24
Consider the following conditional code, which returns a boolean value.
int i; bool a,b; ... if (a && (i > 0))return b;else if (a && i <= 0)return false;else if (a || b)return a;elsereturn (i > 0);
Simplify it by flling in the following blank with a single Boolean expression. Do not use a conditional (such as if or ?:).
int i; bool a,b; ... return ;
Use either Java/C++ or Scheme syntax. In the former case, please fully parenthesize to make your formula unambiguous, rather than relying on Java's33 or C++'s34 many
levels of operator precedence.
- 瀏覽次數：3087
