Formulas in predicate logic
1 place
[edit  edit source]
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:
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.

With coinciding variables  

With negations  

4 places
[edit  edit source]Examples:
matrix  abbreviation  formula 

a3 e2 a4 e1  
e1 a3 e24  
a1 e3 a24  
e3 a124 
weight 3  


weight 2  


weight 1  


Pairs
[edit  edit source]Formulas with nplace predicates can be broken down in T_{(n1)} formulas with 2place 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 pseudooctal 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.
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) 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 nplace predicate is PA of an nset together with a Boolean value: