Aplicaciones de álgebra universal al reticulado de Post

El reticulado de todos los clones de funciones booleanas ordenados por inclusión, mejor conocido como reticulado de Post, es de suma importancia en Ciencias de la Computación en lo referido al problema de satisfacibilidad booleana y su complejidad. En este trabajo se logra describir una de las caden...

Full description

Bibliographic Details
Main Author: Leberle, Maico Carlos
Other Authors: Vaggione, Diego José
Format: bachelorThesis
Language:spa
Published: 2018
Subjects:
Online Access:http://hdl.handle.net/11086/5792
Description
Summary:El reticulado de todos los clones de funciones booleanas ordenados por inclusión, mejor conocido como reticulado de Post, es de suma importancia en Ciencias de la Computación en lo referido al problema de satisfacibilidad booleana y su complejidad. En este trabajo se logra describir una de las cadenas infinitas del reticulado de Post mediante la aplicación de varios conceptos de Álgebra Universal. Para esto, estudiaremos el reticulado de congruencias de un álgebra, las variedades, las álgebras subdirectamente irreducibles, el álgebra libre de una variedad, las condiciones de Mal'cev y de Jónnson, y los clones. Además, se presentan la variedad de las álgebras implicativas y las AE-sentencias (sentencias de la forma "para todo existe un único (conjunción de equivalencias)"), centrales en el desarrollo de este trabajo. A través de las AE-sentencias, estudiaremos el clon de funciones algebraicas y las (sub)clases algebraicamente expandibles. Será posible, entonces, describir la cadena infinita de clones comprendidos entre el clon de operaciones término y el clon de funciones algebraicas del álgebra implicativa de 2 elementos (i.e., los clones que contienen a la función booleana implica) mediante la demostración de un anti-isomorfismo con el reticulado de subclases algebraicamente expandibles de la variedad de las álgebras implicativas