1 Desarrollo Unidad 1

1. LOGICA PROPOSICIONAL Y CALCULO DE PREDICADOS.
1.1. Conceptos.
La lógica proposicional, o a veces lógica de orden cero, es

un sistema formal cuyos elementos más simples representan
proposiciones, y cuyas constantes lógicas, llamadas conectivas lógicas,
representan operaciones sobre proposiciones, capaces de formar otras
proposiciones de mayor complejidad.1
Las lógicas proposicionales carecen de cuantificadores o variables de
individuo, pero tienen variables proposicionales (es decir, que se
pueden interpretar como proposiciones con un valor de verdad
definido), de ahí el nombre proposicional. Los sistemas de lógica
proposicional incluyen además conectivas lógicas, por lo que dentro de
este tipo de lógica se puede analizar la inferencia lógica de
proposiciones a partir de proposiciones, pero sin tener en cuenta la
estructura interna de las proposiciones más simples.2
Como las lógicas proposicionales no tienen cuantificadores o variables
de individuo, cualquier secuencia de signos que constituya una fórmula
bien formada admite una valoración en la proposición es verdadera o
falsa dependiendo del valor de verdad asignado a las proposiciones
que la compongan. Esto implica que cualquier fórmula bien formada
define una función proposicional. Por tanto, cualquier sistema lógico
basado en la lógica proposicional es decidible y en un número finito de
pasos se puede determinar la verdad o falsedad semántica de una
proposición. Esto hace que la lógica proposicional sea completa y con
una semántica muy sencilla.
Considérese el siguiente argumento:
1. Mañana es miércoles o mañana es jueves.

2. Mañana no es jueves.
3. Por lo tanto, mañana es miércoles.
Es un argumento válido. Quiere decir que es imposible que
las premisas (1) y (2) sean verdaderas y la conclusión (3) falsa.
Sin embargo, a pesar de que el argumento sea válido, esto no quiere
decir que la conclusión sea verdadera. En otras palabras, si las
premisas son falsas, entonces la conclusión también podría serlo. Pero
si las premisas son verdaderas, entonces la conclusión también lo es.
La validez del argumento no depende del significado de las
expresiones «mañana es miércoles» ni «mañana es jueves», sino de la
estructura misma del argumento. Estas premisas podrían cambiarse
por otras y el argumento permanecería válido. Por ejemplo:
1. Hoy está soleado o está nublado.

2. Hoy no está nublado.
3. Por lo tanto, hoy está soleado.
La validez de los dos argumentos anteriores depende del significado de
las expresiones «o» y «no». Si alguna de estas expresiones se cambia
por otra, entonces los argumentos podrían dejar de ser válidos. Por
ejemplo, considérese el siguiente argumento inválido:
1. Ni está soleado ni está nublado.

2. No está nublado.
3. Por lo tanto, está soleado.
Estas expresiones como «o» y «no», de las que depende la validez de
los argumentos, se llaman conectivas lógicas. En cuanto a expresiones
como «está nublado» y «mañana es jueves», lo único que importa de
ellas es que tengan un valor de verdad. Es por esto que se las
reemplaza por simples letras, cuya intención es simbolizar una
expresión con valor de verdad cualquiera. A estas letras se las
llama variables proposicionales, y en general se toman del alfabeto
latino, empezando por la letra p (de «proposición») luego q, r, s, etc. Es
así que los dos primeros argumentos de esta sección se podrían
reescribir así:
1. p o q
2. No q
3. Por lo tanto, p
Y el tercer argumento, a pesar de no ser válido, se puede reescribir así:
1. Ni p ni q
2. No q
3. Por lo tanto, p
[ CITATION htt21 \l 3082 ]

1.2. Tablas de verdad, Formas normales y dispositivos de dos estados.
Tablas de verdad.
Artículo principal: Tablas de verdad
La tabla de verdad de una fórmula es una tabla en la que se

presentan todas las posibles interpretaciones de las variables
proposicionales que constituye la fórmula y el valor de verdad de la
fórmula completa para cada interpretación. Por ejemplo, la tabla de
verdad para fórmula:
Como se ve, esta fórmula tiene 2n interpretaciones posibles —una

por cada línea de la tabla— donde n es el número de variables
proposicionales (en este caso 3, es decir p, q, r) y resulta ser
una tautología, es decir que bajo todas las interpretaciones posibles
de las variables proposicionales, el valor de verdad de la fórmula
completa termina siendo V.
¿Qué es una tabla de verdad?

Fundamentalmente, una tabla de verdad es un dispositivo para
demostrar ciertas propiedades lógicas y semánticas de enunciados
del lenguaje natural o de fórmulas del lenguaje del cálculo
proposicional:
- Sin son tautológicas, contradictorias o contingentes
- Cuáles son sus condiciones de verdad
- Cuál es su rol inferencial, es decir, cuáles son sus conclusiones

lógicas y de qué otras proposiciones se siguen lógicamente el
procedimiento para construir una tabla de verdad es sencillo y
relativamente mecánico;
en esta plática, asumiré que todos saben ya cómo hacer una tabla
de verdad para cualquier fórmula del cálculo proposicional clásico.
Para aplicar el método de tablas de verdad a un enunciado o
proposición, por lo tanto, es necesario primero simbolizarlo, es decir,
determinar qué fórmula del lenguaje proposicional muestra su forma
lógica y, luego, elaborar la tabla de verdad de dicha formula.
Si al aplicar el método de tablas de verdad encontramos que una

fórmula es tautológica, presumimos que ella es una verdad lógica
del cálculo proposicional es decir que es lógicamente válida,
lógicamente verdadera o verdadera con necesidad lógica. Por lo
tanto, el uso de las tablas de verdad como métodos para demostrar
que algo es lógicamente necesario presupone ciertas tesis sobre la
verdad y la necesidad lógicas. Cada uno de los pasos y cada una de
las características de las tablas de verdad representa una tesis
lógica sustancial.
Tomemos por ejemplo, el popular principio de que toda tabla tiene

2n renglones, dónde la n corresponde al número de variables
proposicionales (también conocidas como “letras proposicionales”)
que aparecen en la fórmula. Una fórmula de 3 variables
proposicionales, por ejemplo, tendría 23=8 renglones.
Pero ¿por qué es esto? La respuesta más directa es que ése es el

número de combinaciones que existen de asignaciones de valores
de verdad a cada una de las variables. En otras palabras, porque si
asignamos a cada variable uno de los dos valores de verdad –
verdadero o falso –, las posibles combinaciones son exactamente
ocho, ni más, ni menos. Si bien es una verdad matemática
indudable que la combinatoria de dos valores a n número de
variables es 2n, para que este principio valga como principio lógico
dentro de una demostración lógica – que, a fin de cuentas es lo que
una tabla de verdad es –, es necesario que ciertas cosas sean
verdaderas: Por ejemplo, entre otras cosas, es necesario que para
determinar que una fórmula sea tautológica baste tomar en cuenta
sólo cuál es el posible valor de verdad que tome la interpretación de
sus variables proposicionales. También es necesario que se
requieran considerar todas las posibles interpretaciones de las
variables. Además, es necesario que a cada asignación de valores a
las variables les corresponda uno y sólo un renglón. También es
necesario que los valores de verdad sean dos – verdadero o falso.
Si los valores de verdad fueran más, o fueran menos, las
combinaciones posibles serían otras: más renglones si son más
valores, y menos renglones si fueran menos valores. Además, el
número de renglones a considerar también cambiaría si en cada
renglón cada variable proposicional pudiera tener, no un sólo valor
determinado, sino dos (o más) o ninguno. Las así-llamadas lógicas
no-clásicas surgen precisamente de cuestionar y cambiar algunos
de estos presupuestos de las tablas de verdad clásicas, dando pie
así a un tipo de tablas de verdad no-clásicas.
El principio que pone en cuestión la lógica multivalente, por

ejemplo, es el principio de que la interpretación de toda variable
proposicional no puede tener sino uno de los dos valores de verdad:
verdadero y falso. A este principio se le conoce comúnmente como
bivalencia y junto con el principio de no-contradicción ha sido

considerado uno de los principios lógicos básicos. Los métodos
semánticos de las lógicas intensionales, por su parte, surge de
cuestionar otro principio lógico básico: el de que es necesario
considerar todas las posibles interpretaciones de las variables.
Además de estas tablas, hay muchas otras tablas de verdad raras,
de las cuales no hablaremos en clase, pero no pro ello quiero dejar
de mencionar. Por ejemplo, hay tablas de verdad en las que los
renglones se bifurcan en dos o más sub-renglones y son útiles para
lo que en lógica llamamos super-valuaciones.
También existen tablas con n valores y más de 2n renglones, ¿cómo

es posible? Pues porque, a diferencia de las tablas tradicionales, en
estas tablas el orden de los renglones sí importa, de tal manera que
renglones repetidos cuentan como renglones distintos.
Lógica Intensional y el Principio de Independencia Lógica
Como hemos visto, en clases básicas de lógica solemos aprender

que una tabla de verdad tiene siempre 2n renglones, dónde n es el
número de ocurrencias de operadores lógicos en la fórmula o
argumento que se esté simbolizando. Lo que comúnmente no se
nos enseña es que, como bien señalo Wittgenstein ya en su
Tractatus Logico-Philosophicus para que esto sea verdad, las
variables deber simbolizar proposiciones atómicas o, por lo menos,
lógicamente independientes entre sí (es decir, cada proposición

simbolizada debe ser lógicamente independiente de las demás).
Para verificar que efectivamente estamos tratando con dos

proposiciones independientes, A y B, es necesario que estas
satisfagan cuatro condiciones:
(i) A no debe seguirse de B, es decir, debe ser posible que A sea

verdadero y B falso, y
(ii) vice versa, B no debe seguirse de A, es decir, debe ser posible

que B sea
verdadero y A falso.
(iii) La verdad de A debe ser compatible con la verdad de B, debe

ser posible que tanto A como B sean ambos verdaderos al mismo
tiempo, es decir, en la misma
circunstancia.
(iv) La falsedad de A debe ser compatible con la de B, debe ser
posible que tanto A
como B sean ambos falsos al mismo tiempo, es decir, en la misma

circunstancia.
Cuando sólamente tenemos una proposición, ésta no debe ser

necesariamente verdadera ni necesariamente falsa.
Si no se cumplen alguna de estas condiciones, entonces alguna de

los renglones posibles de la tabla representara como posible un
caso que no es realmente posible. Si A se sigue lógicamente de B,
por ejemplo, entonces ya no es posible que A sea verdadera y B
falsa. Por ello, el renglón que le asigna verdadero a A y falso a B no
representa una posibilidad real. Es necesario, pro lo tanto, eliminarlo
de la tabla.
El que una fórmula sea tautológica, contradictoria o contingente,

depende por supuesto, de cuales son los renglones de la tabla en la
que se evalúa. La misma fórmula puede ser contingente en una
tabla, contradictoria en otra y tautológica en otra más,
dependiendo de qué renglones tenga la tabla en cuestión. Hay

formulas que siempre serán tautológicas o contradictorias, no
importa en qué tablas las evaluemos. Estas son lastautologías y
contradicciones que ya conocemos de nuestro cálculo proposicional.
En otras palabras, si una fórmula es tautológica en la tabla de
verdad tradicional de 2n renglones, entonces será tautológica en
cualquier otra tabla de verdad. Si una formula es verdadera en todos
los renglones, no importa qué renglones eliminamos, seguirá siendo
verdadera en todos ellos. Lo mismo sucede con las formulas que
resultan contradictorias en las tablas de 2n renglones: también son
contradictorias en cualquier otra tabla. Por el contrario, si una
fórmula es contingente en la tabla de 2n renglones, entonces
dependerá de qué renglones se incluyan o eliminen de la tabla para
que sea contradictoria, tautológica o contingente.
Supongamos que queremos hacer la tabla de verdad del siguiente
enunciado:
(2) Si tu hermano no hace el examen, no lo pasará.
Identificamos las proposiciones atómicas y les asignamos una

variable:
P: Tu hermano hace el examen.
Q: Tu hermano pasará el examen.
De esta manera, podemos formalizar (2) como (~P)⇒(~Q) y

construir su tabla de la
siguiente manera:
Sin embargo, hay algo extraño en el análisis que presenta

esta tabla, ya que nos dice,
entre otras cosas, que el enunciado sería falso si P fuera

falso y Q verdadero, es decir, si
tu hermano no hiciera el exámen y, sin embargo, lo pasará,

¡lo cual es imposible! Por eso
es que pareciera que este renglón no debería de aparecer en

la tabla, ya que no es una
posibilidad sino una imposibilidad. Así pues, la tabla de

verdad correcta debería ser algo
así cómo:
Y ahora sí podemos ver que, en realidad, ¡el enunciado
expresaba una tautología! Desde esta perspectiva, por lo
tanto, las fórmulas no son tautológicas, contradictorias o
contingentes en sí mismas, sino en una tabla, y qué tabla
sea la adecuada para evaluar una formula no va a depender
de la fórmula misma, sino de su interpretación, es decir,
de qué proposiciones simboliza cada variable proposicional.

Por ello, mucha gente dice que este tipo de tablas no
respetan el principio según el cual las propiedades lógicas de
una proposición, en particular si una proposición es

tautológica o no, debe depender sólo de su forma, no de su
interpretación particular.
La notación polaca, también conocida como notación de

prefijo o notación prefija, es una forma de notación para
la lógica, la aritmética, el álgebra y la computación. Su
característica distintiva es que coloca los operadores a la
izquierda de sus operandos. Si la aridad de los operadores
es fija, el resultado es una sintaxis que carece de paréntesis
u otros signos de agrupación, y todavía puede ser analizada
sin ambigüedad. El lógico polaco Jan Łukasiewicz inventó
esta notación alrededor de 1920 para simplificar la lógica
proposicional.
Aquí hay una cita de Axiom and Generalizing Deduction de
Nicod , página 180.
Vine sobre la idea de una notación libre de paréntesis en

1924. Utilicé esa notación por primera vez en mi artículo
Lukasiewicz(1), P. 610, nota al pie de la página.
La referencia de arriba, citada por Jan Lukasiewicz es

al parecer un informe litografiado en polaco.
Alonzo Church menciona esta notación en su libro

clásico sobre lógica matemática como digna de
observación en los sistemas notacionales incluso
contrastados con la Exposición notacional lógica y el
trabajo Principia
Mathematica de Whitehead y Russell.1
Mientras que no se ha usado más en lógica, la

notación polaca ha encontrado un espacio en
las ciencias de la computación.
La expresión para sumar los números uno y dos, en la

notación de prefijo, se escribe "+ 1 2" en vez de "1 + 2".
En expresiones más complejas, los operadores todavía
preceden sus operandos, pero los operandos pueden
ser ellos mismos expresiones no triviales incluyendo sus
propios operadores. Por ejemplo, la expresión que sería
escrita en la notación de infijo convencional como
(5 - 6) * 7
puede ser escrito en prefijo como
* (- 5 6) 7
o simplemente
*-567
Puesto que los simples operadores

aritméticos son todos binarios (por lo
menos, en contextos aritméticos), cualquier
representación prefijo de ellos es
inequívoca, y poner signos de agrupamiento
a la expresión de prefijo es innecesario. En
el ejemplo anterior, los paréntesis en la
versión de infijo eran requeridos. Si los
movemos:
5 - (6 * 7)
o simplemente los quitamos:
5-6*7
cambiaría el significado y el
resultado de toda la expresión. Sin
embargo, la versión
correspondiente de prefijo de este
segundo cálculo sería escrita como:
-5*67
El proceso de la substracción
es diferido hasta que ambos
operandos de la substracción
se hayan leído (es decir, 5 y el
producto de 6 y 7). Como
con cualquier notación, las
expresiones más interiores son
evaluadas primero, pero en la
notación de prefijo este
"interioridad" se puede
transportar por el orden en vez
del agrupamiento.
La notación de prefijo de la aritmética simple es en

gran parte de interés académico. Como la similar
notación de posfijo o notación polaca inversa, la
notación de prefijo ha sido usada en algunas
calculadoras comerciales (HP-11C).April
2009[cita requerida] Sin embargo, la aritmética de notación
de prefijo es usada con frecuencia como primer paso
conceptual en la enseñanza de la construcción de
un compilador.
Formas normales
A menudo es necesario transformar una fórmula en otra, sobre
todo transformar una fórmula a su forma normal. Esto se
consigue transformando la fórmula en otra equivalente y
repitiendo el proceso hasta conseguir una fórmula que solo use
los conectivos básicos:
Para lograr esto se utilizan las equivalencias lógicas:

1.3. Forma normal disyuntiva principal.
En lógica booleana, una forma normal

disyuntiva (FND) es una estandarización (o
normalización) de una fórmula lógica que es
una disyunción de cláusulas conjuntivas. Como
una forma normal, es útil en la demostración
automática de teoremas. Una fórmula FND está
en forma normal disyuntiva completa si cada
una de sus variables aparece exactamente una
vez en cada cláusula.
Al igual que en forma normal conjuntiva (FNC),
los únicos operadores proposicionales en FND
son la conjunción, disyunción y negación. Una
negación solo se puede aplicar a un literal, lo que
significa que solo puede preceder a una variable
proposicional. Por ejemplo, todas las siguientes
fórmulas están en FND:
Convertir una fórmula en FND

La conversión de una fórmula para FND implica el
uso de equivalencias lógicas como la eliminación de
la doble negación, las leyes de De Morgan, y uso de
la distributividad.
Todas las fórmulas lógicas se pueden convertir en
forma normal disyuntiva. Sin embargo, en algunos
casos, la conversión a FND puede conducir a una
explosión exponencial de la fórmula. Por ejemplo, en
FND, las fórmulas lógicas de las siguientes formas
tienen términos 2n:
Cualquier función booleana en particular puede ser

representada por una y solo una forma normal
disyuntiva completa, una de las dos formas
canónicas.
Una variación importante utilizada en el estudio de
la complejidad computacional es k-DNF. Una fórmula
está en k-FND si está en FND y cada cláusula
contiene en la mayoría de los literales k. A diferencia
de las subclases correspondientes de forma normal
conjuntiva para k> = 3, no hay algoritmo fácil de
convertir una instancia arbitraria de una fórmula en
FND a k-FND.
La siguiente fórmula es una gramática formal para
FND:
1. disyunción → conjunción
2. disyunción → disyunción ∨ conjunción
3. conjunción → literal
4. conjunción → (conjunción ∧ literal)
5. literal → variable
6. literal → ¬variable
Donde variable es cualquier variable.

1.4. Forma normal conjuntiva principal.
En lógica booleana, una fórmula está en forma normal

conjuntiva (FNC) si corresponde a
una conjunción de cláusulas, donde una cláusula es
una disyunción de literales, donde un literal y su
complemento no pueden aparecer en la misma cláusula.
Esta definición es similar a la de forma de productos de
sumas usadas en teoría de circuitos.
Todas las conjunciones de literales y todas las
disyunciones de literales están en FNC, puesto que
pueden ser vistas, respectivamente, como conjunciones
de cláusulas de un literal, y como conjunciones de una
única cláusula. Al igual que en una forma normal
disyuntiva (FND), los únicos conectivos lógicos que
pueden aparecer en una fórmula en FNC son
la conjunción, disyunción y negación. El operador
negación solo puede aplicarse a un literal, y no a una
cláusula completa, lo que significa que este sólo puede
preceder a una variable proposicional o un símbolo de
predicado.
En demostración automática de teoremas, la noción de
«forma normal clausal» se utiliza frecuentemente en un
sentido más estricto, significando una representación
particular de una fórmula FNC como un conjunto de
conjuntos de literales.
1.5. Notación polaca y patentizada.
La notación polaca, también conocida como notación de

prefijo o notación prefija, es una forma de notación para la lógica,
la aritmética, el álgebra y la computación. Su característica distintiva
es que coloca los operadores a la izquierda de sus operandos. Si
la aridad de los operadores es fija, el resultado es una sintaxis que
carece de paréntesis u otros signos de agrupación, y todavía puede
ser analizada sin ambigüedad. El lógico polaco Jan
Łukasiewicz inventó esta notación alrededor de 1920 para simplificar
la lógica proposicional.
Aquí hay una cita de Axiom and Generalizing Deduction de Nicod ,
página 180.
Vine sobre la idea de una notación libre de paréntesis en 1924.
Utilicé esa notación por primera vez en mi artículo Lukasiewicz(1),
P. 610, nota al pie de la página.
La referencia de arriba, citada por Jan Lukasiewicz es al parecer un
informe litografiado en polaco.
Alonzo Church menciona esta notación en su libro clásico
sobre lógica matemática como digna de observación en los sistemas
notacionales incluso contrastados con la Exposición notacional
lógica y el trabajo Principia Mathematica de Whitehead y Russell.1
Mientras que no se ha usado más en lógica, la notación polaca ha
encontrado un espacio en las ciencias de la computación.
La expresión para sumar los números uno y dos, en la notación de
prefijo, se escribe "+ 1 2" en vez de "1 + 2". En expresiones más
complejas, los operadores todavía preceden sus operandos, pero los
operandos pueden ser ellos mismos expresiones no triviales incluyendo
sus propios operadores. Por ejemplo, la expresión que sería escrita en
la notación de infijo convencional como
(5 - 6) * 7
puede ser escrito en prefijo como
* (- 5 6) 7
o simplemente
*-567
Puesto que los simples operadores aritméticos son
todos binarios (por lo menos, en contextos aritméticos),
cualquier representación prefijo de ellos es inequívoca, y
poner signos de agrupamiento a la expresión de prefijo es
innecesario. En el ejemplo anterior, los paréntesis en la
versión de infijo eran requeridos. Si los movemos:
5 - (6 * 7)
o simplemente los quitamos:
5-6*7
cambiaría el significado y el resultado de toda la
expresión. Sin embargo, la versión
correspondiente de prefijo de este segundo cálculo
sería escrita como:
-5*67
El proceso de la substracción es diferido hasta
que ambos operandos de la substracción se
hayan leído (es decir, 5 y el producto de 6 y 7).
Como con cualquier notación, las expresiones
más interiores son evaluadas primero, pero en
la notación de prefijo este "interioridad" se
puede transportar por el orden en vez del
agrupamiento.
La notación de prefijo de la aritmética simple es en gran parte de
interés académico. Como la similar notación de posfijo o notación
polaca inversa, la notación de prefijo ha sido usada en algunas
calculadoras comerciales (HP-11C).April 2009[cita requerida] Sin embargo,
la aritmética de notación de prefijo es usada con frecuencia como
primer paso conceptual en la enseñanza de la construcción de
un compilador.
Orden de las operaciones

El orden de operaciones es definido dentro de la estructura de la
notación de prefijo y puede ser fácilmente determinada. Una cosa
a tener presente es que al ejecutar una operación, la operación es
aplicada AL primer operando POR el segundo operando. Esto no
es un problema con las operaciones que conmutan, pero para las
operaciones no conmutativas como la división o la substracción,
este hecho es crucial para análisis de una sentencia. Por ejemplo,
la sentencia siguiente:
/ 10 5 = 2 (prefijo)
Se lee como "Divide 10 POR 5". Así la solución es 2, no ½ como

sería el resultado de un análisis incorrecto de dividir 5 entre 10.
La notación de prefijo es especialmente popular entre las
operaciones basadas en pila debido a su capacidad natural de
distinguir fácilmente el orden de las operaciones sin la necesidad
de paréntesis. Para evaluar el orden de las operaciones bajo la
notación de prefijo, incluso no se necesita memorizar una
jerarquía operacional, como con la notación de infijo. En lugar de
eso, se mira directamente a la notación para descubrir qué
operador evaluar primero. Leyendo una expresión de izquierda a
derecha, primero se busca un operador y se procede a buscar dos
operandos. Si se encuentra otro operador antes de que se
encuentren los dos operandos, entonces el operador viejo es
colocado a un lado hasta que este nuevo operador sea resuelto.
Este proceso se itera hasta que un operador sea resuelto, lo cual
debería suceder siempre, puesto que en una sentencia completa
debe haber un operando más que la cantidad de operadores. Una
vez que esté resuelto, el operador y los dos operandos son
reemplazados por un nuevo operando. Puesto que un operador y
dos operandos son eliminados y un operando es añadido, hay una
pérdida neta de un operador y un operando, lo cual todavía deja
una expresión con N operadores y N+1 operandos, permitiendo
así que el proceso iterativo continúe. Ésta es la teoría general tras
el uso de stacks en lenguajes de programación para evaluar una
sentencia en la notación de prefijo, aunque hay varios algoritmos
que manipulan el proceso. Una vez que es analizada una
sentencia en la notación de prefijo, llega a ser menos intimidante
mientras que permite una cierta separación desde la convención
con una añadida conveniencia. Un ejemplo muestra la facilidad
con la cual una sentencia compleja en la notación de prefijo se
puede descifrar a través del orden de las operaciones:
La expresión en notación de infijo ((15 / (7 - (1 + 1))) * 3) - (2 + (1
+ 1)) se resuelve de la siguiente manera en notación polaca o de
prefijo:
La notación polaca inversa, notación de postfijo, o notación

posfija (en inglés, Reverse Polish Notation, o RPN), es un
método algebraico alternativo de introducción de datos. Su
nombre viene por analogía con la relacionada notación polaca,
una notación de prefijo introducida en 1920 por el matemático
polaco Jan Łukasiewicz(alias Robert) en donde cada operador
está antes de sus operandos. En la notación polaca inversa es
al revés: primero están los operandos y después viene el
operador que va a realizar los cálculos sobre ellos. Tanto la
notación polaca como la notación polaca inversa no necesitan
usar paréntesis para indicar el orden de las operaciones,
mientras la aridad del operador sea fija.
El esquema polaco inverso fue propuesto en 1954 por Burks,

Warren y Wright1 y reinventado independientemente por
Friedrich L. Bauer y Edsger Dijkstra a principios de los años
1960, para reducir el acceso de la memoria de computadora y
para usar el stack para evaluar expresiones. La notación y los
algoritmos para este esquema fueron extendidos por el
filósofo y científico de la computación australiano Charles
Leonard Hamblin a mediados de los años 1960.23
Posteriormente, Hewlett-Packard lo aplicó por primera vez en
la calculadora de sobremesa HP-9100A en 1968 y luego en la
primera calculadora científica de bolsillo, la HP-35. Durante
los años 1970 y 1980, el RPN tenía cierto valor incluso entre
el público general, pues fue ampliamente usado en las
calculadoras de escritorio del tiempo - por ejemplo, las
calculadoras de la serie HP-10C.
En ciencias de la computación, la notación de postfijo es

frecuentemente usada en lenguajes de programación
concatenativos y basados en pila. También es común en
sistemas basados en flujo de datos y tuberías, incluyendo las
tuberías de Unix.
Funcionamiento
Su principio es el de evaluar los datos directamente cuando se
introducen y manejarlos dentro de una estructura LIFO (Last In
First Out), lo que optimiza los procesos a la hora de programar.
Básicamente las diferencias con el método algebraico
o notación de infijo es que, al evaluar los datos directamente al
introducirlos, no es necesario ordenar la evaluación de los
mismos, y que para ejecutar un comando, primero se deben
introducir todos sus argumentos, así, para hacer una suma
«a+b = c» el RPN lo manejaría «a b +», dejando el
resultado c directamente.
Nótese que la notación polaca inversa no es literalmente la
imagen especular de la notación polaca: el orden de los
operandos es igual en la tres notaciones (infijo, prefijo o polaca,
y postfijo o polaca inversa), lo que cambia es el lugar donde va
el operador. En la notación infija, el operador va en el medio de
los operandos, mientras que en la notación polaca va antes y en
la notación polaca inversa va después. Así pues, «640 / 16» (en
notación de infijo), se escribe como «/ 640 16» (en notación
polaca) y como «640 16 /» en notación polaca inversa. El orden
de los operandos es importante cuando se manejan operadores
no conmutativos (como la resta o la división), así, si dividimos
10 entre 2, por ejemplo, en las tres notaciones se debe escribir
de la siguiente manera: «10 / 2», «/ 10 2», «10 2 /».
El algoritmo RPN
El algoritmo que utilizan las calculadoras RPN es relativamente
simple:
 Si hay elementos en la bandeja de entrada:

o Leer el primer elemento de la bandeja de
entrada.
o Si el elemento es un operando.
 Poner el operando en la pila.
o Si no, el elemento es una función (los
operadores, como "+", no son más que
funciones que toman dos argumentos).
 Se sabe que la función x toma n
argumentos.
 Si hay menos de n argumentos en la
pila
 (Error) El usuario no ha
introducido suficientes
argumentos en la
expresión.
 Si no, tomar los últimos n operandos
de la pila.
 Evaluar la función con respecto a los
operandos.
 Introducir el resultado (si lo hubiere)
en la pila.
 Si hay un solo elemento en la pila:
o El valor de ese elemento es el resultado del
cálculo.
 Si hay más de un elemento en la pila:
o (Error) El usuario ha introducido demasiados
elementos.
Ejemplo
La expresión algebraica 5+((1+2)*4)-3 se traduce a la notación
polaca inversa como 5 1 2 + 4 * + 3 - y se evalúa de izquierda a
derecha según se muestra en la siguiente tabla. La «pila» es la
lista de los valores que el algoritmo mantiene en su memoria
después de realizar la operación dada en la segunda columna.

1.6. Transformación de notaciones.
La notaciones de prefijo (o polaca, en homenaje a Jan

Łukasiewicz), de infijo y de postfijo (o polaca inversa) son
formas de escritura de expresiones algebraicas que se
diferencian por la posición relativa que toman
los operadores y los operandos. En la notación de prefijo, el
operador se escribe delante de los operandos (+ 3 4), entre
los operandos en la notación de infijo (3 + 4) y tras los
operandos en la de posfijo (3 4 +).
La notación de prefijo fue propuesta en 1924 por el

matemático, lógico y filósofo polaco Jan Łukasiewicz (1878-
1956), de allí el nombre alternativo por la que se conoce.
Al igual que la de postfijo, la notación polaca permite

prescindir de los paréntesis en el caso de operadores
de aridad fija conocida. Por ejemplo, la operación 5 * (12 +
4).puede escribirse en prefijo como: * 5 (+ 12 4); o
sencillamente: * 5 + 12 4 (y como 5 12 4 + *en postfijo).
Łukasiewicz introdujo esta notación con la intención de

simplificar la lógica proposicional. El matemático y
lógico Alonzo Church la mencionaba en su libro
clásico Introduction to Mathematical Logic (1956) como una
notación digna de observación. Aunque dejó pronto de
utilizarse en lógica, encontró su lugar en las ciencias de la
computación. Por ejemplo, el lenguaje de
programación LISP basa precisamente su sintaxis en la
notación polaca.
Las calculadoras Hewlett-Packard usan la notación polaca

inversa, económica en número de entradas, pero que
requiere un esfuerzo adicional para la interpretación del
resultado. Esta empresa utilizó este sistema por primera vez
en 1968, en la calculadora de sobremesa HP-9100A. Y fue
también ésta la notación de la primera calculadora científica
de bolsillo, la HP-35, usada entre 1972 y 1975.
En ciencias de la computación, la notación de postfijo se usa

en lenguajes de programación orientados a pila y en
sistemas basados en tuberías.
Pero volvamos, para finalizar, a Jan Łukasiewicz, al que

rendimos hoy homenaje porque falleció un 13 de febrero, en
Dublin, donde emigró tras la Segunda Guerra Mundial.
Como ya hemos comentado, trabajó fundamentalmente en

lógica proposicional, sistema formal en el que pensaba
realizar innovaciones. Estudió los sistemas axiomáticos de la
lógica e impulsó las lógicas multivaluadas, dando una
interpretación de la lógica modal.
Hoc est falsum (Esto es falso).

No, no, lo que he comentado arriba no es falso. Esta
sentencia es la versión de Girolamo Savonarola de la
famosa paradoja del mentiroso. Jan Łukasiewicz dio una
solución de esta paradoja en los siguientes términos:
Todo principio lógico contiene variables. Estas variables,

como las variables en matemáticas, pueden tener varios
valores. Existe una ley lógica que dice que todos los
principios lógicos se refieren solo a aquellos objetos que
pueden ser valores de variables. Se puede demostrar que la
frase anterior que contiene la contradicción no puede ser el
valor de una variable. Por lo tanto, los principios lógicos no
se aplican a esta oración. Esta construcción está fuera de la
lógica.

1.7. Elementos de inferencia para el cálculo proposicional.
Las reglas de inferencia usa dos tipos de elementos: los datos

(hechos o evidencia) y el conocimiento (el conjunto de reglas
almacenadas en la base de conocimiento), para obtener nuevas
conclusiones o hechos. Por ejemplo, si la premisa de una regla es
cierta. Los datos iniciales se incrementan incorporando las
nuevas conclusiones. Por ello, tanto los hechos iniciales o datos
de partida como las conclusiones derivadas de ellos forman
parte de los hechos o datos de que se dispone en un instante
dado.
Las conclusiones pueden clasificarse en dos tipos: simples o
compuestas. Las conclusiones simples son las que resultan de
una regla. Las conclusiones compuestas son las que resultan de
más de una regla. Para obtener conclusiones, los expertos
utilizan diferentes tipos de reglas y estrategias de inferencia y
control.
Tipos de reglas de inferencia
 Modus Ponens
 Modus Tollens
 Mecanismo de Resolución
Modus Ponens
Es quizás la regla de inferencia más comúnmente utilizada. Se
utiliza para obtener conclusiones simples. En ella, se examina la
premisa de la regla, y si es cierta, la conclusión pasa a formar
parte del conocimiento. Considere el siguiente ejemplo,
supóngase que se tiene la regla, "Si A es cierto, entonces B es
cierto" y que se sabe además que "A es cierto". Entonces la regla
Modus Ponens concluye que "B es cierto". Esta regla de
inferencia, que parece trivial, debido a su familiaridad, es la base
de un número de sistemas expertos.
Ejemplo:
1. p® q
½¾
2. p
3. q
Modus Tollens
Se utiliza también para obtener conclusiones simples. En este
caso se examina la conclusión y si es falsa se concluye que la
premisa también es falsa. Por ejemplo, supóngase de nuevo que
se tiene la regla "A es cierto, entonces B es cierto" pero se sabe
que "B es falso". Entonces, utilizando la regla Modus Ponens no
se puede obtener ninguna conclusión, pero, la regla Modus
Tollens concluye que "A es falso". Auque muy simple y con
muchas aplicaciones útiles, la regla Modus Tollens es menos
utilizada que la Modus Ponens.
Por ello, la regla Modus Ponens se mueve hacia delante, es decir,
de la premisa a la conclusión de una regla, mientras que la regla
Modus Tollens se mueve hacia atrás, es decir, de la conclusión a
la premisa. Las dos reglas de inferencia no deben ser vistas como
alternativas sino como complementarias. La regla Modus
Ponens necesita información de los objetos de la premisa para
concluir, mientras que la regla Modus Tollens necesita
información sobre los objetos de la conclusión. De hecho, para
un motor de inferencia que solamente utiliza Modus Ponens, la
incorporación de la regla de inferencia Modus Tollens puede ser
considerada como una expansión de la base de conocimiento
mediante la adición de reglas.
Ejemplo:
1. p® q
½¾
2. Ø q
3. Ø p
Mecanismo de resolución
Las reglas de inferencia Modus Ponens y Modus Tollens pueden
ser utilizadas para obtener conclusiones simples. Por otra parte,
las conclusiones compuestas, que se basan en dos o más reglas,
se obtienen usando el llamado mecanismo de resolución. Esta
regla de inferencia consiste en las etapas siguientes:
1. Las Reglas son sustituidas por expresiones lógicas
equivalentes.
2. Estas expresiones lógicas se combinan en otra
expresión lógica.
3. Esta última expresión se utiliza para obtener la
conclusión.
Estas etapas involucran conceptos tales como la combinación y

simplificación de expresiones lógicas, que se ilustra de modo
intuitivo en el siguiente ejemplo.
Supóngase que se tienen las dos reglas:
Regla 1: Si A es cierto, entonces B es cierto
Regla 2: Si B es cierto, entonces C es cierto
La primera etapa en el mecanismo de resolución consiste en
sustituir cada una de las dos reglas por expresiones lógicas
equivalentes. Esto se hace como sigue:
 La Regla 1 es equivalente a la expresión lógica: "A es
falso o B es cierto". Una prueba de esta equivalencia
se muestra en la tabla de verdad que se muestra en la
figura No. 12.
 Similarmente, la Regla 2 es equivalente a la expresión
lógica: "B es falso o C es cierto".
Figura No. 12 Tabla de verdad mostrando que la regla "Si A es

cierto, entonces B es cierto" es equivalente a la expresión lógica
"A es falso o B es cierto"
La segunda etapa consiste en combinar las dos expresiones
anteriores en una, tal como sigue: las expresiones lógicas "A es
falso o B es cierto y "B es falso o C es cierto" implican la
expresión "A es falso o C es cierto". Una prueba de esta
equivalencia se muestra en la figura No. 13. Esta última
expresión se utiliza seguidamente en la tercera etapa para
obtener la conclusión.

1.8. Método basado en tablas de verdad.Una tabla de verdad lista
todos los posibles valores de una o varias proposiciones simples y el
valor de verdad de una o varias proposiciones compuestas construidas
a partir de las proposiciones simples. En el caso más sencillo tenemos
satiro simplemente una proposición simple y listamos los valores de
verdad que puede tener, que en el caso de la lógica proposicional son
verdadero y falso
1.9. Método de derivación paso a paso.
1.10. Prueba automática de teoremas.
La demostración automática de teoremas (de siglas ATP, por el

término en inglés: Automated theorem proving) que también puede
ser denominada Deducción automatizada, es actualmente el
subcampo más desarrollado del razonamiento automático, y se
encarga de la demostración de teoremas
matemáticos mediante programas de ordenador.
1.11. Razonamiento automático.
El razonamiento automatizado es un área de la ciencias de la

computación dedicada a comprender diferentes aspectos
del razonamiento de manera que permita la creación de programas
informáticos que posibiliten a los ordenadores razonar de forma
completamente automática, o casi automática. Se le considera
habitualmente como una subárea de la inteligencia artificial, pero
además posee fuertes conexiones con la Teoría de la
computación e incluso con la filosofía.
La historia del razonamiento automatizado se remonta a los

primeros indicios de la mecanización del mismo, que pueden
remontarse a la filosofía de la Antigua Grecia, que dio origen,
finalmente de la mano de Aristóteles, al tratado de lógica
proposicional descrito en su compendio de libros, Órganon. Éste
pretendía esquematizar los razonamientos usando símbolos que
sustitutían a las distintas afirmaciones (proposiciones) que formaban
parte de un razonamiento. Los debates y discusiones sobre lógica
proposicional estuvieron desde entonces en boga de los filósofos
griegos, hasta la llegada de la Edad Media. Por ejemplo, y con
respecto a la interpretación de la conectiva llamada
implicador, Calímaco llegó a decir:
Hasta los cuervos discuten en los tejados éste problema
Con la llegada de los pueblos bárbaros, y la caída de la cultura
clásica, la Europa Medieval perdió y no reavivó el interés científico
aproximadamente hasta el siglo XII con la introducción de los textos
aristotélicos, que desde entonces gobernaron la filosofía escolástica,
alrededor del siglo XI, traídos y recopilados celosamente desde
hacía siglos por la tradición musulmana, en la Casa de la sabiduría.
Esto propició la aparición de la llamada Revolución Científica del
siglo XII, que volvió a reavivar, entre otras cosas, las
preocupaciones de la lógica, todavía desde un punto de vista
totalmente filosófico.
Ya en el 1305, el pensador catalán Ramon Llull, fuertemente
influenciado por Roger Bacon (uno de los
primeros revolucionarios del siglo XII), escribió un tratado, el Ars
Magna, que puede considerarse un claro precursor del
razonamiento automatizado, ya entendido como un procedimiento
mecánico que razona por sí mismo. A diferencia de la lógica
aristotélica (sinónima de proposicional), que solo es una herramienta
para hacer razonamientos desde un punto de vista más analítico,
pero realizados en última instancia por el individuo, el Ars Magna de
Llull era un sistema de circunferencias con etiquetas de símbolos
que representan conceptos, y que conectados como si de una
maquinaria de reloj se tratara, permitía seleccionar distintos
atributos o conceptos en la máquina, y, accionándola, permitiría
llegar a las conclusiones de dicho razonamiento. Estos estaban muy
fuertemente imbuidos de conceptos teológicos y filosóficos, para
realizar razonamientos en estas áreas, de modo que se llegara a
verdades indiscutibles (de principal orientación a la ideología
cristiana), a partir de conceptos que atribuirían como verdaderos
tanto judíos como musulmanes, a fin de convencer a ambos
bandos.
El siguiente eslabón de esta cadena recaía en posesión de Gottfried
Leibniz. Debido a su fuerte convicción racionalista, reflexionó sobre
la posibilidad de construir, ya no solamente una máquina, sino
también un lenguaje universal (concepto preconizado por René
Descartes, padre del racionalismo) que tuviera el suficiente poder de
expresión para razonar con coherencia, rigidez y sin ambigüedad
sobre cualquier tipo de concepto. Él se inspiró en el Ars Magna de
Llull para construir éste Ars combinatoria.
Durante todo este período, el estudio sobre el razonamiento, tanto
mecánico como analítico, caía dentro del campo de la filosofía y en
las manos de los filósofos y matemáticos con inclinaciones
filosóficas.
Fue en el siglo XIX y XX, ya de la mano de la matemática, donde se
obtuvieron nuevos enfoques sobre el razonamiento. El principal
interés fue axiomatizar la matemática en una teoría axiomática basal
que la constituyera entera, entre cuyos principales autores y
responsables pueden citarse a Dedekind (que consiguió reunir la
matemática numérica e infinitesimal, mediante las
llamadas cortaduras de Dedekind), los debates y la disputa
entre Georg Cantor, Gottlob Frege y Bertrand Russell (sobre los
problemas y conceptos del infinito y el conjunto, y la construcción de
la lógica de primer orden), David Hilbert, estableciendo su finitismo
metodológico, y por último Ernst Zermelo y Adolf Fraenkel que
construyeron su axiomática ZF, que ha permanecido prácticamente
invariable hasta nuestros días. Se consiguió entonces culminar este
proceso de axiomatización que la matemática llevaba
experimentando durante más de un siglo.
Y es este proceso el que propició los nuevos enfoques sobre el
razonamiento automatizado moderno. Una vez conseguido un
marco formal de razonamiento y construcción de la matemática, la
siguiente pregunta obvia era la capacidad mecánica de los sistemas
que se acaban de constituir. Es decir, qué información me otorgan
los símbolos, qué conexiones pueden existir entre las premisas y las
conclusiones que se intentan demostrar, dentro de una teoría
axiomática, y cuáles son sus limitaciones teóricas. Dicho de otra
forma, hasta qué punto un matemático o un lógico podía trasladar a
los símbolos la responsabilidad de realizar el horrible y tedioso
trabajo de conseguir demostrar teoremas, con solo seguir los pasos
marcados por un procedimiento mecánico.
Las respuestas a estas preguntas tuvieron dos salidas principales: la
primera fue la construcción de todo el corpus matemático de
la computación (la formalización del concepto de algoritmo, es decir,
la formalización del concepto de proceso mecánico y función
computable), principalmente de la mano de Alan Turing, y la
segunda los resultados sobre las limitaciones de expresión
y aptitud de los lenguajes formales, que son los usados para
razonar, resultados principalmente tomados de la mano de Kurt
Gödel.
A partir de todos estos resultados teóricos conjuntos, empezó a
divergir su utilidad práctica (al menos en los problemas que caben
dentro de las limitaciones teóricas), con la construcción
de softwares de razonamiento, tanto automatizado como interactivo,
para ayudar, por ejemplo, a guiar al usuario que desee demostrar
algunos teoremas de sus propios sistemas, por ejemplo, en
problemas de verificación del software.
Las subáreas más desarrolladas del razonamiento automatizado
son probablemente la demostración automática de teoremas (y la
menos automática, pero más pragmática demostración interactiva
de teoremas y la verificación de demostraciones (que garantiza que
un razonamiento es correcto). Además, se ha realizado un trabajo
enorme en el razonamiento por analogía, inducción y abducción.
Otros temas importantes son el razonamiento con incertidumbre y el
razonamiento no monótono. Una parte importante del razonamiento
con incertidumbre es la argumentación, donde se aplican
restricciones de minimalidad y de consistencia sobre el
razonamiento automatizado clásico. El sistema Oscar de John
Pollock es un ejemplo de argumentación automática que es más
específico que un "simple" demostrador automatizado de teoremas.
La argumentación formal es un subárea de la inteligencia artificial.
Las herramientas y las técnicas del razonamiento automatizado
incluyen las lógicas y los cálculos clásicos de demostración
automática de teoremas, así como la lógica difusa, la inferencia
bayesiana el razonamiento por el principio de entropía maximal y un
gran número de técnicas ad hoc menos formales.
1.12. Prueba automática de teoremas.
METODO DE REDUCCION MATRICIAL (RM)

En general el método intenta unificar, combinar y extender
algunas reglas del método de Davis y Putnam con las de
Prawitz, la
técnica de demostración seguida es por refutación.
Este método en sus primeros pasos transforma al conjunto
inicial
de cláusulas S en una matriz de clausuléis (como en el método
de
Prawitz), adicionando propiedades a caída cláusula; como el
número
de literales, el de literales positivas, y el número de literales
negativas. Propiedades similares son colocadas a la matriz
recien
formada. La idea al adicionar tales propiedades es para
facilitar
la aplicación de los siguientes pasos del método.
Enseguida se intenta trabajar con el número mínimo de
cláusulas, por lo que se aplican estrategias de simplificación,
como:
- Eliminación de Tautologías
- Reducción clausular (elimina literales repetidos de la
cláusula)
- Eliminación de cláusulas con literales puros
Después de simplificar a cada cláusula y reducir el número de

cláusulas, el método intenta probar la inconsistencia de la
matriz
utilizando para ello a las cláusulas unitarias (cláusulas que
constan de sólo un literal), aplica resolución y eliminación por
inclusión de las cláusulas unitarias con todas las demás
posibles
(Regla del literal aislado en el método de Davis y Putnam).
Este
paso es aplicado hasta que no más resoluciones y
eliminaciones
puedan aplicarse sobre cláusulas unitarias.
Def. Una cláusula D incluye a otra cláusula C, si existe una
sustitución 0 tal que C0 £ D. Por ejemplo:
P(x) está incluida en P(y) v Q(z) (con 0 = <x/y> )
Una cláusula D que incluye a alguna otra cláusula, puede
eliminarse sin afectar la inconsistencia del resto del conjunto
clausular.
Toda cláusula resolvente de una cláusula unitaria con otra, es
adicionada a la matriz de cláusulas, en tanto que el proceso de
inclusión elimina a toda cláusula de la matriz que sea incluida
por la cláusula unitaria. Este es un proceso finito, puesto que
se
tiene un número finito de cláusulas (entre ellas las unitarias),
y
la longitud del resolvente E de una cláusula D con una
cláusula
unitaria, es en cada paso reducido en uno. Es decir, si
definimos:
Longitud(C) = número de literales en C, y E es un resolvente
de D
y C (cláusula unitaria), entonces: Longitud(E) = Longitud(D)
- 1.
Si en este paso se genera la cláusula NIL, entonces el método

termina indicando inconsistencia del conjunto original de
cláusulas.
Si después de la aplicación de este paso el conjunto resultante
de
cláusulas es vacío, entonces el conjunto inicial de cláusulas es
satisfacible.
Si después de este paso no se prueba la inconsistencia o
satisfactibilidad de la matriz clausular, se aplica entonces el
principio
de reducción matricial del método de Prawitz, la cual divide a
la
matriz que se está trabajando M en dos matrices MI y M2,
este paso
va formando el árbol matricial.
Cada una de las nuevas matrices creadas tienen una cláusula unitaria
más que la matriz padre de la que provienen. Y el proceso general
vuelve a aplicarse ahora para las nuevas matrices hijos. Para dividir
la matriz M en dos matrices Mi y M2 , la estrategia a seguir es la
siguiente: Se buscan dos cláusulas C. y C. no unitarias (puesto que
las unitarias ya han sido resueltas) que resuelvan sobre una literal 1
Lo que genera un árbol de matrices. Y a cada una de las submatrices

se le puede aplicar el algoritmo general.
El proceso de manera general puede verse como:

1.- Traducir el conjunto inicial de cláusulas. se pasa el
conjunto original de cláusulas a una notación matricial y se
renombran variables comúnes entre ellas.
2.- Simplificación y reducción de cláusulas, aplicando

estrategias de simplificación como: a) Eliminación de
tautologías
b) Eliminación de literales repetidos
c) Eliminación de cláusulas con literales puros

1.13. Cálculo de predicados.
1.14. Predicados.
1.15. Fórmulas de predicados.
En el cálculo de predicados el valor de verdad depende de los

componentes que forman el predicado. Por ejemplo: Pedro es padre
de Idalia es una expresión en cálculo de predicados, que en general
podría ser: x es padre de y, o simplemente p(x,y).
En otras palabras, se tiene aquí una proposición abierta que

depende de dos variables, y que por supuesto el valor de verdad
depende de los valores que se le dan a las variables, porque por
ejemplo: Frank es padre de Lisbeth puede tener un valor de verdad
diferente al anterior.
En general, se puede decir que un predicado puede tener una o

más variables y que las variables pueden tomar valores de un
conjunto específico llamado DOMINIO. Así por ejemplo las dos
expresiones mencionadas anteriormente son de la forma p(x,y)
donde el predicado p representa “es padre de” y el domino es el
conjunto de las personas.
El Cálculo de Predicados permite ampliar el espectro

del Cálculo_Proposicional, trabajando con fórmulas de diversos
tipos además del booleano.
Mientras la lógica proposicional presenta limitaciones expresivas no

permitiendo describir la estructura interna de las proposiciones, la
lógica de predicados cuenta con un lenguaje mucho más expresivo
que posibilita resolver esas limitaciones.
En la lógica proposicional la representación proposicional del juicio

“Si Ana estudia, aprueba” se compone de dos átomos “Ana estudia”,
representado como p y “Ana aprueba”, representado como q, pero
las variables proposicionales p y q no reflejan el vínculo que existe
entre las proposiciones que representan, (ambas hacen referencia a
Ana).
En el lenguaje del cálculo de predicados los átomos tienen una

representación relacional, pudiendo representarse “Ana estudia”
como Est(ana), donde Est(x) es la relación untaria (de un
argumento) que expresa que el individuo x estudia, de un modo
similar “Ana aprueba” puede representarse como Apr(ana), siendo
Apr(x) la relación que expresa que el individuo x aprueba, de este
modo Est(ana) y Apr(ana) expresan explícitamente que ambas
proposiciones hacen referencia a propiedades distintas (estudiar y
aprobar) de un mismo objeto (Ana).
Por lo tanto se puede definir Cálculo de predicado como

un sistema formal, estructurado para el estudio de la inferencia en
los lenguajes formales con cuantificadores que alcanzan solo a
variables de individuos, y con predicados y funciones cuyos
argumentos son constantes o variables de individuos.
La construcción de fórmulas en este cálculo obliga a definir nuevas
expresiones llamadas predicados.
Un predicado es una aplicación de una función booleana cuyos

argumentos pueden ser de diferentes tipos, es decir un predicado
puede ser una función de tipo Z → B.
Los nombres de las funciones (igual, menor) son llamados símbolos

de predicados. También se utiliza la notación x < y para expresar el
predicado menor(x, y). Por ejemplo, la siguiente expresión x < y ∧ x
= z ⇒ q(x, z + x) contiene tres predicados, x < y, x = z y q(x, x + z).
Los argumentos de los predicados son en este caso, variables de

tipo distinto de B o también expresiones de éstos tipos.
Los argumentos de un predicado son llamados términos, por

ejemplo en la fórmula anterior los términos en los predicados son x,
y, z y z + x.
El cuantificador universal
La conjunción ᴧ es asociativa, conmutativa y tiene elemento neutro

verdadero. Por lo tanto puede considerarse una operación válida
para definir la expresión cuantificada.
(ᴧ x : R : P )
El símbolo Ɐ, que se lee “para todo”, se conoce como cuantificador
universal y la expresión anterior se denomina cuantificación
universal y se lee “para todo x que satisfaga R se satisface P ”.
La sentencia “todos los cantantes hacen uso intensivo de la voz”,
presenta una variable, pues “cantantes” no hace referencia a ningún
elemento en particular por lo que sólo puede ser representado por
una variable, sin embargo constituye una proposición porque se le
puede asignar un valor veritativo.
Esto se debe a que la variable está cuantificada universalmente por

“todos” con lo que se expresa que la propiedad “hacer uso intensivo
de la voz” se cumple por todos los elementos del universo (conjunto
de todos los cantantes).
El cuantificador universal (∀) es la operación que en el cálculo de

predicados permite representar este tipo de proposiciones
quedando el ejemplo anterior de la siguiente manera:
∀(x) UsoIntVoz(x)
>Puede apreciarse que x, de acuerdo con lo planteado en el

epígrafe anterior, es libre en UsoIntVoz(x), pero no ocurre lo mismo
en ∀(x) UsoIntVoz(x) pues al cuantificarse una variable, esta deja de
ser libre.
Algunos ejemplos del uso de este cuantificador son los siguientes:

a)Todos los perros ladran.
b)Cada hombre debe pensar por su propia cabeza.
Es posible definir este nuevo operador a partir de otro ya conocido,

la conjunción (ᴧ), pues si a1, a2, a3... son los elementos del
universo en que toma valores la variable x, entonces:
∀(x) A(x) ⇔ A(a1) ᴧ A(a2) ᴧ A(a3) ᴧ ...
Esta equivalencia, evidencia que basta con que para un valor ai del
universo, A(ai) sea falsa para que∀(x) A(x) sea falsa también.
Por último queda especificar que si el universo en que toma valores

la variable x es vacío se establece que ∀(x) A(x) es verdadera.
El cuantificador existencial
La disyunción ⅴ es simétrica, asociativa y su elemento neutro es

falso. Por lo tanto puede considerarse una operación válida para
definir la expresión cuantificada
(ⅴ x : R : P )
Esta expresión se escribe usualmente así:
(∃x : R : P )
El símbolo ∃, que se lee “existe”, se conoce como cuantificador

existencial y la expresión anterior se denomina cuantificación
existencial y se lee “existe x en el rango R que satisface P ”.
La sentencia “alguien ha llegado”, es una proposición con una

variable, pero esta no está cuantificada universalmente. Este tipo de
proposiciones presentan cuantificación existencial, que se expresa
mediante: “alguien”, “algún”, “un”, etc.
En este caso se plantea que la propiedad “haber llegado” se cumple

por al menos uno de los elementos del universo (conjunto de todas
las personas).
El cuantificador existencial (∃) es la operación que en el cálculo de

predicados permite representar este tipo de proposiciones
quedando el ejemplo anterior de la siguiente manera:
∃(x) HaLlegado(x)
Algunos ejemplos del uso de este cuantificador son los siguientes:
c)Hay hombres que han dado su vida por la libertad.

d)Un estudiante llegó tarde.
Este operador, al igual que ∀(), puede definirse a partir de otro ya

conocido, en este caso la disyunción (v), pues si a1, a2, a3... son
los elementos del universo en que toma valores la variable x,
entonces:
∃(x) A(x) ⇔ A(a1) v A(a2) v A(a3) v ...
Esta equivalencia, evidencia que basta con que para un valor ai del
universo, A(ai) sea verdadera para que ∃(x) A(x) sea verdadera
también.
En caso de que el universo en que toma valores la variable x sea

vacío se establece que ∃(x) A(x) es falsa.
Alfabeto del cálculo de predicados
Al igual que el cálculo proposicional, el cálculo de predicados cuenta

con un alfabeto, algunos de cuyos símbolos ya se han analizado.
Este alfabeto cuenta, en primer lugar, con símbolos de constantes

individuales, que se denotarán como combinaciones de letras y
números comenzando siempre por una letra minúscula. En caso de
utilizar solo una letra, esta será de las primeras del alfabeto latino (a,
b, c, d, e,...).
También forman parte de este alfabeto los símbolos de variables

individuales que se denotarán mediante las últimas letras del
alfabeto latino (u, v, w, x, y, z).
Otros componentes del alfabeto son los símbolos de funciones que

serán letras minúsculas del alfabeto latino, o combinaciones de
letras y números (con inicial minúscula), preferentemente se
emplearán f, g y h.
Integran el alfabeto también símbolos de relaciones, que serán

combinaciones de letras y números comenzando siempre por una
letra mayúscula.
Los símbolos del cuantificador universal ∀() y existencial ∃() vistos

con anterioridad, evidentemente también componen este alfabeto.
Por último, los símbolos de constantes proposicionales, operaciones
proposicionales y de agrupación, vistos en el alfabeto del cálculo
proposicional integran este alfabeto también.
Términos y fórmulas del cálculo de predicados
Al igual que el cálculo proposicional, el cálculo de predicados define

el concepto de fórmula, pero establece además, una expresión
fundamental que se denomina término y se define según las reglas
siguientes:
1. Toda constante y toda variable es un término.
2. Si t1,t2,...,tn son términos y f es un símbolo de función n-aria, en-

tonces f(t1,t2,..., tn) es un término.
3. Todo término es el resultado de la aplicación un número finito de
veces de las dos reglas anteriores.
Conociendo la definición de término, es posible establecer el

concepto de fórmula del cálculo de predicados, que se sustenta en
el de fórmula elemental o átomo:
definiciòn. Si t1, t2,..., tn son tèrminos y R un símbolo de relación n-

aria, entonces R(t1, t2,..., tn) es una fórmula elemental o átomo.
Algunos ejemplos de fórmulas elementales o átomos son los

siguientes:
a) R(a, x).
b) Amigo(luis, juan).
c) Hermano(x, y).
d) Grande(x).
e) Padre(x, y).
f) Madre(x, y).
g)Padres(x,y,z).
Evidentemente, un átomo representará una proposición elemental,

pero para representar la proposiciones no elementales no basta con
una fórmula atómica por lo que se define el concepto de fórmula de
la siguiente manera:
1. Toda fórmula elemental es una fórmula.
2. Si A es una fórmula, entonces ¬A es una fórmula.
3. Si A y B son fórmulas, entonces [A v B], [A ᴧ B], [A ⇒ B] y

[A ⇔ B] son fórmulas.
4. Si A es una fórmula donde x ocurre libre, entonces ∀(x)A y ∃(x)A

son fórmulas.
5. Toda fórmula es el resultado solamente de la aplicación de un

número finito de veces de las reglas1, 2, 3 y 4.
Algunos ejemplos de fórmulas son los siguientes:
a) Padres(x,y,z).
e) Padres(x,y,z) ⇔ Padre(x,z) ᴧ Madre(y,z).
b) Padres(luis,ana,jose).
f) Padre(luis,jose) ᴧ Madre(ana,jose).
g) ∀(x)∀(y)∀(z)[ Padres(x,y,z) ⇔ Padre(x,z) ᴧ Madre(y,z)].
Interpretación de fórmulas del cálculo de predicados
En el cálculo proposicional, una interpretación de una fórmula es

una asignación de valores a las variables involucradas, determinar
todas las interpretaciones de una fórmula no resulta difícil pues cada
variable sólo tomas valores en {0, 1}.
En el cálculo de predicados esto se torna mucho más complejo,

pues las variables toman valores en diversos universos y aparecen
los cuantificadores que hacen necesario analizar desde otra
perspectiva la interpretación de fórmulas, siendo preciso establecer:
1. Un conjunto U, que será el dominio de valores de cada variable

libre y al que pertenecerán todas las constantes.
2. Una función con dominio en Un y codominio en U por cada

símbolo de función n-aria.
3. Una relación definida en Un por cada símbolo de relación n-aria.
Quedando entonces determinado que una fórmula A tiene una

interpretación en U si todos los símbolos de constantes, de
funciones n-arias y de relaciones n-arias que ocurren en A se
interpretan, respectivamente, en elementos, funciones n-arias y
relaciones n-arias en U.
Establecido lo anterior, para determinar el valor veritativo de una

fórmula, dada una interpretación, se procede de la siguiente
manera:
1. Si A es una fórmula atómica de la forma R(a1,…, an), entonces A

es verdadera en U si y solo si < a1,…, an > pertenece a R
2. Si A es la fórmula ¬B, entonces A es verdadera en U si y solo si B

es falsa en U.
3. Si A es la fórmula B v C, entonces A verdadera en U si y solo si al

menos una de las fórmulas B o C es verdadera en U.
4. Si A es la fórmula B ᴧ C, entonces A es verdadera en U si y solo

si las fórmulas B y C son verdaderas en U.
5. Si A es la fórmula B ⇒ C, entonces A es verdadera en U si y solo

si al menos B es falsa en U o C es verdadera en U.
6. Si A es la fórmula B ⇔ C, entonces A es verdadera en U si y solo

si ambas fórmulas B ⇒ C y C ⇒ B son verdaderas en U.
7. Si A es la fórmula ∀(x)B(x), entonces A es verdadera en U si y

solo si B(x) es verdadera en U para cualquier valor de x
pertenece U.
8. Si A es la fórmula ∃(x)B(x), entonces A es verdadera en U si y
solo si B(x) es verdadera en U para al menos un valor de x
pertenece a U.
El siguiente ejemplo ilustra la interpretación de fórmulas del cálculo

de predicados.
Sea la interpretación I definida por:
U = {1, 2, 3, 4},
R = {<1,1>,<1,2>,<1,3>,<1,4>,<2,3>},
f = {<1,2>,<2,3>,<3,4>,<4,1>}
a = 1, b = 2
Sean las fórmulas del cálculo de predicados:
a) ∀(x)R(x, f(x))
b) ∃(x)R(x, f(x))
c) ∀(x)R(a, x)
d) ∃(x)R(b, x)
e)∀(x)[∃(y)R(x, y) ⇒ R(x, 3)]
Determine el valor de las fórmulas anteriores:
a) ∀(x)R(x, f(x)).
En este caso la fórmula es falsa para I, pues R(3, f(3)), es R(3, 4) y

<3,4> no pertenece a R.
b) ∃(x)R(x, f(x)). Esta fórmula es cierta para I, pues basta con que
un valor de x haga R(x, f(x)) verdadera y esto ocurre con x = 1.
c) ∀(x)R(a, x). Como a = 1, la veracidad de esta fórmula depende de

que R(1,x) sea cierta para todos los valores de x, lo que en efecto
ocurre, siendo entonces verdadera.
d) ∃(x)R(b, x). Como b = 2 y para x = 3 se tiene R(2, 3), que es

cierto, entonces la fórmula lo es también.
e) ∀∃(y)R(x, y) ⇒ R(x, 3)]. Esta fórmula es cierta pues lo son:
∃(y)R(1, y) ⇒ R(1, 3)
∃(y)R(2, y) ⇒ R(2, 3)
∃(y)R(3, y) ⇒ R(3, 3)
∃(y)R(4, y) ⇒ R(4, 3)
La primera lo es, pues la parte derecha de la implicación lo es. Lo

mismo ocurre con la segunda. La tercera y la cuarta son ciertas
pues sus implicantes son falsos (ningún par de R tiene como primer
elemento al 3 o al 4).

REFERENCIAS
Bibliografía
http://di002.edv.uniovi.es/~labra/FTP/LPRED.pdf. (01 de 01 de 2021).
http://di002.edv.uniovi.es/~labra/FTP/LPRED.pdf. Obtenido de
http://di002.edv.uniovi.es/~labra/FTP/LPRED.pdf:
http://di002.edv.uniovi.es/~labra/FTP/LPRED.pdf
http://www.filosoficas.unam.mx/~abarcelo/INTENSIONAL/2012/260312.pdf. (01 de 01 de
2021). http://www.filosoficas.unam.mx/~abarcelo/INTENSIONAL/2012/260312.pdf.
Obtenido de
http://www.filosoficas.unam.mx/~abarcelo/INTENSIONAL/2012/260312.pdf:
http://www.filosoficas.unam.mx/~abarcelo/INTENSIONAL/2012/260312.pdf
http://www.iesseneca.net/iesseneca/IMG/pdf/tema_7_logica.pdf. (01 de 01 de 2021).
http://www.iesseneca.net/iesseneca/IMG/pdf/tema_7_logica.pdf. Obtenido de
http://www.iesseneca.net/iesseneca/IMG/pdf/tema_7_logica.pdf:
http://www.iesseneca.net/iesseneca/IMG/pdf/tema_7_logica.pdf
https://culturacientifica.com/2019/02/13/la-notacion-polaca-la-de-jan-
lukasiewicz/#:~:text=Por%20ejemplo%2C%20la%20operación%205, d. (01 de 01
de 2021). https://culturacientifica.com/2019/02/13/la-notacion-polaca-la-de-jan-
lukasiewicz/#:~:text=Por%20ejemplo%2C%20la%20operación%205,de
%20simplificar%20la%20lógica%20proposicional. Obtenido de
%20simplificar%20la%20lógica%20proposicional.:
%20simplificar%20la%20lógica%20proposicional.
https://es.wikipedia.org/wiki/Lógica_proposicional#Tablas_de_verdad. (01 de 01 de 2021).
https://es.wikipedia.org/wiki/Lógica_proposicional#Tablas_de_verdad. Obtenido
de https://es.wikipedia.org/wiki/Lógica_proposicional#Tablas_de_verdad:
https://es.wikipedia.org/wiki/Lógica_proposicional#Tablas_de_verdad
https://es.wikipedia.org/wiki/Demostración_automática_de_teoremas#:~:text=9%20Bibliog
rafía-, D. (06 de 06 de 2021).
https://es.wikipedia.org/wiki/Demostración_automática_de_teoremas#:~:text=9%2
0Bibliografía-,Definición,demostrar%20teoremas%20de%20geometría%20plana.
Obtenido de
Bibliografía-,Definición,demostrar%20teoremas%20de%20geometría%20plana.:
Bibliografía-,Definición,demostrar%20teoremas%20de%20geometría%20plana.
https://es.wikipedia.org/wiki/Forma_normal_conjuntiva. (01 de 01 de 2021).
https://es.wikipedia.org/wiki/Forma_normal_conjuntiva. Obtenido de
https://es.wikipedia.org/wiki/Forma_normal_conjuntiva:
https://es.wikipedia.org/wiki/Forma_normal_conjuntiva
https://es.wikipedia.org/wiki/Forma_normal_disyuntiva. (01 de 01 de 2021).
https://es.wikipedia.org/wiki/Forma_normal_disyuntiva. Obtenido de
https://es.wikipedia.org/wiki/Forma_normal_disyuntiva:
https://es.wikipedia.org/wiki/Forma_normal_disyuntiva
https://es.wikipedia.org/wiki/Notación_polaca. (01 de 01 de 2021).
https://es.wikipedia.org/wiki/Notación_polaca. Obtenido de
https://es.wikipedia.org/wiki/Notación_polaca:
https://es.wikipedia.org/wiki/Notación_polaca
https://es.wikipedia.org/wiki/Notación_polaca_inversa#:~:text=La%20notación%20polaca
%20inversa%2C%20notación, a. (01 de 01 de 2021).
https://es.wikipedia.org/wiki/Notación_polaca_inversa#:~:text=La%20notación
%20polaca%20inversa%2C%20notación,alternativo%20de%20introducción
%20de%20datos.&text=En%20la%20notación%20polaca%20inversa,realizar
%20los%20cálculos%20sobre%20ellos. Obtenido de
%20polaca%20inversa%2C%20notación,alternativo%20de%20introducción%20de
%20datos.&text=En%20la%20notación%20polaca%20inversa,realizar%20los
%20cálculos%20sobre%20ellos.:
%20polaca%20inversa%2C%20notación,alternativo%20de%20introducción%20de
%20datos.&text=En%20la%20notación%20polaca%20inversa,realizar%20los
%20cálculos%20sobre%20ellos.
https://es.wikipedia.org/wiki/Razonamiento_automático. (6 de 01 de 2021).
https://es.wikipedia.org/wiki/Razonamiento_automático. Obtenido de
https://es.wikipedia.org/wiki/Razonamiento_automático:
https://es.wikipedia.org/wiki/Razonamiento_automático
https://es.wikiversity.org/wiki/Lógica_proposicional/Tablas_de_verdad#:~:text=Una
%20tabla%20de%20verdad%20permite, l. (01 de 01 de 2021).
https://es.wikiversity.org/wiki/Lógica_proposicional/Tablas_de_verdad#:~:text=Un
a%20tabla%20de%20verdad%20permite,las%20proposiciones%20simples%20que
%20contiene. Obtenido de
%20contiene.:
%20contiene.
https://www.cs.cinvestav.mx/TesisGraduados/1989/TesisGuillermoIta.pdf. (06 de 01 de
2021). https://www.cs.cinvestav.mx/TesisGraduados/1989/TesisGuillermoIta.pdf.
Obtenido de
https://www.cs.cinvestav.mx/TesisGraduados/1989/TesisGuillermoIta.pdf:
https://www.cs.cinvestav.mx/TesisGraduados/1989/TesisGuillermoIta.pdf
https://www.ecured.cu/Cálculo_de_predicados. (06 de 01 de 2021).
https://www.ecured.cu/Cálculo_de_predicados. Obtenido de
https://www.ecured.cu/Cálculo_de_predicados:
https://www.ecured.cu/Cálculo_de_predicados
https://www.monografias.com/trabajos16/calculo-proposicional/calculo-
proposicional.shtml. (01 de 01 de 2021).
proposicional.shtml. Obtenido de https://www.monografias.com/trabajos16/calculo-
proposicional/calculo-proposicional.shtml:
proposicional.shtml
https://www.oposinet.com/temario-de-filosofia/temario-1-filosofia/tema-6-el-clculo-de-
proposiciones-y-de-predicados/. (01 de 01 de 2021).
https://www.oposinet.com/temario-de-filosofia/temario-1-filosofia/tema-6-el-clculo-
de-proposiciones-y-de-predicados/. Obtenido de
https://www.oposinet.com/temario-de-filosofia/temario-1-filosofia/tema-6-el-
clculo-de-proposiciones-y-de-predicados/: https://www.oposinet.com/temario-de-
filosofia/temario-1-filosofia/tema-6-el-clculo-de-proposiciones-y-de-predicados/
https://www.youtube.com/watch?v=5zhXm3J9xdE. (01 de 01 de 2021).
https://www.youtube.com/watch?v=5zhXm3J9xdE. Obtenido de
https://www.youtube.com/watch?v=5zhXm3J9xdE:
https://www.youtube.com/watch?v=5zhXm3J9xdE

1 Desarrollo Unidad 1

Cargado por

Copyright:

Formatos disponibles

1 Desarrollo Unidad 1

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

1 Desarrollo Unidad 1

Cargado por

Copyright:

Formatos disponibles

1. LOGICA PROPOSICIONAL Y CALCULO DE PREDICADOS.

La lógica proposicional, o a veces lógica de orden cero, es

1. Mañana es miércoles o mañana es jueves.

1. Hoy está soleado o está nublado.

1. Ni está soleado ni está nublado.

[ CITATION htt21 \l 3082 ]

La tabla de verdad de una fórmula es una tabla en la que se

Como se ve, esta fórmula tiene 2n interpretaciones posibles —una

[ CITATION htt21 \l 3082 ]

¿Qué es una tabla de verdad?

- Sin son tautológicas, contradictorias o contingentes

- Cuáles son sus condiciones de verdad

- Cuál es su rol inferencial, es decir, cuáles son sus conclusiones

Si al aplicar el método de tablas de verdad encontramos que una

Tomemos por ejemplo, el popular principio de que toda tabla tiene

Pero ¿por qué es esto? La respuesta más directa es que ése es el

El principio que pone en cuestión la lógica multivalente, por

bivalencia y junto con el principio de no-contradicción ha sido

También existen tablas con n valores y más de 2n renglones, ¿cómo

Lógica Intensional y el Principio de Independencia Lógica

Como hemos visto, en clases básicas de lógica solemos aprender

lógicamente independientes entre sí (es decir, cada proposición

Para verificar que efectivamente estamos tratando con dos

(i) A no debe seguirse de B, es decir, debe ser posible que A sea

(ii) vice versa, B no debe seguirse de A, es decir, debe ser posible

(iii) La verdad de A debe ser compatible con la verdad de B, debe

como B sean ambos falsos al mismo tiempo, es decir, en la misma

Cuando sólamente tenemos una proposición, ésta no debe ser

Si no se cumplen alguna de estas condiciones, entonces alguna de

El que una fórmula sea tautológica, contradictoria o contingente,

dependiendo de qué renglones tenga la tabla en cuestión. Hay

(2) Si tu hermano no hace el examen, no lo pasará.

Identificamos las proposiciones atómicas y les asignamos una

P: Tu hermano hace el examen.

Q: Tu hermano pasará el examen.

De esta manera, podemos formalizar (2) como (~P)⇒(~Q) y

Sin embargo, hay algo extraño en el análisis que presenta

entre otras cosas, que el enunciado sería falso si P fuera

tu hermano no hiciera el exámen y, sin embargo, lo pasará,

es que pareciera que este renglón no debería de aparecer en

posibilidad sino una imposibilidad. Así pues, la tabla de

de qué proposiciones simboliza cada variable proposicional.

una proposición, en particular si una proposición es

La notación polaca, también conocida como notación de

Vine sobre la idea de una notación libre de paréntesis en

La referencia de arriba, citada por Jan Lukasiewicz es

Alonzo Church menciona esta notación en su libro

Mientras que no se ha usado más en lógica, la

La expresión para sumar los números uno y dos, en la

puede ser escrito en prefijo como

Puesto que los simples operadores

o simplemente los quitamos:

La notación de prefijo de la aritmética simple es en

[ CITATION htt211 \l 3082 ]

Para lograr esto se utilizan las equivalencias lógicas:

1.3. Forma normal disyuntiva principal.

En lógica booleana, una forma normal

Convertir una fórmula en FND

Cualquier función booleana en particular puede ser