Suppose a school has three periods (called 1, 2, and 3) during which a class can
ID: 3807361 • Letter: S
Question
Suppose a school has three periods (called 1, 2, and 3) during which a class can be scheduled. For each class, there are three variables. For example, for class A, there are variables x_A1, x_A2, and x_A3. Setting x_A2 = 1 represents scheduling class A during period 2. Give a Boolean expression that evaluates to 1 if and only if A is scheduled in at least one of the three periods. Give a Boolean expression that evaluates to 1 if and only if A is not scheduled in more than one period. Give a Boolean expression that evaluates to 1 if and only if A and B are not scheduled in the same period. The final Boolean expression representing the entire scheduling problem will be a product of many terms. If there are n classes and m pairs of classes that cannot be scheduled at the same time, then how many terms will be in the entire Boolean expression?Explanation / Answer
a. Give a Boolean expression that evaluates to 1 if and only if A is scheduled in atleast
one of the three periods.
XA1 || XA2 || XA3 This expression evaluates to true if atleast one variable is true,
which means A is scheduled in atleast one of the three periods.
b. Give a Boolean expression that evaluates to 1 if and only if A is not scheduled in more
than one period.
(XA1 && !XA2 && !XA3) || (!XA1 && XA2 && !XA3) || (!XA1 && !XA2 && XA3) || (!XA1 && !XA2 && !XA3)
c. Give a Boolean expression that evaluates to 1 if and only if A and B are not scheduled
in the same period.
!(XA1 && XB1) && !(XA2 && XB2) && !(XA3 && XB3)
d. The final Boolean expression representing the entire schedule problem will be product
of many terms. If there are n classes and m pairs of classes that cannot be
scheduled at the same time, then how many terms will be in the entire Boolean expression?
There will be 2 * m terms.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.