Vlugt, T van der (2015) Computation of the Size of a Fragment of Intuitionistic Logic. Bachelor's Thesis, Mathematics.

Text
Article.pdf  Published Version Download (616kB)  Preview 

Text
Toestemming.pdf  Other Restricted to Backend only Download (58kB) 
Abstract
This thesis will give a stepbystep solution to the calculation of the size of the fragments F[n] = [∧, ∨, ¬¬]^n of intuitionistic propositional logic. These fragments are sets of formulae that contain at most n different propositional variables and only the connectives ∧, ∨ and ¬¬. The size of a fragment will be defined as the total number of equivalence classes of F[n]. The diagram of a fragment is the partially ordered set of equivalence classes ordered by derivability. The calculation of the size of F[n] will be done by finding the set of join irreducible elements I(F[n]) of the diagram of F[n], and generate all upward closed subsets of I(F[n]). These will form a finite distributive lattice by Birkhoff’s theorem. The set of upper sets is isomorphic to the diagram of F[n]. The algorithm successfully computed the sizes #F[1] = 4, #F[2] = 21 and #F[3] = 1891 (with ⊤ and ⊥ included in each fragment), but is not efficient enough to compute #F[4], yet.
Item Type:  Thesis (Bachelor's Thesis) 

Degree programme:  Mathematics 
Thesis type:  Bachelor's Thesis 
Language:  English 
Date Deposited:  15 Feb 2018 08:04 
Last Modified:  15 Feb 2018 08:04 
URI:  http://fse.studenttheses.ub.rug.nl/id/eprint/12785 
Actions (login required)
View Item 