-
Suppose we have six speakers to schedule
(Alice, Bob, Cathy, Don, Eve, Fred), and
two sessions (1 and 2) to put them in.
Note: not scheduling someone (i.e. not putting them in either
session) is a possibility!
Assume your variables are a1,a2,b1,b2,...,f1,f2, where a1
means "alice in session 1", a2 means "alice in session 2", and
so on.
-
Write a formula for the constraint: Nobody can be scheduled for both sessions
-
Write a formula for the constraint: Alice and Bob cannot be in the same session
-
Write a formula for the constraint: either Cathy or Don,
but not both, are in session 1.
-
Write a formula for the constraint: Eve cannot be
scheduled for a later session than Fred.
-
Why can't we just have variable "a" to mean "Alice in
session 1", and then say that if "a" is false that means
that Alice is in session 2?
-
Is (a⊕b⊕c)⇒(¬a⇒(c∨b)) a tautology? How did you check?
-
Is the formula below a tautology? How did you check?
(a∧p⇒(b∧l⊕c∧m))∧(e∧n∨b∧l∨f∧o)⇒(d∧a⊕g∧c∧m⊕f∧o∧h⇒(¬i∨¬j∨¬k∨b∧l∨g∨a))
-
One of the answers in the "car options" problem from the
previous homework was the formula ¬sp∧¬tp⇒¬t. Simplify this a
step at a time
by applying the tautologies given at each step.
F = ¬sp∧¬tp⇒¬t
= __________________________ apply tautology (a⇒b)⇔(¬b⇒¬a) [note: called the "contrapositive" rule]
= __________________________ apply tatuology ¬¬a⇔a [note: "double negation"]
= __________________________ apply tautology ¬(a∧b)⇔(¬a∨¬b) [note: one of de morgan's laws]
= __________________________ apply tatuology ¬¬a⇔a twice! [note: "double negation" ... again!]
-
Use the propositional logic tool and verify that
(a∨¬a∧b)⇔(a∨b) is a tautology. I'm not kidding, do it!
Using that tautology, show how to simplify the code below:
if (y == 0 || y != 0 && x/y < 0.33) {
cout << "pass" << endl;
}
else {
cout << "fail" << endl;
}
-
Note: This problem is not directly about
in-class content. But if you've been learning not how to
read and understand mathematics (which is actually a big part
of what you should get from this course), you should be able to do this
pretty easily.
In computer architecture, it is common to adopt a different
syntax for propositional formulas than what we've been
seeing. Let's call these "comp-arch formulas".
Here is a definition:
- propositional variables are comp-arch formulas
(equivalent to variables in regular propositional formulas)
-
if $A$ is a comp-arch formula, $\overline{A}$ is a
comp-arch formula (equivalent to $\neg(A)$)
-
if $A$ and $B$ are comp-arch formulas, then
$(A)(B)$ is a comp-arch formula (equivalent to $(A)\wedge(B)$)
-
if $A$ and $B$ are comp-arch formulas, then
$(A)+(B)$ is a comp-arch formula (equivalent to $(A)\vee(B)$)
-
nothing else is a comp-arch formula
For these formula we also adopt the rule that "and" has higher
precedence than "or" so that we can drop many of the
parentheses. So, for instance:
- comp-arch formula $a+\overline{b}c$ is equivalent
to propositional formula $a \vee \neg b \wedge c$,
and
- comp-arch formula $a+\overline{bc + \overline{d}}$ is equivalent to
propositional formula
$a \vee \neg(b\wedge c \vee \neg d)$.
-
Write the propositional formula equivalent to: $abc+a\overline{b}c$
-
Write the propositional formula equivalent to:
$a\overline{(b + cd)}$
-
Write the propositional formula equivalent to:
$\overline{xy + \overline{z}}+xz$
-
Consider the truth table for function $F$ below. Following
the algorithm from the Class 4 theorem, write down a
definition formula for $F$, but write it down using the
comp-arch formula notation.
