Lógica y pensamientocomputacional

Fernando Soler ToscanoUniversidad de Sevilla

RESUMEN

J.M. Wing define el pensamiento computacional comola habilidad consistente en aplicar nociones provenientes delas ciencias de la computación a la resolución de problemasen cualquier ámbito, sin que necesariamente se emplee unacomputadora.

La metodología habitualmente propuesta para el desarro-llo del pensamiento computacional consta de cuatro fases: (i)descomposición, (ii) abstracción, (iii) reconocimiento de pa-trones y (iv) diseño de algoritmos. Proponemos que la lógicapuede servir como herramienta para guiar estos cuatro pasosy, a la vez, la motivación hacia el pensamiento computacionalpuede servir para despertar interés por el aprendizaje de lalógica.

412

Pensamiento computacional

Jeannette M. Wing (2006) define el pensamiento computacional como lahabilidad consistente en aplicar nociones provenientes de las ciencias dela computación a la resolución de problemas en cualquier ámbito, sin quenecesariamente se emplee una computadora. Piensa que, del mismo modoque la biología computacional ha cambiado la forma de pensar de losbiólogos, o la teoría de juegos ha modificado el modo en que piensan loseconomistas, la introducción de nociones computacionales en cualquierámbito puede ofrecer nuevas soluciones que doten de mayor creatividady eficiencia el modo en que nos enfrentamos a los problemas. Se trata depreguntarnos sobre la dificultad de resolver un cierto problema, sobre sihay forma de optimizar una solución determinada, o si podemos reducirnuestro problema a otro conocido, empleando conceptos propios de lacomputación para tratar de abordar estas preguntas.

Wing entiende que el pensamiento computacional es una «competen-cia fundamental para todos, no solo para científicos de la computación».Cree que del mismo modo que desde pequeños adquirimos las habilidadesbásicas de lectura, escritura y aritmética, el pensamiento computacionalse debe añadir a las habilidades analíticas de cualquier niño. En el tiempoque ha pasado desde el manifiesto de Wing ciertamente existen numero-sos programas educativos y propuestas como Scratch para que niños deedades muy tempranas se acerquen al mundo de la computación. Perola propuesta de Wing va más allá del uso de computadoras. Su carrac-terización del pensamiento computacional (Wing, 2006, la traducción delas citas es nuestra) reúne, entre otras, las siguientes notas:

• Conceptualizar, no programar : «Pensar como un científico de lacomputación significa más que ser capaz de programar una compu-tadora. Requiere pensar a múltiples niveles de abstracción».

• Es una habilidad fundamental, algo que cualquier persona debedominar en la sociedad contemporánea.

• El modo en que piensan los humanos, no las computadoras: «Elpensamiento computacional es un modo en que los humanos re-suelven problemas [. . . ]. Las computadores son torpes y aburridas;los humanos son inteligentes e imaginativos».

413

• Complementa y combina las matemáticas y la ingeniería. Las cien-cias de la computación se fundamentan en las matemáticas, peroresolver problemas computacionalmente requiere asumir el puntode vista del ingeniero, en tanto que nos preguntamos por el costede resolver un problema y la posibilidad de hacerlo con los recursosdisponibles.

• Ideas, no aparatos. Como indicamos más arriba, no se trata de usarcomputadoras, sino conceptos computacionales que nos ayudan enlos problemas cotidianos.

• Para todos y en cualquier situación: «El pensamiento computacio-nal será una realidad cuando esté tan presente en las tareas huma-nas que desaparezca como una filosofía explícita».

Ciertos autores se han preguntado por la relación entre el pensamien-to computacional y el pensamiento crítico. La propuesta original de Wingy los desarrollos posteriores de la noción de pensamiento computacionalguardan muchas similitudes con las competencias que tradicionalmentese han calificado de pensamiento crítico. La diferencia evidente es queel pensamiento computacional recurre a nociones básicas de las cienciasde la computación, mientras que el pensamiento crítico tiene como mo-delo nociones clásicas de la lógica. Pero realmente la lógica se encuentratambién entre los fundamentos de las ciencias de la computación comobien señala María Manzano (2005). Otra diferencia es la relevancia delas nociones de complejidad y optimización en el pensamiento compu-tacional. Esa es tal vez la novedad más notable que aporta a la idea depensamiento crítico. Siguiendo la ecuación de Kowalski (1979),

Algoritmo = Lógica + Control

lo que el pensamiento computacional (Algoritmo) añade al pensamientocrítico (Lógica) es la idea del Control, que incluye la mencionada preo-cupación por la eficiencia de las soluciones.

Lógica y pensamiento computacional

La metodología habitualmente propuesta para el desarrollo del pensa-miento computacional consta de cuatro fases: descomposición, abstrac-

414

ción, reconocimiento de patrones y diseño de algoritmos. Proponemos quela lógica puede servir como herramienta para guiar estos cuatro pasos y,a la vez, la motivación que existe hacia el pensamiento computacionalpuede servir para despertar interés por el aprendizaje de la lógica. Va-mos a analizar dos ejemplos. El primero de ello es la resolución de unproblema MAFIA [4] utilizando lógica proposicional. El siguiente proble-ma, de Alfredo José Villarino Medina, se encuentra publicado en SummaLogicae xxi1:

El cocinero del padrino IIITras los sucesos acaecidos tiempo atrás en los que el co-

cinero del padrino murió de forma sospechosa, éste ha de-cidido hacer una prueba a cuatro cocineros famosos de lacocina italiana. Les propone un menú degustación de tal for-ma que cada uno pueda mostrar sus cualidades al padrino.Desgraciadamente el padrino murió instantes después de lagran comida. Estos son los resultados que arrojan los foren-ses tras el análisis de los platos y tras la autopsia realizadaal padrino:

1. El padrino comió aquel día.

2. El harina usada para hacer la Pizza y los Tagliatelle esmortal si se mezcla con un ingrediente de los Spaghetti.

3. Si comió Tagliatelle entonces no comió Ravioles.

4. La autopsia demostró que no comió ni Pizza ni Ravioles.

5. Siempre que el padrino come Spaghetti la acompaña conRavioles o Tagliatelle.

Descomposición. La descomposición consiste en transformar un pro-blema complejo en pequeños problemas más simples. La propia estruc-tura del enunciado del problema MAFIA permite identificar cinco enun-ciados con las pistas relevantes. En lógica proposicional, cada pista seconvertirá en una fórmula.

1http://logicae.usal.es/.

415

Abstracción. La abstracción consiste en detectar cuál es la informa-ción relevante del problema y eliminar lo accesorio. En lógica proposicio-nal se utilizan variables para representar los portadores básicos de infor-mación. En la solución ofrecida por el autor de este problema MAFIA,se utilizan cuatro proposiciones: p (pizza), r (ravioles), s (spaguetti), t(tagliatelle).

Reconocimiento de patrones. Pese a la distinta forma gramaticalde cada una de las pistas del problema MAFIA, reconocemos en ellaspatrones, esquemas que representan distintos tipos de relación entre pro-posiciones. En la lógica proposicional, los patrones vienen dados por lasconectivas y determinen la estructura de las fórmulas. Cada una de lascinco pistas del enunciado del problema MAFIA es formalizada por suautor, respectivamente, como:

1. p ∨ r ∨ s ∨ t

2. (p ∨ t) ∧ s

3. t→ ¬r

4. ¬p ∧ ¬r

5. s→ (r ∨ t)

Diseño de algoritmos. Finalmente, la metodología del pensamientocomputacional recurre a algoritmos para resolver los problemas. En ló-gica, los algoritmos pueden ser procedimientos sistemáticos de pruebacomo los tableaux semánticos [4]. El tableau de la figura 1 resuelve elproblema MAFIA que hemos tomado como ejemplo. Para reducir el ta-maño del tableau, se ha omitido la primera pista p ∨ r ∨ s ∨ t dado quesolo impone que alguna de las variables proposicionales sea verdadera, locual podemos comprobar en la solución, que viene dada por los literalesque aparecen en la intersección de todas las ramas abiertas.

416

(p ∨ t) ∧ s1.

t→ ¬r2.

¬p ∧ ¬r3.

s→ r ∨ t4.

p ∨ t5. α,1

s6. α,1

¬p7. α,3

¬r8. α,3

p9. β,5⊗7,9

t10. β,5

¬t11. β,2⊗10,11

¬r12. β,2

¬s13. β,4⊗6,13

r ∨ t14. β,4

r15. β,14⊗8,15

t16. β,14

Figura 1: Tableau semántico para resolver un problema MAFIA

En este caso solo hay una rama abierta con: {¬p,¬r, s, t}. Así que, comoconcluye Alfredo J. Villarino,

Tras analizar las pesquisas y realizar el cálculo los resul-tados muestran que la mezcla de Tagliattele y Spaghetti fuemortal para nuestro querido padrino. Así pues, los cocinerosde estos platos recibirán la visita de la mafia. . .

Nuestro segundo ejemplo es para ilustrar cómo podemos utilizar lametodología del pensamiento computacional para introducir una nuevalógica. Se trata de la lógica proposicional dinámica (PDL, PropositionalDynamic Logic), una lógica multi-modal para realizar razonamiento pro-posicional acerca de la ejecución de programas [1].

417

Figura 2: El robot Bee Bot R© de TTS Group. A la derecha, sobre untablero en una imagen de Bee-Bot Emulator

Nuestra motivación será modelar el comportamiento de Bee Bot, unrobot educativo que se ha hecho muy popular en los programas de pensa-miento computacional. La figura 2 muestra su aspecto y permite apreciarsu funcionalidad. Dispone de cuatro botones de control que permiten gi-rar 90 grados sobre sí mismo a izquierda o derecha y avanzar o retrocederuna posición. A la derecha de la figura 2 lo vemos en acción sobre un ta-blero en una simulación de Bee-Bot Emulator2. Pulsando sucesivamentelos botones rojos se programa un camino que comienza a ejecutarse cuan-do se pulsa el botón verde de OK. Los botones azules sirven para borrarel programa introducido o pararlo cuando se está ejecutando.

Vamos a acercarnos a PDL a través de la metodología del pensamien-to computacional. En lugar de ofrecer la sintaxis y la semántica de modoconvencional, el formalismo aparecerá en la medida en que lo necesite-mos.

En la fase de descomposición, nos damos cuenta de que se trata demodelar por una parte las posiciones del tablero y por otra el movimientodel robot. Los tableros por los que se mueve Bee Bot están divididos enceldas. Podemos identificar como wij la celda que está en la fila i ycolumna j del tablero. En cada momento, Bee Bot se encuentra sobreuna de tales celdas y los pasos de computación consisten en cambiarde celda hacia adelante o atrás o bien rotar sobre sí mismo a izquierdao derecha sin cambiar de celda. En los tableros que tienen obstáculos,habrá desplazamientos que estarán prohibidos.

2https://www.bee-bot.us/emu/beebot.html

418

wnij

wsij

weijww

ij

r

rr

rl l

ll

Figura 3: Giros del robot sobre sí mismo en una celda: izquierda (l, left)o derecha (r, right)

En la fase de abstracción tenemos que dar forma a los elementos queacabamos de presentar. La noción clave es la de estado. Los movimientosque puede realizar el robot no solo dependen de la celda sobre la queestá, sino también de su orientación. La figura 3 muestra un esquema delos cuatro estados en que puede encontrarse Bee Bot en una celda wij :mirando hacia el norte (wn

ij), hacia el sur (wsij) al este (we

ij), o al oeste(ww

ij). Además, se han representado las rotaciones del robot dentro deuna celda: a izquierda (l) y derecha (r). Las rotaciones solo cambian laorientación del robot.

Los desplazamientos entre distintas celdas están representados en lafigura 4. Son dos tipos de movimiento: hacia adelante (f , front) y haciaatrás (b, back). Dependiendo de la orientación del robot, cada movimien-to le lleva a una celda diferente.

Ya que tenemos idea de cuál es la información relevante que debemosmodelar, podemos pasar a la fase de reconocimiento de patrones paraadaptar la información que tenemos al formalismo de la lógica dinámicaproposicional. Vamos a presentar únicamente los elementos que nece-sitamos para modelar el movimiento del robot. Para una presentacióncompleta de PDL se puede acudir a [1].

419

wn11

ws11

we11ww

11

wn12

ws12

we12ww

12

wn21

ws21

we21ww

21

wn22

ws22

we22ww

22

f

b

b

f

f

b

b

f

b

f

f

b

b

f

f

b

Figura 4: Movimientos del robot por cuatro celdas: hacia adelante (f ,front) o atrás (b, back). Por claridad, se han omitido las etiquetas l y rde los giros del robot (ver Fig. 3)

Definición 1 (Lenguaje LPDL) Dado un conjunto de variables propo-sicionales P y un conjunto de operaciones básicas A, el lenguaje LPDL

viene dado por las fórmulas ϕ y programas π que se definen mediante lasiguiente gramática,

ϕ :: = > | p | ¬ϕ | ϕ ∧ ϕ | [π]ϕ

π :: = a | ?ϕ | π;π | π ∪ π | π∗

para cualquier p ∈ P y a ∈ A.

Las fórmulas tipo [π]ϕ se leen como “tras ejecutar el programa π

se verifica ϕ”. En cuanto a los programas, cada a ∈ A representa unainstrucción elemental, para nosotros serán los desplazamientos del robot(l, r, f y b). El test ?ϕ comprueba si la fórmula ϕ es verdadera. Dados dosprogramas πi y πj , el programa πi;πj es la concatenación que primeroejecuta πi y después πj . Por otra parte πi ∪ πj consiste en la elecciónno determinista entre πi y πj . Una fórmula como [πi ∪ πj ]ϕ se lee como

420

“tras ejecutar πi o πj , indistintamente, se verifica ϕ”. Finalmente, π∗

representa la ejecución de π un número arbitrario de veces que puede sercero. Se pueden utilizar otras conectivas como ∨ o →. Además, 〈π〉ϕ seinterpreta como ¬[π]¬ϕ.

La semántica de PDL viene dada por modelos de Kripke multimodalesen que cada operación básica a ∈ A está representada por una relaciónde accesibilidad.

Definición 2 (Estructuras PDL) M = (W, 〈Ra〉a∈A, V ) es una es-tructura para LPDL que viene dada por

• W 6= ∅, que es el conjunto de estados.

• Para cada a ∈ A, Ra ⊆W ×W .

• V :P 7→ 2W , es la función de evaluación atómica, que asigna a cadaproposición p ∈ P el conjunto de estados en los que es verdadera:V (p) ⊆W .

Podemos usar la definición 2 para convertir la información de lasfiguras 3 y 4 en un modelo PDL para cualquier tablero por el que vaya amoverse Bee Bot. Por ejemplo:

• Por cada casilla wij del tablero introducimos enW los estados wnij ,

wsij , w

eij y w

wij .

• Para cada una de las cuatro operaciones básicas l, r, f y b, se definela correspondiente relación de accesibilidad. Por ejemplo, si el ta-blero tuviera solo las cuatro celdas de la figura 4, Rf = {(we

11, we12),

(wo12, w

o11), (we

21, we22), (wo

22, wo21), (ws

11, ws21), (wn

21, wn11), (ws

12, ws22),

(wn22, w

n12)}. Si en nuestro modelo hay movimientos prohibido, los

omitiremos de la relación de accesibilidad correspondiente.

• Se pueden introducir variables proposicionales para representar to-da la información necesaria en cada problema. Por ejemplo, si que-remos saber qué orientación tiene Bee Bot, podemos usar las va-riables proposicionales on (norte), os (sur), oe (este), ow (oeste), demodo que, por ejemplo, V (on) = {wn

ij}. Estas variables nos van apermitir verificar en el modelo fórmulas como

on → [(l; l) ∪ (r; r)]os

421

que indica que si el robot está mirando hacia el norte entonces,después de hacer o bien dos rotaciones a la izquierda (l; l) o a laderecha (r; r), se encontrará mirando hacia el sur. También pode-mos introducir variables que indican sobre qué tipo de celda estáel robot, por ejemplo ph puede indicar que está sobre la hierba, peque está en un edificio, etc.

El último paso que debemos abordar es el diseño de algoritmos.Dado que estamos usando PDL, acudimos en primer lugar a su semántica,que nos da los criterios para verificar fórmulas sobre el comportamientode Bee Bot en el tablero que estemos modelando.

Definición 3 (Semántica de PDL) Dada M = (W, 〈Ra〉a∈A, V ), defi-nimos la función [ · ]M , que devuelve tanto los estados de W donde unafórmula es verdadera como los pares de W ×W entre los que se puedeejecutar un programa de LPDL. Se define como

[>]M := W [a]M := Ra

[p]M := V (p) [?ϕ]M := Id[ϕ]M

[¬ϕ]M := W \ [ϕ]M [π1;π2]M := [π1]M ◦ [π2]M

[ϕ1 ∧ ϕ2]M := [ϕ1]M ∩ [ϕ2]M [π1 ∪ π2]M := [π1]M ∪ [π2]M

[[π]ϕ]M := {w ∈W | ∀v((w, v) ∈ [π]M ⇒ v ∈ [ϕ]M )} [π∗]M := ([π]M )∗

donde ◦ es el operador de composición de relaciones y ∗ representa laclausura reflexiva transitiva. Mediante Id[ϕ]M representamos la relaciónidentidad restringida a los estados en que ϕ es verdadera.

Existen herramientas como DEMO [5] que permiten describir un modeloPDL y comprobar la verdad de una fórmula en un cierto estado o en todoel modelo. Un buen ejercicio puede ser representar fórmulas acerca delos recorridos de Bee Bot sobre cierto tablero y verificar que logran losobjetivos planteados. Por ejemplo, podemos verificar que si Bee Bot estáen la biblioteca (pb) mirando hacia el norte (on) entonces puede llegar acasa (pc) moviéndose dos celdas hacia adelante y tres a la derecha,

M |= pb ∧ on → 〈f ; f ; r; f ; f ; f〉pc

Como Bee Bot solo se desplaza hacia adelante y atrás, para moverse ala derecha, primero ha rotado (r) y luego ha avanzado las tres posicio-nes (f ; f ; f). Es importante notar que la fórmula usa 〈f ; f ; r; f ; f ; f〉 y

422

no [f ; f ; r; f ; f ; f ] dado que la semántica de [f ; f ; r; f ; f ; f ]ϕ no requie-re que de hecho exista la posibilidad de ejecutar el programa, sino quede cualquier modo que se ejecute se verificará después ϕ. Sin embar-go, 〈f ; f ; r; f ; f ; f〉ϕ requiere que el programa sea de hecho ejecutable yentonces se verifique ϕ.

Pensamiento computacional en filosofía

Como vimos más arriba, el pensamiento computacional, tal como lo pro-pone Wing, es una habilidad básica para cualquier persona. Tambiénpara el filósofo. Lo que aporta el calificativo de computacional es la ma-nipulación eficiente de la información. Vivimos en la sociedad de la infor-mación, por lo que disponer de herramientas que nos permitan explotareficazmente dicha información resulta de interés para cualquiera. La bio-logía computacional, por ejemplo, es hoy un área de investigación bienestablecida. Es importante estructurar nuestra mente con patrones deresolución de problemas que tengan en cuenta la manipulación eficientede grandes cantidades de información, con las que también nos encon-tramos en las ciencias humanas. El ámbito de las humanidades digitalespretende ser la intersección entre humanidades y computación.

La noción de pensamiento computacional resulta útil como objeto deestudio filosófico. ¿En qué se diferencia de la lógica? ¿Y del pensamientocrítico? Son preguntas interesantes para el análisis epistemológico. Nu-merosas nociones provenientes de la lógica se han convertido en objeto deestudio filosófico, en el campo tradicionalmente conocido como filosofíade la lógica. Del mismo modo, las técnicas y paradigmas del pensamien-to computacional son interesantes problemas para la filosofía. De hecho,desde mediados del siglo xx han aparecido numerosos problemas filosó-ficos que no pueden comprenderse sin disponer de ciertas nociones decomputación. Por poner solo algunos de los ejemplos más conocidos, po-demos pensar en la conocida pregunta de Turing sobre si las máquinaspueden pensar, o la analogía funcionalista entre mente y computador,o el experimento mental de la habitación china de Searle. Es muy di-fícil comprender estos problemas y los argumentos de sus autores sinciertas nociones sobre cómo funciona una computadora. El pensamientocomputacional nos da las claves que los ingenieros utilizan para transfor-

423

mar la resolución de un problema en un conjunto de pasos que puedenser ejecutados por una máquina. Nos enseña que el procesador de esamáquina se limita a ejecutar el programa que le dieron, a través de mi-llares de pequeñas instrucciones que ejecuta una a una sobre los datosde su memoria. ¿Es eso pensar? ¿Funciona así nuestro cerebro/mente?El pensamiento computacional no nos da la respuesta, pero nos ayuda adescubrir lo fascinante de las preguntas.

Referencias

[1] Fischer, Michael J., y Richard E. Ladner [2019]. “Propositional dy-namic logic of regular programs”. Journal of Computer and SystemSciences, 18 (2), 194 - 211.

[2] Kowalski, Robert [1979]. “Algorithm = logic + control”. Commun.ACM, 22 (7), 424-436

[3] Manzano, María [2005]. “La Bella y la Bestia (perdón, lógica e in-formática)”. Summa logicae en el siglo XXI.

[4] Manzano, María y Antonia Huertas [2006]. Lógica para principian-tes. Madrid: Alianza Editorial.

[5] van Eijck, Jan [2004]. Dynamic epistemic modelling (Inf. Téc.).Amsterdam: CWI.

[6] Wing, Jeannette M. [2006]. “Computational thinking”. Commun.ACM , 49 (3), 33–35.