| << Chapter < Page | Chapter >> Page > |
For each of the following, find a satisfying truth assignment, (values of the propositions which make the formula true),if any exists.
For each of the following, find a falsifying truth assignment, (values of the propositions which make the formula false),if any exists.
Formula
is
stronger than
formula
if
is true
whenever
is 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 falsifying truth assignment for . When false, give a truth table and truth assignment the other wayaround.
is stronger than .
is stronger than .
is stronger than .
is stronger than .
Using truth tables, show that is equivalent to . but not equivalent to .
[Practice problem solution provided.]
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)));
}} list merge_sorted_lists(list list1, list list2)
{if (is_empty(list1))
return list2;else if (is_empty(list2))
return list1;else {
if (first_element(list1)<first_element(list2))
return make_list(first_element(list1),merge_sorted_lists(rest_elements(list1),list2));
elsereturn make_list(first_element(list2),merge_sorted_lists(list1,rest_elements(list2)));
}}
Alternatively, we could test the emptiness of the lists in the other order.
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;else
return (i>0);
Simplify it by filling 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 yourformula unambiguous, rather than relying on Java's or C++'s many levels of operator precedence.
[Practice problem solution provided.]
Using algebraic identities , and the definition or nor (mnemonic:
not or), written , , express the function ∧ in terms of only. That is, give a formula which doesn't use ∧, ∨, ¬, butinstead only uses and which has the same truth table as .
First we show that we can write negation in terms of , or more specifically, . Checking this on a truth table is pretty easy(there are only two rows to check). But for this question we need to use algebraic manipulation.This can be derived in a couple of simple steps:
| 1 | ||
| 2 | Idempotency of ∧ | |
| 3 | DeMorgan's law | |
| 4 | Definition of nor |
We use this lemma to show our ultimate goal:
| 1 | ||
| 2 | Double Complementation | |
| 3 | DeMorgan's law | |
| 4 | Lemma, with | |
| 5 | Lemma, with | |
| 6 | Definition of nor, where , and |
Note that we judiciously used new meta-variables and rather than re-using and (which would still be correct, but would make the graders need to pay much closer attention to the scope of those variables).
Similar to the previous exercise, express each of the following using nand only, and prove correctness using the algebraic identities .
This operation is particularly interesting, since making a NAND gate in hardware requires only two transistors.
Using algebraic identities , show that is equivalent to .
This is an algebraic hand-evaluation: a series of formulas joined by . Don't write just portions of previous formulasand mysteriously re-introduce the dropped parts later. For each step, mention which identity you used.It is also helpful if you underline the formula you are rewriting in the next step.You can use commutativity and associativity without using a separate line, but mention when you use it.
In two exercises, you've shown the same equivalence by truth tables and by algebraic identities .
What is an advantage of using truth tables? What is an advantage of using identities?
In that truth table exercise , you also showed twoformulas and non -equivalent. It is also possible to do so with Boolean algebra ratherthan truth tables. How?
Describe a hybrid approach, combining truth tables and Boolean algebra, to prove the equivalence and non-equivalence of formulas.
To ponder on your own without turning it in: Which approach appeals more to you?
Using algebraic identities , rewrite the formula to one with fewer connectives.
Notification Switch
Would you like to follow the 'Intro to logic' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|