Logic for Computer Science - Exercise Sheet 4

Vocabulary flashcards covering key definitions, mathematical operators, notation, and concepts from Logic for Computer Science Exercise Sheet 4.

HMS Logcos

The space research vessel exploring the jungle planetoid COA107 in the Loboro system at the rim of the Lestashyr nebula.

Planetoid COA107

A jungle planetoid located in the Loboro system at the rim of the Lestashyr nebula whose ecosystem is dominated by space hamsters.

Space Hamster

A species of furry rodents dominating planetoid COA107 that closely resembles Earth's hamster and can possess properties such as fluffy fur, beady eyes, tentacles, or lethality.

Lethality of Space Hamsters

A deadly property exhibited by certain space hamsters on COA107, caused by a cruel combination of a vicious, venomous bite and an appalling appetite for human hands.

$$\beta \succeq \alpha$$

A relation between partial functions $\alpha, \beta$ from $PVAR$ to $\{0, 1\}$ with $\text{Dom}(\alpha) = \text{Dom}(\beta)$, defined such that $\beta(X) \ge \alpha(X)$ for all $X \in PVAR$, meaning that if $\alpha(X) = 1$, then $\beta(X) = 1$.

Monotonic Formula (in $PL$)

A formula $\varphi \in PL$ such that for all assignments $\alpha$ and $\beta$ for $\varphi$ with $\beta \succeq \alpha$, if $\llbracket\varphi\rrbracket_\alpha = 1$, then $\llbracket\varphi\rrbracket_\beta = 1$.

$$PL^+$$

The set of formulas defined recursively by base rules (B1) $0 \in PL^+$, (B2) $1 \in PL^+$, (B3) $V_i \in PL^+$ for all $V_i \in PVAR$, and recursive rules (R1) $(\varphi_1 \land \varphi_2) \in PL^+$ and (R2) $(\varphi_1 \lor \varphi_2) \in PL^+$ for all $\varphi_1, \varphi_2 \in PL^+$.

$$\mathcal{O}^+$$

The operator set defined as $\{\land, \lor, 0, 1\}$, which is shown to be not functionally complete because every formula in $PL^+$ is monotonic.

nor (Junctor)

The binary junctor (short for not or) defined for all $\varphi, \psi \in PL$ through $(\varphi \lor \psi) \equiv \neg(\varphi \lor \psi)$.

ite (Junctor)

The ternary junctor (short for if-then-else) defined for all $\varphi, \psi, \chi \in PL$ through $\text{ite}(\varphi, \psi, \chi) \equiv (\varphi \rightarrow \psi) \land (\neg\varphi \rightarrow \chi)$.

$$\mathcal{O}_1$$

The operator set consisting of the single binary junctor nor, which is functionally complete.

$$\mathcal{O}_2$$

The operator set defined as $\{0, 1, \text{ite}\}$, which is functionally complete.

Satisfiable Formula

A propositional formula $\varphi_i$ for which there exists an assignment $\alpha_i$ such that $\llbracket\varphi_i\rrbracket_{\alpha_i} = 1$.

Tautology

A propositional formula that evaluates to true under every assignment, meaning there exists no assignment $\beta_i$ such that $\llbracket\varphi_i\rrbracket_{\beta_i} = 0$.

$\varphi_1$ (Exercise 4.2)

The propositional formula defined as $(0 \lor \neg A) \rightarrow \neg A$.

$\varphi_2$ (Exercise 4.2)

The propositional formula defined as $((A \rightarrow B) \lor (B \rightarrow A)) \rightarrow (\neg C \rightarrow C)$.