Formulas in predicate logic

From Wikiversity
Jump to navigation Jump to search

1 place[edit]

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



Rdrdo.svg 2 places[edit]


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


Rdrdo.svg 3 places[edit]

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]

Examples:

matrix abbreviation formula
Predicate logic; 4 variables; ordered partition a3e2a4e1.svg a3 e2 a4 e1
Predicate logic; 4 variables; ordered partition e1a3e24.svg e1 a3 e24
Predicate logic; 4 variables; ordered partition a1e3a24.svg a1 e3 a24
Predicate logic; 4 variables; ordered partition e3a124.svg 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: 2-element subsets of 4 elements; array, hexagonal.svg


weight 1
Ordered partitions
1000
0100
0010
0001

Pairs[edit]

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]

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


Rdr.svg Preferential arrangements of set partitions[edit]

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

E.g. this PA Preferential arrangement 3-(14)2.svg corresponds to this Predicate logic; 4 variables; ordered partition a3e(14)2.svg and this Predicate logic; 4 variables; ordered partition e3a(14)2.svg formula.