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

Boolean functions and truth tables

In what ways can a Boolean function be specified (formula, truth table, …)? What are the trade-offs?
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?
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.
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”?

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

Define a literal, a term (elementary conjunction), and a clause (elementary disjunction).
Define DNF and CNF. Which is a sum of products and which a product of sums? Which does a SAT solver take as input?
Give the three-step recipe for reducing a formula to DNF or CNF, and say which distributive direction each form uses.
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?

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

Practical/Practical3/6questions.md · 2.1 KB · updated 2026-07-31 21:14