Assignment (logic)

An assignment is part of the interpretation of formal systems

• in propositional logic, a mapping that assigns a truth value w or f to each propositional variable ;
• In the predicate logic (with a given structure S) a mapping that assigns an element of the universe A to each free variable from S.

Propositional logic

In propositional logic, an assignment is defined as a mapping of the set of proposition variables onto the set . So a truth value is assigned to each proposition variable . ${\displaystyle {\textbf {AV}}}$ ${\displaystyle \{0,1\}}$ ${\displaystyle p\in {\textbf {AV}}}$

${\displaystyle \omega \colon {\textbf {AV}}\to \{0,1\}}$

The application of this mapping to whole formulas is possible through the recursive definition of to the whole set of Boolean formulas . ${\displaystyle \omega }$ ${\displaystyle {\mathcal {F}}}$

${\displaystyle \omega \colon {\mathcal {F}}\to \{0,1\}}$

With

${\displaystyle \omega (\alpha \land \beta )=\omega \alpha \land \omega \beta }$

${\displaystyle \omega (\alpha \lor \beta )=\omega \alpha \lor \omega \beta }$

${\displaystyle \omega \neg \alpha =\neg \omega \alpha }$

This definition is given here as an example for the logical signature . If the signature contains other joiners, the definition must be expanded. ${\displaystyle \{\land ,\lor ,\neg \}}$

This ensures that an entire formula can be processed. At the lowest level, however, discrete values ​​are still assigned to the individual proposition variables. If such a formula is now assigned, it is possible to determine a total truth value for the entire formula that corresponds to the assignment. ${\displaystyle \omega }$ ${\displaystyle \alpha \in {\mathcal {F}}}$

The amount of all assignments of a formula is usually shown with the help of a value table. ${\displaystyle \alpha }$

	${\displaystyle p_{1}}$	${\displaystyle p_{2}}$	${\displaystyle \dots }$	${\displaystyle p_{n}}$	${\displaystyle \alpha }$
1	0	0	${\displaystyle \dots }$	0	${\displaystyle \omega _{1}\alpha }$
2	0	0	${\displaystyle \dots }$	1	${\displaystyle \omega _{2}\alpha }$
${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$
n	1	1	${\displaystyle \dots }$	1	${\displaystyle \omega _{n}\alpha }$

${\displaystyle \omega _{k}}$( ) refers to the corresponding line that reflects the assignment of the individual variables that occur in. On the basis of this assignment, additional terms such as tautology are built up in the logic. ${\displaystyle 1\leq k\leq n}$ ${\displaystyle \alpha }$

Predicate logic

Let the variables of the structure be . An assignment is z. B. given by the function for . ${\displaystyle v_{n},n\in \mathbb {N} }$ ${\displaystyle \beta (v_{n})=2n}$ ${\displaystyle n\geq 0}$

literature

• Hans-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic . 4th edition. Spektrum Akademischer Verlag, Heidelberg 1996, ISBN 3-8274-1691-4 .
• Wolfgang Rautenberg: Introduction to Mathematical Logic . 3. Edition. Vieweg + Teuber, Berlin 2008, ISBN 978-3-8348-0578-2

Individual evidence

1. ↑ Ebbinghaus u. a., chap. III, §1
2. ↑ Rautenberg, chap. I.1