Appendix A

Notation

Johannes Korbmacher about 9 min read

To type symbols in the apps, go to the LaTeX cheat sheet .

Use this table to look up a symbol or read an expression. Related entries sit together: sets and strings first, then formulas, models and proofs, and finally uncertainty and learning. Linked terms open the glossary .

$A$ , $B$ , and $C$ stand for formulas; $Γ$ (capital gamma) stands for a set of assumptions.

Notation	Reading and meaning
$x \in S$ , $x \notin S$	$x$ is, or is not, a member of the set (glossary, opens in a new tab) $S$ .
$S \subseteq T$	$S$ is a subset of $T$ : every member of $S$ belongs to $T$ . Equality is allowed.
$\emptyset$	The empty set: a set with no members.
$S \cap T$	The intersection: members common to $S$ and $T$ .
$S \cup T$	The union: members of $S$ or $T$ , including those in both.
$Σ$ , $Σ*$	An alphabet (glossary, opens in a new tab) and the set of all finite strings over it, including the empty string. See formal language (glossary, opens in a new tab) .
$p₁$ , $p₂$ , …	Propositional variables (glossary, opens in a new tab) ; the subscripts distinguish them.
$\negA$	Not $A$ (negation (glossary, opens in a new tab) ).
$A \land B$	$A$ and $B$ (conjunction (glossary, opens in a new tab) ).
$A \lor B$	$A$ or $B$ , including both (disjunction (glossary, opens in a new tab) ).
$A \to B$	If $A$ , then $B$ (conditional (glossary, opens in a new tab) ).
$A \leftrightarrow B$	$A$ if and only if $B$ (equivalence (glossary, opens in a new tab) ).
$⊥$ , $⊤$	Falsity and truth constants; in classical logic, always false and always true, respectively. See contradiction (glossary, opens in a new tab) and tautology (glossary, opens in a new tab) .
$\forallx A(x)$	For every object $x$ in the domain, $A(x)$ (universal quantifier (glossary, opens in a new tab) ).
$\existsx A(x)$	For some object $x$ in the domain, $A(x)$ (existential quantifier (glossary, opens in a new tab) ).
$a = b$	The terms $a$ and $b$ denote the same object (identity (glossary, opens in a new tab) ).
$A[x/t]$	Substitute $t$ for the free occurrences of $x$ in $A$ , avoiding variable capture (substitution (glossary, opens in a new tab) ).
$Aσ$	Apply the substitution $σ$ to $A$ , as in unification (glossary, opens in a new tab) .
$D$	The domain (glossary, opens in a new tab) of a first-order model: its nonempty set of objects.
$v(A)$	The truth-value of $A$ under the valuation (glossary, opens in a new tab) $v$ .
$⟦a⟧$ , $⟦R⟧$ , $⟦A⟧$	The interpretation of a name, predicate, or formula; see semantic brackets below.
$M ⊨ A$	$A$ is true in model $M$ ; checking this is model checking (glossary, opens in a new tab) .
$M, s ⊨ A$	$A$ is true in $M$ under assignment $s$ , which supplies values for free variables (glossary, opens in a new tab) .
$Γ ⊨ A$	Every model of all formulas in $Γ$ makes $A$ true (entailment (glossary, opens in a new tab) ).
$Γ ⊭ A$	Some model of all formulas in $Γ$ does not make $A$ true: a countermodel (glossary, opens in a new tab) .
$Γ ⊢ A$	There is a proof of $A$ from $Γ$ in the specified calculus (derivability (glossary, opens in a new tab) ).
$Γ ⊬ A$	There is no proof (glossary, opens in a new tab) of $A$ from $Γ$ in the specified calculus.
$P₁, \dots, Pₙ ∴ C$	Premises $P₁, \dots, Pₙ$ ; therefore $C$ . Presents an inference (glossary, opens in a new tab) without asserting its validity.
$0$ , $1$ , $ω$ in K3	False, true, and unknown. Only $1$ is a designated value (glossary, opens in a new tab) .
$μCold(T)$	The degree to which temperature $T$ is cold (fuzzy predicate (glossary, opens in a new tab) ).
$Ω$ , $ω \in Ω$	A sample space and an outcome belonging to it (probability (glossary, opens in a new tab) ).
$p(ω)$	The probability mass assigned to outcome $ω$ .
$Pr(A)$	The probability of $A$ .
$Pr(A \| B)$	The conditional probability (glossary, opens in a new tab) of $A$ given $B$ : $Pr(A \land B) / Pr(B)$ , provided $Pr(B) > 0$ .
$P₁, \dots, Pₙ C$	Inductive validity (glossary, opens in a new tab) : the premises jointly weakly raise the probability of $C$ under every distribution where their conjunction has positive probability.
$Cn(K)$	All logical consequences of the set $K$ (deductive closure (glossary, opens in a new tab) ).
$KB + A$	Expand the knowledge base $KB$ by $A$ : $Cn(KB \cup {A})$ (expansion (glossary, opens in a new tab) ).
$KB * A$	Revise $KB$ in light of $A$ (belief revision (glossary, opens in a new tab) ).

Reading the notation

Formulas, truth, and proofs. $\to$ is a connective inside a formula. $⊨$ and $⊢$ belong to our language about formulas: they express semantic and proof-theoretic claims, respectively. The expression to the left of $⊨$ matters: $M ⊨ A$ concerns one model, while $Γ ⊨ A$ concerns every model of the assumptions. The symbol $∴$ presents an inference for consideration; it does not certify validity.

Semantic brackets. Their meaning depends on what they enclose and the chapter’s definition. In first-order logic, $⟦a⟧$ is an object’s denotation (glossary, opens in a new tab) , $⟦f⟧$ is a function, and $⟦R⟧$ is a predicate’s extension. For formulas, $⟦A⟧$ can be a truth-value or a set of satisfying valuations. In the first-order database discussion, $⟦A(x)⟧$ is the set of objects satisfying an open formula; in fuzzy logic, $⟦A⟧$ is a numerical degree. Check the surrounding definition to see which is intended.

Uncertainty. The outcome symbol $ω$ is unrelated to the unknown truth-value $ω$ in K3. A fuzzy degree of $0.5$ is not automatically a probability of $0.5$ : one measures degree of membership, the other probability. For the book’s inductive-inference symbol, “weakly raise” means $Pr(C | E) \geq Pr(C)$ , where $E = P₁ \land \dots \land Pₙ$ . The requirement is imposed for every distribution with $Pr(E) > 0$ ; it does not require a strict increase.

LaTeX cheat sheet

Typing in the apps

In the book’s formula inputs, type a backslash \ followed by a command: \neg turns into $\neg$ as you type. You can also paste a whole expression. Don’t include dollar signs ($). Ordinary letters and round brackets can be typed directly; leave a space after a command before the next letter.

To enter	Type	Meaning
$\neg$	`\neg`	Not
$\land$	`\land`	And
$\lor$	`\lor`	Or
$\to$	`\to`	If … then
$\leftrightarrow$	`\leftrightarrow`	If and only if
$p₁$	`p_1`	Variable with a subscript
$p₁₂$	`p_{12}`	Use braces for a longer subscript

The commands are case-sensitive. Alternatives are \lnot for $\neg$ , \wedge for $\land$ , \vee for $\lor$ , and \rightarrow for $\to$ . You can also copy the symbols themselves into an input.

Complete examples for the parsing app

Copy an entry from the left column into the parsing app :

Type or paste	Result
`\neg p_1`	$\negp₁$
`(p_1 \land p_2)`	$(p₁ \land p₂)$
`\neg(p_1 \lor p_2)`	$\neg(p₁ \lor p₂)$
`((p_1 \land p_2) \to \neg p_3)`	$((p₁ \land p₂) \to \negp₃)$
`(p_1 \leftrightarrow p_2)`	$(p₁ \leftrightarrow p₂)$

The parser accepts $p₁$ , $p₂$ , … and the shorthand $p$ , $q$ , $r$ . In its fully bracketed mode, every two-place connective needs its own pair of brackets: use (p \land q), not p \land q. Negation needs no extra pair: \neg p is fine. In the formula builder, the input takes a single variable, such as p_1; the operator controls combine formulas for you.

More symbols

These commands also convert in the apps’ formula inputs. A converted symbol still has to belong to the language of the app: the propositional parser, for example, accepts neither quantifiers nor set symbols.

To enter	Type	Meaning
$⊥$ , $⊤$	`\bot`, `\top`	Falsity, truth
$\forall$ , $\exists$	`\forall`, `\exists`	For every, for some
$\in$ , $\notin$	`\in`, `\notin`	Member, not a member
$\subseteq$	`\subseteq`	Subset (possibly equal)
$\emptyset$	`\emptyset`	Empty set
$\cap$ , $\cup$	`\cap`, `\cup`	Intersection, union
$⊨$ , $⊭$	`\models`, `\not\models`	Entails, does not entail
$⊢$ , $⊬$	`\vdash`, `\nvdash`	Derivable, not derivable
$∴$	`\therefore`	Therefore
$Γ$ , $Σ$	`\Gamma`, `\Sigma`	Capital gamma, capital sigma
$Ω$ , $ω$	`\Omega`, `\omega`	Capital omega, lowercase omega
$μ$	`\mu`	Lowercase mu

For the meanings of whole expressions, such as $M ⊨ A$ and $Γ ⊨ A$ , see the symbol lookup above.

Writing a LaTeX document

In a LaTeX document, put formulas in math mode by surrounding them with dollar signs. For example, write $\neg(p_1 \land p_2)$ to produce $\neg(p₁ \land p₂)$ . The dollar signs mark the formula; they aren’t displayed.

An underscore introduces a subscript (p_{12}); a caret introduces a superscript (\Sigma^*). Braces group the characters in a subscript or superscript and aren’t displayed. Some commands, including \nvdash and \therefore, require \usepackage{amssymb} in the document’s preamble. For semantic brackets, use \llbracket and \rrbracket with \usepackage{stmaryrd}. The book’s custom inductive-inference symbol has no standard LaTeX command.

The apps only convert a selection of commands to symbols. They don’t process general LaTeX, including \sigma, \mid, superscripts, or semantic-bracket commands. In a LaTeX document, \sigma gives $σ$ and \mid gives the vertical bar in $Pr(A | B)$ .