| $F_1 := \neg(a \vee b)$ |
Truth table for $F_1$ |
$F_2 := a\wedge b \vee \neg a \wedge \neg b$ |
Truth table for $F_2$ |
|
|
|
|
|
| $F_3 := a \oplus b \Rightarrow a$ |
Truth table for $F_3$ |
$F_4 := a \oplus b \Rightarrow (a\vee c)$ |
Truth table for $F_4$ |
|
|
|
|
|
ACTIVITY PART I
- Write down the truth table for $(a \Rightarrow b)
\Rightarrow a$.
- Write down the truth table for $a \oplus \neg(b \oplus c)$.
-
Why would you refuse to write a truth table for
$(a \wedge e \oplus \neg b \wedge c) \Rightarrow (b \oplus d \Leftrightarrow e)$?
- Given $F_1$ from above, write down an interpretation
(assignment of values to variables) for which $F_1$
evaluates to true.
- Given $F_2$ from above, write down an interpretation
(assignment of values to variables) for which $F_2$
evaluates to false.
- How many different assignments of values to variables
are there for which $F_3$ evaluates to true?
- Given $F_4$ from above, write down an interpretation
(assignment of values to variables) for which $\neg F_4$
evaluates to true.
-
(This one is harder!)
Let $f$ be the function defined by $F_4$, and
let $g_1$ be the function defined by $x \wedge y$,
let $g_2$ be the function defined by $x \oplus y$, and
let $g_3$ be the function defined by $x \Rightarrow y$.
Find values for $x$ and $y$ for which the function
$f(g_1(x,y),g_2(x,y),g_3(x,y))$ returns false.
-
Consider the boolean function G1 given by the
following truth table:
Find a propositional formula that defines G1.
-
Consider the boolean function G2 given by the
following truth table:
Find a propositional formula that defines G2.
-
There is a useful boolean function called "ite", which
stands for "if-then-else". The way ite works is this:
the value of ite(x,y,z) is y when x is true, and z when x
is false. So, for example,
$\text{ite}(\text{true,false,true}) = \text{false}$ because
the first argument ("x") is true, so we return the second argument
("y"), which is false. On the other hand,
$\text{ite}(\text{false,false,true}) = \text{true}$ because
the first argument ("x") is false, so we return the third argument
("z"), which is true.
Your job: Write the truth table for the ite function.
ACTIVITY PART II
- Given a function $f$ with truth table
write down the formula the algorithm from the proof would
produce for $f$.
-
Give a more concise defining formula for function $f$ from
the previous problem.