2. Methodical guidelines / Методичні вказівки

This section is self-contained: it collects all the theory needed for the theme — Boolean formulas, truth tables, the laws of Boolean algebra, and the two normal forms — together with the techniques used to solve the tasks in 3classroom.md. No outside material is required.

2.1 Boolean formulas

A Boolean (propositional) variable takes one of two values, $1$ (true) or $0$ (false). Formulas are built from variables, the constants $0$ and $1$ , and the connectives:

Connective	Symbol	Value
Negation (NOT)	$\neg A$ (also $\overline{A}$ )	$1$ iff $A=0$
Conjunction (AND)	$A \wedge B$ (also $AB$ )	$1$ iff both are $1$
Disjunction (OR)	$A \vee B$	$1$ iff at least one is $1$
Implication	$A \to B$	$0$ only when $A=1,\ B=0$ ; equals $\neg A \vee B$
Equivalence	$A \leftrightarrow B$	$1$ iff $A$ and $B$ are equal

Two shorthands used throughout: an overline $\overline{A}$ means $\neg A$ , and juxtaposition $AB$ means $A \wedge B$ .

Precedence. To drop parentheses, connectives bind in the order

\neg \;>\; \wedge \;>\; \vee \;>\; \to \;>\; \leftrightarrow.

So $x \vee \overline{y}\,z \to t$ reads $\big(x \vee (\overline{y} \wedge z)\big) \to t$ . When in doubt, parenthesise.

2.2 From a formula to a truth table

A formula in $n$ variables defines a Boolean function; its truth table lists the value on each of the $2^n$ interpretations (assignments of $0/1$ to the variables). To build it:

write the $2^n$ rows in the standard order — read the variable values as a binary number counting up from $0\ldots0$ to $1\ldots1$ ;
for each row, substitute the values and evaluate the formula inside-out, respecting precedence;
record the result in the last column.

For example, one row of $f(x,y,z,t)=x \vee \overline{y}(z \vee \overline{x}\, \overline{y}) \to t$ at $(x,y,z,t)=(0,0,0,0)$ evaluates as

0 \vee \overline{0}\,(0 \vee \overline{0}\,\overline{0}) \to 0 = 0 \vee 1(0 \vee 1) \to 0 = 0 \vee 1 \to 0 = 1 \to 0 = 0.

The number of the row (its binary value) doubles as the number of the interpretation.

2.3 The laws of Boolean algebra

These identities let you transform a formula without changing the function it computes. They come in dual pairs (swap $\wedge\leftrightarrow\vee$ and $0\leftrightarrow1$ ).

Law	For $\wedge$	For $\vee$
Double negation	(\overline{\overline{A}} = A)
Complement (excluded middle)	$A \wedge \overline{A} = 0$	$A \vee \overline{A} = 1$
Constants	$A \wedge 0 = 0,\quad A \wedge 1 = A$	$A \vee 0 = A,\quad A \vee 1 = 1$
Idempotence	$A \wedge A = A$	$A \vee A = A$
Absorption	$A \wedge (A \vee B) = A$	$A \vee (A \wedge B) = A$
Combining	$(A \vee B)(A \vee \overline{B}) = A$	$AB \vee A\overline{B} = A$
Commutativity	$A \wedge B = B \wedge A$	$A \vee B = B \vee A$
Associativity	$A(BC) = (AB)C$	$A \vee (B \vee C) = (A \vee B) \vee C$
Distributivity	$A(B \vee C) = AB \vee AC$	$A \vee BC = (A \vee B)(A \vee C)$
De Morgan	$\overline{A \wedge B} = \overline{A} \vee \overline{B}$	$\overline{A \vee B} = \overline{A} \wedge \overline{B}$

The two workhorses for normal forms are De Morgan (a bar over a group flips the operation and complements each part) and distributivity.

2.4 Literals, DNF and CNF

A literal is a variable or its negation: $x$ or $\overline{x}$ .
A term (elementary conjunction, “product”) is an AND of literals, e.g. $x\,\overline{y}\,z$ .
A clause (elementary disjunction, “sum”) is an OR of literals, e.g. $x \vee \overline{y} \vee z$ .

The two standard shapes are:

Disjunctive normal form (DNF) — an OR of terms (a sum of products), e.g. $(x\,\overline{y}) \vee (\overline{x}\,z)$ ;
Conjunctive normal form (CNF) — an AND of clauses (a product of sums), e.g. $(x \vee \overline{y})(\overline{x} \vee z)$ .

CNF is an AND of OR-clauses; DNF is an OR of AND-terms

Every formula has both forms. DNF makes satisfiability obvious (a term with no clashing literals is satisfiable); CNF is the input format expected by SAT solvers.

2.5 Reducing a formula to DNF or CNF

Follow the same first two steps, then distribute in the appropriate direction:

Eliminate $\to$ and $\leftrightarrow$ . Replace $A \to B$ by $\overline{A} \vee B$ , and $A \leftrightarrow B$ by $(\overline{A} \vee B)(\overline{B} \vee A)$ .
Push negations inward with De Morgan and double negation until every $\neg$ sits on a single variable (this is negation normal form).
Distribute:
- for DNF, distribute $\wedge$ over $\vee$ until the formula is an OR of AND-terms;
- for CNF, distribute $\vee$ over $\wedge$ until it is an AND of OR-clauses.
Simplify with idempotence, the complement laws ( $x \wedge \overline{x} = 0$ , $x \vee \overline{x} = 1$ ), absorption, and the constant laws. A term that contains both $x$ and $\overline{x}$ is $0$ (drop it from a DNF); a clause that contains both is $1$ (drop it from a CNF). If everything cancels, the formula is a constant: $0$ (a contradiction) or $1$ (a tautology).

Algebraic reduction: apply one law per step until the formula reaches its target shape

2.6 Working checklist

For a truth-table task, list all $2^n$ rows in binary order and evaluate inside-out; a final algebraic simplification of the formula is a good cross-check (the table and the simplified formula must agree).
For a normal-form task, always start by removing $\to$ and $\leftrightarrow$ , then apply De Morgan to reach negation normal form before distributing.
DNF distributes $\wedge$ over $\vee$ ; CNF distributes $\vee$ over $\wedge$ — keep straight which one the task asks for.
Cite one law per step, and finish by simplifying; watch for a term/clause collapsing to $0$ or $1$ .

Practical/Practical3/2method.md · 6.0 KB · updated 2026-08-01 18:44

2. Methodical guidelines / Методичні вказівки #

2.1 Boolean formulas #

2.2 From a formula to a truth table #

2.3 The laws of Boolean algebra #

2.4 Literals, DNF and CNF #

2.5 Reducing a formula to DNF or CNF #

2.6 Working checklist #