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

## Propositions and connectives

1. What is a **proposition**? Give an example of a sentence that is a proposition
   and one that is not.
2. Write the truth tables of $\neg A$, $A \wedge B$, and $A \vee B$.
3. State the **precedence** of `NOT`, `AND`, and `OR`. How do parentheses change
   the reading of an expression? Fully parenthesise `NOT A AND B OR C`.

## Evaluation and truth tables

4. How many rows does the truth table of a formula with $n$ distinct variables
   have? Why?
5. Define a **tautology**, a **contradiction**, and a **contingency** in terms of
   a formula's truth table.
6. Two formulas are **logically equivalent** when their truth tables are
   identical. Are `NOT (A AND B)` and `(NOT A) OR (NOT B)` equivalent? Justify
   your answer. *(This is one of De Morgan's laws.)*

## Implementation

7. Why should you **not** use the host language's `eval` to solve Task 1? Name
   one risk and one limitation.
8. Outline how a **recursive-descent** parser encodes the precedence of `NOT`,
   `AND`, and `OR`. Which grammar rule handles the lowest-precedence operator?
9. Describe an algorithm that enumerates **all** $2^n$ assignments of $n$
   variables. How can counting in binary from $0$ to $2^n - 1$ help?
10. What is the time complexity of generating a full truth table for an
    expression of size $m$ with $n$ variables?

## Tasks by hand

11. Evaluate `(A AND B) OR (NOT C)` under $A = F,\ B = T,\ C = F$. Show each step.
12. Build the complete truth table of `A OR (NOT B)`.
13. Determine, by building its truth table, whether `(A AND B) OR (NOT A)` is a
    tautology, a contradiction, or a contingency.