Formulas in predicate logic

## 1 place

[edit | edit source]

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:

1. P = {}, drawn as an empty rectangle
2. P = {c}, drawn as a rectangle with a dot on the left (for c)
3. P = {d}, drawn as a rectangle with a dot on the right (for d)
4. 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 |  ∀ x . P x {\displaystyle \forall x.Px} | full
| e1 |  ∃ x . P x {\displaystyle \exists x.Px} | not empty
|  |  ∀ x . ¬ P x {\displaystyle \forall x.\neg Px} | empty
|  |  ∃ x . ¬ P x {\displaystyle \exists x.\neg Px} | not full

##  2 places

[edit | edit source]

description

Two-place formulas

| sketch | abbreviation | formula | description

|
|
|

| a12 = a21 |  ∀ x y . P x y {\displaystyle \forall xy.Pxy} | matrix full
| e12 = e21 |  ∃ x y . P x y {\displaystyle \exists xy.Pxy} | matrix not empty
| e2a1 |  ∃ y . ∀ x . P x y {\displaystyle \exists y.\forall x.Pxy} | one row full
| e1a2 |  ∃ x . ∀ y . P x y {\displaystyle \exists x.\forall y.Pxy} | one column full
| a2e1 |  ∀ y . ∃ x . P x y {\displaystyle \forall y.\exists x.Pxy} | no row empty
| a1e2 |  ∀ x . ∃ y . P x y {\displaystyle \forall x.\exists y.Pxy} | no column empty

With negations

sketch | abbreviation | formula | description

|
|
|

|  |  ∀ x y . ¬ P x y {\displaystyle \forall xy.\neg Pxy} | matrix empty
|  |  ∃ x y . ¬ P x y {\displaystyle \exists xy.\neg Pxy} | matrix not full
|  |  ∃ y . ∀ x . ¬ P x y {\displaystyle \exists y.\forall x.\neg Pxy} | one row empty
|  |  ∃ x . ∀ y . ¬ P x y {\displaystyle \exists x.\forall y.\neg Pxy} | one column empty
|  |  ∀ y . ∃ x . ¬ P x y {\displaystyle \forall y.\exists x.\neg Pxy} | no row full
|  |  ∀ x . ∃ y . ¬ P x y {\displaystyle \forall x.\exists y.\neg Pxy} | no column full

With coinciding variables

sketch | abbreviation | formula | description

|
|
|

| a(12) = a(21) |  ∀ x . P x x {\displaystyle \forall x.Pxx} | diagonal full
| e(12) = e(21) |  ∃ x . P x x {\displaystyle \exists x.Pxx} | diagonal not empty

With negations

sketch | abbreviation | formula | description

|
|
|

|  |  ∀ x . ¬ P x x {\displaystyle \forall x.\neg Pxx} | diagonal empty
|  |  ∃ x . ¬ P x x {\displaystyle \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

[edit | edit source]

| 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

[edit | edit source]

Examples:

matrix | abbreviation | formula

|
|

| a3 e2 a4 e1 |  ∀ y   ∃ x   ∀ z   ∃ w   P w x y z {\displaystyle \forall y~\exists x~\forall z~\exists w~Pwxyz}
| e1 a3 e24 |  ∃ w   ∀ y   ∃ x   ∃ z   P w x y z {\displaystyle \exists w~\forall y~\exists x~\exists z~Pwxyz}
| a1 e3 a24 |  ∀ w   ∃ y   ∀ x   ∀ z   P w x y z {\displaystyle \forall w~\exists y~\forall x~\forall z~Pwxyz}
| e3 a124 |  ∃ y   ∀ w   ∀ x   ∀ z   P w x y z {\displaystyle \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

[edit | edit source]

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

[edit | edit source]

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)

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

[edit | edit source]

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.