Computation of the Size of a Fragment of Intuitionistic Logic

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

Preview	Text Article.pdf - Published Version Download (616kB) | Preview
	Text Toestemming.pdf - Other Restricted to Backend only Download (58kB)

Abstract

This thesis will give a step-by-step 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:	https://fse.studenttheses.ub.rug.nl/id/eprint/12785

Actions (login required)

View Item