Jump to content

Formulas in predicate logic

From Wikiversity

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




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


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
e1 a3 e24
a1 e3 a24
e3 a124
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 1
Ordered partitions
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 Sloane'sA000629(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 * Sloane'sA232598 = 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


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.