# 6. Control questions and tasks / Контрольні запитання і завдання

## Boolean functions and truth tables

1. In what ways can a **Boolean function** be specified (formula, truth table,
   …)? What are the trade-offs?
2. How many interpretations, and how many rows, does the truth table of an
   $n$-variable function have? How do you order the rows in the **standard** way?
3. How is the **number of an interpretation** read from a row? Build the truth
   table of $g(x,y) = \overline{x} \vee y$ and state which two-variable connective
   it is.
4. Describe, step by step, how to go **from a formula to its truth table**
   (as in Task 1). Why is it enough to evaluate the formula "inside-out"?

## Connectives, precedence, and the laws

5. State the value of $A \to B$ as a formula in $\neg,\vee$. When is $A \to B$
   false?
6. State the **precedence** of $\neg,\wedge,\vee,\to,\leftrightarrow$. Fully
   parenthesise $x \vee \overline{y}\,z \to t$.
7. State both **De Morgan** laws and the **distributive** laws. Which pair does
   the heavy lifting when reducing to a normal form?
8. Which two formulas are called **equivalent**? Give two ways to check
   equivalence (truth tables; a chain of laws).

## Normal forms (DNF and CNF)

9. Define a **literal**, a **term** (elementary conjunction), and a **clause**
   (elementary disjunction).
10. Define **DNF** and **CNF**. Which is a *sum of products* and which a *product
    of sums*? Which does a SAT solver take as input?
11. Give the **three-step recipe** for reducing a formula to DNF or CNF, and say
    which distributive direction each form uses.
12. In a reduction, what does a **term** containing both $x$ and $\overline{x}$
    equal, and what does a **clause** containing both equal? How does each affect a
    DNF vs. a CNF?

## Tasks by hand

13. Reduce $x \to (y \to x)$ to CNF. What special formula is it?
14. Reduce $(x \wedge y) \vee (\overline{x} \wedge z)$ — already a DNF — to **CNF**
    by distributing $\vee$ over $\wedge$.
15. Show, by simplifying with the laws, that
    $\overline{(x \to y)} \wedge (x \to y)$ is a **contradiction** ($\equiv 0$).