Formulas in predicate logic

1 place

Implications between 1-place formulas, on the right the negations (To match the traditional square of opposition the subalterns point downwards here.)

All cases with 2 individuals

description

In the second diagram, the four rectangles at each of the corners represent the possible unary predicates on a domain of two individuals. Specifically, if we consider a predicate P as a subset of a domain D = {c, d}, then either: P = {}, drawn as an empty rectangle P = {c}, drawn as a rectangle with a dot on the left (for c) P = {d}, drawn as a rectangle with a dot on the right (for d) P = {c,d}, drawn as a rectangle with two dots. The rectangles are colored red iff the predicate they represent validates the formula near which they are placed. For example only P = {c,d} validates the formula forall x: P(x) at the top left corner, hence only the rectangle with the two dots is colored red. Thus, the squares together with their coloring represents a subset of the set of unary predicates P on a domain with two individuals. In the first diagram, the subsets are summarised in a different graphical notation, called a sketch. There, each square represents a specific subset of the set of unary predicates on a domain of arbitrary size. This subset is the extension of the formula near which it is placed, and with that, it is a canonical representation of that formula. sketch abbreviation formula description a1 $\forall x.Px$ full e1 $\exists x.Px$ not empty $\forall x.\neg Px$ empty $\exists x.\neg Px$ not full

2 places

description

Two-place formulas sketch abbreviation formula description a12 = a21 $\forall xy.Pxy$ matrix full e12 = e21 $\exists xy.Pxy$ matrix not empty e2a1 $\exists y.\forall x.Pxy$ one row full e1a2 $\exists x.\forall y.Pxy$ one column full a2e1 $\forall y.\exists x.Pxy$ no row empty a1e2 $\forall x.\exists y.Pxy$ no column empty With negations sketch abbreviation formula description $\forall xy.\neg Pxy$ matrix empty $\exists xy.\neg Pxy$ matrix not full $\exists y.\forall x.\neg Pxy$ one row empty $\exists x.\forall y.\neg Pxy$ one column empty $\forall y.\exists x.\neg Pxy$ no row full $\forall x.\exists y.\neg Pxy$ no column full With coinciding variables sketch abbreviation formula description a(12) = a(21) $\forall x.Pxx$ diagonal full e(12) = e(21) $\exists x.Pxx$ diagonal not empty With negations sketch abbreviation formula description $\forall x.\neg Pxx$ diagonal empty $\exists x.\neg Pxx$ diagonal not full

	3 ordered partitions in Cayley graph	Pairs, nodes of the square
Sketches in Hasse diagram	6 matrices in Hasse diagram	Pairs in Hasse diagram

With coinciding variables
Sketches in Hasse diagram	Matrices in Hasse diagram	Pairs in Hasse diagram

With negations
Sketches in Hasse diagram	Sketches in Hasse diagram, negations
All cases with 2 individuals	All cases with 2 individuals, negations

3 places

	13 ordered partitions in Cayley graph	Pairs, nodes of the cube
Sketches in Hasse diagram	26 matrices in Hasse diagram	Pairs in Hasse diagram

4 places

Examples:

matrix	abbreviation	formula
	a3 e2 a4 e1	$\forall y~\exists x~\forall z~\exists w~Pwxyz$
	e1 a3 e24	$\exists w~\forall y~\exists x~\exists z~Pwxyz$
	a1 e3 a24	$\forall w~\exists y~\forall x~\forall z~Pwxyz$
	e3 a124	$\exists y~\forall w~\forall x~\forall z~Pwxyz$

75 ordered partitions in Cayley graph

150 matrices in Hasse diagram

Pairs, nodes of the tesseract 2-element subsets of a 4-element set:

weight 3
Ordered partitions 1110 1101 1011 0111 Pairs 1110 1101 1011 0111

weight 2
Ordered partitions 1100 1010 0110 1001 0101 0011 Pairs 1100 1010 0110 1001 0101 0011

weight 1
Ordered partitions 1000 0100 0010 0001 Pairs 1000 0100 0010 0001

Pairs

Formulas with n-place predicates can be broken down in T_(n-1) formulas with 2-place predicates.
These triangles (or vectors) with up to 8 different entries are a convenient way to determine whether one formula implies another one.

The image captions in this section are the abbreviated formulas and the pseudo-octal strings.

Among the following four formulas - visualized in the different ways used here - the left one implies a1 e2 a3, and the two on the right are implied by it.

a(12)3  =  20-0

a1 e2 a3  =  60-1

e12 a3  =  71-1

a1 e(23)  =  66-5

e2 a14 e3  =  460-71-3

Symbolic representation of pairs and the corresponding pseudo-octal digits

e(12)8 a(35)(46) e7  =  5111177-111177-02064-0264-064-64-7

e(128) a(356)4 e7  =  5111175-111175-02264-0064-264-64-7

Places and different variables

The number of formulas with n place predicates and n different variables is  A000629(n) = 2 * OrderedBell(n).
These formulas form the lattices shown above.

The number of formulas with n place predicates and k different variables is 2 *  A232598 = 2 * Stirling2(n,k) * OrderedBell(k):

      k  =  1        2        3        4        5        6        7        8              sum = 2 * A083355(n)
n
1           2                                                                                 2
2           2        6                                                                        8
3           2       18       26                                                              46
4           2       42      156      150                                                    350
5           2       90      650     1500     1082                                          3324
6           2      186     2340     9750    16230     9366                                37874
7           2      378     7826    52500   151480   196686    94586                      503458
8           2      762    25116   255150  1136100  2491356  2648408  1091670            7648564

Preferential arrangements of set partitions

A formula with an n-place predicate is PA of an n-set together with a Boolean value:

E.g. this PA corresponds to this and this formula.