Thursday, August 24, 2017

Geodetic graphs

Geodetic graphs have the particular property that each pair of points has a unique shortest path between them, or geodesic. Trees are a special case of geodetic graphs in which each pair of points has a unique path in general between them. Block graphs are sometimes called clique trees, they include trees and also happen to be the chordal geodetic graphs.

Monday, April 3, 2017

Partition logic

The logic of set partitions is a fundamental part of the analysis of ordering relations. The set partitions necessarily form a lattice which has certain properties corresponding to its join and meet operations. At the same time, the elements themselves form a Moore family depending upon which direction you intend to take the ordering. The Moore family then necessarily comes with a corresponding closure operation.

Sunday, January 1, 2017

2016 year in review

The methods of propositional logic can be applied to situations that arise from boolean algebra. Boolean formulas are applicable to any boolean algebra structure rather it is booleans themselves or sets, classes, and other predicate like structures. Set theoretic operations like union, intersection, difference, and symmetric difference can be expressed in terms of boolean formulas. These set theoretic operations are not unlike the logical connectives defined by these same boolean formulas.

At the same time, a wide variety of constraint satisfaction problems like sudoku can be expressed in terms of boolean formulas. Boolean formulas defined by clauses that have no more then two elements are equivalent to implication graphs. Backtracking search methods can be used to solve constraint satisfaction problems like sudoku and implications can be used to narrow down the search space for any partial candidate solution in the backtracking search.

The exact solutions to constraint satisfaction problems can therefore be deduced. In the vast majority of cases exact constraint satisfaction methods are not applicable and we need to use heuristics and statistics instead to get approximate solutions to optimization problems.

Friday, December 16, 2016

Boolean algebra equations

Boolean algebra equations can be built from meet, join, and complementation based upon the distributive law and the fact that complementation is an involution. These boolean algebra formulas can be put into conjuctive normal form or disjunctive normal form based upon which lattice operation is going to be at the highest level of nesting. These boolean algebra equations are applicable to any boolean algebra rather it is truth values or entire sets. Propositional logic formulas then can be defined based upon the principles of boolean algebra.

Saturday, September 24, 2016

Propositional logic formulas

Propositional logic deals with the truth values of propositions and how they are related through logical connectives. In general propositional logic formulas can be represented using conjunctive normal form or disjunctive normal form. These propositional logic formulas have a wide variety of general applications. In particular, numerous constraint satisfaction problems can be described as boolean satisfiability problems in propositional logic. Constraint satisfaction is a vital area of interest in propositional logic.

Thursday, June 30, 2016

Families of kuratowski pairs

Families of kuratowski pairs which are set systems that define a pair between two elements fully characterize correspondences between sets. It is by using families of kuratowski pairs that we can deal with questions of relation algebra. Each family of kuratowski pairs necessarily has rank at most two because each kuratowski pair has a maximum cardinality of two. This means that these are rank limited set systems.

Wednesday, June 15, 2016

The rank of set systems

Given a set of sets then the rank of that set system is the maximum cardinality of the sets it contains as members. We can determine certain characteristics of a set system based upon their rank. Set systems of rank at most one are rank complete which means they are like a set which may or may not contain the empty set. Set systems of rank at most two include as a particular case set systems that define comparability. This process can be extended further to determine properties of the rank of higher set systems.

The rank property can also be used to understand sets of sets of sets. Given a sets of sets of sets then the rank is the maximum cardinality of a set of sets contained in the set of sets of sets. We can deduce that families of kuratowski pairs necessarily have a rank of at most two because the pairs never have more then two members. The families of kuratowski pairs effectively generalize correspondences between sets. Kuratowski pairs also have the property that their union has at most two elements so the rank of the set of unions is at most two which makes the ranking property even stronger for them.