zeroth order logic (original) (raw)

\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.

Contents:

• 1 Propositional forms

1 Propositional forms

Table 1 lists equivalent expressions for the four functions of concrete type X→𝔹 and abstract type 𝔹→𝔹 in a number of different languages for zeroth order logic.

Table 1. Propositional Forms on One Variable
ℒ1	ℒ2	ℒ3	ℒ4	ℒ5	ℒ6
x=	1 0
f0	f00	0 0	()	false	0
f1	f01	0 1	(x)	not x	¬⁢x
f2	f10	1 0	x	x	x
f3	f11	1 1	(())	true	1

Table 2 lists equivalent expressions for the sixteen functions of concrete type X×Y→𝔹 and abstract type 𝔹×𝔹→𝔹 in the same set of languages.

Table 2. Propositional Forms on Two Variables
ℒ1	ℒ2	ℒ3	ℒ4	ℒ5	ℒ6
x=	1 1 0 0
y=	1 0 1 0
f0	f0000	0 0 0 0	()	false	0
f1	f0001	0 0 0 1	(x)⁢(y)	neither x nor y	¬⁢x∧¬⁢y
f2	f0010	0 0 1 0	(x)⁢y	y and not x	¬⁢x∧y
f3	f0011	0 0 1 1	(x)	not x	¬⁢x
f4	f0100	0 1 0 0	x⁢(y)	x and not y	x∧¬⁢y
f5	f0101	0 1 0 1	(y)	not y	¬⁢y
f6	f0110	0 1 1 0	(x,y)	x not equal to y	x≠y
f7	f0111	0 1 1 1	(x⁢y)	not both x and y	¬⁢x∨¬⁢y
f8	f1000	1 0 0 0	x⁢y	x and y	x∧y
f9	f1001	1 0 0 1	((x,y))	x equal to y	x=y
f10	f1010	1 0 1 0	y	y	y
f11	f1011	1 0 1 1	(x⁢(y))	not x without y	x⇒y
f12	f1100	1 1 0 0	x	x	x
f13	f1101	1 1 0 1	((x)⁢y)	not y without x	x⇐y
f14	f1110	1 1 1 0	((x)⁢(y))	x or y	x∨y
f15	f1111	1 1 1 1	(())	true	1

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

• •
  Language ℒ3.

  In Table 1, ℒ3 describes each boolean function f:𝔹→𝔹 by means of the sequence of two boolean values (f⁢(1),f⁢(0)).
  In Table 2, ℒ3 describes each boolean function f:𝔹2→𝔹 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 ℒ2 lists the functions in the form fi, where the index i is a bit string formed from the sequence of boolean values in ℒ3.
• •
  Language ℒ1 notates the functions fi with an index i that is the decimal equivalent of the binary numeral index in ℒ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 ℒ4 expresses the boolean functions in terms of two families of logical operations:

  Logical conjunctions written as continued products. For example:

  x⁢y=x∧yx⁢y⁢z=x∧y∧z

  Minimal negation operators written as parenthesized lists. For example:

  ()=0(x)=¬⁢x(x,y)=x≠y

• •
  Language ℒ5 lists ordinary language expressions for the propositional forms. Many other paraphrases are possible, but these afford a sample of the simplest equivalents.
• •
  Language ℒ6 expresses the propositional forms in one of the several notations that are commonly used in formal logic.