deducción automática en gráficos existenciales

5/7/2018 Deducción automática en Gráficos Existenciales - slidepdf.com

http://slidepdf.com/reader/full/deduccion-automatica-en-graficos-existenciales 1/68

DEDUCCIÓN A UTOMÁTICA EN

GRÁFICOS EXISTENCIALES

D ANIEL B ARAJAS HIGUERA [email protected]

Trabajo de grado para optar por el título deMatemático

Director: Pervys Rengifo RengifoIngeniero Civil Universidad Nacional de Colombia

Docente Facultad de Matemáticas

FUNDACIÓN UNIVERSITARIA

K ONRAD LORENZ

Bogotá, 2003



Agradecimientos

Al profesor Schweitzer Rocuts quien me animó a poner enmacha la idea y colaboró en la fase inicial del proyecto.

Al profesor José Joaquín Valderrama por leer mi trabajo y hacerme algunas valiosas sugerencias para organizar mejor

la estructura del mismo.

A Arnold Oostra y Yuri Poveda quienes meproporcionaron algunos de sus documentos acerca de la

lógica de Peirce e igualmente al Decano de la facultad Antonio Velazco quien además de creer en el proyecto,

facilitó que dichos documentos llegaran a mis manos.

Por ultimo obviamente le agradezco por sus sabiosconsejos al director del trabajo, el profesor Pervys Rengifo,

responsable también de que en el documento incluyeradetalles que pueden hacer más interesante su lectura.



3

Resumen

Se ha desarrollado una herramienta didáctica computacional para el manejo de lasección alfa de los gráficos existenciales. En este documento se presenta inicialmente,una introducción a los enfoques semántico y sintáctico del cálculo proposicional,luego se explica un sistema formal de gráficos existenciales alfa; finalmente se muestracómo la representación del problema y algunos conceptos de inteligencia artificialfueron utilizados para que dicho programa de computador pueda generar deduccionesde forma automática.

Abstract

Automated deduction in existential graphs:

Tool didactic software has been developed for the handling of the alpha section of

existential graphs. In this document it is presented initially, an introduction to thesemantic and syntactic focuses for proposicional calculus, then, a formal system foralpha existential graphs is explained; finally, it is shown how the problem’srepresentation and some Artificial Intelligence concepts were used making thiscomputer program able to generate deductions in an automatic way.



4

Índice General

Introducción ..............................................................................................................5 1 Cálculo proposicional........................................................................................6

1.1 Cálculo proposicional Informal: Semántica..............................................................6 1.1.1 Tablas de verdad.......................................................................................................... 7 1.1.2 Consecuencia Lógica y Equivalencia ........................................................................ 8 1.1.3 Formas normales.......................................................................................................10

1.2 Cálculo proposicional Formal: Sintaxis.................................................................. 11 1.2.1 El Sistema Formal L . ................................................................................................ 11 1.2.2 Metateoremas............................................................................................................. 14

1.3 Completitud y consistencia....................................................................................... 14 1.4 Otros Sistemas deductivos ....................................................................................... 17

1.4.1 Otras Axiomatizaciones............................................................................................17

1.4.1.1 Whitehead-Russell .......................................................................................... 17 1.4.1.2 Frege-Lukasiewicz .......................................................................................... 17 1.4.1.3 Peirce, Wajsberg..............................................................................................18 1.4.1.4 Rosser............................................................................................................... 18 1.4.1.5 Hilbert-Ackermann ........................................................................................ 18 1.4.1.6 Nicod................................................................................................................19

1.4.2 Deducción Natural....................................................................................................19 1.4.3 El principio de Resolución.......................................................................................20

2 Gráficos Existenciales: Alfa.............................................................................22

2.1 Convenciones y reglas para Alfa.............................................................................. 22 2.1.1 Símbolos de los Gráficos Existenciales.................................................................. 22 2.1.2 Reglas de transformación ......................................................................................... 24

2.2 Semántica: Alfa y el Cálculo proposicional............................................................ 26 2.2.1 Proposiciones y conectivos......................................................................................26 2.2.1.1 Verdad y contradicción..................................................................................26 2.2.1.2 Implicación y Negación ................................................................................. 27 2.2.1.3 Conjunción y disyunción ............................................................................... 27 2.2.1.4 Traducción entre Alfa y el CP....................................................................... 29

2.2.2 Valores de verdad......................................................................................................29 2.3 El sistema Formal A ................... .................... ................... .................... .................... 30

2.3.1 Sintaxis ........................................................................................................................ 30 2.3.2 Teorema de la deducción ......................................................................................... 32 2.3.3 Reducción al Absurdo...............................................................................................35

2.4 Completitud y consistencia....................................................................................... 36 2.5 Deducción Natural en Alfa ...................................................................................... 42

2.6 Los Sistemas deductivos Alfa0 y Alfa00................................................................... 43 2.7 Método de decisión ................................................................................................... 45

3 Deducción automática ....................................................................................49

3.1 Representación ........................................................................................................... 50 3.2 Chemotaxis................... ................... .................... ................... ................... .................. 52 3.3 Búsqueda en grafos.................................................................................................... 54

3.3.1 Búsqueda primero en anchura ................................................................................. 56 3.3.2 Búsqueda primero el mejor...................................................................................... 57

3.4 Métodos automáticos de demostración ................................................................. 60

4 Conclusiones ...................................................................................................64



5

Introducción

Una de las inquietudes naturales en el aprendizaje de las matemáticas es la de“aprender a hacer demostraciones”. Para este objetivo no existen ‘recetas’, se logra demodo autodidacta con base en la rectificación de errores. Generalmente el proceso dedescubrimiento de una demostración es exactamente al contrario del proceso lógicodeductivo para presentarla como una demostración organizada, terminada y rigurosa.Los cursos de lógica son escenarios comunes de muchos cursos de informática y dematemáticas en los que se pretende desarrollar este tipo de competencias, tales comoel razonamiento, y el sentido crítico y analítico.

La motivación de este trabajo es la propuesta lógica de Peirce equivalente al cálculoproposicional clásico, es decir, la sección Alfa de los gráficos existenciales que si bienno fue presentada como una teoría formal, cuenta con los mismos elementos y con

ventajas pedagógicas sobre los otros sistemas deductivos formales. Alfa es un sistemalógico con lenguaje y reglas de inferencia sencillas y fáciles de manejar, con laparticularidad que pueden presentarse como algo similar a un rompecabezas en el quemediante la manipulación de gráficos se parte de un estado inicial (hipótesis) parallegar a uno final (conclusión).

Planteado de esta forma se ha desarrollado una herramienta didáctica computacionalpara el manejo de los gráficos existenciales, durante su desarrollo fue también posibleimplementar nociones de Inteligencia Artificial que permitieron que el programa seaun demostrador automático de teoremas. El análisis y diseño del software no ha sidoincluido en el documento porque el autor consideró que no tiene relevancia en unamonografía de matemáticas, sin embargo, se describen algunos conceptos y

experimentos utilizados.

Los gráficos existenciales fueron presentados por Peirce como tres sistemas generalesllamados, respectivamente, “Alfa”, “Beta”, y “Gamma”. La parte Alfa de los gráficosexistenciales es la base del sistema, Beta se construye sobre Alfa y Gamma sobre losotros dos. Este documento sólo se refiere a Alfa, por lo tanto, las convenciones y reglas presentadas son las que corresponden únicamente a este sistema.

Este trabajo pretende al igual que el software ser comprendido por estudiantes deniveles básicos o intermedios de matemáticas o ingeniería; inicialmente se abordan losenfoques semántico y sintáctico del calculo proposicional, la bibliografía básica de la

primera parte ha sido [H AMI81] y [C AIC90]. La segunda parte específicamente serefiere a los gráficos existenciales, en su mayoría basado en el trabajo de Don Roberts[R OBD73] tratando de mantener analogía con lo descrito en la primera parte. En laparte final se describe la representación y nociones de IA utilizadas en el programaque se desarrolló (KLPeirce) y se proponen algunas estrategias de deducción.

Para la presentación de este documento se ha seguido en su mayor parte las normas dela AMS, se hace diferencia entre gráficos existenciales como figuras, en los ejemplos y en la presentación de las convenciones; y gráficos existenciales como fórmulas ográficos bien formados en las demostraciones.



6

1 Cálculo proposicional

En la lógica se estudian los principios y métodos a través de los cuales podemosdeterminar la validez de argumentos, desde el punto de vista de su interpretación odesde el punto de vista de su estructura. En el cálculo de enunciados o deproposiciones los dos puntos de vista son equivalentes y se fundamentan en ladefinición de un lenguaje. La información contenida en las oraciones declarativas queutilizamos en el lenguaje natural es lo que se conoce como proposiciones.

1.1 Cálculo proposicional Informal: Semántica

En un primer acercamiento al cálculo proposicional el objetivo es abstraer la forma delos enunciados y las argumentaciones, con el fin de ver las relaciones entre ellas y definir de forma intuitiva el concepto de argumentación valida. Para ello es necesariodefinir un conjunto de símbolos y unas reglas para la construcción de expresionescorrectas, es decir definir un lenguaje.

Definición 1.1 En el cálculo de proposiciones se utilizan los siguientes símbolos:

• Letras proposicionales: El conjunto infinito enumerable: p, q, r…, p1, p2,p3,..., q 1, q 2, q 3,...

• Conectivos: ¬, ∧, ∨ ,→, ↔, llamados “negación ”, “conjunción ”, “disyunción ”,“condicional” 1 y “bicondicional” respectivamente.

• Signos de Agrupación: Los paréntesis “(” y “)”.

• Constantes proposicionales: Las letras V y F.

Definición 1.2 Una forma enunciativa es una cadena de símbolos que se puede obtenersólo mediante alguna de las reglas siguientes:

1. Cualquier letra proposicional es una forma enunciativa.2. Si α es una forma enunciativa, entonces (¬α ) es una forma enunciativa.3. Si α y β son formas enunciativas entonces ( α∨β ), ( α∧β ), ( α→β) y ( α↔β)

también son formas enunciativas.

El papel de la semántica es el de asociar los elementos de un lenguaje lógico con loselementos de un dominio del discurso. Tales asociaciones las denotamos como

significados . En el cálculo proposicional se relacionan las letras proposicionales conenunciados o afirmaciones. Esta asociación se denomina interpretación. Las evaluacionesde las formas enunciativas en la lógica de proposiciones se basan en valores de verdad,

verdadero y falso, que conforman el dominio semántico.

Definición 1.3 Una interpretación de una forma enunciativa α es una asignación de valores {Verdadero, Falso}, a cada una de las letras proposicionales de α. El valor deuna letra proposicional cualquiera p bajo una interpretación I se denota como ( ) P v

I .

1 También se le llama implicación material.



7

El significado de una forma enunciativa debe ser una función del significado de suscomponentes, se dice que esto es una función de verdad . Específicamente, el valor de

verdad asignado a una forma enunciativa dependerá de la estructura de esa formaenunciativa y de los valores de verdad asignados a las letras proposicionales contenidasen ella.

Definición 1.4 Dada una forma enunciativa P y una interpretación I , el valor de P bajo I (denotado por ( ) P v I ) es:

• Si P es una letra proposicional p, ( ) ( ) pv P v I I =

• Si P es de la forma (¬α ), entonces ( )

=

==

V)(siF

F)(siV

α

α

I

I

I v

v P v

• Si P es de la forma ( α∧β ), entonces ( ) ==

=contrariocasoen F

V)()(siV β α I I

I

vv P v

• Si P es de la forma ( α∨β ), entonces ( ) ===

contrariocasoen V

F)()(siF β α I I

I

vv P v

• Si P es de la forma ( α→β ), entonces ( ) ==

=contrariocasoen V

F)(yV)(siF β α I I

I

vv P v

• Si P es de la forma ( α↔β ), entonces ( ) =

=contrariocasoen F

)()(siV β α I I

I

vv P v

Los conectivos determinan funciones de verdad simples. Si una forma enunciativatiene n variables proposicionales entonces hay 2n maneras en que las letrasproposicionales pueden presentar los valores V y F para esa forma enunciativa. Para

los conectivos binarios existen 16 posibles combinaciones o funciones de verdad.

1.1.1 Tablas de verdad

Dados los valores de las letras proposicionales bajo alguna interpretación se utiliza unatabla de verdad para calcular su valor de verdad para cualquier forma enunciativa bajodicha interpretación. La tabla de verdad es una representación gráfica de una función de verdad .

Sean α y β dos formas enunciativas, las reglas para la construcción de las tablas de verdad para α y β son:

• (¬α ) tiene el valor Falso si α es Verdadero, de lo contrario tiene el valorVerdadero. (¬α ) representa el enunciado “No α” o “No es cierto”.

• ( α∧β ) tiene el valor Verdadero si ambas α y β tienen el valor Verdadero; en otrocaso tiene el valor Falso. ( α∧β ) representa el enunciado “α y β”.

• ( α∨β ) tiene el valor Verdadero si alguna de las dos, o ambas formaenunciativas, tienen el valor Verdadero; en caso contrario tiene el valor Falso. ( α∨β ) representa el enunciado “α o β”.

• ( α→β ) tiene el valor Falso si α tiene el valor Verdadero y a la vez β tiene el valor Falso. En cualquier otro caso tiene el valor Verdadero. ( α→β ) representael enunciado “α implica β” o “si α entonces β”.



8

• ( α↔β ) tiene el valor Verdadero cuando α y β tengan el mismo valor de verdad(ambos Verdaderos o ambos falsos) de lo contrario tiene valor Falso. ( α↔β )

representa el enunciado “α si y sólo si β” .• Los símbolos constantes V y F siempre tienen el valor Verdadero y Falso

respectivamente2.

Observe que estas reglas indican como representar la función de verdad que sepresentó en la definición 1.4. En la Tabla 1.1 se encuentra una implementación de latabla de verdad.

Definición 1.5 Una interpretación satisface una forma enunciativa si a la formaenunciativa le es asignado el valor V bajo dicha interpretación. Una interpretación quesatisface una forma enunciativa es denominada modelo de dicha interpretación.

Definición 1.6 Una forma enunciativa es una tautología si y sólo si tiene un modelopara todas las interpretaciones posibles de las letras proposicionales que la componen3.

Definición 1.7 Una forma enunciativa es una contradicción , si y sólo si ningunainterpretación la satisface. También se dice que dicha forma enunciativa es inconsistente o insatisfacible .

1.1.2 Consecuencia Lógica y Equivalencia

La noción de consecuencia lógica provee un mecanismo robusto para demostrar quesi ciertas proposiciones son ciertas en el mundo, entonces otras proposiciones deinterés (tal vez algunas en las que no pueda determinase su valor de verdad) debenserlo también. Por otra parte las equivalencias son útiles para simplificar o manipularexpresiones.

Definición 1.8 Una forma enunciativa β es una consecuencia lógica de un conjunto deformas enunciativas Γ = {α1, α2, α3,...,αn} si y sólo si para toda interpretación I secumple que si I

v ( α 1 ) = I v ( α 2 )... = V entonces I

v ( β ) = V . Para denotar esto se utilizael símbolo |=4 y se escribe Γ |= β.

α β (α∧β) (α∨β) (α→β) (α↔β)α ¬α V V V V V V

V F V F F V F FF V F V F V V F

F F F F V V

Tabla 1.1 Tabla de verdad proposicional

2 En adelante se escribirá V en lugar de la palabra Verdadero y F en lugar de Falso.3 El símbolo V es una tautología.4 El símbolo |= no hace parte de los definidos para el cálculo proposicional, sirve para referirnos acerca de el cálculo proposicional, por este motivo se dice que es un símbolo del metalenguaje (El lenguaje que seusa para describir otro lenguaje), que en este caso es el español con algunos símbolos.



9

En otras palabras decir que Γ |= β es decir que todo modelo de Γ también es modelode β.

Definición 1.9 Se dice que dos formas α y β enunciativas son lógicamente equivalentes siy sólo si sus valores de verdad son idénticos bajo todas sus interpretaciones, esto sedenota usando el signo ≡5 y se escribe α ≡ β.

Las equivalencias de la Tabla 1.2 se pueden probar mediante tablas de verdad paracualesquiera formas enunciativas α, β y γ. Se consideran como leyes lógicas([GRAS97]). Algunas de estas leyes sugieren que ciertos conectivos se pueden expresaren términos de los demás, por este motivo se puede escoger un conjunto mínimo deconectivos para las formas enunciativas del cálculo proposicional.

Definición 1.10 Un conjunto completo de conectivos es un conjunto de símbolos, tal quetoda función de verdad puede representarse por medio de una forma enunciativa quecontenga solamente los conectivos del conjunto.

Teorema 1.1 Los siguientes son conjuntos completos de conectivos: {¬,∧}, {¬,∨} y { ¬, → }.6▪

Teorema 1.2 Si existe una constante de falsedad F en el alfabeto del cálculoproposicional, {→} es un conjunto completo de conectivos.Demostración: Por teorema anterior se sabe que {¬, →} es completo, pordefinición, F es una constante falsa, y se puede verificar que (¬α ) ≡ ( α→F) paracualquier forma enunciativa.▪

Los conceptos de consecuencia y equivalencia lógica pueden presentarse de maneramás general:

Teorema 1.3 {α1, α2, α3,...,αn} |= β si y sólo si (( α1 ∧ α2 ∧ α3 ∧... ∧ αn )→β )7 es unatautología.Demostración: Por definición {α1, α2, α3,...,αn} |= β si sólo si para toda I

I v ( α 1 ) = I v ( α 2 )... = V entonces I v ( β ) = V. De acuerdo a la definición de interpretación

de la conjunción I v ( α1 ∧ α2 ∧ α3 ∧... ∧ αn ) = V si y sólo si I

v ( α 1 ) = I v ( α 2 )... = V,

luego I v (( α1 ∧ α2 ∧ α3 ∧... ∧ αn )→β ) = V si I

v ( α1 ∧ α2 ∧ α3 ∧... ∧ αn ) = V y

I v β = V por definición de la implicación para toda interpretación I, entonces

I v (( α1 ∧ α2 ∧ α3 ∧... ∧ αn )→

β ) debe ser una tautología.

5 ≡ también hace parte del metalenguaje.6 Demostración en [C AIC90] p 76 y [H AMI81] p 28.7 Se asumirá que ( α1 ∧ α2 ∧ α3 ) es una forma provisional y mas conveniente de escribir (( α1 ∧ α2 ) ∧ α3 ),porque pueden suprimirse paréntesis por la ley asociativa.



10

Identidad( α∧ V) ≡ α

( α∧F) ≡ F

( α∨ V) ≡ V

( α∨ F) ≡ α

Idempotencia ( α∧α ) ≡ α ( α∨α ) ≡ α

Absorción( α∧( α∨β )) ≡ α

( α∨ ( α∧β )) ≡ α

Leyes conmutativas.( α∧β ) ≡ ( β∧α )

( α∨β ) ≡ ( β∨α )

Leyes Asociativas8:(( α ∨ β ) ∨ γ ) ≡ ( α ∨ ( β ∨ γ ))(( α ∧ β ) ∧ γ ) ≡ ( α ∧ ( β ∧ γ ))

Leyes Distributivas( α ∧ ( β ∨ γ )) ≡ (( α ∧ β ) ∨ ( α ∧ γ ))( α ∨ ( β ∧ γ )) ≡ (( α ∨ β ) ∧ ( α ∨ γ ))

Doble Negación (¬(¬α )) ≡ α

Leyes de DeMorgan(¬( α∧β )) ≡ ((¬α ) ∨ (¬β ))(¬( α∨β )) ≡ ((¬α ) ∧ (¬β ))

Leyes de Reducción

( α→β ) ≡ ((¬α )∨β )( α↔β ) ≡ (( α→β )∧( β→α ))

( α↔β ) ≡ (((¬α )∨β )∧( α∨(¬β )))

Tabla 1.2 Leyes lógicas

Teorema 1.4 α ≡ β si y sólo si ( α↔β ) es una tautología.Demostración: Por definición I

v ( α↔β ) = V si y sólo si I v ( α ) = I

v ( β ), por otrolado α ≡ β si y sólo si sus valores de verdad son idénticos bajo todas sus

interpretaciones, por lo tanto I v

( α↔β

) = V para toda interpretación I , luego ( α↔β

)es una tautología.

1.1.3 Formas normales

Para las expresiones lógicas existen formas enunciativas estándar que hacen más sencilla la

identificación y comparación de formas enunciativas. Estas expresiones se denominan

formas normales .

Definición 1.11 Sea α una forma enunciativa, se dice que α es un literal si es una letra

proposicional o es la negación de una letra proposicional. Una cláusula es una disyunción

de literales.

Definición 1.12 Una forma enunciativa está en Forma Normal Conjuntiva (FNC) si es una

conjunción α1∧...∧αn, dónde cada αi es una disyunción de literales. Una forma enunciativa

está en Forma Normal Disyuntiva (FND) si es una disyunción α1 ∨... ∨ αn, donde cada αi es

una conjunción de literales.

Para la traducción de formas enunciativas a formas normales se utilizan las equivalencias

lógicas expresadas como leyes en la Tabla 1.2.

8 Incluso se podría prescindir de los paréntesis y escribir α ∧ β ∧ γ o α ∨ β ∨ γ.



11

Teorema 1.5 Toda forma enunciativa que no sea contradicción puede transformarse en

otra equivalente en FNC (FND)9.▪

Las cláusulas son un tipo especial de formas enunciativas. El teorema 1.5 garantiza que

toda forma enunciativa se puede expresar como la conjunción de cláusulas. Este tipo

especial de formas enunciativas se utilizan para representar el conocimiento en

computadoras, usando la resolución10, para deducir o inferir nuevos enunciados.

1.2 Cálculo proposicional Formal: Sintaxis

Así como semánticamente el concepto clave es el de “interpretación” , sintácticamente el

concepto a desarrollar es el de “demostración” que está más ligado con el concepto derazonamiento y es lo que en [T ARS68] se denomina como metodología de lamatemática. Un razonamiento es una secuencia de argumentos que nos permitensostener la verdad de una afirmación (conclusión) a partir de otras (premisas). La

validez de una deducción lógica no depende en absoluto de ningún significadoespecial que pueda estar asociado con los términos. La lógica es algo totalmenteabstracto y formal; abstracto, porque las afirmaciones lógicas pueden ser hechas enprincipio sobre cualquier objeto, sin estar esencialmente circunscritas a undeterminado conjunto de objetos o propiedades del objeto; y formal, porque la validezde las demostraciones lógicas se asienta en la estructura de las afirmaciones más queen la naturaleza especial de su contenido.

Para especificar todo sistema formal se requieren los siguientes elementos:1. Un conjunto enumerable de símbolos, o alfabeto.2. Un conjunto de cadenas finitas de los símbolos que componen el alfabeto, a

estas cadenas se les llama fórmulas bien formadas (fbfs).3. Un conjunto especial de fórmulas bien formadas, estos son los axiomas del

sistema formal.4. Un conjunto de reglas de inferencia, es decir, reglas que permiten obtener o

deducir nuevas fórmulas a partir de otras fórmulas bien formadas.

1.2.1 El Sistema Formal L.

Para el cálculo de proposiciones especificaremos un sistema formal llamado L 11.

Definición 1.13 (Alfabeto) 12 El alfabeto del sistema formal L consiste de los siguientessímbolos ¬,→, (, ), p1, p2, p3, ...

9 En [H AMI81] se presenta como el colorario de otro teorema junto con la demostración.10 Estos temas se abordaran más adelante.11 L por Lukasiewicz, este sistema formal es el definido en [H AMI81]12 En [BURR 01], el alfabeto se especifica con un conjunto de conectivos, un conjunto de variablesproposicionales y un conjunto de constantes proposicionales.



12

Definición 1.14 (Sintaxis) El conjunto de fórmulas bien formadas de L está dadopor:

1. pi es una fbf para todo i ≥ 1.2. Si α y β son fbfs entonces (¬α ) y ( α→β ) son fbs.

Con el fin de simplificar la escritura, se introducen las convenciones siguientes para ellenguaje13 de L : Inicialmente, se adoptará una convención para la supresión deparéntesis: se omitirá el uso de paréntesis externos; de la misma forma se escribirá ¬α en lugar de (¬α ) y α→β en lugar de ( α→β ), luego, se define que ¬ se aplica a lafórmula más corta y cercana a este signo, es decir, ¬α→β abrevia ((¬α )→β ). Losparéntesis sólo se utilizarán para evitar ambigüedades, por ejemplo: si se quiereescribir (¬ ( α→β )) son necesarios los paréntesis: ¬( α→β ).

Definición 1.15 (Axiomas) Para cualesquiera fbfs α,β y γ, las fbfs siguientes sonaxiomas de L :

(L1) α → ( β → α )(L2) ( α → ( β → γ )) → (( α → β ) → ( α →γ ))(L3) ( ¬α → ¬β ) → ( β → α )

Los axiomas de un sistema formal no necesariamente deben ser los anteriores, laelección se hace de una forma más bien arbitraria; se establecen en este caso esquemasde axiomas, es decir, que los símbolos α,β y γ pueden reemplazarse por cualquierfbf 14.

En el sistema formal L sólo existe una regla de inferencia:

Definición 1.16 (Regla Modus Ponens) De las fórmulas bien formadas α y α→β,se obtiene la nueva fórmula bien formada β. Esta regla de deducción se denota deforma abreviada por MP.

Una forma usual de escribir una regla de inferencia es la siguiente:

α → β

α ____ β

o también α, α → β |− β

Una regla de inferencia puede ser vista como un par ordenado cuyo primer elementoes un conjunto de fórmulas (las premisas), y el segundo elemento es una nuevafórmula, la conclusión de la regla. El uso de las reglas de inferencia es fundamentalpara la deducción formal.

13 Note que no hacen parte del lenguaje de L los símbolos ∨, ∧,↔ y ni siquiera se han definido lossímbolos ¬,→ como conectivos, ni se han relacionado con algún significado.14 Al definir esquemas de axiomas no es necesaria la regla de sustitución que en [H ILB59] se define comouna regla de inferencia.



13

Definición 1.17 Una sucesión finita de fbfs α1, α2,...αk se llama una deducción formal odemostración si cada αi (1 ≤ i ≤ k), es un axioma proposicional o resulta de fórmulas

anteriores por la aplicación de la regla de deducción MP.

Definición 1.18 Una fbf es un teorema si aparece como la última fórmula de unadeducción formal.

En otras palabras una deducción o prueba es una sucesión finita de fbfs tal que cadauna es una axioma o una consecuencia directa de una de las fbfs precedentes pormedio de las reglas de inferencia. Un teorema es una fórmula bien formada para lacual existe una prueba.

Ejemplo 1.1 ¬β →( β→α ) es un teorema de L

Demostración: 15

(1) ((¬α→ ¬β )→ ( β→ α )) → (¬β→((¬α→ ¬β )→ ( β→ α ))) ( L1 )

(2) ( ¬α→ ¬β )→ ( β→α ) ( L3 )

(3) ¬β→((¬α→ ¬β )→ ( β→ α )) 1, 2 MP

(4) ( ¬β → ((¬α→¬β )→ ( β→ α )))→ ((¬β → (¬α→¬β ) )→ (¬β→( β→ α ))) ( L 2)

(5) (¬β → (¬α→¬β ) )→ (¬β→( β→ α )) 3, 4 MP

(6) ¬β→(¬α→¬β ) ( L 1)

(7) ¬β →( β→α ) 5, 6 MP

▪

Definición 1.19 Sea Γ un conjunto de fbfs de L (No necesariamente axiomas de L ).Una sucesión finita α1, α2,...αk de fbfs de L se llama una deducción a partir de Γ si cada αi

(1 ≤ i ≤ k) es un axioma proposicional, o αi pertenece a Γ, o αi se deducedirectamente de dos miembros de la sucesión aplicando MP.

Una deducción a partir de Γ es una demostración en la cual los miembros de Γ seconsideran temporalmente como axiomas. Si una fbf α es el último miembro de unademostración a partir de Γ, se dice que α es una consecuencia de Γ en L y se escribeΓ |−L α. Un teorema de L es una deducción a partir de un conjunto vacío de premisasy se denota como |−L α. Cuando la referencia a un sistema sea obvia se utilizará elsímbolo16 |− en lugar de |−R para un sistema R en particular.

Ejemplo 1.2 ¬¬α |−L α

Demostración.(1) ¬¬α Premisa

(2) (¬¬α )→((¬¬¬¬α )→(¬¬α )) ( L 1)

(3) (¬¬¬¬α )→(¬¬α ) 1,2 MP

(4) ((¬¬¬¬α )→(¬¬α ))→((¬α )→(¬¬¬α )) ( L 3)

(5) (¬α )→(¬¬¬α ) 3,4 MP

(6) ((¬α )→(¬¬¬α ))→((¬¬α )→α ) ( L 3)

(7) (¬¬α )→α 5,6 MP

15 En una demostración se escriben las fbfs que la conforman en el orden que se obtienen junto con larazón por la cual se escriben.16 Los símbolos |−L y |− no pertenecen al alfabeto de L. Estos hacen parte del metalenguaje.



14

(8) α 1,7 MP

▪

1.2.2 Metateoremas.

Los siguientes teoremas permiten que la labor de realizar una demostración sea menosardua, por ser teoremas acerca del cálculo proposicional se les denominametateoremas.17

Teorema 1.6 (Deducción) Sean α y β dos fbfs de L y Γ un conjunto (posiblemente vacío) de fbfs de L . Si Γ U {α} |− β entonces Γ |− (α→β).18

Por tanto, si se quiere demostrar una fbf que sea de la forma α→β, bastará con anexar

α a las premisas y deducir β, note que si se desea demostrar un teorema el conjuntode premisas inicialmente es vacío, y la demostración se simplifica de la misma manera.El teorema de la deducción generalmente se denota como (TD).

Teorema 1.7 (Reducción al absurdo) Sean α y β dos fbfs de L y Γ un conjunto defbfs. Si Γ, ¬α |− β y Γ, ¬α |− ¬β entonces Γ |− α.19

1.3 Completitud y consistencia

Como se ha observado el lenguaje de L es prácticamente el mismo que el del enfoque

semántico del cálculo proposicional, las formas enunciativas son las mismas fbfs de L ;se ha hecho contraste en llamarlas formas enunciativas y fórmulas bien formadas encada caso para diferenciar los dos enfoques, sin embargo, existe una estrechainterrelación entre ellos, interrelación que culmina con los teoremas de completitud y

validez en los que se demuestra que al menos para el cálculo de proposiciones losresultados sintácticos y semánticos son realmente los mismos.

En el lenguaje de L se utilizan sólo los símbolos ¬ y → como conectivos, sin embargose pueden anexar al alfabeto los demás conectivos.

Definición 1.20 Sean α y β fbfs, los símbolos ∧, ∨, ↔ hacen parte del alfabeto de L y se utilizan para escribir de forma abreviada fbfs de la siguiente forma20:

• α∧β := ¬( α → ¬β )• α∨β := ¬α → β • α↔β := ¬(( α→β )→ ¬( β→α ))

17 Su demostración se encuentra en [C AIC90] y [H AMI81].18 El reciproco de este teorema es fácil de demostrar usando MP porque si Γ |− (α→β), puede deducirseβ al añadirse α como premisa.19 De forma similar se anexa a las premisas la negación de la conclusión y se trata de obtener una fbf y sunegación, es decir una contradicción. Note que no se han introducido aún los términos negación y contradicción en L , se ha insinuado de manera intuitiva la relación con el enfoque semántico del cálculoproposicional.20 El símbolo := traduce ‘es una forma más conveniente de escribir’.



15

Ahora se va a introducir en el sistema formal L las nociones de función de verdad y

tautología con el fin de relacionar L con lo expuesto en 1.1.

Definición 1.21 Una valuación de L es una función v cuyo dominio es el conjunto defbfs de L y su rango es el conjunto {V,F}, tal que para fbfs cualesquiera α, β de L :

1. v ( α ) ≠ v (¬α )2. v ( α→β ) = F si y sólo si v ( α ) = V y v ( β ) = F.

Definición 1.22 Una fbf α de L es una tautología si y sólo si para toda valuación v , v ( α )= V. Se escribe |= α.

Como se puede observar por los teoremas 1.3 y 1.4, semánticamente el objetivo delcálculo de proposiciones es verificar tautologías. El teorema de validez21 asegura queen L sólo se deducen tautologías.

Teorema 1.8 (Validez) Todo teorema de L es una tautología.▪

También se puede afirmar que en L se deducen todas las tautologías. Un sistema en elque se deducen todas las tautologías es deductivamente completo.

Teorema 1.9 (Completitud) Si α es una fbf de L y |= α entonces |−L α.▪

En resumen para el sistema formal L se cumple:

Teorema 1.10 |= α si y sólo si |−L α.▪

Para introducir el concepto y la importancia de la consistencia en un sistemadeductivo, la expresión en la que se asegura que de una contradicción se puedededucir cualquier cosa, es un teorema común en este tipo de sistemas formales.

Teorema 1.11 α,¬α |−L βDemostración:

(1) α Premisa

(2) ¬α Premisa

(3) ¬α→

(¬β→

¬α ) ( L 1)(4) (¬β→¬α )→( α→β ) ( L 3)

(5) (¬β→¬α ) 2,3 MP

(6) α→β 4,5 MP

(7) β 1,6 MP

▪

Si se hubiera obtenido de alguna manera α y ¬α, por la demostración anterior seobtiene β, pero β es cualquier fbf. Un sistema en el que se deduce cualquier fbf pierde

21 Este teorema también se conoce con los nombres de ‘corrección’ o ‘solidez’ (soundness en inglés).



16

total utilidad e interés, ya que el conjunto de fbf sería el mismo que las fbf deduciblesen el sistema, y por lo tanto no aporta ninguna información. Esto se conoce como “el

argumento de trivialización”22. Por este motivo es indispensable garantizar que unsistema formal sea consistente23.

Definición 1.23 Un sistema formal L es consistente si no existe una fbf α de L tal que

α como ¬α sean teoremas de L .

Teorema 1.12 L es consistente.Demostración: Por teorema de validez, todo teorema de L es una tautología. Comola negación de una tautología no puede ser una tautología, es imposible que exista unafbf α tal que ambas, α y ¬α sean teoremas de L .▪

Definición 1.24 Un sistema formal T es decidible si existe un procedimiento paradeterminar si una arbitraria fbf es un teorema o no. Si no existe tal procedimiento sedice que es T indecidible .

Teorema 1.13 L es decidible.Demostración: Para decidir si una fbf α es o no teorema de L basta considerarlacomo forma enunciativa y verificar si es una tautología construyendo su tabla de

verdad.▪

Por ultimo en la Tabla 1.3 presentamos un paralelo entre las definiciones semánticas y del sistema formal L, que son equivalentes.

Enfoque semántico Enfoque sintácticoUna forma enunciativa es una tautologíasi es verdadera con cualquierinterpretación.

Una fbf es un teorema si existe unademostración de ella a partir de losesquemas axiomáticos.

Una forma enunciativa es unacontradicción si es falsa con cualquierinterpretación.

Una fbf es una contradicción si sunegación es un teorema.

Una forma enunciativa β es unaconsecuencia lógica de un conjunto Γ deformas enunciativas, si es verdadera bajotodas aquellas interpretaciones en lascuales todas las formas enunciativas de Γ

son verdaderas.

Una fbf β es deducible de un conjunto defbfs Γ si existe una demostración de β apartir de los axiomas y de Γ.

Dos formas enunciativas son equivalentessi son verdaderas exactamente en lasmismas interpretaciones.

Dos fbf α y β son lógicamenteequivalentes si α es demostrable a partirde β y viceversa.

Tabla 1.3 Definiciones

22 En [BOBM96]] se presenta la reseña histórica acerca del argumento de trivialización y de las pruebas deconsistencia del cálculo proposicional que realizaron Post y Hilbert por separado.23 En [H AMI81] y en [CHUR 56] se presenta primero la prueba de consistencia del cálculo proposicional y con base en esta se realiza la prueba de completitud.



17

1.4 Otros Sistemas deductivos

El sistema deductivo formal L no es el único enfoque sintáctico que se ha presentadopara el cálculo proposicional. Los diferentes sistemas que mencionaremos acontinuación tienen en común ser deductivamente completos y consistentes([K RAU01]). Los métodos de deducción natural y resolución tienen la particularidad deno contar con axiomas, además cuentan con más reglas de inferencia y algunasrestricciones.

1.4.1 Otras Axiomatizaciones

Durante el siglo XX se presentaron diferentes sistemas formales del cálculoproposicional. El lenguaje de cada uno es prácticamente el mismo que el de L , con ladiferencia en los conectivos que se proponen como primitivos24, al igual que en L losdemás conectivos se utilizan para escribir de forma abreviada algunas fbfs.

1.4.1.1 Whitehead-Russell

Este sistema fue propuesto originalmente por Whitehead y Russell en la primeraedición de Principia Mathematica , los conectivos primitivos son ¬ y ∨ e incidentalmenteutilizan el símbolo → como una abreviación. α→β es una forma más conveniente deescribir ¬α∨β.25 Los axiomas son los siguientes, expuestos por Hilbert y Ackermannen [HILB59],con las reglas de sustitución26 y Modus Ponens como reglas de inferencia.

1. α∨α → α 2. α → α∨β 3. α∨β → β∨α 4. ( α→β ) → ( γ∨α → γ∨β )

Originalmente Whitehead y Russell usaban un quinto axioma:α∨( β∨γ ) → β∨ ( α∨γ )

que Bernays27, demostró en 1926 que es innecesario.

1.4.1.2 Frege-Lukasiewicz

Originalmente Frege propuso los siguientes seis axiomas con los conectivos ¬ y → como primitivos y las mismas reglas de inferencia que el anterior.

1. α → ( β → α )2. ( α → ( β → γ )) → (( α → β ) → ( α → γ ))3. ( α → ( β → γ )) → ( β → ( α →γ ))

24 Dichos símbolos deben ser un conjunto completo de conectivos.25 Observe que para L se ha definido α∨β como una forma más conveniente de escribir ¬α→β.26 La regla de sustitución dice que toda letra proposicional puede ser reemplazada por cualquier fbf encada una de sus ocurrencias. Esta regla no es necesaria cuando se utilizan esquemas de axiomas.27 Axiomatische Untersuchung des Aussagenkalküls der Principia Mathematica.



18

4. ( α → β ) → ( ¬β → ¬α )5. ¬¬α → α

6. α → ¬¬α

J. Lukasiewicz mostró que los últimos 4 axiomas pueden ser reemplazados por:( ¬α → ¬β ) → ( β → α )

Dejando como resultado al mismo sistema L 28 .

1.4.1.3 Peirce, Wajsberg

Originalmente Peirce propuso en 188529 este sistema usando sólo → como conectivoprimitivo y las siguientes fbfs que llamó “icons”.

1. p→

p2. (p→ (q →r))→ (q → (p→r))3. (p→q) → ((q →r) → (p→r))4. ((p→q)→p)→p 30

En [ZEMJ64] aparece referenciado el siguiente sistema que además utiliza el símbolofalso constate ∅, regla de inferencia MP y los siguientes axiomas31:

1. (p→q) → ((q →r) → (p→r))2. ((p→q)→p)→p3. p→ (q →p)

4. ∅ → p

1.4.1.4 Rosser

En este sistema los conectivos primitivos son ¬ y ∧ , regla de inferencia MP, α→β esuna forma abreviada de escribir ¬( α∧¬β ), sus axiomas son:

1. α→(α∧α )2. ( α∧β )→α 3. ( α→β )→(¬( β∧γ )→¬( α∧γ )

1.4.1.5 Hilbert-Ackermann

En [HILB59] también se propone un sistema con un único axioma y seis reglas deinferencia, estas reglas son métodos de manipulación de fbf usando FNC. El sistema

28 Este sistema también es presentado en [CHUR 56] como el sistema P2.29 [S TUD97], Peirce’s influence on logic in Poland. C-calculus.30 Se conoce como la ley de Peirce31 Están escritos originalmente en notación polaca:

1. CCpqCCqrCpr2. CCCpqpp3. CpCqp4. C∅p



19

es presentado como dos conjuntos de reglas, las primeras las denominan reglas paratransformación de expresiones lógicas:

a1) Cálculos con los símbolos ∧ y ∨ cumplen las leyes asociativas, conmutativas y distributivas, como en álgebra.

a2) ¬¬α se puede sustituir por α (y viceversa).a3) Se puede reemplazar ¬α∨¬β por ¬( α∧β ), y ¬α∧¬β por ¬( α∨β ) (y

viceversa).a4) Se puede sustituir ¬α∨β por α→β, y (¬α∨β )∧(¬β∨α ) por α↔β (y

viceversa).

Las siguientes reglas se utilizan entonces para determinar cuando una expresión enforma normal representa una combinación lógicamente verdadera de enunciados (lo que seconoce como tautología):

b1) α∨¬α es lógicamente verdadera.b2) Si α es cierto, y β representa una fbf cualquiera, entonces α∨β es cierto.b3) Si α es cierto y β es cierto, entonces α∧β es cierto.

Tal como fueron presentadas, estas reglas pueden considerarse como un método dedecisión, los autores presentaron estas reglas antes de referirse a sistemas deductivosformales, sugieren después de presentar el sistema Whitehead-Russell, que puedeconsiderarse lo anterior como un sistema deductivo con el axioma α∨¬α y seis reglasde inferencia.

1.4.1.6 Nicod

Este sistema utiliza como único conectivo primitivo el símbolo de Sheffer “|”, querepresenta la función de verdad conocida como NAND. Se puede decir que α|β esuna forma mas conveniente de escribir ¬( α∧β ), de acuerdo con [ K NEA84 ] Nicodmostró en 1917 que el cálculo proposicional puede derivarse del único axioma:

• ( α|( β|γ )) |(( δ|( δ|δ ))|(( ε|β )|(( α|ε )|( α|ε ))))

y la regla: α, α|( β|γ ) |− γ.

Si se utiliza ¬ y → como conectivos primitivos, se obtiene un sistema equivalente conregla de inferencia MP y el axioma:

• (((( α→β )→(¬γ→ ¬δ ))→γ )→ ε ) → (( ε→α )→ ( δ→α ))

1.4.2 Deducción Natural

Es un método constructivo de prueba que se asemeja a las demostraciones habituales.Sus características principales son que no contiene axiomas y en el alfabeto se incluyenlos conectivos ¬,→,∨, ∧. El sistema G de deducción natural de Gentzen se basa enocho reglas de inferencia básicas, dos (una de introducción y una de eliminación) porcada uno de los conectivos. Estas reglas están resumidas en la Tabla 1.4.



20

α .β ____

α ∧ β

_ α ____ α ∨ β

(TD)32 (IC) (ID) (RA)33

α → β

α ____

β

_ α ∧ β __

α

_¬¬α _

α

(MP) (EC) (ED) (EN)

Tabla 1.4 Reglas de inferencia para G

En el caso de la reglas TD y RA lo que se hace es una subprueba asumiendotemporalmente como premisas el antecedente de la implicación.

Ejemplo 1.3 p→(q → r), p → ¬r |−G p→ ¬q Demostración:

(1) p→(q→ r) Premisa

(2) p→ ¬r Premisa

(3) p Premisa temporal(4) q Premisa temporal

(5) ¬r 2,3 MP

(6) q →r 1,3 MP

(7) r 4,6 MP

(8) r ∧ ¬r 5,7 IC

(9) ¬q 4,8 RA

(10) p→ ¬q 3,9 TD

▪

1.4.3

El principio de Resolución

Este sistema deductivo se aplica solamente a un tipo especial de fbfs, las fbf que seencuentran en FNC. Dado que el Teorema 1.5 garantiza que todas las fbfs del cálculoproposicional pueden llevarse a FNC, para hacer una demostración se requiere quepreviamente se trasformen las fbfs en una FNC. Llamaremos a este sistema deductivoR .

32 El teorema de la deducción que en L es un metateorema aquí como una regla de inferencia.33 Igualmente se introduce reducción al absurdo como una regla de inferencia, también se conoce comointroducción de la negación (IN).



21

Definición 1.25 Una fórmula está en Forma Clausal si es un conjunto de cláusulas (disyunción de literales).

Ejemplo 1.4 (¬ p∨ q) ∧ (¬ p∨ q ∨ r) ∧ p se escribe en forma clausal:{¬p∨ q, ¬p ∨ q ∨ r, p}.

En el alfabeto de R se incluye una constante ⊥ (Falso) Al igual que el sistema dededucción natural no hay axiomas, sólo existen dos reglas de inferencia.

D1 ∨ p∨ D2

D3 ∨ ¬p∨ D4

D1 ∨ D2 ∨ D3 ∨ D4

p¬p

⊥

D1 ∨ p∨ D2 ∨ p∨ D3

D1 ∨ D2 ∨ p∨ D3

Corte (C) Simplificación (S)

Tabla 1.5 Reglas de inferencia para R

El método de resolución es válido, o sea que si Γ |−R D entonces Γ |= D pero no escompleto, sin embargo se ha demostrado que Γ es insatisfacible si y sólo si Γ |−R ⊥.De esta manera para hacer una demostración por el método de resolución, basta conagregar la negación de la conclusión a las premisas y deducir⊥.

Ejemplo 1.5 p→q, q →r |− p→r

Inicialmente se manipulan las fbfs originales utilizando equivalencias lógicas parahallar las FNC y la forma clausal de las premisas y la negación de la conclusión.

p→q ≡ ¬p ∨ q que en forma clausal se escribe {¬p ∨ q }

q →r ≡ ¬q ∨ r que en forma clausal se escribe {¬q ∨ r }

¬( p→r) ≡ ¬(¬p∨r) ≡ p ∧ ¬r que en forma clausal se escribe {p , ¬r }

Ahora se debe demostrar que ¬p ∨ q,¬q ∨ r ,p , ¬r |−R ⊥

Demostración:

(1) ¬p ∨ q Premisa(2) ¬q ∨ r Premisa(3) p Premisa

(4) ¬r Premisa(5) q 1,3 C(6) ¬q 2,4 C(7) ⊥ 5,6 C

▪



22

2 Gráficos Existenciales: Alfa

Dentro de la obra de C. S. Peirce se encuentran un gran número de referencias acercade algunos sistemas de ‘lógica gráfica’. Estos son sus sistemas de “Gráficos deEntidades” y “Gráficos Existenciales”. Los primeros fueron un intento que fueabandonado en favor de los gráficos existenciales.

Peirce define “gráfico” como “la expresión proposicional en el Sistema de GráficosExistenciales de cualquier posible estado del universo” ([ZEMJ64]). Los gráficosexistenciales son pensados entonces por Peirce para ser sistemas de “proposiciones” o“aserciones”.

2.1 Convenciones y reglas para Alfa

La presentación de Alfa fue dada en dos partes, en la primera aparecen cincoconvenciones que se pueden considerar las reglas de formación del sistema, y lasegunda se presentan las reglas de transformación, esto son instrucciones para obtenerun gráfico a partir de otro.

2.1.1 Símbolos de los Gráficos Existenciales

Previamente se toma una superficie (papel, tablero, etc.): Es lo que Peirce denomina

“hoja de aserción” (HA). HA se considera como un gráfico y representa lo que sedenomina “universo del discurso”. Cualquier parte en blanco de HA es un gráfico.

Escribir una instancia de gráfico34 sobre la HA35 es llamada la inscribir un gráfico, loque significa afirmar que es verdadero; su localización sobre HA es irrelevante ( Figura

2-1 ).

De la misma forma inscribir dos o más gráficos sobre HA es afirmar que al mismotiempo todos son verdaderos en el universo representado por HA, el orden no esrelevante( Figura 2-2 ).

Figura 2-1 “ϕ es verdadero”

34 Peirce hace distinción entre los términos “gráfico” (‘graph’) e “instancia de gráfico” (‘graph-instance’)una “instancia de gráfico” es cada una de las ocurrencias de lo que se denomina un gráfico que se puedeconsiderar un tipo (o clase).35 Usualmente se omite el dibujo de HA.



23

“ϕ y ψ son verdaderos” “ψ, β y ϕ son verdaderos”

Figura 2-2 Yuxtaposición

Para la siguiente convención se introduce un nuevo símbolo para representar laimplicación material que Peirce denota como “scroll” dos líneas cerradas36, una dentrode la otra ( Figura 2-3 )37.

La idea de la utilización de líneas para separar los elementos de la implicación de HA

la expresa Peirce ([THIB81])“… el consecuente de una proposición condicional afirmalo que es verdadero no en el universo entero de de las posibilidades consideradas, sinoen un universo subordinado circunscrito al antecedente”38. Cada línea del scroll sedenomina como “corte” (cut o sep), y el interior del mismo se llama área (‘area’ o‘close’). En la Figura 2-4 se encuentra un ejemplo de como se representa “Si ϕ entonces ψ”.

Posteriormente expresa la forma de representar la negación de un gráfico, para ello seintroduce un nuevo símbolo: “El relleno de una superficie con cualquier material deescritura que se pueda usar (tiza, tinta, etc.) se dice que obstruye esa superficie y seentiende como la expresión de un pseudográfico ( Figura 2-5 ) sobre esta superficie, el

pseudo-gráfico en sí mismo no es un gráfico y representa un estado imposible de lascosas”39. En ocasiones Peirce representaba el pseudo-gráfico sin relleno.

Figura 2-3 Scroll

Figura 2-4 “Si ϕ entonces ω”

36 Peirce manifestaba que él pensaba primero en que en ([R OBD73]).37 En [THIB82] se le llama ‘voluta’38 Una figura que Peirce utilizó que lo expresa de forma más natural es similar a la siguiente:

sin embargo por comodidad se utilizarán curvas no tangentes. 39 [THIB81] y [SOWA14].



24

Figura 2-5 Pseudográfico

“ϕ es verdadero” “ϕ es falso” “Es falso que ϕ sea falso”

Tabla 2.1 El corte y la falsedad

Dado que el corte es una separación de HA el interior de un corte es falso, si ungráfico se inscribe allí, también lo es, en otras palabras, cualquier cosa inscrita en HAes afirmada y si es encerrada por un corte simple, es negada (Ver Tabla 2.1 ).

En resumen las convenciones presentadas para Alfa son:(C1) La hoja de aserción en todas sus partes es un gráfico.(C2) Cualquier cosa escrita sobre la hoja de aserción es aseverada como verdad

del universo representado por esa hoja.(C3) Gráficos inscritos sobre diferentes lugares de la hoja de aserción son

todos acertados como verdaderos.(C4) “Scroll” es el signo del condicional.(C5) El corte vacío es el pseudo-gráfico; y el corte precisamente niega su

contenido.

2.1.2 Reglas de transformación

Puesto que el propósito de los gráficos existenciales es representación delrazonamiento, Peirce propone unas reglas para la modificación de premisas quepermiten obtener conclusiones válidas, las denota como modificaciones permitidas opermisos. Para denotar que un gráfico ψ es el resultado de aplicar una reglas detransformación sobre otro ϕ se usará el símbolo |− y se escribe ϕ |− ψ. Cuando latransformación es reversible puede escribirse ϕ ≡ ψ.

El primer permiso se conoce como inserción-eliminación ( Figura 2-6 ): Se puede borrarcualquier gráfico sobre una superficie dada, si está cercada por un número par decortaduras, y, se puede inscribir un nuevo gráfico sobre un área cercado por un

número impar de cortaduras.

|−Inserción

|−Eliminación

Figura 2-6 Ejemplo de inserción-eliminación



25

|− 40 Iteración

|−Desiteración

Figura 2-7 Ejemplo iteración desiteración

La siguiente regla conocida como iteración establece que un gráfico puede ser repetidoen la misma superficie o sobre una superficie cercada por un número superior de

cortaduras41

, el proceso inverso lo denominó como desiteración ( Figura 2-7 ).

El tercer permiso se llama regla de doble corte. El doble cerramiento es la figura formadapor dos cortaduras encajadas una en la otra, si no hay nada escrito sobre la superficiecomprendida entre las dos cortaduras.

La regla de doble corte establece que este doble cerramiento puede estar situadoalrededor de todo gráfico, así como puede borrarse de la superficie en que se presenta(Ver Figura 2-8 y Figura 2-9 ).

Las reglas de inserción y eliminación no son reversibles, se consideran como reglas deinferencia, es decir, una vez se elimina un gráfico no puede obtenerse por inserción y

viceversa. Las reglas de iteración-desiteración y doble corte se consideran más quecomo reglas de inferencia, reglas de equivalencia.

Figura 2-8 Doble cerramiento

≡ ≡

Figura 2-9 Ejemplo regla de doble corte

En resumen las reglas de transformación presentadas para la sección Alfa de losgráficos existenciales son:

40 Se podría usar ≡ en lugar de |− porque es reversible usando desiteración..41 Hay que aclarar que el área donde está el gráfico original esta contenida en la misma área que contieneal área donde se va a inscribir la copia del gráfico.



26

(R1) Regla de Eliminación. Puede borrarse cualquier gráfico cercado por unnúmero par de cortes.

(R2) Regla de Inserción. Puede inscribirse cualquier gráfico en un área encerradapor un número impar de cortaduras.

(R3) Regla de Iteración. Si un gráfico β ocurre en la hoja de aserción o dentro uncorte, entonces una copia del gráfico puede inscribirse sobre un área noparte de β, que está contenida en {β}.

(R4) Regla de desiteración. Un gráfico cuya ocurrencia pueda ser resultado deiteración puede borrarse.

(R5) Regla del doble corte. El doble corte puede ser insertado o removido de ungráfico o sobre un área.

2.2

Semántica: Alfa y el Cálculo proposicional En Alfa se representan proposiciones de forma similar que el CP (CálculoProposicional), se puede establecer analogías entre los gráficos existenciales y el CP 42,ahora, de una manera informal e intuitiva se presentaran algunas similitudes.

2.2.1 Proposiciones y conectivos

En CP las afirmaciones son representadas por las letras proposicionales. Losconectivos lógicos se utilizan para la representación de proposiciones compuestas y sehan definido como representaciones de funciones simples de verdad. Con estas

funciones de verdad se demuestra que ciertas fbfs son equivalentes, de la mismaforma, en Alfa un enunciado es una letra pero algunas de estas equivalencias son“perceptibles”.

2.2.1.1 Verdad y contradicción

Cualquier espacio en blanco de HA puede llamarse gráfico nulo. Así, cualquier gráficopuede verse como la yuxtaposición de ese gráfico con un gráfico nulo. Sin embargo,ésta yuxtaposición debe expresar lo mismo que el gráfico original, luego cualquiergráfico nulo expresa una tautología. Otra manera de mirar esto es ver algunatautología como “la afirmación vacía”' donde, lo que es una tautología; efectivamenteno afirma nada.

Por otro lado el pseudográfico expresa un estado imposible de las cosas, es decir unacontradicción. De otra manera y relacionándolo con el concepto de tautología, elpseudográfico es un cerramiento que sólo contiene un gráfico nulo. Puesto que uncorte vacío niega un gráfico nulo, cualquier pseudográfico expresa una falsedad ( Figura2-10 ).

42 De hecho en [ZEMJ64]] se presenta la demostración de la equivalencia entre estos dos sistemas.



27

Verdad Contradicción

Figura 2-10 Verdad y contradicción

2.2.1.2 Implicación y Negación

De forma directa Peirce establece que la implicación se representa con el scroll

entonces se puede traducir directamente la fbf del CP ϕ→ψ a gráficos existenciales.

Previamente en C5 se determina que encerrar un gráfico por un corte es equivalente anegarlo, sin embargo, Peirce definía la negación de una proposición como esa

proposición implicando una falsedad, (que en CP sería: p→F). Se puede usar la reglade doble corte para demostrar esta equivalencia.

≡ doble corte

2.2.1.3 Conjunción y disyunción

Como se sugiere en (C3) la yuxtaposición de gráficos es una forma de representar laconjunción de proposiciones, debido a que el orden de lectura no es relevante sepuede observar que la yuxtaposición de gráficos es asociativa y conmutativa; de estaforma son “visibles” estas leyes para la conjunción en CP43. Por otro lado en ladefinición 1.19 se establece que para fbfs ϕ y ψ; ϕ∧ψ es una forma más convenientede escribir ¬( ϕ → ¬ψ ). Ahora representando ¬( ϕ → ¬ψ ) en Alfa se puede verificarque es equivalente44 a ϕ∧ψ.

≡ doblecorte

≡ doblecorte

Para la disyunción, la cual no se define su representación desde el comienzo, podemosplantearla de la misma forma que Russell: ([R USS06])45 “‹‹p o q ›› es equivalente a‹‹ ‘p implica q’ implica q››”. En otras palabras: (p→q)→q ≡ p ∨ q. Escribiendo p como

43 En la Tabla 1.2 están las leyes de equivalencias lógicas.44 Se puede verificar en el CP que ϕ∧ψ ≡ ¬( ϕ → ¬ψ ) usando tablas de verdad.45 Más adelante afirma: “Otra definición equivalente que se puede deducir de la anterior es ‹‹Cualquierproposición implicada por p e implicada por q es verdadera››, o en otras palabras, ‹‹ ‘p implica s’ y ‘q implica s’ juntas implican s, cualquiera que sea s ››”



28

ϕ y q como ψ, escribimos en Alfa el equivalente a ( ϕ→ψ )→ϕ y aplicamos la regla dedesiteración:

desiteración

≡ iteración

Sin embargo, en la definición 1.19 se establece que ϕ ∨ ψ := ¬ϕ→ψ y representando¬ϕ→ψ en Alfa se consigue directamente:

De forma intuitiva se puede decir que para representar la disyunción de dos o másproposiciones se escribe cada uno de los gráficos que las representan sobre HAencerradas por un corte, y finalmente una cortadura cercándolos a todos.

Luego ϕ ∨ ψ ∨ τ sería:

y al igual que la conjunción se ve que la disyunción es asociativa y conmutativa.

En la Tabla 2.2 aparece como resumen cómo se puede hacer la traducción del cálculoproposicional a Alfa.

Cálculo proposicional Alfa

α −−−−>

¬α −−−−>

α∧β −−−−>

α∨β −−−−>

α→β −−−−>

Tabla 2.2 Traducción del cálculo proposicional a Alfa



29

2.2.1.4 Traducción entre Alfa y el CP

La ventaja de representar proposiciones en Alfa es entre otras:• No se usan paréntesis.

• Las leyes asociativas y conmutativas de la conjunción y la disyunción sonobvias.

• Traducir una fbf del cálculo proposicional a Alfa es relativamente sencillo.

Sin embargo traducir un gráfico a una fbf puede presentar diferentes lecturas, porejemplo:

Se podría traducir como (( ϕ∧¬τ)→ ψ), (( ϕ∧¬τ)→ ψ), o ¬( ϕ∧ (¬τ ∧ ¬ψ )), debido aque Peirce definió la forma de representar la implicación mediante el scroll y laconjunción como la yuxtaposición, es posible escoger de diferente forma elantecedente. Por esta razón es más conveniente para la traducción de un gráfico Alfa auna fbfs del CP, leer el gráfico desde el exterior hacia el interior46 únicamente teniendoen cuenta como conectivos los cortes y la yuxtaposición (negación y conjunción)47. Deesta forma, cada vez que se encuentra un corte se escribe ‘¬’ y si los gráficos estánsobre la misma superficie se escribe ‘∧’.

2.2.2 Valores de verdad

Los gráficos existenciales fueron pensados con el fin de representar el equivalente afbfs verdaderas para llegar conclusiones verdaderas, pero precisamente porque puedensimbolizar lo mismo que las fbfs del CP, se puede determinar su validez bajo algunainterpretación de las letras que lo componen.

Se extiende la noción de interpretación a Alfa, donde se asigna valores de verdad acada letra y por medio del método presentado a continuación se obtiene un valor de

verdad de una forma similar al método de tablas de verdad.• Los símbolos 1 y 0 representan los valores de verdad Verdadero y Falso

respectivamente.

• El valor de una zona no marcada de HA es 1.• El valor de un área será 1 sí todos los gráficos de esa área tienen el valor 1.• El valor de un área encerrada por un corte es 0 si el valor de su interior es 1, y

1 si en su interior el valor es 0.

46 Este procedimiento Peirce lo llamó ‘Endoporéutic’ ([Sowa14]).47 Se establece Alfa como un sistema formal usando sólo el corte y la yuxtaposición, por este motivo seprueba la equivalencia de Alfa con el CP usando el sistema de Rosser ([ZEMJ64],[THIB82], [POV 071]y [ JIMM03]). En [ZEMJ64] además de hacer la prueba completa también se prueba la equivalencia con elsistema de Wajsberg, en el que la traducción de fbfs a gráficos existenciales es más sencilla. En [M ALD98]se prueba la equivalencia con un lógica algebraica de Leibniz.



30

Figura 2-11

Por ejemplo el valor de verdad del gráfico de la Figura 2-11 es 0 si a ϕ se le asigna el valor 1 y a ψ el valor 0. Observe que para calcular el valor de un área encerrada sehace de forma recursiva, el valor de un gráfico depende de cada uno de los gráficosque lo componen, en el procedimiento de tablas de verdad se van construyendo sub-expresiones cada vez más complejas hasta construir la fbf deseada, en Alfa se empiezaa evaluar del interior hacia el exterior.

Igualmente que en el CP existen gráficos que bajo todas sus interpretaciones, su valores 1 o 0, es decir, son tautologías o contradicciones respectivamente.

2.3 El sistema Formal A

Como anteriormente se había mencionado el interés de definir un sistema formal es eldel razonamiento; precisamente las reglas de transformación de Alfa, representan unasecuencia de pasos que permiten que, a partir de un gráfico inicial que se afirma(premisa) se obtenga otro que también es válido (conclusión).

2.3.1 Sintaxis

De la misma manera que en 1.2.1 se define el lenguaje, axiomas y reglas de inferenciapara el sistema formal A .

Definición 2.1 (Alfabeto) Los símbolos que se utilizarán en A son los siguientes 1. Hoja de Aserción:

2. Linea de cortadura.

3. Scroll

4. Letras48

α, β, γ.

Definición 2.2 (Sintaxis) Las reglas de formación para A son: 1. (HA) Toda zona no marcada de la hoja de aserción es un Gráfico Bien

Formado (gbf).2. Inscribir una letra sobre HA es un gbf.

48 Las presentaciones usuales utilizan letras mayúsculas, en esta monografía se usarán letras griegas porqueel programa “KLPEIRCE” las utiliza.



31

3. Si ϕ y ψ son gbfs, entonces y

son gbfs.

Se ha puntualizado para A un lenguaje con los equivalentes a los conectivos ¬, → delCP presentados en C5 y C4, se ha omitido por ahora el equivalente al conectivo ∧ definido de forma implícita en C3. También se habría podido incluir el pseudográficocomo el símbolo constante equivalente a F del cálculo proposicional. Sin embargopara probar la completitud de ese sistema es suficiente con los símbolos equivalentes a¬ y →.

Definición 2.3 (Axioma) HA es el único axioma de A 49 .

Definición 2.4 Se denota por área como la superficie comprendida en el interior de

una cortadura. Un subgráfico es un gbf que hace parte de otro gbf. Un subgráfico es par- envuelto si está sobre la hoja de aserción, o si está rodeado por un número par decortaduras. Un subgráfico es Impar-envuelto si está rodeado por un número impar decortes.

Definición 2.5 (Reglas de transformación) Son transformaciones validas en A: • (Eliminación) Puede borrarse de HA cualquier gbf par envuelto.• (Inserción) Puede inscribirse cualquier gbf en un área impar-envuelta de HA.• (Iteración) Se Puede inscribir cualquier gbf ϕ en un área de (HA) que no sea

parte del área de ϕ y esté envuelta en un número mayor (o igual) de cortesque el área de ϕ.

• (Desiteración) Puede borrarse de (HA) cualquier gbf

ϕcuya ocurrencia pueda verse como un resultado de la regla de iteración.

• (Doble Corte) Puede insertarse o eliminarse un doble corte alrededor decualquier gbf, en cualquier área de (HA). La inserción no debe producirintersecciones entre cortes.

Definición 2.7 Sean ϕ , ψ gbfs de A, ϕ |− A ψ si y sólo si existe una sucesión finita α1,

α2,...αk , de gbfs tal que α1 es ϕ, ψ es αn, y cada αi (1 ≤ i ≤ n) se obtiene de aplicaralguna de las reglas de transformación a αj, j<i; si ϕ es (HA) |− A ψ .

En las deducciones formales que serán presentadas se omitirá el dibujo de la hoja deaserción (excepto en el enunciado), los gráficos se escribirán horizontales y para evitar

ambigüedades se escribirán todas las letras del gráfico sobre un eje imaginariohorizontal situado en el centro del gráfico. Los pasos de las demostraciones semostrarán igual que en el capitulo 1, escribiendo en lugar de fbfs, gráficosexistenciales; sobre la columna de la derecha no es necesario escribir sobre cuál pasose aplica cierta regla de inferencia ya que en Alfa siempre se aplican sobre el gráficoanterior. Cuando se tiene un conjunto de premisas, dado que todas se estánconsiderando como verdaderas se inscriben desde el comienzo sobre la hoja deaserción, el gráfico formado por la yuxtaposición de las premisas es el gráfico inicial.

49 [ZEMJ64] sugiere HA como axioma puesto que no puede ser derivada de otros gráficos.



32

Ejemplo 2.1

|− Demostración

(1) Premisa

(2) Desiteración

(3) Eliminación

(4)Doble corte

▪

Hay una propiedad interesante de los gráficos existenciales que es pedagógicamenteuna gran ventaja. El punto es que las reglas de transformación que funcionan para losgráficos, pueden aplicarse también dentro de los gráficos. Esto es contrario a otrasformulaciones conocidas de lógica proposicional y de predicados que sólo permiten laaplicación de reglas en fbfs “globales”. La única condición para aplicar la inferencia serefiere a si los gráficos involucrados están par-envueltos o impar-envueltos , todos las otrascondiciones son completamente locales50. Esta propiedad se conoce como el ‘Cut-

And-Paste Theorem’ (Teorema cortar-y-pegar)51. Usando esta propiedad sedemostrarán los teoremas de la deducción y reducción al absurdo.

2.3.2 Teorema de la deducción

La tarea de construir deducciones formales en Alfa puede simplificarse de la mismaforma que en CP con un teorema equivalente al de deducción. Para realizar lademostración es necesario usar la ‘propiedad’ mencionada anteriormente.

Lema 2.1 ( Teorema Cortar-y-Pegar ) Si para un subgráfico ϕ, de un gbf τ se tiene

ϕ |− ψ y ϕ es par-envuelto, entonces ϕ puede ser reemplazado por ψ en τ.Demostración: Sea τ un gbf tal ϕ es un subgráfico de τ, y sea τ’ el mismo gbf τ talque en lugar de ϕ se encuentra ψ. Para demostrar que ϕ puede ser reemplazado por ψ basta garantizar que τ |− τ’. Cómo ϕ |− ψ, entonces existe una sucesión finita α1,

α2,...αn de gbfs tal que α1 es ϕ, αn es ψ, y que αi+1 es obtenido al aplicar una de lasreglas de transformación sobre αi. Diremos que α’i es el subgráfico de τ que está en lamisma área que ϕ, luego hay que mostrar que para cada αi de la deducción que de ϕ lleva a ψ existe un α’i correspondiente en la sucesión que de τ lleva a τ’, es decir que laregla de transformación aplicada a αi es aplicable al subgráfico α’i. Luego por

50 De esta manera haciendo una demostración puede prácticamente olvidarse del gráfico completo, y encambio concentrarse sobre el subgráfico pertinente. Similar a un puzzle en el que una vez acomodadasciertas figuras el nuevo objetivo se concentra en las que hacen falta.51 Esto al parecer fue formalizado por John Sowa, se hace referencia a este teorema en[FRIT02]



33

inducción si el subgráfico ϕ está bajo 2k cortes (k = 0, 1, 2,..., n) se evaluaran doscasos:

i) (k =0 ) Si ϕ está sobre HA, τ es el gbf resultado de la yuxtaposición de ϕ conotro gbf β, luego para cada α’i es aplicable cada una de las reglas detransformación utilizadas para transformar αi

52. Por tanto τ |− τ’.ii) Se va a mostrar que si es cierto para el caso bajo k cortes entonces lo es para

k+1 cortes, surgen 3 posibilidades:a) Si αi+1 ha sido obtenido mediante la aplicación de iteración, desiteración o

doble corte sobre un subgráfico γ de αi. Puesto que γ es subgráfico de αi también debe serlo de α’i, sólo que debe estar bajo p+2k cortes, siendo pel número de cortes que rodean a γ, y dado que el número de cortes noinfluye sobre la aplicabilidad de estas tres reglas, las condiciones dadas parala aplicación de alguna de ellas sobre αi deben ser las mismas para α’i. Poreste motivo también es cierto ya que γ está bajo p+2(k+1) cortes.

b) αi+1 ha sido obtenido mediante la aplicación de la regla de inserción sobre

αi. Entonces un nuevo gbf γ se ha podido inscribir en un área cercada por2p+1 cortaduras (p = 0, 1, 2...), luego en α’i debe ser posible insertar unnuevo gbf γ sobre el área cercada por (2p+1)+2k cortes análoga a la de αi.Esto es posible porque dicha área se encuentra bajo 2(p+k)+1 cortes, esdecir un número impar de cortes, y también es cierto si esta área estárodeada por 2(p+k+1)+1 cortaduras.

c) αi+1 ha sido obtenido mediante la eliminación de un subgráfico γ de αi.Luego si γ se ha podido borrar porque estaba bajo 2p cortaduras (p = 0, 1,2...) también puede borrarse de α’i porque estaría bajo 2p+2k cortes.

También sería posible eliminar γ si está bajo 2p+2(k+1) (o sea 2(p+k+1))

cortes. ▪

Se puede garantizar este reemplazo porque el ‘comportamiento’ de dicho subgráficoserá el mismo que si se encuentra como gbf inscrito sobre HA. La aplicación de lasreglas sólo se debe cuidar en el caso de inserción y eliminación, por este motivo sólopuede hacerse la ‘sub-demostración’ si el subgráfico es par-envuelto.

Para los metateoremas de la deducción y reducción al absurdo en Alfa, se considera ϕ como el equivalente a una colección de gbfs, puesto que inscribirlos en la misma hojaes un gbf.

Teorema 2.1 (Deducción en Alfa) Sean ϕ, ψ y χ. |−si y sólo si

|−

Demostración ‘==>’

(1) Premisa

52 Puede pensarse en que la hoja de aserción se separara dejando por una parte a ϕ y en otra hoja a β, endonde está ϕ se sigue el mismo proceso para obtener ψ, y dado que tanto β (porque es una premisa)como ψ (es consecuencia de la premisa válida ϕ ) son válidos pueden ser inscritos sobre la misma hoja.



34

(2) Doble corte

(3) Inserción

(4) Iteración

(5)

Hipótesis, Lema2.1

▪

‘<==’

(1) Premisa

(2) Hipótesis,

Lema 2.1 53

(3) Desiteración

(4) Doble corte

(5)Eliminación

▪

Colorario: |− si y sólo si |−

Demostración: Simplemente suponga que ϕ es HA.▪

Una consecuencia inmediata es que si se sabe que para dos gbfs ϕ y ψ se cumple

ϕ |− ψ, por teorema de deducción se puede inscribir sobre HA:

Teorema 2.2 (Reversión) Si |− entonces |−

Demostración:

(1) Premisa

(2)

Hipótesis, Teorema de

deducción

(3) Desiteración

(4)Eliminación

▪

53 Sigue MP.



35

2.3.3 Reducción al Absurdo

En CP, ésta es una estrategia de demostración indirecta, en A se puede considerar másbien una estrategia o algoritmo (las pruebas se hacen directamente, se parte de lahipótesis y se llega a la conclusión) la ventaja pedagógica de Alfa es que es literalmenteuna ‘reducción al pseudográfico’, es decir, el asunto es tratar de obtener elpseudográfico en la zona envuelta por dos cortes. Este sub-proceso lo ilustramos en elsiguiente lema.

Lema 2.2 Si |− y |− entonces

|−Demostración:

(1) Premisa

(2) Iteración

(3)Hipótesis, Lema

2.1

(4)Hipótesis, Lema

2.1

(5) Desiteración

(6)Eliminación

▪

Teorema 2.3 (Reducción al absurdo) Si |− y

|− entonces |−Demostración:

(1) Premisa

(2) Doble corte

(3) Inserción

(4) Iteración

(5)Lema 2.2Lema 2.1

(6) Doble corte

(7)Doble corte

▪



36

2.4 Completitud y consistencia

La ventaja que ofrece A como sistema formal en cuanto a la sencillez de lasdemostraciones perdería total relevancia y utilidad si no fuera un sistema completo y consistente tal como el sistema L del cálculo proposicional.

Para probar que en A se pueden deducir todas las tautologías basta con demostrarcomo teoremas de A los axiomas y reglas de inferencia de otro sistema que seadeductivamente completo, para este propósito se utilizará el sistema L .

Definición 2.8 (Traducción de fbfs de L a Alfa). Toda fbf de L puede expresarsecomo gbf utilizando las siguientes convenciones.

1. Toda parte de fbf de la forma p→q será reemplazada por un gbf de la forma

2. Toda parte de fbf de la forma ¬p será reemplazada por un gbf de la

forma

De esta forma, los axiomas de L se expresan en A. Se utilizarán los nombres L1*, L2*

y L3* para referirnos a los gbfs traducidos correspondientes.

L1 ϕ → ( ψ → ϕ )

L1*

L2 ( ϕ → ( ψ → χ ))→ (( ϕ → ψ )→ ( ϕ → χ ))

L2*

L3 ( ¬ψ → ¬ϕ )→ ( ϕ→ ψ )

L3*

Tabla 2.3 Axiomas de L traducidos a Alfa



37

Puesto que al axioma sólo es posible aplicarle doble corte, las pruebas comenzaráncon la doble cortadura como primer gráfico.

Lema 2.3 |− A L1*

Demostración:

(1) Axioma, doble

corte

(2) Inserción

(3) Iteración

(4)Eliminación

(5)Doble corte

▪

Lema 2.4 |− A L2*

Demostración:

(1) Axioma,

doble corte

(2) Inserción

(3) Iteración

(4) Doble corte

(5) Iteración



38

(6) Doble corte

(7)Doble corte

▪

Lema 2.5 |− A L3*

Demostración:

(1) Axioma, doble

corte

(2) Inserción

(3) Iteración

(4)Doble corte

▪

Lema 2.6 Deducir en A Modus Ponens.Demostración

Ejemplo 2.1.▪

Teorema 2.3 A es deductivamente completo.Demostración: Por los lemas 2.3 a 2.6▪

Probado que en A se pueden deducir todas las tautologías, se mostrará que en A todoteorema es una tautología. Puesto que todo teorema de A se deduce del axioma, hay que probar que el axioma es una tautología, y que las reglas de transformaciónpreservan tautologías.



39

En los lemas siguientes se hará referencia a áreas α y β de un gráfico cualquiera, talque β⊆α, también se hará referencia en algún momento a un corte N que encierra a

α. Cuando se habla del valor de un corte se habla al valor de verdad del gráficoformado por un determinado corte y su área interior, de forma análoga el valor de ungráfico es su valor de verdad.

Lema 2.7 Sean α y β áreas bajo un número de cortes N. Si el valor de β no influyesobre el valor de α entonces el valor de β no tiene efecto sobre el valor de N.Demostración: El procedimiento para calcular el valor de un área encerrada secalcula del interior al exterior, el valor de cada área se calcula exactamente una vez.▪

Lema 2.8 Borrar un gráfico de un área α puede cambiar el valor de α de 0 a 1 perono de 1 a 0.

Demostración: El procedimiento asigna el valor a la yuxtaposición siendo 0 cuandoalguno de los gráficos es 0, puesto que el valor de una zona no marcada de HA es 1, alborrar un gráfico el área no valdrá 0; por el contrario, si el gráfico tiene valor de

verdad 0, al borrarlo el área tomará el valor 1 si era el único gráfico.▪

Lema 2.9 Insertar un gráfico sobre un área α puede cambiar el valor de α de 1 a 0pero no de 0 a 1.Demostración: De forma análoga con el lema anterior se asigna el valor a layuxtaposición, si se inserta un gráfico de valor 0 el valor del área será 0, si el área vale0 antes de la inserción es imposible cambiarlo al insertar un gráfico.▪

Lema 2.10: Borrar un gráfico de un área β que está contenida por un área α y

encerrada por dos cortes más que α puede cambiar el valor de α de 0 a 1 pero no de 1a 0.Demostración: Hay dos casos:

i) El valor de α es 1. Digamos que α está bajo n cortes y β bajo n+2 cortes,como α vale 1 cada área bajo n+1 cortes contenida en α debe valer 0,porque cada gráfico bajo de α debe valer 1. Puesto que el valor de un áreabajo n+1 cortes debe ser 0 basta con que algún gráfico de la misma valga 0,pero por lema 2.8 el valor de β no cambiará de 1 a 0 si se elimina ungráfico de β, luego el valor de β encerrado (corte n+2) no cambiará de 0 a1 (luego estaría garantizado que valor del área bajo n+1 cortes sea 0después de borrar el gráfico).

ii) El valor de α es 0. Entonces algún cambio en el valor de α sería de 0 a 1.Suponga que el valor 0 de α se da porque el corte n+1 tiene valor de verdad 0, entonces el valor del área n+1 es 1 y si el valor de β cambia, todoesto cambiaría.▪

Lema 2.11: Insertar un gráfico en un área β que está contenida por un área α y encerrada por dos cortes más que α puede cambiar el valor de α de 1 a 0 pero no de 0a 1.▪ Demostración: Se presentan dos casos:

i) El valor de α es 0. Por lema 2.9 insertar un gráfico sobre β no cambiará el valor de β ó por otro lado cambiará el valor de β de 1 a 0. Si no hay



40

cambios entonces no hay efecto sobre el valor de α; si cambia el valor de β de 1 a 0, por el proceso de valuación se ve que α debe mantener el valor 0.

ii) El valor de α es 1. Cada área bajo n+1 cortes contenida en α debe valer 0,por eso basta con que un gráfico de allí valga 0, por ejemplo si cambia el

valor de β de 1 a 0 el valor del corte n+2 que contiene a β cambiaría a 1, sieste corte es precisamente el que hace que el área bajo n+1 cortes sea 0,cambiaria el valor de α.▪

Lema 2.12 El axioma de A es una tautología.Demostración: Esto es cierto porque por definición una zona no marcada de HAtiene valor de verdad 1, luego el valor de verdad de HA en blanco es 1▪

Para probar que las reglas conservan las tautologías llamaremos premisa al gráficoinscrito sobre HA antes de la aplicación de una determinada regla y conclusión algráfico después de la aplicación de dicha regla.

Lema 2.13 La regla de Eliminación preserva tautologías.Demostración: La prueba se obtiene por inducción matemática sobre n (n=0,1,2,...),donde 2n es el número de cortes que encierran el área donde se realiza la eliminación.

i) La eliminación se aplica sobre un gráfico que se encuentra sobre HA(n=0). Si la premisa tiene el valor de verdad ,1 por lema 2.8 el valor delgráfico nunca cambiará de 1 a 0, luego la conclusión también tendrá valor1.

ii) Por hipótesis de inducción se afirma que la eliminación preservatautologías cuando se aplica a un área encerrada bajo 2k (n=k) cortes, es

decir que no cambia el valor de 1 a 0, Si se aplica eliminación sobre 2(k+1)cortes (n=k+1), por el lema 2.10 puede asegurarse que también es ciertoque el valor no cambiará de 1 a 0.

Esto completa la inducción y se concluye que la eliminación preserva tautologías si seaplica dentro de un área encerrada por un número par de cortaduras. ▪

Lema 2.14 La regla de Inserción preserva tautologías.Demostración: La prueba también se obtiene por inducción matemática sobre n(n=0,1,2,...), donde 2n+1 es el número de cortes que encierran el área donde se realizala eliminación.

i) La inserción se aplica sobre el área encerrada por una sola cortadura (n=0).

Dado que el valor del corte es 1, el área interior debe tener valor 0. Porlema 2.9 el valor de esa área nunca cambiará de 0 a 1, luego la conclusióntendrá valor 1.

ii) Por hipótesis de inducción se afirma que la inserción preserva tautologíascuando se aplica a un área encerrada bajo 2k+1 (n=k) cortes, es decir queno cambia el valor del gráfico de 1 a 0, de acuerdo con el lema 2.9 decirque inserción preserva tautologías cuando se aplica a 2k+1 cortes es decirque cambiar el valor del area encerrada bajo 2k+ 1 cortes de 1 a 0 notransformará una tautología en algo que no lo sea. Luego cualquieroperación que pueda producir sólo este cambio sobre un área encerradabajo 2k+1 cortes debe preservar tautologías Pero de acuerdo con el lema



41

2.11, la aplicación de la inserción bajo dos cortes más, es decir 2(k+1)+1cortes, es la misma operación, por lo tanto inserción preserva tautologías

bajo 2(k+1)+1 cortes.Esto completa la inducción y se concluye que la inserción preserva tautologías si seaplica a un área encerrada por un número impar de cortaduras. ▪

Lema 2.15 Iteración y desiteración preservan tautologías.Demostración: Sea N el corte donde las operaciones se realizan, α el área donde seencuentra el gráfico original que es iterado o desiterado, y sea β el area donde elgráfico es copiado por Iteración o es borrado por desiteración, suponiendo que β⊆α consideramos dos casos:

i) El gráfico ϕ que es iterado o desiterado tiene valor 1. Sin importar el valorde β antes de el uso de iteración o desiteración, es claro que por la formaen que la yuxtaposición es evaluada la inserción de ϕ sobre β o borrar ϕ de β no cambiará el valor de β y de esta manera no cambiará el valor deN, luego si la premisa es tautología también lo es la conclusión.

ii) El gráfico ϕ que es iterado o desiterado tiene valor 2. Entonces el valor deα es 0 sin importar el valor de β antes o después del uso de iteración odesiteración, por lema 2.7 sigue que el valor de β no tiene efecto sobre el

valor de N, por ello si la premisa es tautología la conclusión también esuna tautología.▪

Lema 2.16 La regla del doble corte preserva tautologías.Demostración: Es inmediato por el procedimiento de evaluación para un corte, para

cualquier gráfico

y tienen el mismo valor.▪

Teorema 2.4 (Validez) Todo teorema de A es una tautología.

Demostración: Por los lemas 2.12 a 2.15.▪

Teorema 2.5 A es consistente.Demostración: Por teorema 2.4, todo teorema de A es una tautología. Como lanegación de una tautología no puede ser una tautología, es imposible que exista un gbf

, tal que

y sean teoremas de A .▪

Como ya se había mencionado un sistema es consistente si en el no se pueden deducir

contradicciones, debido a que a partir de ellas el sistema se trivializa. Observe que altraducir las fbf del CP, β y ¬β a A y asumirlas como premisas sucede lo mismo que enel Teorema 1.11.

Ejemplo 2.2 |−

Demostración:

(1) Premisas



42

(2) Desiteración

(3) Eliminación

(4) Inserción

(5)Doble corte

▪

Anteriormente se mencionó que el pseudográfico representa la falsedad. En A no esposible deducir el pseudográfico porque la única regla que genera cortaduras a partirde HA es la regla del doble corte, pero esta regla sólo produce un número par decortaduras.

2.5 Deducción Natural en Alfa

Al igual que el sistema de deducción natural de Gentzen, es posible presentar elsistema Alfa sin axiomas, para este sistema de deducción natural que se denotarácomo A * se utilizará el mismo lenguaje, y una regla más de inferencia llamada porPeirce regla de introducción de la implicación, y que es el equivalente a la regla TD de1.4.2.

Definición 2.9 (Regla TD)

Si puede transformarse en entonces puede serinscrito sobre HA

También es necesario suprimir la convención C1 (La hoja de aserción en todas suspartes es un gráfico), ya que HA es el axioma de A .

Sólo falta demostrar que es deducible a partir de las reglas de transformaciónmás la nueva regla de introducción de la implicación54 para que este sistema seacompleto y consistente. Previamente se demostró que A es consistente y completocon HA como axioma.

Lema 2.7

|− A*

Demostración:

(1) Premisa

(2) Doble corte

54 Observe que esta regla es el colorario del teorema de la deducción de Alfa pero para su demostraciónse utilizó la convención C1. Por este motivo es necesario que se defina como una regla de inferencianueva ya que se va utilizar esta regla para prescindir precisamente de C1.



43

(3) Doble corte

(4) TD

(5) Doble corte

(6) Desiteración

(7) Eliminación

(8) Desiteración

Estrictamente hablando, el primer gráfico que se escribe sobre HA es 4. De 1 a 3 sepresenta una prueba del antecedente de la nueva regla. En otras palabras, los sistemasde deducción natural en CP utilizan el teorema de la deducción como regla deinferencia, y a partir de ella, y las demás reglas de inferencia se prueban los axiomas delCP, lo que se acaba de mostrar es exactamente el mismo proceso en Alfa.

2.6 Los Sistemas deductivos Alfa 0 y Alfa 00

Estos sistemas fueron propuestos en [POV 071] por Yuri Poveda, tienen las siguientes

características:1. Ninguna de las reglas de transformación se define en función de la paridad

de cortes.2. Cada regla es una sub-regla de A .3. Los sistemas son equivalentes al CP

El lenguaje de Alfa0 y Alfa00 se define con base en las convenciones (C1), (C2) , (C3) y (C5), es decir , como equivalentes a los conectivos primitivos se usa la yuxtaposición y el corte. El condicional se obtiene usando la equivalencia α→β ≡ ¬( α∧¬β ) de fbfs delCP.

El axioma de Alfa0

es el mismo de A .

Las reglas de inferencia para Alfa0 son:

R1 |−



44

R2 |−

R3 |−

R4 |−

R5 |−

R6 |−

R7|−

R8 Si |−

entonces |−

Las reglas de inferencia para Alfaoo son las mismas de Alfao R1 a R7. El axioma

propuesto es:

que hace que Alfa00 sea equivalente a Alfa0 (Allí se demuestra que el axioma de Alfa00 es equivalente a R8 de Alfa0 ). Puesto que el lenguaje de ambos sistemas se basa en elcorte y la yuxtaposición se hace la prueba de la equivalencia con el sistema de Rosser.



45

2.7 Método de decisión

El procedimiento descrito en 2.2.2 para calcular el valor de verdad de un determinadogbf es particularmente similar a las tablas de verdad, hay que comprobar todas lasposibles interpretaciones, pero comprobar de forma iterativa reemplazando todos losposibles valores es una tarea menos práctica.

Peirce también ideó un método de decisión para comprobar de forma más sencilla siun gbf es posible y bajo que condiciones, para ello utilizaba el scroll y algunas reglas desimplificación.

Figura 2-12

Para el gráfico de la Figura 2-12 el objetivo es encontrar ψ, es decir determinar bajocuales condiciones ϕ es verdad. En CP p→q es verdadero si para cuando p es cierto q también lo es55. ψ debe tener únicamente letras simples o letras simples encerradas porun corte (Los equivalentes a literales del CP).

Por ejemplo para:

se debe obtener

La cual nos indica que es suficiente que β tenga valor 1 para que toda la expresión lotenga. Presentaremos primero el metodo y en el ejemplo se mostrará porque se llegó aesta conclusión.

El método indica inscribir primero 56 y realizar las siguientes operacionesen el área encerrada por dos cortes. Las letras separadas se escriben arriba de la lineapunteada.

(A) Borrar todo corte vacío junto con el área y el corte que lo rodean.

(B) Borrar todo corte doble.(C) Separar una letra no encerrada y borrar todas sus apariciones en el área.(D) Separar una letra encerrada y sustituir todas sus apariciones en el área por

cortes vacíos.(E) Escoger una letra no separada; iterar todos los gráficos en el área ‘mayor’

excepto ϖ; en una copia, separar sin encerrar la letra escogida y borrartodas sus apariciones (C); en la otra, separar encerrada la letra escogida y sustituir todas sus apariciones por cortes vacíos (D).

55 Observe que sólo interesa el caso en que p es verdadero.56 Por comodidad se utilizará un scroll con cortes de forma rectangular redondeada.



46

En el caso que se obtenga el corte vacío o pseudográfico, se concluye que bajo

ninguna interpretación ϕ es verdadero, es decir, es una contradicción.

Ejemplo 2.3 Encontrar bajo cuales interpretaciones es verdadero.Por comodidad se escribirá en el área cercada por un corte ϖ en lugar de todo elgráfico, ya que sobre él no se realizan modificaciones.

Por (C)==>

Y finalmente por (A)==>

Ejemplo 2.4 Encontrar bajo cuales interpretaciones es falso el siguiente gráfico:

En este caso o que se hace es negar el gráfico, ya sea quitando primer corte oencerrando dicho gráfico por un corte (que luego se simplifica porque se quitan losdobles cortes). Ahora se buscará bajo cuales interpretaciones el gráfico siguiente esposible:



47

De igual forma que el ejemplo anterior se usará ϖ por comodidad.

Por(B)

==>

Por (C)==>

Por (D)==>

Por(B)

==>

Ahora el problema se divide en ‘casos’57 para aplicar (E). En el llamado original(izquierda), se aplica (C), y en la copia se aplica (D), en este caso la letra elegida es laúnica: β.

(E)

==>

En el original se aplica (A) y en la copia se aplica (B):

57 Esta división por casos hace que al ser presentado este método como una función sea una funciónrecursiva ([HEUV 02] y [HEUV 03])



48

Observe que en la copia se ha obtenido el pseudográfico, por este motivo se descartaesta posibilidad y sólo se considera la obtenida en el original.

Luego se concluye que para que tenga valor de

verdad 0, α y β deben tener valor 1, y χ debe tener valor de verdad 0.



49

3 Deducción automática

Hacia finales del siglo XVII, Leibniz formuló dos argumentos que sintetizan viejasaspiraciones del hombre:

• La necesidad de disponer de un lenguaje universal ( lingua characteristica ) en elque poder expresar cualquier idea.

• La posibilidad de mecanizar cualquier tipo de razonamiento ( calculus ratiocinator ).

La primera cuestión formulada por Leibniz, la necesidad de construir un lenguajeuniversal, empezó a tener respuestas parcialmente satisfactorias con los lenguajesformales. Hacia finales de los cincuenta, con la irrupción de los computadores

electrónicos y con el soporte de los muchos logros obtenidos en el campo de la LógicaMatemática, se retoma con fuerza el segundo objetivo de Leibniz: la automatizacióndel razonamiento, que se convierte en uno de los problemas iniciales de la Inteligencia

Artificial.

En 1960, Hao Wang con sus programas consiguió demostrar 9 capítulos de losPrincipia Mathematica en 9 minutos, incluyendo teoremas del cálculo de predicadosusando el sistema deductivo de Gentzen. En el mismo año, Gilmore presenta otraforma de tratar el problema de la deducción en la Lógica de primer orden basándoseen un resultado de Skolem y Herbrand que reduce la demostración de una fórmula deprimer orden, F , a la de una fórmula proposicional, F’ , asociada a ella. En esta

reducci´on aparecen dos problemas: (1) La búsqueda de un “candidato” proposicional,F’ , y (2) la demostración de F’ .

Los intentos de obtener una solución satisfactoria al problema (1) hacen emerger elconcepto de unificación, que subyace en los trabajos de Prawitz, y culmina en eltrabajo “ A machine oriented logic based on the resolution principle ” de J.A. Robinsonpublicado en 1965. En el mismo, presenta el principio de resolución en el que secombina la regla de corte proposicional y la simplificación. Desde entonces se hanintroducido diversos refinamientos del principio de resolución encaminados a mejorarla potencia del mismo en ciertos casos, y se han proporcionado estrategias paraorientar el proceso y acotar el espacio de búsqueda.

Durante la realización de este trabajo se ha implementado para Alfa un programa decomputador para el manejo didáctico de los gráficos existenciales (KLPeirce), lasclases utilizadas para su desarrollo proveen ciertas herramientas que han sidoaprovechadas para encontrar un método automático de deducción. Es unprocedimiento que muestra una deducción formal, es decir cada uno de los gráficos dela sucesión que la conforman.

Antes se mencionó que en un sistema un gbf ϕ es una consecuencia lógica de otro ψ si a partir de ϕ existe una demostración o un camino hacia ψ.



50

Definición 3.1 Un camino solución de un par ordenado de gbfs ( ϕ,ψ ) es unademostración de ψ a partir de ϕ, y se denota como S( ϕ,ψ ). Un agente es el módulo o

sistema de inteligencia artificial en el que se ha representado un gbf τ tal que ϕ |− τ. Sedice que un agente está en el estado inicial si τ es ϕ, en un estado solución si τ es ψ y que

τ ∈ S( ϕ,ψ ) si τ |− ψ.

Puede pensarse en un agente como algo similar a un robot que parte del gráfico inicial

ϕ y busca el gráfico final. Ahora se describirá como se representó el problema y lastécnicas que se han utilizado para encontrar un camino solución para ( ϕ,ψ ).

3.1 Representación

Existen diferentes tipos de representación del conocimiento, en [NILS00] se refieren a

dos tipos de modelos de representación, los basados en características que usandescripciones declarativas del entorno, y los icónicos que utilizan algoritmos y estructuras de datos y para simular aspectos del entorno de un agente.

En KLPeirce se utilizan principalmente dos clases CGrafico y CDibujo, se eligío unmodelo icónico58. CGráfico representa un gbf con un campo de tipo string y lossubgráficos de nuestro agente son las posiciones: inicial y final de caracteres . SobreCGráfico se pueden usar las reglas de transformación de acuerdo con su aplicabilidadsobre un subgráfico seleccionado. Las funciones que representan las reglas detransformación verifican internamente si una regla es aplicable en determinadosubgráfico.

Por otro lado CDibujo es la representación de CGráfico, la información que contienese pensó originalmente sólo para dibujar el gbf en pantalla, sin embargo CDibujo“sabe” cual subgráfico está seleccionado, esta información es un número entero quesirve de índice de posición del string. Este número ha sido llamado Marca. Unsubgráfico está seleccionado o marcado de acuerdo con el valor almacenado en la

variable marca. Los subgráficos se etiquetan de izquierda a derecha asignándoles unentero positivo a las áreas encerradas por un corte y un número negativo a las letras.En el ejemplo de la Figura 3-1 el valor de la marca está entre -4 y 5. Observe que el

valor 0 no se asigna, cuando marca es 0 se refiere a la HA.

Para algunas reglas de transformación también se utiliza una marca que indica el área

donde se inserta o itera un CGráfico; note que este valor debe siempre positivoporque sólo puede hacerse dentro de los cortes o también sobre HA en el caso de laiteración.

58 En IA la base de los modelos basados en características es el cálculo proposicional por este motivo sonlos más utilizados para la demostración automática de teoremas (Prolog). No se ha utilizado un métodosimilar con este problema porque el autor consideró que la implementación utilizando grafos es másinteresante.



51

Figura 3-1 Ejemplo del valor de marca

La siguiente notación corresponde a las funciones implementadas para reglas detransformación.

R1 ( τ , N) Representa la inserción de un gbf dentro de un área marcada por N (N>0) R2 (M) Representa la eliminación del subgráfico señalado por la marca M.

R3 (M, N) Representa la iteración del subgráfico señalado por la marca M sobre lamarca N (N≥0).R4 (M) Representa la desiteración del subgráfico señalado por MR5 (M) Representa la eliminación del doble corte alrededor o dentro59 de M.R6 (M 1 , M 2 , ... M n ) Representa la inserción del doble corte alrededor de los subgráficosseñalados por M 1 , M 2 , ... M n .60

Hay que aclarar que cuando se ejecuta alguna de estas funciones no necesariamente esposible aplicar dicha regla sobre el gbf que representa el agente, estas funciones sonestímulos que generan como respuesta una transformación o movimiento, en el caso deque sea posible o de lo contrario, una respuesta de fallo.

Para la deducción automática en ‘KLPEIRCE’ se prescinde inicialmente del uso de R1( τ , N) y R6 (M 1 , M 2 , ... M n ) para simplificar el uso de los operadores.61 Las demásfunciones pueden reducirse a una sola:

Regla (R, M, N)

Donde R representa cual regla se aplica, M cual gráfico es marcado62 y N en el casoque R sea 3 el lugar donde se itera.

59 El Subgráfico señalado por M puede ser un corte que contiene un subgráfico encerrado.60 Pueden señalarse al mismo tiempo por ejemplo varias letras que se encuentren en el mismo nivel y encerrarlas en un doble corte, por esta razón debe ser más de una marca. ‘KLPEIRCE’ le permite alusuario señalar más de un elemento (Ver Manual de usuario)61 La regla de inserción se podría generar seleccionado marcas de la conclusión.62 Se considerará marca y subgráfico señalado por marca como sinónimos, por comodidad.



52

Al suprimir el uso de estas reglas de transformación se limita al agente las

posibilidades de encontrar soluciones dado que el sistema lógico representado ya no esdeductivamente completo. Al final se presentarán algunas sugerencias para la soluciónde este problema, el objetivo del autor fue experimentar con un modelo icónico de unproblema de común representación de tipo declarativo. Se mostrará a continuaciónalgunas técnicas que permitieron que se implementara en KLPeirce un método dededucción automática.

3.2 Chemotaxis

El algoritmo utilizado es similar al que se usa para el entrenamiento de un tipo de redneuronal (Hopfield), que se basa en el movimiento de una bacteria en un medio donde

hay una solución alimenticia ([ALVA01]). Lo que describe a continuación es el primerintento que el autor implementó para generar deducciones de forma automática63.

El objetivo es hacer que el agente se “mueva”, ya se tiene la manera de generarestímulos y sólo se manejan 3 parámetros R, M y N. Por este motivo el primer intentoes generar números aleatorios y “esperar” que ante sucesivos intentos o estímulos elagente llegue al estado solución, por supuesto la efectividad es mínima puesto que sedeja todo al azar

El espacio muestral para R es {2, 3, 4, 5}, en el caso del ejemplo de la Figura 3-1 elespacio muestral para M es [-4, 5] y para N [0, 5]. Puesto que los valores de N y M son

relativos al gbf representado, se usarán las variables min y max para denotar el mínimoy máximo valor de marca, respectivamente. Luego M oscilará ente min y max, y N entre 0 y max.

De forma arbitraria se ha escogido una función de probabilidad para la generación denúmeros aleatorios para el valor de R . Dándole menos prelación a 3 porque no seutiliza con mucha frecuencia la regla de iteración. En el caso de M se han escogidociertos criterios para la asignación de pesos a cada una de las marcas, esto se haceusando como referencia el string que representa la conclusión:

Algoritmo 3.1 (Función asignar pesos)Función Asignar pesos

Inicio1. Por cada letra se incrementa +1 el peso si se encuentra en laconclusión.

2. Si tanto en la conclusión como en la marca dicha letra estábajo par cortes +1 de nuevo. De forma análoga con imparcortes.

3. Por cada letra -1 si no está en la conclusión.Fin

Para N, los números aleatorios tienen una distribución uniforme.

63 La similitud con el algoritmo de chemotaxis se observó después de haber desechado el algoritmo.



53

El algoritmo consiste en generar estímulos para que el agente se mueva, para esto seutiliza una variable denominada “Alimento”que es el número de oportunidades que

el agente tiene para llegar al estado solución, por cada movimiento o condición exitosade Regla se le dan más oportunidades. En determinado momento el agente puedeencontrar un “punto sin salida” en el que el alimento se agota, puesto que el alimentodisminuye en cada intento; en este momento se retrocede un paso (regresa a su estadoinmediatamente anterior), y se inicializa de nuevo alimento. Hay un número deoportunidades general que cuando se terminan, se lleva al agente al estado inicial y se

vuelve a comenzar. Cada movimiento es registrado en una lista que almacena elcamino recorrido.

Algoritmo 3.2 (Búsqueda aleatoria con alimento) InicioAsignar pesos a GEncontrar números aleatorios: r, m, nÉxito = Regla(r ,m, n);Alimento = Alimento - 1

Si ( Exito )RegistrarPaso ListaAlimento += 10Si ( Solución )

Devolver soluciónSalir

Si ( Alimento <= 0 )Alimento = 10RetrocederIteraciones = Iteraciones + 1;

Si ( Iteraciones > 50 )Inicializar ListaIr a inicio

Fin

Una forma de mejorar el algoritmo ha sido asumir que la regla del doble corte es obvia(para una persona esa eliminación se percibe a simple vista), implementando unafunción que intente todas las posibles Regla (5, M, 0) 64 y aumentando las probabilidadesde las demás reglas. También se ha implementado la forma de decidir si se aplica o noun intento, con base en la media de las marcas, de esta forma si este promedio es muy bajo no vale la pena hacer muchos intentos, ya que este valor puede decir que tancerca se está de la solución.

Observe que cuando se inicia nuevamente el proceso no se tiene ninguna informaciónde los anteriores intentos. Aunque en el recorrido hay pistas no hay mayor eficiencia.En la Figura 3-2 también se puede observar que inclusive dentro del recorrido puedellegar a un mismo estado en varias oportunidades. La función de asignación de pesostampoco es la mejor ya que puede estimular a que una marca sea iterada sucesivas

veces por contener letras de la solución, sin embargo, aun con estas limitaciones elalgoritmo es capaz de encontrar algunas soluciones.

64 Observe que el valor de N solamente es importante cuando R = 3.



54

Figura 3-2 Ejemplo de solución del silogismo hipotético usando chemotaxis

3.3 Búsqueda en grafos

En la sección anterior se ha descrito un algoritmo que siendo un experimentointeresante ha sido rechazado por su poca efectividad. Si bien hay un modelo delestado actual, el agente no es capaz de predecir las consecuencias de las acciones querealiza. Para predecir esas consecuencias hay que tener un modelo de las mismas, y lasacciones solamente se deben realizar hasta que sus simulaciones hayan mostrado serseguras y efectivas.

En el problema de estudio, se dice que una acción valida es la ejecución exitosa de unade las reglas de transformación, los modelos de estas acciones se denomina comooperadores. En la Figura 3-3 se muestra un boceto de algunas posibles situaciones en laque el estado inicial es la hipótesis del Modus Ponens.

Definición 3.2 Un grafo dirigido se compone de un conjunto de nodos (nonecesariamente finito). Ciertos pares de nodos se conectan mediante arcos. Si un arcoestá dirigido del nodo ni al nodo nj se dice que el nodo nj es sucesor de ni o que ni espadre de nj. Un árbol dirigido es un tipo especial de grafo dirigido en el cual cada nodo

(excepto uno) tiene un único padre. El nodo sin padres se denomina raíz . Un nodoraíz tiene profundidad 0. La profundidad o nivel de un nodo está dado como laprofundidad de su padre más 1.

Una de las ventajas de representar los mundos posibles en una estructura de grafo, esque los nodos pueden etiquetarse para representar diferentes situaciones u objetivos(un puzzle por ejemplo). Para encontrar un conjunto de acciones que llevan a laconsecución del objetivo solamente se debe encontrar el “camino” entre el nodo querepresenta el estado inicial al nodo que representa el estado objetivo.



55

Específicamente en el problema de la demostración automática la tarea es encontrar elcamino solución. Las acciones ejecutadas pueden ser recuperadas mediante los arcosdel camino. Esos operadores que etiquetan los arcos a lo largo de dicho camino sonensamblados en una secuencia que de forma general se denomina plan , y la búsquedade esa secuencia se llama planificación .

Representar todos los posibles estados, es lo que se conoce como especificar elespacio de búsqueda. En este problema al igual que en otros de interés practico elespacio de búsqueda es demasiado grande para ser representado de forma explícita, esdecir, modelar todos los nodos y arcos del grafo para luego buscar el camino, sin

embargo, es suficiente representar el estado inicial y los efectos que las accionesproducen sobre ese estado (por ejemplo el de la Figura 3-3), esta es una representaciónimplícita y a medida que se va necesitando explorar los diferentes efectos se hacenexplícitos estos estados.

Figura 3-3 Efectos de aplicar las reglas de transformación



56

Definición 3.3 Los elementos necesarios para la representación implícita de un grafode estados:

1. Una descripción icónica para etiquetar el nodo inicial.2. Los operadores, es decir modelos de los efectos de las acciones. Cuando unoperador se aplica a un nodo se genera uno de sus sucesores.

3. Una condición de éxito, que puede ser una función booleana.

Es evidente que la representación elegida cuenta con estos elementos, los operadoresse han agrupado en la función Regla (R, M, N), y la condición de éxito está dada por lafunción comparar de CGráfico.

3.3.1 Búsqueda primero en anchura

El procedimiento de búsqueda en anchura es el más simple de los llamados métodosde búsqueda a ciegas, los procedimientos de búsqueda a ciegas operan aplicando losoperadores disponibles a los nodos con sólo la información acerca de si es posiblerealizar una acción. Es común en estos procesos de búsqueda la agrupación de laaplicación de todos los operadores en una sola función de de estados sucesores . Cuando seaplica dicha función a un nodo se obtienen todos los sucesores que se obtienen alaplicar todos los operadores (una sola vez) a dicho nodo. La aplicación de esta funciónse denomina expansión de un nodo.

La búsqueda en anchura está orientada a recorrer el árbol o grafo correspondiente porniveles. Para conseguirlo se utiliza una estructura de tipo cola 65 (Primero en entrar,

primero en salir) en la que se van introduciendo los nodos que son generados.

Algoritmo 3.3 (Búsqueda en anchura) Inicio

1. Crear un árbol de búsqueda, T, que sólo esté formado por elnodo inicial n.

2. Crear una lista de nodos llamada ABIERTOS y asignarle el nodoraíz n

3. Si ABIERTOS está vacía salir del algoritmo con fallo.

4. Extraer el primer nodo de ABIERTOS y llamarlo m.

5. Si m es el nodo objetivo, salir del algoritmo y devolver lasolución. La solución es el camino formado por los arcos queconducen de n a m.

6. Expandir m, es decir, generar el conjunto de todos sussucesores M.

7. Incorporar elementos de M como sucesores de m en el árbol T,creando los arcos correspondientes. Incorporar también loselementos de M a la lista ABIERTOS

8. Ir al paso 3.Fin

En la Figura 3-4 se muestra como se realizaría el recorrido en anchura.

65 Si en lugar de una estructura tipo cola se implementa una Pila (último en entrar, primero en salir) serealiza una búsqueda en profundidad.



57

Figura 3-4 Recorrido en anchura

3.3.2 Búsqueda primero el mejor

La búsqueda en anchura puede mejorarse examinando primero los nodos que de

acuerdo con cierta información, están situados en el mejor camino hacia el objetivo.Esta información se obtiene mediante una función de evaluación heurística, la cualdados ciertos criterios puede indicar que tan cerca se encuentra del objetivo.

En el problema específico de la deducción automática en Alfa, la función deasignación de pesos utilizada para chemotaxis podría servir, seleccionando entonceslos nodos con mayor promedio, sin embargo, esta función favorece los nodos que hansido producidos por iteración. Otro factor para tener en cuenta es que como se va adefinir como una función de distancia, los valores que toma deben ser positivoscercanos a 0 cuanto más se esté cerca del objetivo. El algoritmo es el mismo que el debúsqueda en anchura más una nueva instrucción:

8. Reordenar la lista abiertos en orden creciente, de acuerdocon la función de distancia, el primer nodo debe ser el demenor valor.

Debido a que el algoritmo tiende a escoger siempre el mejor nodo de acuerdo con unafunción heurística f , es de vital importancia seleccionar dicha función. En los gráficosexistenciales es complejo distinguir la forma de expresar la relación ‘es parecido a’como una función, es recomendable que la función f sea calculada utilizando un factorde profundidad:

f (n) = g(n) +h(n)



58

Donde la función g es la profundidad del nodo n y h es el componente heurístico. La

función heurística h definida para este problema en particular es a su vez la suma deotros componentes:

h(n) = u(n*) + 2t(n)

La función t(n) es el tamaño del string que contiene CGráfico, es decir se buscan losgráficos más ‘pequeños’, es decir, los menos complejos puesto que en la mayoría dededucciones se parte de uno o varios gráficos complejos y se busca uno más simple; lafunción u(n*) se define de acuerdo con la regla aplicada sobre el nodo padre de n , ( n* )usada para obtener a n :

( )

=

==

=

=

3030

23

42

50

*

R si

R si

R si

R si

nuSiendo R la regla de transformación aplicada.

De forma arbitraria se está dando prelación:

• A los strings de menor tamaño.

• A los obtenidos por regla de doble corte y luego a los obtenidos pordesiteración.

Se desestímula la regla de iteración pero no se descarta.

Un riesgo frecuente, y más en este problema, es el de encontrar ciclos 66, es decir,

evaluar un nodo que ya ha sido propagado, por ello se implementa también una listallamada cerrados en la que se almacenan los nodos que ya han sido propagados.

También se evita propagar nodos que excedan cierto limite de aceptación, o sea, que f tenga un valor muy grande indicando que se está muy lejos de la solución. Elalgoritmo queda finalmente:

Algoritmo 3.4 (Búsqueda heurística) Inicio

1. Crear un árbol de búsqueda, T, que sólo esté formado por elnodo inicial n.

2. Crear una lista de nodos llamada ABIERTOS y asignarle el nodoraíz n

3. Si ABIERTOS está vacía salir del algoritmo con fallo.

4. Extraer el primer nodo de ABIERTOS, llamarlo m y anexarlo enCERRADOS.

5. Si m es el nodo objetivo, salir del algoritmo y devolver lasolución. La solución es el camino formado por los arcos queconducen de n a m.

6. Si m no está en la lista CERRADOS, expandir m.

7. Incorporar elementos de M como sucesores de m en el árbol T,creando los arcos correspondientes. Incorporar también los

66 Iteración y desiteración son inversas por ejemplo.



59

elementos de M a la lista ABIERTOS con la condición de que noexcedan el limite de aceptación.

8. Reordenar la lista abiertos en orden creciente, de acuerdocon f.

9. Ir al paso 3.Fin

Puesto que la función f todavía no es la mejor no se extrae un sólo nodo n, sino los 5primeros, permitiendo que se acepten nodos peores de los que se generan en lasiguiente expansión y simulando el procesamiento en paralelo. El otro ajuste se hacesobre la función f que queda definida de la siguiente forma:

f(n) = 3g(n) + u(n*) + 2t(n) + d(n)

Ahora el factor de profundidad es más relevante y hay un nuevo componente de lafunción h que evalúa si aún quedan todas las letras de la conclusión sobre el string querepresenta el estado actual. Si esto no ocurre d(n) se le asigna un valor mayor que elmáximo de asignación para que no sea propagado posteriormente.

La función d(n) podría ser más determinante si se implementara el método de decisióndescrito en 2.7 para verificar que efectivamente τ ∈ S( ϕ,ψ ), dado que si τ |− ψ, elequivalente a τ→ψ en Alfa debe ser una tautología67:

Ejemplo 3.1 Verificar si

∈ S( , )

Primero se mostrará que el gráfico dado es consecuencia lógica de las premisas:

(1) Premisa

(2) Iteración

(3)Eliminación

▪

67 Esta función solo vale la pena aplicarla después de aplicar Inserción o Eliminación porque las demásreglas son reversibles.



60

Ya verificado lo anterior, el interés es saber si

es una tautología, pero en el ejemplo 2.4 se mostró que si el valor de α es 1, el de β es

1 y el de χ es 0 el gráfico toma el valor 0, por tanto no es una tautología y se concluyeque:

no pertenece al camino solución.

3.4 Métodos automáticos de demostración

Anteriormente se presentaron los teoremas de la deducción y reducción al absurdocomo posibles estrategias de deducción, ahora se mostrarán un par de ejemplos dedemostraciones que utilizan estas estrategias para simplificar (en el sentido que labúsqueda en el grafo sea más simple) la deducción.

En el caso de un teorema de A es obvio que se requiere del uso de la regla deinserción, a partir del paso 2 de toda deducción, regla que no se utiliza como operadoren la búsqueda en el grafo, pero se puede proveer al sistema para que ‘sepa’ que debeinsertar.

Primero se asumirá que el agente (un módulo de búsqueda) devuelve el caminosolución S( ϕ,ψ ) para dos gbfs ϕ y ψ en cuya demostración solamente se utilizan lasreglas de transformación que usa como operadores. Se utilizará entonces el Lema 2.1(cortar-y-pegar) para resumir esa parte de la demostración.

El ejemplo 3.1 es una simulación de un camino solución cualquiera devuelto por el

módulo descrito.

Ejemplo 3.2 |−

Demostración

(1) Premisa

(2) Desiteración



61

(3)Doble corte

▪

Ahora supongamos que el sistema debe demostrar el siguiente teorema:

Inicialmente se seleccionan dos subgráficos, uno del área encerrada por un sólo corte,y el otro del área encerrada por dos cortes, de tal forma que si se borraran quedaría ladoble cortadura vacía, observe que todos los teoremas de A son expresados con elscroll68 o con la yuxtaposición de varios69. En la Figura 3-5 está señalado en verde elsubgráfico uno que se llamará ϕ y en azul el subgráfico dos que se denotaraprovisionalmente ψ.

Figura 3-5 Subgráficos seleccionados

Lo que sigue es enviar al módulo de deducción a ϕ como hipótesis y a ψ comoconclusión. Y puesto que se obtiene S( ϕ,ψ ) la deducción quedará de la siguienteforma:

Ejemplo 3.3

|−

Demostración: (1)

Axioma,doble corte

(2) Inserción

68 Observe que todos los axiomas del capitulo 1, se tuvieron que expresar utilizando el equivalente alscroll de A ,( → ). Por esto se puede garantizar que todo teorema del CP tiene esta forma.69 En el caso que sean varios se debe hacer la selección en cada uno de los gbf que están sobre HA,puesto que cada uno de ellos es un teorema, la única forma que estos sean teoremas es que a su vez seanexpresados usando el scroll.



62

(3) Iteración

(4)Lema 2.1

Ejemplo 3.1▪

Si se usa RA, el procedimiento es similar, con la diferencia que se selecciona un sólo

subgráfico, el que se encuentra bajo una sola cortadura, el objetivo o conclusión es elpseudográfico. El algoritmo funciona igual con un paso más: al final hay que borrar eldoble corte. En el ejemplo 3.3 se muestra la deducción completa siendo los pasos (3) a(5) los resueltos por el agente.

Ejemplo 3.4 |−

Demostración:

(1) Axioma,

doble corte

(2) Inserción

(3) Iteración

(4) Desiteración

(5) Eliminación

(6) Doble corte▪

Cuando se realiza una deducción con premisas, es claro que el módulo podría generarla prueba siempre y cuando no se requiera del uso de las reglas de inserción einserción de doble corte, sin embargo para todos los casos es posible realizar la pruebaporque:

Para dos gbfs ψ y χ, si se quiere mostrar que ψ |− χ, se inscribe ψ por ser unapremisa:



63

Por teorema de deducción se puede inscribir sobre HA:

dado que debe ser un teorema de A y el resultado sigue por MP 70.

|− |−

70 Recuerde que MP no es una regla de inferencia en A , pero puede deducirse en A (Ejemplo 2.1)



64

4 Conclusiones

El desarrollo de este trabajo permite a autor establecer algunas conjeturas y conclusiones, y hacer algunas recomendaciones.

1. Los gráficos existenciales pueden ser presentados a estudiantes de nivelesbásicos, no necesariamente como un sistema formal, sino como unrompecabezas. De esta manera el alumno puede familiarizarse con el procesode descubrimiento o heurística. Otra forma de abordarlo es utilizar Alfacuando ya se han adquirido los conocimientos del lenguaje del cálculoproposicional, con el fin de establecer analogías con Alfa y contribuir aldesarrollo de las competencias relacionadas con las estrategias de deducción.

Como punto medio podría considerarse la propuesta de Yuri Poveda: lossistemas Alfa 0 y Alfa 00 presentados en [POV 071].

2. Consecuente con lo anterior KLPeirce presenta “tres niveles de dificultad”; elprimero representa el sistema de deducción natural A * en el cual no seconsidera HA como un gráfico bien formado. El segundo es el mismosistema de deducción con la convención C1 ( A ), y el tercero, el sistema en elcual sólo se deducen teoremas, es decir, siempre se parte del axioma de A .

3. Puede suprimirse la regla de inserción de A y reemplazar el axioma: HA, por

. De esta forma se obtiene también un sistema deductivocompleto y consistente. Completo porque en la prueba de los axiomas de L como teoremas de A se puede comenzar por el paso 3, que es el axiomapropuesto. También consistente porque es fácilmente verificable que dichoaxioma es una tautología, y se probó que las reglas conservan tautologías. Elsistema es además similar al propuesto por Hilbert y Ackermann (el axioma y la regla del doble corte, prácticamente son lo mismo). Este sistema deductivotiene utilidad práctica porque los métodos automáticos propuestos en 3.4 y elagente serían equivalentes al sistema propuesto si se implementara la regla deinserción del doble corte. En otras palabras solamente es necesarioimplementar R6(M,M,..M) para que KLPeirce pueda generar pruebasautomáticas de todos los teoremas de A.

4. Si se quisiera mejorar aún más la eficiencia del agente se podría implementarh así:

h(n) = W 1 u(n*) + W 2 t(n) + d(n)...donde los coeficientes W 1, W 2,..., W n son ajustables a las circunstancias, porejemplo, en la medida que la profundidad sea mayor se pueden reducir estoscoeficientes para que la búsqueda se realice en un nivel aproximado del quese encuentra la solución. También podrían ajustarse como los pesos de unared neuronal para que el agente aprenda la función heurística.



65

5. Algunos procedimientos avanzados de búsqueda (Ant Colony, Busqueda Tabú, Programación Genética, Simulated Annealing) pueden ser también

aplicables a este problema, permitiendo mejorar la eficiencia. De la mismaforma, los procedimientos de búsqueda desarrollados específicamente paraeste problema pueden ser aplicados a problemas de representación similar.

6. Peirce definió los sistemas Beta y Gama de los gráficos existenciales, que sonequivalentes al Cálculo de Predicados y lógicas modales respectivamente.Dada la representación utilizada para Alfa es posible extender un sistema deInteligencia Artificial de deducción automática para estos sistemas, queestaría en la capacidad, al igual que KLPeirce, de presentar pruebas de formadirecta y no necesariamente por contradicción.

Los ejemplos presentados muestran que la representación utilizada por Peirce,presenta múltiples ventajas. Elementos interactivos pueden contribuir aun más apotencializar el desarrollo de competencias vinculadas con el pensamiento y elrazonamiento: “El pensamiento creativo se debe a la manipulación mental de diagramas. Piensocon diagramas visuales, nunca con palabras” (C. S. Peirce [OOS081], [STUD97]).



66

Referencias

[ALVA01] H. Alvarez.Two Proposals For Searching Improvement In The Bacterial Chemotaxis Algorithm Medellín ,Universidad Nacional de Colombia 2001.

[B ARR 00] Lenin BarreraInteligencia Artificial

Artículo, Escuela Politecnica JaverianaQuito, Ecuador.

[BOBM96] Andrés Bobenrieth.Inconsistencias ¿por que no? : trazos filosóficos en la senda de la lógica paraconsistente

Bogota : Tercer mundo, 1996

[BURR 01] Stanley BurrisComments on propositional proof systems March 13, 2001

www.thoralf.uwaterloo.ca/htdocs/WWW/PDF/discuss.pdf [C AIC90] Xavier Caicedo.

Elementos de Lógica y Calculabilidad Bogotá. Universidad de los Andes, 1990.

[CHUR 56] Alonzo Church

Introduction to mathematical logic Princeton University, 1956.

[FRIT02] Dau. Frithjof The Logic System of Concept Graphs with Negations 2002

www.mathematik.tu-darmstadt.de/~dau/dissertation.pdf

[GRAS97] W. Grassman, J Tremblay. Matemática discreta y lógica. Una perspectiva desde la Ciencia de la Computación.Prentice Hall, 1.997.

[H AMI81] A. G. HamiltonLógica para matemáticos Parainfo, Madrid, 1981

[HEUV 02] Bram van HeuvelnEGTTDP: An Efficient Decision Procedure Based on Existential Graphs, Truth Trees, and Davis-Putnam Summer 2002http://www.cogsci.rpi.edu



67

[HEUV 03] Bram van HeuvelnUsing Existential Graphs for Automated Theorem Proving: The Exclusively

Semantic/Visual Side of the MARMML Automated Reasoner February 2003http://www.cogsci.rpi.edu

[HILB59] David Hilbert, Wilhelm AckermannGrunzuge der theorestische logik(Elementos de lógica teorica)Berlin : Springer-Verlag, 1959

[JIMM03] Leonardo JiménezGráficos Existenciales Gama en Color y Algunos Sistemas de Lógica Modal

Trabajo de Grado, Facultad de Matemáticas Fundación UniversitariaKonrad Lorenz, Bogotá 2003

[K NEA84] William Kneale, Martha KnealeThe development of logic Claredon Press-Oxford, 1984

[K RAU01] Décio Krause Notas de Lógica, Parte 1: Lógica Proposicional Universidade Federal de Santa Catarina, Texto Preliminar 2001.

[M ALD98] Alejandro Martín Maldonado

Completitud De Dos Cálculos Lógicos De Leibniz Trabajo de Grado, Departamento de Matemáticas, Universidad de los Andes, Bogotá 1998

[MEND01] Benito Mendoza GarcíaUso del Sistema de la Colonia de Hormigas para Optimizar Circuitos Lógicos Combinatorios

Tesis: Maestría En Inteligencia ArtificialUniversidad VeracruzanaMayo 2001

[NILS00] Nilsson, N. J..Inteligencia Artificial. Una nueva síntesis .McGraw-Hill, 2.000.

[OOS072] Arnold Oostra, Acercamiento Lógico A Peirce. Boletín de Matemáticas – Nueva Serie VII (2000), no. 2.

[OOS081] Arnold Oostra,Los diagramas de la matemática y la matemática de los diagramas. Boletín de Matemáticas – Nueva Serie VIII (2001), no. 1.



68

[POV 071] Yuri Poveda,

Los Gráficos Existenciales de Peirce en los sistemas Alfa 0 y Alfa 00 Boletín de Matemáticas – Nueva Serie VII (2000), no. 1.

[R OBD73] Don. D RobertsThe Existential Graphs of C. S. Peirce Paris: Mouton & Co. N. V. Publishers, 1973.

[R USS03] Bertrand RussellLos Principios de la matemática.1903

[SOWA14] C. S. Peirce, J. SowaExistential Graphs: MS 514 by Charles Sanders Peirce with Commentary by John F. Sowa.http://www.jfsowa.com/peirce/ms514.htm

[S TUD97] Nathan Houser, Don D. Roberts, James Van Evra (Eds.)

Studies in the Logic of Charles Sanders Peirce Indiana University Press, Bloomington and Indianapolis, 1997.

[T ARS68] Alfred TarskiIntroducción a la lógica y a la metodología de las ciencias deductivas.Espaa – Calpe S.A. Madrid, 1968.

[THIB82] Pierre ThibaudLa Lógica de Charles Sanders Peirce: Del Álgebra a los Gráficos Paraninfo, Madrid, 1982

[ZEMJ64] Jay ZemanThe Graphical Logic of C. S. Peirce Ph. D. dissertation, University of Chicago, 1964.

deducción automática en gráficos existenciales

Documents