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.
Exercise 2.5.18
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)));}}
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 flling33 or C++'s34 many levels of operator precedence.
- 1148 reads