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

This section is **self-contained**: it collects all the theory of the work's
theme — propositional logic, the evaluation of logical expressions, and truth
tables — together with practical guidance for the tasks in [4task.md](4task.md).
No outside material is required.

## 2.1 Propositions and logical connectives

A **proposition** is a declarative statement that is either **true** ($T$) or
**false** ($F$) — never both. Propositional **variables** ($A, B, C, \dots$)
stand for propositions whose value is not yet fixed. This work uses three
connectives, written in expressions as the keywords `NOT`, `AND`, `OR`:

| Keyword | Symbol | Name | Meaning |
|:--:|:--:|---|---|
| `NOT` | $\neg$ | negation | true exactly when its operand is false |
| `AND` | $\wedge$ | conjunction | true exactly when **both** operands are true |
| `OR` | $\vee$ | disjunction | true when **at least one** operand is true |

![Logic-gate symbols for the three connectives NOT, AND, and OR](img/gates.png)

(The connectives implication $\to$ and equivalence $\leftrightarrow$ exist too,
but are not needed here; the design below extends to them naturally.)

## 2.2 Truth tables of the connectives

A **truth table** lists the value of an expression for every combination of its
inputs. For the three connectives:

| $A$ | $B$ | $\neg A$ | $A \wedge B$ | $A \vee B$ |
|:--:|:--:|:--:|:--:|:--:|
| T | T | F | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | F |

These four rules are all that is needed to give a value to any compound formula.

## 2.3 Compound expressions: precedence and parentheses

When operators are not fully parenthesised, they bind by **precedence**, from
highest to lowest:

$$\neg \ \text{(NOT)} \ \succ\ \wedge \ \text{(AND)} \ \succ\ \vee \ \text{(OR)}.$$

So `NOT A AND B` means `(NOT A) AND B`, and `A AND B OR C` means
`(A AND B) OR C`. **Parentheses override** precedence and should be respected
exactly. Getting this order right is the whole difficulty of parsing.

## 2.4 Evaluating an expression under an assignment

An **assignment** maps each variable to $T$ or $F$. To evaluate a formula, give
each variable its value and apply the connectives bottom-up, innermost
parentheses first. For example, evaluate `(A AND B) OR (NOT C)` under
$A = T,\ B = F,\ C = T$:

$$
(A \wedge B) \vee (\neg C)
= (T \wedge F) \vee (\neg T)
= F \vee F
= F .
$$

So the result is **false** — this is Task 1 of [4task.md](4task.md).

## 2.5 Truth tables of compound expressions

A formula with $n$ distinct variables has $2^n$ possible assignments, so its
truth table has $2^n$ rows. Build it by listing every assignment and evaluating
the formula on each. For instance, `A OR (NOT B)`:

| $A$ | $B$ | $\neg B$ | $A \vee (\neg B)$ |
|:--:|:--:|:--:|:--:|
| T | T | F | T |
| T | F | T | T |
| F | T | F | F |
| F | F | T | T |

The order of the rows is a convention (here: variables left-to-right, `true`
before `false`); keep it consistent.

![A compound truth table over three variables, with all eight rows evaluated](img/tt_compound.png)

## 2.6 Implementation notes and algorithms

**Do not use the language's `eval`.** Tokenise the string, then parse it with a
grammar that encodes the precedence of §2.3. A **recursive-descent** parser is
the most direct approach; the following grammar produces the correct binding:

```text
expr   := term   { OR term }        # OR   — lowest precedence
term   := factor { AND factor }     # AND  — middle
factor := NOT factor                # NOT  — highest
        | ( expr )
        | VARIABLE
```

Evaluating directly while parsing, given the current `assignment`:

```text
function evaluate(expression, assignment):
    tokens ← tokenise(expression)   # VARIABLE, AND, OR, NOT, '(', ')'
    return parseExpr()              # parseExpr consumes from tokens

    function parseExpr():
        v ← parseTerm()
        while next token is OR:
            consume(OR);  v ← v OR parseTerm()
        return v

    function parseTerm():
        v ← parseFactor()
        while next token is AND:
            consume(AND);  v ← v AND parseFactor()
        return v

    function parseFactor():
        if next token is NOT:  consume(NOT);  return NOT parseFactor()
        if next token is '(':  consume('(');  v ← parseExpr();  consume(')');  return v
        name ← consume(VARIABLE);  return assignment[name]
```

Generating the truth table reuses `evaluate` on every assignment:

```text
function truthTable(expression):
    vars ← distinct variable names in expression, in a fixed order
    n    ← length(vars)
    rows ← empty list
    for i from 0 to 2^n - 1:                 # i enumerates all assignments
        assignment ← empty map
        for k from 0 to n - 1:
            bit ← (i >> (n - 1 - k)) AND 1   # k-th variable = k-th bit of i
            assignment[vars[k]] ← (bit == 0) # bit 0 → true, so the first row is all-true
        append (assignment, evaluate(expression, assignment)) to rows
    return vars, rows
```

## 2.7 Complexity

Let $m$ be the size of the expression (number of tokens) and $n$ the number of
distinct variables. One **evaluation** costs $O(m)$. A full **truth table** calls
`evaluate` once per assignment, so it costs $O(2^n \cdot m)$: the number of rows
grows **exponentially** in the number of variables — eight rows for three
variables, but over a thousand for ten.