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. 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:

(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:

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.

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):

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

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:

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:

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:

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.

Laboratory/Laboratory4/2method.md · 5.4 KB · updated 2026-07-31 21:14