zeroth order logic

\PMlinkescapephrase

calculus \PMlinkescapephraseCalculus \PMlinkescapephrasecolumn \PMlinkescapephraseColumn \PMlinkescapephrasecolumns \PMlinkescapephraseColumns \PMlinkescapephrasecompact \PMlinkescapephraseCompact \PMlinkescapephrasedegree \PMlinkescapephraseDegree \PMlinkescapephraseformal logic \PMlinkescapephraseFormal logic \PMlinkescapephraselevel \PMlinkescapephraseLevel \PMlinkescapephraseorder \PMlinkescapephraseOrder \PMlinkescapephrasereference \PMlinkescapephraseReference \PMlinkescapephrasetranslation \PMlinkescapephraseTranslation

Note. This entry overlaps to some degree with other entries on boolean functions (http://planetmath.org/BooleanValuedFunction) and propositional logic (http://planetmath.org/PropositionalCalculus), but serves as a compact reference and a translation manual for several different styles of notation.

Zeroth order logic is a term in popular use among practitioners for the common principles underlying the algebra of sets, boolean algebra, boolean functions, logical connectives, monadic predicate calculus, propositional calculus, and sentential logic. The term serves to mark a level of abstraction in which the inessential differences among these subjects can be subsumed under the appropriate isomorphisms.

1 Propositional forms

Table 1 lists equivalent expressions for the four functions of concrete type $X\to\mathbb{B}$ and abstract type $\mathbb{B}\to\mathbb{B}$ in a number of different languages for zeroth order logic.

Table 1. Propositional Forms on One Variable

$\mathcal{L}_{1}$ $\mathcal{L}_{2}$ $\mathcal{L}_{3}$ $\mathcal{L}_{4}$ $\mathcal{L}_{5}$ $\mathcal{L}_{6}$

$x=$ 1 0

$f_{0}$ $f_{00}$ 0 0 $()$ false $0$

$f_{1}$ $f_{01}$ 0 1 $(x)$ not $x$ $\lnot x$

$f_{2}$ $f_{10}$ 1 0 $x$ $x$ $x$

$f_{3}$ $f_{11}$ 1 1 $(())$ true $1$

Table 2 lists equivalent expressions for the sixteen functions of concrete type $X\times Y\to\mathbb{B}$ and abstract type $\mathbb{B}\times\mathbb{B}\to\mathbb{B}$ in the same set of languages.

Table 2. Propositional Forms on Two Variables

$\mathcal{L}_{1}$ $\mathcal{L}_{2}$ $\mathcal{L}_{3}$ $\mathcal{L}_{4}$ $\mathcal{L}_{5}$ $\mathcal{L}_{6}$

$x=$ 1 1 0 0

$y=$ 1 0 1 0

$f_{0}$ $f_{0000}$ 0 0 0 0 $()$ false $0$

$f_{1}$ $f_{0001}$ 0 0 0 1 $(x)(y)$ neither $x$ nor $y$ $\lnot x\land\lnot y$

$f_{2}$ $f_{0010}$ 0 0 1 0 $(x)y$ $y$ and not $x$ $\lnot x\land y$

$f_{3}$ $f_{0011}$ 0 0 1 1 $(x)$ not $x$ $\lnot x$

$f_{4}$ $f_{0100}$ 0 1 0 0 $x(y)$ $x$ and not $y$ $x\land\lnot y$

$f_{5}$ $f_{0101}$ 0 1 0 1 $(y)$ not $y$ $\lnot y$

$f_{6}$ $f_{0110}$ 0 1 1 0 $(x,y)$ $x$ not equal to $y$ $x\neq y$

$f_{7}$ $f_{0111}$ 0 1 1 1 $(xy)$ not both $x$ and $y$ $\lnot x\lor\lnot y$

$f_{8}$ $f_{1000}$ 1 0 0 0 $x y$ $x$ and $y$ $x\land y$

$f_{9}$ $f_{1001}$ 1 0 0 1 $((x,y))$ $x$ equal to $y$ $x=y$

$f_{10}$ $f_{1010}$ 1 0 1 0 $y$ $y$ $y$

$f_{11}$ $f_{1011}$ 1 0 1 1 $(x(y))$ not $x$ without $y$ $x\Rightarrow y$

$f_{12}$ $f_{1100}$ 1 1 0 0 $x$ $x$ $x$

$f_{13}$ $f_{1101}$ 1 1 0 1 $((x)y)$ not $y$ without $x$ $x\Leftarrow y$

$f_{14}$ $f_{1110}$ 1 1 1 0 $((x)(y))$ $x$ or $y$ $x\lor y$

$f_{15}$ $f_{1111}$ 1 1 1 1 $(())$ true $1$

The columns of Tables 1 and 2 are conveniently described in the following order:

•

Language $\mathcal{L}_{3}$ .

In Table 1, $\mathcal{L}_{3}$ describes each boolean function $f:\mathbb{B}\to\mathbb{B}$ by means of the sequence of two boolean values $(f(1),f(0))$ .
In Table 2, $\mathcal{L}_{3}$ describes each boolean function $f:\mathbb{B}^{2}\to\mathbb{B}$ by means of the sequence of four boolean values $(f(1,1),f(1,0),f(0,1),f(0,0))$ .
Sequences of these forms, perhaps in another order and perhaps with the logical values F and T instead of the boolean values 0 and 1, would normally be displayed vertically in a truth table under the column head for $f$ .
•

Language $\mathcal{L}_{2}$ lists the functions in the form $f_{i}$ , where the index $i$ is a bit string formed from the sequence of boolean values in $\mathcal{L}_{3}$ .
•

Language $\mathcal{L}_{1}$ notates the functions $f_{i}$ with an index $i$ that is the decimal equivalent of the binary numeral index in $\mathcal{L}_{2}$ .

Notice that the sense of the binary and decimal codings is highly dependent on context. One needs to know the number of variables in the function and the sequence of points over which it is evaluated in order to decode the indices properly.
•

Language $\mathcal{L}_{4}$ expresses the boolean functions in terms of two families of logical operations:

Logical conjunctions written as continued products. For example:

$\begin{array}[]{ccc}xy&=&x\land y\\ xyz&=&x\land y\land z\\ \end{array}$

Minimal negation operators written as parenthesized lists. For example:

$\begin{array}[]{ccc}()&=&0\\ (x)&=&\lnot x\\ (x,y)&=&x\neq y\\ \end{array}$
•

Language $\mathcal{L}_{5}$ lists ordinary language expressions for the propositional forms. Many other paraphrases are possible, but these afford a sample of the simplest equivalents.
•

Language $\mathcal{L}_{6}$ expresses the propositional forms in one of the several notations that are commonly used in formal logic.

Title	zeroth order logic
Canonical name	ZerothOrderLogic
Date of creation	2013-03-22 17:55:47
Last modified on	2013-03-22 17:55:47
Owner	Jon Awbrey (15246)
Last modified by	Jon Awbrey (15246)
Numerical id	19
Author	Jon Awbrey (15246)
Entry type	Definition
Classification	msc 03G05
Classification	msc 03B05
Related topic	PropositionalCalculus
Related topic	LogicalConnective
Related topic	LogicalGraph
Related topic	LogicalGraphFormalDevelopment
Related topic	TruthFunction
Related topic	TruthTable
Related topic	DifferentialLogic
Related topic	DifferentialPropositionalCalculus
Related topic	DifferentialPropositionalCalculusAppendices
Related topic	DifferentialPropositionalCalculusAppendix2

Table 1. Propositional Forms on One Variable
$\mathcal{L}_{1}$	$\mathcal{L}_{2}$		$\mathcal{L}_{3}$	$\mathcal{L}_{4}$	$\mathcal{L}_{5}$	$\mathcal{L}_{6}$
		$x=$	1 0
$f_{0}$	$f_{00}$		0 0	$()$	false	$0$
$f_{1}$	$f_{01}$		0 1	$(x)$	not $x$	$\lnot x$
$f_{2}$	$f_{10}$		1 0	$x$	$x$	$x$
$f_{3}$	$f_{11}$		1 1	$(())$	true	$1$

Table 2. Propositional Forms on Two Variables
$\mathcal{L}_{1}$	$\mathcal{L}_{2}$		$\mathcal{L}_{3}$	$\mathcal{L}_{4}$	$\mathcal{L}_{5}$	$\mathcal{L}_{6}$
		$x=$	1 1 0 0
		$y=$	1 0 1 0
$f_{0}$	$f_{0000}$		0 0 0 0	$()$	false	$0$
$f_{1}$	$f_{0001}$		0 0 0 1	$(x)(y)$	neither $x$ nor $y$	$\lnot x\land\lnot y$
$f_{2}$	$f_{0010}$		0 0 1 0	$(x)y$	$y$ and not $x$	$\lnot x\land y$
$f_{3}$	$f_{0011}$		0 0 1 1	$(x)$	not $x$	$\lnot x$
$f_{4}$	$f_{0100}$		0 1 0 0	$x(y)$	$x$ and not $y$	$x\land\lnot y$
$f_{5}$	$f_{0101}$		0 1 0 1	$(y)$	not $y$	$\lnot y$
$f_{6}$	$f_{0110}$		0 1 1 0	$(x,y)$	$x$ not equal to $y$	$x\neq y$
$f_{7}$	$f_{0111}$		0 1 1 1	$(xy)$	not both $x$ and $y$	$\lnot x\lor\lnot y$
$f_{8}$	$f_{1000}$		1 0 0 0	$x y$	$x$ and $y$	$x\land y$
$f_{9}$	$f_{1001}$		1 0 0 1	$((x,y))$	$x$ equal to $y$	$x=y$
$f_{10}$	$f_{1010}$		1 0 1 0	$y$	$y$	$y$
$f_{11}$	$f_{1011}$		1 0 1 1	$(x(y))$	not $x$ without $y$	$x\Rightarrow y$
$f_{12}$	$f_{1100}$		1 1 0 0	$x$	$x$	$x$
$f_{13}$	$f_{1101}$		1 1 0 1	$((x)y)$	not $y$ without $x$	$x\Leftarrow y$
$f_{14}$	$f_{1110}$		1 1 1 0	$((x)(y))$	$x$ or $y$	$x\lor y$
$f_{15}$	$f_{1111}$		1 1 1 1	$(())$	true	$1$

zeroth order logic

Contents:

1 Propositional forms