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.

Laboratory/Laboratory4/6questions.md · 1.7 KB · updated 2026-07-31 21:14