Info

Truth-function representations

We looked at how to read off a Boolean expression from a truth-table. Apply the method to the following:

Inspect the resulting Boolean expressions. Can you simplify them while remaining in DNF?

Circuit representations

We’ve observed that our relay circuits are essentially build up from relay implementations of NOT (default “on”) and AND (default “off”). Use the idea to represent the following circuits as Boolean expressions:

Are the resulting formulas in normal form (CNF or DNF)?

Equivalence

The XNOR function is special: it expresses that X and Y have the same value—just check the table!

1. Find the simplest representation of XNOR in terms of NOT and XOR.

   Hint: Inspect XNOR and XOR’s function tables, how are they related?

2. Use this implementation to reduce the verification problem for a relay circuit from two SAT problems for different sets (as in the text) to a single SAT problem for a single expression.

   Hint: Think about when X XNOR Y is true and when X XOR Y is true.

Truth tables

Use the truth-table method to check whether the following claims are true:

1. The set of expressions ((NOT X) OR (NOT Y)) and (X AND Y) is SAT.

2. The set formulas { RAIN, (RAIN ( WIND RAIN) } is SAT.

Mystery formula

Determine the following “mystery formula” form its truth-table:

What’s the shortest representation of the formula you can find?

Normal Forms

Transform the following formulas into DNF and CNF:

1. (RAIN (SUN RAIN))
2. ( RAIN ( RAIN WIND))
3. (RAIN SUN) ( RAIN SUN)

Resolution

Use the resolution method to determine whether the following formulas are satisfiable:

1. (SUN RAIN WIND) (SUN RAIN WIND)
2. (SUN RAIN) (WIND WIND)
3. (SUN RAIN) (SUN RAIN) ( SUN RAIN) ( SUN RAIN)
4. (SUN (SUN RAIN)) (RAIN (RAIN SUN))

Valid inference

Determine whether the following inferences are valid using both the truth-table and the resolution method. Which one is faster?

1. RAIN RAIN ( RAIN SUN)

2. RAIN (RAIN WIND) RAIN SUN