Exercises for propositional logic i  (Page 5/5)

For each of the following, find a satisfying truth assignment, (values of the propositions which make the formula true),if any exists.

1. $a\implies \neg b\land a$
2. $a\implies c\implies \neg b\land a\lor b$

For each of the following, find a falsifying truth assignment, (values of the propositions which make the formula false),if any exists.

1. $a\implies \neg b\lor a$
2. $\neg b\implies a\implies c\lor (a\land b)$

Formula $\phi$ is stronger than formula $\psi$ if $\psi$ is true whenever $\phi$ is true ( i.e. , $\phi$ is at least a strong as $\psi$ ), but not conversely. Equivalently, this means that $\phi \implies \psi$ is always true, but $\psi \implies \phi$ is not always true.

As one important use of this concept, if we know that $\psi \implies \theta$ , and that $\phi$ is stronger than $\psi$ , then we also know that $\phi \implies \theta$ . 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, $\phi$ is weaker than formula $\psi$ whenever $\psi$ is stronger than $\phi$ .

Show which of the following hold. When true, show $\phi \implies \psi$ is true by a truth table, and show a falsifying truth assignment for $\psi \implies \phi$ . When false, give a truth table and truth assignment the other wayaround.

1. $a\land b$ is stronger than $a\lor b$ .

2. $a\lor b$ is stronger than $a$ .

3. $a$ is stronger than $a\implies b$ .

4. $b$ is stronger than $a\implies b$ .

Using truth tables, show that $a\lor c\land b\implies c\land c\implies a$ is equivalent to $b\implies c\land a$ . but not equivalent to $a\lor c\land b\implies c$ .

[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.

Consider the following conditional code, which returns a boolean value.

Simplify it by filling in the following blank with a single Boolean expression.Do not use a conditional (such as if or ?: ).

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

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.

1. ¬
2. ∧
3. ∨

Using algebraic identities , show that $a\lor c\land b\implies c\land c\implies a$ is equivalent to $b\implies c\land a$ .

This is an algebraic hand-evaluation: a series of formulas joined by $\equiv$ . 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 .

1. What is an advantage of using truth tables? What is an advantage of using identities?

2. In that truth table exercise , you also showed twoformulas $\phi$ and $\psi$ non -equivalent. It is also possible to do so with Boolean algebra ratherthan truth tables. How?

3. Describe a hybrid approach, combining truth tables and Boolean algebra, to prove the equivalence and non-equivalence of formulas.

4. To ponder on your own without turning it in: Which approach appeals more to you?

Using algebraic identities , rewrite the formula $a\implies b\lor c\land \neg b$ to one with fewer connectives.