CAPITULO I

INTRODUCCION

En forma natural, el ser humano representa el conocimiento simbólicamente:

imágenes, lenguaje hablado y lenguaje escrito. Adicionalmente, ha desarrollado
otros sistemas de representación del conocimiento: literal, numérico, estadístico,
estocástico y lógico.

En los organismos biológicos se estima que el conocimiento es almacenado como

estructuras complejas de neuronas interconectadas.

En las computadoras, el conocimiento se almacena como estructuras simbólicas,

pero en forma de estados eléctricos y magnéticos.

La lógica proposicional es la más antigua y simple de las formas de lógica.

Utilizando una representación primitiva del lenguaje, permite representar y
manipular aseveraciones sobre el mundo que nos rodea. La lógica proposicional
permite el razonamiento, a través de un mecanismo que primero evalúa sentencias
simples y luego sentencias complejas, formadas mediante el uso de conectivos
proposicionales, por ejemplo Y (AND), O (OR). Este mecanismo determina la
veracidad de una sentencia compleja, analizando los valores de verdad asignados a
las sentencias simples que la conforman.

La historia de la lógica empieza a marcarse a través de los años, haciendo

aportaciones a ella, pensadores muy renombrados por sus hechos. Cabe señalar
que en este documento solo se hará referencia a algunos de ellos.

Principalmente uno de los más conocidos es Aristóteles, siendo la lógica

Aristotélica la base para guiarse y de esta manera continuar haciendo diferentes
estudios y pruebas con el fin de confirmar lo estipulado, siendo así como
empezarían a descubrir algunas fallas en esta disciplina. Aristóteles se basa
básicamente en el Silogismo.

Otro pensador y filosofo y que una de las áreas de la lógica lleva su nombre es
George Boole con la denomina álgebra de Booleana. Hizo importantes
aportaciones a la lógica matemáticas como al álgebra. Por ende el álgebra
Booleana es considerada como la base para la construcción del switch telefónico y
en lo que es la fabricación de computadoras.

Se le atribuye el término de "Inducción matemática" a De Morgan, a él también se

le deben las leyes De Morgan, con su estudio descubrió que el álgebra de la lógica
natural tiene rutas hacia otros tipos de álgebras.

Existieron muchos pensadores y muchas otras aportaciones no sin pensar que no

tienen mucha importancia, solo que el fin no es remontarse desde el nacimiento de
la lógica hasta la denominada lógica moderna. Por último y no menos importante
Lukasiewicz, mismo que escribió fragmentos de los principios de la no
contradicción, desarrollando un árbol de valores para el calculo proposicional.
"La lógica es una ciencia racional no sólo según la forma, sino también según la
materia; una ciencia a priori de las leyes necesarias del pensamiento, no con
relación a objetos determinados, sino con relación a objetos en general; es, pues
una ciencia del recto uso del entendimiento y de la razón en general; no de manera
subjetiva, es decir, no según principios empíricos, psicológicos (como piensa el
entendimiento), sino de manera objetiva, es decir, según principios a priori (cómo
el entendimiento debe pensar)"

INICIOS DEL CALCULO PROPOSICIONAL

Revisión histórica de los métodos del pensamiento. (Aristóteles, George Boole,

Augustus De Morgan y Jan Lukasiewicz.)

Aristóteles

El corazón de la lógica de Aristóteles es el silogismo. La silogística de la

argumentación denominada lógica por 2,000 años.

En lógica, Aristóteles desarrolló reglas para establecer un razonamiento

encadenado que, si se respetaban, no producirían nunca falsas conclusiones si la
reflexión partía de premisas verdaderas (reglas validas.) En el razonamiento los
nexos básicos eran los silogismos: proposiciones emparejadas que, en su conjunto,
proporcionaban una nueva conclusión. El ejemplo más famoso, "Todos los
humanos son mortales" y "Todos los griegos son humanos", se llega a la conclusión
válida de que "Todos los griegos son mortales". La ciencia es el resultado de
construir sistemas de razonamiento más complejos. Aristóteles en su lógica,
distinguía entre la dialéctica y la analítica; para él, la dialéctica sólo comprueba las
opiniones por su consistencia lógica. La analítica, por su parte, trabaja de forma
deductiva a partir de principios que descansan sobre la experiencia y una
observación precisa. Esto supone una ruptura deliberada con la Academia de
Platón, escuela donde la dialéctica era el único método lógico válido, y tan eficaz
para aplicarse en la ciencia como en la filosofía.

George Boole

En el año 1854 publicó una investigación de las leyes del pensamiento sobre las
cuales son basadas las teorías matemáticas de Lógica y Probabilidad. Boole
aproximó la lógica en una nueva dirección reduciéndola a una álgebra simple,
incorporando lógica en las matemáticas. Agudizó la analogía entre los símbolos
algebraicos y aquellos que representan formas lógicas. Comenzaba el álgebra de la
lógica llamada Álgebra Booleana la cual ahora encuentra aplicación en la
construcción de computadoras, circuitos eléctricos, etc.

El sistema de lógica de Boole es una de las muchas pruebas y paciencia combinada.

Esta el proceso simbólico del álgebra, inventado como herramienta de cálculos
numéricos, sería competente para expresar cada acto del pensamiento, y proveer la
gramática y el diccionario de todo el contenido de los sistemas de lógica, no habría
sido creíble hasta probarlo. Cuando Hobbes publicó su "Computación o Lógica" él
tenía un remoto reflejo de algunos de los puntos que han sido ubicados en la luz del
día por el Sr. Boole.

2
El álgebra Booleana tiene una amplia aplicación en el switch telefónico y en el
diseño de computadores modernos. El trabajo de Boole ha llegado a ser como un
paso fundamental en la revolución de los computadores hoy en día.

Considérense los símbolos de la figura No. 1, utilizándolos podemos decir que

Boole pensaba que a una proposición se le podía asignar valores de verdad o
falsedad, por ejemplo:

Si llueve me mojo

P = Sí llueve

Q = Me mojo

Augustus De Morgan

En 1838 él definió él termino "inducción matemática" colocando un proceso que ha

sido usado sin claridad en una rigurosa base. El termino aparece primero en el
artículo de De Morgan (Induction Mathematics) en el Penny Cyclopedia. Que la
Penny Cyclopedia publicó a través de la Sociedad de la Difusión Útil del
Conocimiento, establecido por el mismo reformador quien fundo London
University, y que la Sociedad también publico como un famoso trabajo por De
Morgan El calculo integral y diferencial.

Reconsidero la pureza simbólica del álgebra natural y fue consciente de la

existencia de otras álgebras como álgebras ordinarias. Presenta las leyes De
Morgan y su grandiosa contribución es como un reformador de la lógica
matemática.

De Morgan creo y definió las leyes que llevan su nombre, las cuales son reglas de
equivalencia en las que se muestran que dos proposiciones pueden ser lógicamente
equivalente, como se muestra a continuación.

Jan Lukasiewicz

Trabajo en lógica matemática, escribió ensayos de los principios de la no

contradicción y la excluyo alrededor de 1910, desarrollando un árbol de valores
para el calculo proposicional (1917) y trabajo en muchos valores lógicos.

Lukasiewicz presento la "notation Polish" la cual permitía escribir expresiones sin

ambigüedad en el uso de soportes y su estudio fue de base para el trabajo de
Tarski’s.

Concepto de la matemática lógica y sus dos principales campos. Cálculo

proposicional y cálculo de predicados.

La lógica matemática estudia la forma del razonamiento, se considera como una

disciplina que por medio de reglas y técnicas determina si un argumento es válido
o no.

3
El cálculo proposicional o lógica proposicional, es la ciencia que trata de los
principios válidos del razonamiento y la argumentación. El estudio de lógica es el
esfuerzo por determinar las condiciones que justifican a una persona para pasar
de una proposición dada, llamadas premisas, a una conclusión que se deriva de
aquéllas.

El cálculo de predicados está basado en la idea de que las sentencias realmente

expresan relaciones entre objetos, así como también cualidades y atributos de tales
objetos. Los objetos pueden ser personas, objetos físicos, o conceptos.

Significado de la lógica formal en las ciencias de la computación.

La lógica matemática es la disciplina que trata los métodos de razonamiento. En

un nivel elemental, la lógica proporciona reglas y técnicas para determinar si es o
no valido un argumento dado. El razonamiento lógico se emplea en matemáticas
para demostrar teoremas; en ciencias de la computación para verificar si son o no
correctos los programas.

También la lógica tiene participación en la construcción de programas como son

los Sistemas Expertos y programas de Inteligencia Artificial en sus diferentes
modalidades, que comúnmente se les denominan sistemas basados en reglas.

CALCULO PROPOSICIONAL

Principales Conceptos

El cálculo proposicional es también llamado, lógica proposicional, calculo

sentencial, álgebra Booleana. El cálculo proposicional, junta dos cálculos de
predicados con la constitución de símbolos lógicos.

La Lógica Matemática surge como una disciplina matemática cuyo objeto de

estudio es la lógica del razonamiento matemático humano (y actualmente también
de otras formas de razonamiento.) Requiere de expresar la lógica en términos
susceptibles de ser representados y manejados por un computador.

La lógica proposicional es la parte de la lógica que estudia las formas en que se

relacionan unas proposiciones con otras y, sobre todo, la relación que se da entre
las proposiciones que componen un razonamiento.

Proposiciones

Las proposiciones son definidas, apenas "como un pensamiento completo". Para

nuestro propósito las proposiciones pueden ser tentativamente igual a una
sentencia.

Las proposiciones son una sentencia declarativa, o reglas las cuales tienen valores
de verdad, una proposición puede tener dos valores, verdadero o falso. Pero no
ambos (verdadero y falso) y tampoco pueden no tomar ningún valor. Una
proposición es un hecho. Los argumentos de las proposiciones son: premisas y

4
conclusiones de una proposición. Las proposiciones son portadoras de veracidad y
falsedad.

Mientras las proposiciones son expresadas en sentencias, la rama de la lógica se

conoce como símbolos lógicos empleando letras de variables minúsculas, o
variables de sentencias o variables proposicionales, p, q, r, s,..., para expresar
proposiciones.

Lógica e informática

Una nueva época para la lógica comienza en las décadas de 1950 y 1960 a causa de
la aparición de los ordenadores. Surgió entonces la necesidad de determinar si
fuese posible especificar formalmente programas y de_unir sistemas de
demostración automática de teoremas. Estos tipos de problemas son los principales
objetos de estudio de la lógica informática.

El nacimiento de la inteligencia artificial y del primer lenguaje declarativo (LISP)

se puede fijar en el 1959, con el trabajo de Mc Carthy.
A lo largo de los años sesenta se mejoran los primeros sistemas de demostración
automática y en el 1965 aparece la regla universal de resolución con unificación de
Robinson.

En los años setenta se desarrolló la programación lógica como herramienta de

resolución de problemas. En 1972 Colmerauer creó el primer lenguaje de
programación lógica: Prolog.

A partir de los años ochenta se empiezan a utilizar nuevas lógicas no clásicas,

como, por ejemplo, lógicas que permiten dar una interpretación probabilista de la
incertidumbre.

Los métodos deductivos de la lógica matemática están a la base de la demostración

automática de teoremas. Se trata de buscar los sistemas de demostración más
eficientes para su implementación en un ordenador.

En la semántica de un lenguaje de programación, se pueden usar los métodos de

demostración de la lógica matemática para verificar (automáticamente) la
corrección de programas y sus propiedades.

La programación lógica está a la base de la inteligencia artificial y permite deducir

nuevos conocimientos a partir de una base de conocimientos (los axiomas) y una
serie de deducciones automáticas.
Por tanto, algunas de las áreas de aplicación de la lógica en informática son:
La minería de datos.
La descripción de la semántica de los lenguajes de programación y la verificación
de programas.
La demostración automática de teoremas.
La programación lógica y los sistemas basados en el conocimiento en la inteligencia
artificial.

5
Lenguaje Natural.- Es un instrumento de comunicación que generalmente no es
posible formalizarlo, es decir representarlo mediante un conjunto de signos y
símbolos matemáticas, que determine una fórmula matemática en el campo de la
lógica.

Dentro del lenguaje podemos reconocer tres tipos de oraciones básicas, esta son:

- Oraciones Interrogativas, como ser “ Vas a ir al cine esta noche? ”,

“ Mañana hará frió o calor ? ”. En este tipo de oraciones no existe la
posibilidad de contestar si o no, ya que hay otras posibilidades como talvez,
quien sabe u otras. Por lo tanto uno no se puede pronunciar sobre el valor
de verdad { V , F } de las mismas, y por lo tanto no podemos representar
mediante un símbolo matemático la estructura gramatical de la frase, es
decir no podemos formalizar la oración.
- Oraciones Imperativas, como ser “ Haga esto ”, “ Trabaje ” , “ Estudie ”.
este tipo de oraciones son de orden, por lo tanto no se puede uno pronunciar
sobre su valor de verdad { V , F }, como consecuencia tampoco es posible
formalizarlas.
- Oraciones Declarativas, como ser “ Luís es amigo de José ” , “ La casa de
Mónica esta en la avenida España ” , “ La Luna atrae a los enamorados ” ,
“ El zoológico alberga diferentes tipos de animales ”, en este caso este tipo
de oraciones contienen cierto tipo de información sobre cuyo valor de
verdad { V , F } es posible que uno pueda pronunciarse. Por consiguiente
dentro del campo de estudio de la lógica bivalente que es el sujeto de
estudio, es posible que la oración sea verdadera o falsa, pero al mismo
tiempo considerar que la oración no puede ser verdadera o falsa al mismo
tiempo.

Oraciones Declarativas : Se dice que una oración es declarativa, cuando contiene

cierto tipo de información de la cual es posible pronunciarse, de la cual se extrae
cierto tipo de conocimiento y que a partir de este se puede generar nuevo
conocimiento.
Del mismo modo podemos considerar una oración declarativa, como el elemento
mínimo del leguaje que es posible representarlo mediante un símbolo o conjunto
de símbolos, es decir formalizar la oración matemáticamente.

Definiciones.- para comprender el alcance de la lógica, consideraremos algunas

definiciones, que nos permitirán entender el amplio campo de acción de esta
disciplina.

La lógica trata de la representación matemática del lenguaje, tomando como

unidad básica las oraciones declarativas.

La lógica es una ciencia que estudia el conocimiento, tal como es este, y la

generación de conocimiento a partir de la estructura primaria, este conocimiento
puede generarse a partir de las siguientes consideraciones:
- Por Constatación de hechos, a objeto de entender esta manera de generar
conocimiento nos valemos de la ejemplificación. “ Sabemos que el Señor

6
 Quiroga, saca a su perro todas las mañanas a las 6:30 a.m a pasear, hoy
miércoles nos asomamos a la ventana de nuestra habitación y vemos al
Señor Quiroga y a su perro en la puerta de su casa, por lo tanto inferimos
como conclusión que son las 6:30 a.m.
- Otra forma de generar conocimiento es mediante un argumento o
deducción, a partir de conocimientos comprobados, como ejemplo,
podemos hacer uso de una simple deducción matemática:
- Cinco es mayor que dos
- Dos es mayor que menos siete
Por lo tanto, Cinco es mayor que menos siete

La lógica es una ciencia formal mediante la cual es posible estructurar un sistema

que nos permita inferir cierto conocimiento.
Esta estructura, se da a dos niveles claramente diferenciados : Cálculo de
Proposiciones y Cálculo de Predicados

7
 CÁLCULO PROPOSICIONAL
CAPITULO II

INTRODUCCION

Proposición.- Es el elemento mínimo del lenguaje que contiene información, de la

cual es posible pronunciarse y por lo tanto representarla simbólicamente, mediante
un conjunto de signos y símbolos.

Clasificación: En función de ciertas características propias de las proposiciones,

clasificaremos estas en dos grandes grupos:

- Proposiciones de acción sin sujeto definido: Son aquellas que no se refieren

a alguien o algo especifico, es decir no tienen un articulo, como ser : “
Llueve ” , “ Hace frió ”.
- Proposiciones de Atribución con sujeto definido, en este caso la oración se
refiere a alguien o algo especifico y al cual le atribuye cierta propiedad o
característica propia, como ser “ Luís es amante de los gatos ” , “ la casa
verde pertenece al señor Santibáñez ” , “ El libro intitulado fue escrito por
el dramaturgo francés Víctor Hugo ”.
- Proposiciones de Relación, este tipo de proposiciones relacionan mas de un
objeto o sujeto, e introducen el concepto de conectivo proposicional, como
ejemplos : “ Maria y Alfonso se quieren ” , Mónica esta sentada entre
Agustín y Mercedes ” , La casa del señor Lora es mas grande que la casa
del señor Ruiz, pero mas pequeña que la mía ”

- Proposiciones Atómicas: Son aquellas que tan solo están formadas por una
única proposición, pueden llevar sujeto como no, como ser “ El Perro de
Maria es blanco “ , “ Si hace sol saldré con impermeable ” , “ Los árboles
de la plaza principal son de color marrón en otoño ” , “ Los automóviles de
la Ford del año cincuenta eran mejores que los actuales ”.
- Proposiciones Moleculares: Son aquellas que relacionan mas de un sujeto u
objeto y que en su estructura están formadas por mas de un conectivo
lógico, como ser : “ El Almirante de la flota del pacifico y el Comandante
de la flota del atlántico son hermanos ” , “ Los aviones a reacción y los
aviones de turbo hélice fueron fabricados en la década del cincuenta ” , “
Los amigos de Juan y Pedro son o no amigos de los de Maria y Marcela ”

Conectivas.- Son símbolos matemáticos que permiten relacionar proposiciones

atómicas, generar nuevas estructuras a partir de la relación que generan las
primarias. Entre estas tenemos:

Negación:
Símbolo : ~
Notación : ~ p
Acepciones :
- no p
- no ocurre p
- es falso que p

8
 - no es cierto que p

- Pedro no ira al cine mañana

- No iremos de excursión con Juan el día domingo
- No es cierto que Maria sea bilingüe
- Es falso que el sol salga todos los días
- No ocurre que Juan sea hermano de Lucas

Conjunción:
Símbolo : ^
Notación : p ^ q
Acepciones :
- p y q
- p e q
- p no obstante q
- p sin embargo q
- p pero q

- Juan y Luís son primos hermanos

- La marea roja y las tormentas marinas son fenómenos naturales
- Cuando Maria va al cine y Luís no obstante va a la salchichería siguen
siendo enamorados

Disyunción:
Símbolo : ν
Notación : p ν q
Acepciones :
- po/uq
- o bien p o bien q
- al menos p o q
- como mínimo p o q

- La casa del señor Legizamon es colorada o amarilla

- La novia de Manuel es pelirroja o rubia teñida
- O nos vamos al cine todos o nos vamos al fútbol
- Al menos Juan es amigo del Señor Teodosio o conocido de el

Implicación:
Símbolo : →
Notación : p → q
Acepciones :
- p implica q
- p entonces q
- solo si q entonces p
- p suficiente para q
- q necesario para p
- no p a menos que q

- Si Marcela va a la piscina entonces su hermano va al restaurante

- Todos los noctámbulos farrean esto implica que tienen una vida disipada

9
 - Es suficiente que Begoña sea pequeña para que su descendencia sea
también enana

Bicondicional o Doble Implicación:

Símbolo : ↔
Notación : p ↔ q
Acepciones :
- p si y solo si q

Si Juan estudia, se debe si y solo si a que sus padres lo obligan

Tablas de verdad.- Una tabla de verdad establece la relación entre proposiciones,

construyendo de esta manera una fórmula lógica y permite determinar en que
condiciones esta es verdadera o falsa. Para construir una tabla de verdad es
necesario conocer en forma previa cuantas proposiciones distintas contiene la
fórmula, y mediante que conectivos están relacionadas las proposiciones, en forma
general en este acápite se darán los lineamientos de las tablas de verdad para cada
conectiva.

Tabla Negación

Proposición Negación Valor de Valor de Verdad

Verdad de p de ~ p
P ~p V F
~p P F V

Ejemplos :

Juan es amigo de Lucas Juan no es amigo de Lucas

Maria es gorda Maria no es gorda – Maria es flaca
La Luna es blanca La luna no es blanca
La casa es negra La casa no es negra

Tabla Conjunción

Proposición Proposición Conjunción

P Q pΛq
V V V
V F F
F V F
F F F

Como se puede observar en la relación de dos proposiciones mediante el conectivo

de la conjunción, la proposición resultante tan solo es verdadera cuando ambas
proposiciones componentes tiene valor de verdad verdadero, caso contrario la
proposición resultante es falsa.

Ejemplos :

Luis y Maria van al cine

10
La casa de Pedro y la de Lucia es bonita
La luna es grande pero el sol es mas grande

Tabla Disyunción

Proposición Proposición Disyunción

P Q PνQ
V V V
V F V
F V V
F F F

Tal como se observa en el caso de la proposición resultante entre la disyunción de

dos proposiciones, el valor de verdad de esta es tan solo falsa, cunado ambas
proposiciones componentes tiene valor de verdad falso, caso contrario es siempre
verdadera la proposición.

Ejemplos :

Tomas o Claudia son hermanos u Pedro es el tío de ambos

Al me0nos Juan o Marcelo van de compras al supermercado
No obstante que los autos son ruidosos la fiat construye otro modelo

Tabla Implicación

Proposición Proposición Implicación

P Q P→q
V V V
V F F
F V V
F F V

En el caso de la proposición resultante de la relación entre otras dos con el

conectivo de la implicación, tan solo esta es falsa cuando el antecedente es
verdadero y el consecuente falso, caso contrario la proposición resultante es
siempre verdadera.

Ejemplos :

Si Juan va al cine entonces Maria se queda en casa

Sin embargo que las aves son bellas los cazadores las matan
Las máquinas son necesarias para el agro pero el agua es esencial para el
crecimiento

11
Tabla Bicondicional

Proposición Proposición Bicondicional

P Q p↔q
V V V
V F F
F V F
F F V

La proposición resultante entre otras dos proposiciones relacionadas mediante el

conectivo bicondicional da como resultado que esta sea verdadera tan solo cuando
el valor de ambas proposiciones sea el mismo, siempre y cunado estas sean
verdaderas o falsas, caso contrario la proposición obtenida es falsa.

Ejemplos :

Yo estudio si y solo si como bien

Yo trabajo si y solo si me pagan bien

Construcción de Tablas de Verdad.- Para construir una tabla de verdad, se debe

tomar en cuenta el número de proposiciones que intervienen en la fórmula, para
poder determinar el número de líneas que tendrá la tabla, y del mismo modo la
asignación de valores de verdad a las proposiciones dentro de la lógica bivalente, es
decir el uso de valores { V , F }.
Supongamos que el número de proposiciones distintas que existen en la fórmula es
cuatro, entonces la distribución de valores de verdad será la siguiente:

p Q R S
V V V V
V V V F
V V F V
V V F F
V F V V
V F V F
V F F V
V F F F
F V V V
F V V F
F V F V
F V F F
F F V V
F F V F
F F F V
F F F F

Tal como se puede observar en la tabla, para cada proposición distinta el número
de valores { V , F } es el mismo, lo único que varia es la repartición de valores, es

12
así que para la primera proposición, los valores verdaderos son ocho y los falsos
también ocho, de manera que primero van los ocho verdaderos y a continuación
los ocho falsos, para la segunda proposición, la repartición es la mitad de la
anterior, cuatro verdaderos, cuatro falsos, seguidos de cuatro verdaderos y cuatro
falsos, haciendo también el total de 16 valores de verdad, para el resto de las
proposiciones se toma en cuenta la mitad del anterior de valores verdaderos,
seguido de la mitad de valores de verdad falsos, y así sucesivamente hasta
contemplar las diez y seis líneas de la tabla.

El número de líneas que debe contener la tabla se calcula mediante la fórmula :

2 n = líneas de la tabla ( donde la base 2 representa los

valores de verdad { V , F } que asumen las proposiciones dentro del ámbito de la
lógica bivalente sujeto de estudio, y n representa el número de proposiciones
distintas que intervienen en la fórmula. De este modo si tenemos una fórmula con
seis proposiciones distintas el cálculo será :

2 6 = 64 líneas que tendrá la tabla de verdad

Estos valores de verdad están repartidos en la tabla de verdad para cada

proposición distinta de la manera siguiente.

A) Para la primera proposición n/2 V ; n/2 F

B) Para la segunda proposición n/4 V ; n/4 F ; n/4 V ; n/4 F
C) Para la tercera proposición n/8 V ; n/8 F ;……..
D) Para la cuarta proposición n/16 V ; n/16 F ;………
E) Para la quinta proposición n/32 V ; n/32 F;…..

Así sucesivamente de manera que para la ultima proposición será una verdadera,
una falsa, hasta completar el número de líneas de la tabla de verdad de acuerdo a
la fórmula dada.

Formalización.- Formalizar es representar matemáticamente mediante un

conjunto de símbolos y signos una proposición o un conjunto de estas.
Para formalizar se debe tomar en cuenta las siguientes reglas:
- Cada proposición distinta debe estar simbolizada por un único signo.
- Dos o más proposiciones deben estar simbolizadas por diferentes signos.
- Se debe representar siempre la proposición en afirmativo, aun esta sea
negativa.
- Al obtener la fórmula o deducción resultante de la oración o conjunto de
oraciones, se deben relacionar las proposiciones con el conectivo correcto.
- Al momento de confeccionar la fórmula o premisa, se debe tener en cuenta
si la oración era negativa, para recién introducir el conectivo de la
negación.

Introduciremos algunos ejemplos de formalización del lenguaje natural. La

formalización es una herramienta básica y el alumno tendrá ocasión de practicarla
a lo largo de todo el estudio de la lógica proposicional y de predicados.

13
A partir de la formalización de estos ejemplos podemos formalizar frases y
razonamientos más complejos.

Para formalizar un razonamiento con premisas p1; p2; : : : ; pn y conclusión

q usaremos cualquiera de las dos formas:
p1
p2 ...
pn
q

o
p1 Λ p2 Λ ……. Λ pn → ! q

Una manera sencilla de verificar la validez de la formalización de una frase del

lenguaje natural es de volver a traducir al lenguaje natural la formalización
obtenida.

Ejemplos A)

1) Así, por ejemplo, consideremos la frase: “ No voy a la playa a menos que haga
mucho calor “
Siendo:

p = voy a la playa
q = hace mucho calor
La formalización

( p → q) es correcta y la formalización ( q → p) no es correcta.

En efecto. La primera se lee como “ Voy a la playa sólo si hace mucho calor “ y la
segunda como “ Si hace mucho calor, entonces voy a la playa “ En la segunda
formalización se ha intercambiado la condición necesaria (la conclusión) con la
suficiente (la premisa).

2) Sea el enunciado “ Si una función f es derivable en el intervalo [a; b]; entonces f

es continua en [a; b] “
Se puede formalizar definiendo

p = la función f es derivable en [a; b]

q = la función f es continua en [a; b]

Aplicando el conectivo de implicación. Se obtiene ( p →! q) y, en forma abreviada,

p →! q

3) Sea la frase “ Si salto por la ventana, o me hago daño o empiezo a volar “

Se puede formalizar por medio de las proposiciones atómicas:

p = salto por la ventana

q = me hago daño
r = empiezo a volar

14
La formalización seria
( p → ( q νr ) )

En forma abreviada, p → (q ν r )

4) Sea la frase “ Si salto por la ventana me podría hacer daño, sin embargo
empiezo a volar “ Se puede formalizar por medio de las proposiciones atómicas

p = salto por la ventana

q = me podría hacer daño
r = empiezo a volar

La formalización seria

(( p → q ) Λ r )

En forma abreviada, ( p → q ) Λ r

5) Sea el enunciado “ Condición necesaria y suficiente para que un número entero

n sea par es que n sea divisible por 3 “

Se puede formalizar por medio de las proposiciones atómicas

p = n es un número entero
q = n es par
r = n es divisible por 3

Formalizando se obtiene

(( p Λ q) ↔ r)

En forma abreviada p Λ q ↔ r

6) Sea el argumento “ Me gusta el helado de fresa, pero también el de limon. Si hay

sólo helado de chocolate lo comeré, a pesar de que no me guste. Por tanto, no
comeré helado de fresa “

Para formalizar el razonamiento dado, definimos las proposiciones atómicas

p = me gusta el helado de fresa

q = me gusta el helado de limon
r = hay sólo helado de chocolate
s = comeré helado de chocolate
t = me gusta el helado de chocolate,
u = comeré helado de fresa

La formalización se puede escribir, en forma abreviada, como

p Λ q

15
( r → s) Λ ~ t
~u
o como

p Λ q Λ (r→ s)Λ ~t  ~u

Ejemplos B

a) Jacinto es bajo y Morgan es alto

Tal como se puede observar esta es una proposición compuesta o molecular, ya
que esta formada por dos proposiciones distintas, el conectivo de relación o de
unión es el de la conjunción, al representarlas por lo tanto se debe tener en
cuenta este hecho.

Formalización :

- p = Jacinto es bajo
- q = Morgan es alto

Función lógica : p Λ q

b) La casa verde es de mi abuela o el coche de mi tío es azul

Del mismo modo que el caso anterior se trata de una proposición molecular,
pero relacionada mediante el conectivo de la disyunción.

Formalización :

- r = la casa verde es de mi abuela

- s = el coche de mi tío es azul

Función lógica : r ν s

c ) Si Maria va a la piscina entonces Pedro no ira a trabajar a la fabrica o Luís

se ira a La Paz

En este caso la proposición resultante esta formada por tres proposiciones

atómicas, relacionadas por los conectivos de la implicación y de la disyunción

Formalización :
- m = Maria va a la piscina
- n = Pedro ira a trabajar a la fabrica
- o = Luís ira a La Paz

Función lógica : m → ~ n ν o

c) Yo no soy un literato y ese compañero es un timador

- A = Soy literato
- B = El compañero es un timador

Función Lógica : ~ A → B

16
 d) Si Juventud ha jugado el domingo, entonces, si ha empatado o ha ganado el
campeonato, o este queda por decidir en un partido
- A = el Juventud ha jugado el domingo
- B = el Juventud ha ganado
- C = el Juventud ha empatado
- D = El campeonato queda por decidir

Función Lógica : A → ( C → B ν D )

e) No ocurre que tenga un libro cantando, a menos que fume un habano

- A = El tiene un libro
- B = El canta
- C = El fuma un habano

Función Lógica : ~ C → ~ ( A Λ C )

Ejercicios Propuestos

Dadas las siguientes oraciones formalizarlas, representándolas en forma abreviada

y no abreviada

1) Al menos Juan o Pedro van al cine, entonces el rio llega caudaloso

2) No ocurre que tengamos un piano y no exista nadie en la casa que lo toque o
lo sepa afinar
3) O las Matemáticas no son difíciles o talvez a Juan le guste la Lógica y la
Filosofía, sin embargo a nadie le gusta la Biología
4) Si el ángulo de un cuadrilátero es igual a otro, entonces los otros ángulos no
suman 120 grados
5) Si Lucia gana el campeonato, entonces Maria y Marcela llegaran después y
perderán la medalla de oro
6) Si Claudia no deja de comer, al menos entonces su novio pensara en no
casarse con ella
7) No voy de viaje a menos que los pasajes aéreos sean mas caros que la
estadía del hotel o no me regalen nada en navidad
8) No ocurre nunca que dos líquidos no miscibles se colorean igual a menos
que el químico cambien su composición o cambie de líquidos
9) Si Roberto y Mario tiene la misma edad, entonces Maria o Lucia son
menores de edad, a menos que no sean hermanas
10) La ciudadanía no ve con estupor las marchas y huelgas debido a que el
partido no saben jugar a la política o todos ellos ganan mas de lo que dicen
siempre que dicen que no trabajan por el lucro

Fórmulas.- Una fórmula es el resultado de la representación simbólica de una

proposición o de un conjunto de proposiciones relacionadas entre si mediante
conectivos lógicos.

Ejemplos:
a) p → { ( s Λ q ) ↔ { ( ~ p ν q ν r → ( s Λ ~ r ) ) → ( s → r ) } }
b) a → ( b ν ( c Λ ( ~ d ↔ ( e → ~ a ) ) ) )

17
Deducción.- Una deducción o argumento esta formada por un conjunto de
fórmulas, llamadas premisas que permiten inferir una conclusión a partir del
conjunto de premisas, la demostración de la deducción se dará mas adelante.

1) p → ( q → r )
2) p Λ a
3) ~ r → ~ q
4) ~ r
* ~q

En el ejemplo anterior se puede ver que a partir del conjunto de tres premisas, se
infiere o se llega a una conclusión que es la negación de la fórmula o proposición q.

Definición Formal del Lenguaje Proposicional.- Como todo leguaje el cálculo de

proposiciones se basa en dos conceptos, que permiten definir el lenguaje empleado
para el cálculo de proposiciones, estos son :
- El Alfabeto
- La Sintaxis

En el campo del cálculo de Proposiciones, definimos el alfabeto como:

Alfabeto: Conjunto de símbolos y signos que nos permiten representar las

proposiciones, y las relaciones entre estas.

Dentro del alfabeto consideramos tres tipos de signos y símbolos que nos permiten
esta representación de las proposiciones, ya sean estas atómicas o moleculares.

- Símbolos de proposiciones : Consideramos la representación de estas

mediante el empleo o uso de las letras minúsculas, como ser p , q , r , s ,
t………..
- Símbolos de conectivas : Los símbolos matemáticos detallados
anteriormente, como ser : ~ , → , Λ , ↔ , ν
- Símbolos de agrupación, como ser paréntesis, corchetes y llaves : ( ) ,
{ } ,[ ]

La Sintaxis: Es el conjunto de reglas, normas y leyes que nos permiten la

construcción correcta de estructuras o fórmulas matemáticas representativas de
estructuras idiomáticas, y nos permite introducir en este campo el concepto de
“ fórmula bien construida “ fbc

La sintaxis comprende las siguientes estructuras :

- Definición de Fórmulas: las fórmulas del Cálculo de proposiciones se

definen de acuerdo a los siguientes tres niveles:
a) Si los símbolos p , q , r , … representan proposiciones, estas son f.b.c
b) Si A , B son f.b.c, entonces las siguientes fórmulas son f.b.c
~ A , ~ B , A Λ B , A ν B , A → B , A ↔ B

18
 c) Solo son f.b.c las obtenidas a partir de los anteriores puntos, con las
combinaciones que se puedan realizar entre si.

- Definición de Estructuras, las estructuras que se construyen deben regirse

de acuerdo a las siguientes normas, para que puedan ser consideradas
válidas.
a) No deben aparecer conectivos adyacentes, excepto el de la negación con
otra. Como ser : A → ~ B
b) Se debe definir en forma previa el alcance de una conectiva en relación a
las proposiciones componentes de la fórmula, de acuerdo al siguiente
detalle :
- Una conectiva afecta al símbolo de proposición adyacente a esta, o al
conjunto de proposiciones encerrados entre signos de agrupación
- A objeto de restringir y evitar el uso excesivo de signos de agrupación, se
define una serie de niveles :
a) Nivel 1 : ~
b) Nivel 2 : Λ ν
c) Nivel 3 : → ↔

Fórmulas en forma usual y abreviada

Forma usual

Siguiendo las reglas de formación de las fórmulas proposicionales obtenemos

ejemplos de expresiones bien construidas como las siguientes:

1. ((p Λ (p → r)) ν (q ↔ t))

2. (p Λ ( ~( ~((q → r) → (p ν ( ~ (r)))))))
3. (p → (q → r))
Se puede notar que se usan paréntesis para evitar ambigüedad en la formalización.
Sin embargo este uso se puede relajar obteniendo expresiones que no son fórmulas
bien construidas, pero vienen empleadas como tales por razones de convenios.

Forma abreviada

Para reducir una fórmula bien construida a su forma abreviada podemos seguir
los siguientes pasos:

a) Se puede omitir el par de paréntesis externo.

Así, por ejemplo, las anteriores fórmulas 1., 2. y 3. se escribirían como:

( p Λ (p → r)) ν ( q ↔ t)
p Λ ( ~ ( ~ ( ( q → r) → (p ν ( ~ ( r ))))))
p→(q→r)

b) Se introducen las siguientes reglas de precedencia entre conectivos que definen

las prioridades que tenemos que respectar a la hora de aplicarlos:

Nivel 1: ~
Nivel 2: _Λ ν

19
Nivel 3: → ↔

Así, por ejemplo, las anteriores fórmulas se escribirían como:

( p Λ ( p → r)) ν ( q ↔ t )
p Λ ~ ~ (( q → r) → p ν ~ r )
p→(q→r)

c) Se admite el convenio de asociatividad: los conectivos _Λ ν y → ↔ se asocian

por la derecha:

p Λ q Λ r es p Λ ( q Λ r )
p ν q ν r es p ν ( q ν r )
p → q → r es p → ( q → r )

Así, por ejemplo, las anteriores fórmulas se escribirían como:

( p Λ ( p → r )) ν ( q ↔ t )
p Λ ~ ~ (( q → r ) → p ν ~ r )
p →q →r

Problema Inverso.- Este acápite se refiere a que dada la salida de la tabla de verdad
de una fórmula, se debe construir la fórmula correspondiente a dicha salida.
Las salidas dadas deben ser necesariamente potencias de dos, ya que como se ha
visto en la construcción de fórmulas , para determinar el número de líneas que
debe tener una tabla se usa la fórmula : 2 n = líneas de la tabla.
Existen dos procedimientos que nos permiten realizar este problema, estos son :

- La Forma Normal Conjuntiva ( F . N . C )

- La Forma Normal Disyuntiva ( F . N . D )

Para entender estos dos mecanismos de construcción de fórmulas, introduciremos

dos nuevos conceptos, es tos son :

- Conjunciones Fundamentales
- Disyunciones Fundamentales

Conjunción Fundamental.- Una conjunción se dice que es fundamental cuando el

valor de salida para cada línea de la tabla de verdad es siempre verdadero.

Para construir las conjunciones fundamentales se procede de la siguiente manera:

- Se analizan los valores de verdad de las proposiciones componentes.
- Si el valor de verdad de todas las proposiciones es verdadero, las
proposiciones entran en la conjunción fundamental con su mismo valor, si
existe alguna falsa, esta ingresa en la conjunción fundamental con valor
negado.

A objeto de ejemplificar la construcción de Conjunciones fundamentales,

construiremos para dos y tres proposiciones distintas.

20
Conjunciones Fundamentales para dos Proposiciones

P q p Λ q Conjunción Valor de
Fundamental Verdad
V V V p Λ q V
V F F p Λ ~q V
F V F ~p Λ q V
F F F ~ p Λ ~ q V

Conjunciones Fundamentales para tres Proposiciones

P Q r p Λq Λ r Conjunción Valor de
Fundamental Verdad
V V V V p Λq Λ r V
V V F F p Λq Λ~r V
V F V F p Λ~q Λ r V
V F F F p Λ~q Λ~r V
F V V F ~p Λq Λ r V
F V F F ~p Λq Λ~r V
F F V F ~p Λ~q Λ r V
F F F F ~p Λ~q Λ ~r V

Disyunción Fundamental.- Una Disyunción se dice que es Fundamental cuando el

valor de salida de cada una de las líneas de la tabla de verdad es siempre falso.

Para construir las Disyunciones Fundamentales se analizan los valores de verdad

de las proposiciones componentes, y se procede de acuerdo a los siguientes
principios:
- Se analizan los valores de verdad de las proposiciones componentes.
- Si el valor de verdad de todas las proposiciones es falso, las proposiciones
entran en la disyunción fundamental con su mismo valor, si existe alguna
verdadera, esta ingresa en la disyunción fundamental con valor negado.

A objeto de ejemplificar la construcción de Disyunciones fundamentales,

construiremos para dos y tres proposiciones distintas.

Disyunciones Fundamentales para dos Proposiciones

P q p ν q Disyunción Valor de
Fundamental Verdad
V V V ~p ν~q F
V F V p ν~ q F
F V V ~p ν q F
F F F p ν q F

21
Disyunciones Fundamentales para tres Proposiciones

P Q r p νq ν r Disyunción Valor de
Fundamental Verdad
V V V V ~p ν~q ν~ r F
V V F V ~p ν~q ν r F
V F V V ~p νq ν~ r F
V F F V ~p νq ν r F
F V V V p ν~q ν~r F
F V F V p ν~q ν r F
F F V V p νq ν~ r F
F F F F p νq ν r F

Para determinar la fórmula correspondiente a una salida dada, entonces se puede

proceder haciendo uso ya sea de la F.N.D o de la F.N.C, tomado en cuenta que:

- La F.N.D es la disyunción de Conjunciones Fundamentales

- La F.N.C es la conjunción de disyunciones Fundamentales

Si en el ejercicio no se especifica que forma usar, se deben analizar los valores de

verdad de la salida dada, y en función del número de valores verdaderos o falsos se
determina que forma se debe emplear, de manera que la fórmula a ser
determinada correspondiente a la salida sea la menor posible.

Por ejemplo si se da la salida VVFFFFFV Al observar esta salida se ve que

existen tres valores verdaderos y cinco falsos, entonces en función de la
observación anterior se debe emplear la F.N.D ( Disyunción de Conjunciones
Fundamentales ), ya que la fórmula ha obtener tan solo contendrá tres esquemas
de fórmulas unidas mediante el conectivo de la disyunción, si por el contrario se
usa la F.N.C ( Conjunción de Disyunciones Fundamentales ) la fórmula ha
determinar esta formada por cinco Disyunciones Fundamentales unidas o
relacionadas entre si por el conectivo de la Conjunción.

Determinar mediante la F.N.C y mediante la F.N.D la fórmula correspondiente a

la siguiente salida : VVFF
Los pasos que se deben emplear son los siguientes :

- Determinar el número de proposiciones distintas de las cuales estará

formada la fórmula mediante la fórmula matemática : 2 n = 4 líneas ,
entonces, mediante el proceso matemático que a continuación se detalla, se
determina el número de proposiciones distintas : 2 n = 2 2 , por el principio
de a bases iguales, entonces los exponentes iguales, se determina que : n = 2.
- Se observa en que posiciones están los valores verdaderos y los valores
falsos de la salida dada, en función de esto se determina que conjunciones o
disyunciones fundamentales entraran en la fórmula correspondiente a la
salida dada.

F.N.D ( Forma Normal Disyuntiva ) , ( Disyunción de Conjunciones

Fundamentales ). La salida dada es VVFF, entonces se toman las salidas
verdaderas, las cuales están en la primera y segunda posición, se va a la tabla

22
 de Conjunciones fundamentales y se toman estas dos líneas que corresponden a
los valores verdaderos, y se escribe la fórmula, relacionando las dos
Conjunciones Fundamentales mediante el conectivo de la Disyunción.

(p Λ q) ν ( p Λ ~q)

F.N.C ( Forma Normal Conjuntiva ), ( Conjunción de Disyunciones

Fundamentales ). La salida dada es VVFF, entonces se toman las salidas falsas,
las cuales están en las posiciones tercera y cuarta, se va a la tabla
correspondiente de disyunciones Fundamentales, y se toman estas dos líneas, y
se escribe la fórmula, relacionando ambas Disyunciones Fundamentales
mediante el conectivo de la Conjunción.

(~p ν~q) Λ (p ν~ q)

Ambas fórmulas resultantes son equivalentes es decir, van a tener la misma

salida de la tabla de verdad que se construye.

P q (p Λ q) ν ( p Λ ~q) (~p ν~q) Λ (p ν~ q)

V V V V
V F V V
F V F F
F F F F

Ejercicios Propuestos

Dadas las siguientes salidas, usando tanto la F.N.C y la F.N.D hallar la fórmula
correspondiente a la salida y comprobar la misma construyendo la respectiva tabla
de verdad.

1) VVFF
2) FFVF
3) FFFF
4) VVVV
5) VVFFVVFF
6) FFVVVVFF
7) FVFVFVFV
8) VFFFFFFV
9) FFFVVFFF
10) VVVFFVVV

Método Interpretativo.- este método permite determinar cuando una determinada

deducción es válida, se basa en el valor de verdad atribuible a una fórmula, y parte
del principio de que si el conjunto de fórmulas o premisas de la deducción es
verdadera, entonces la conclusión no puede ser falsa.

Regla :
- Dada la deducción, se establece en principio que todas las premisas son
verdaderas y la conclusión es falsa.

23
 - Mediante la asignación de valores de verdad a las proposiciones
componentes de la fórmula o premisa, se establece o corrobora el valor de
verdad verdadero atribuida, a esta en principio.
- Si en este proceso se establece que cualquiera de las premisas, con los
valores de verdad atribuidos a las premisas, es falso, entonces existe una
contradicción, y por lo tanto la deducción es correcta.

Ejemplos:

1) ~ p → ~ q V Valores de verdad de las proposiciones

2) ~ q → ~ r V p= F
3) r ν s V q= V
4) ~ s V r= V
5) p F s= F

Resolución.- Para resolver se construye mediante el valor de verdad de las tablas,

de acuerdo a las conectivas de relación existentes entre proposiciones.

De 5) p = F
De 4) s = F
De 3) r ν s r = V
Si s es falso entonces necesariamente r debe ser verdadero para que la premisa sea
verdadera.
De 2) ~ q → ~ r q=V
Como r es verdadero, entonces la negación de r es falsa, por lo tanto para que la
premisa sea verdadera, necesariamente la negación de q debe ser falsa, y q debe
ser verdadera.
De 1) Con estos valores de las proposiciones debe satisfacer la condición de verdad
de la primera premisa, si no cumple entonces existe una contradicción, y por lo
tanto la deducción será correcta.
~P → ~ q
Como q es verdadero, y la negación es falsa, y p es falso y la negación de p
verdadero, entonces tendremos : V → F , en implicación el resultado de esta
premisa es falsa, y no verdadera, por lo tanto existe contradicción, entonces la
deducción es válida o correcta.

Ejercicios Propuestos

Dadas las siguientes deducciones determinar la validez de las mismas, haciendo

uso del método o modelo interpretativo.
1.-
1) A ν B P
2) B → C P
3) A → C P
 C

2.-
1) ~ S ν ~ T → P Λ Q P
2) ~ P P
 S ν R

24
3.-
1) P ν Q → R Λ S P
2) ~ ( ~ P ν ~ R ) P
3) ~ T → ~ ( P Λ S ) P
 T

4.-
1) P → Q P
2) R → S P
3) S Λ Q → T P
 P Λ R → T

5.-
1) P ν Q ν R P
2) Q → S Λ R → T P
3) ~ S Λ ~ P P
 R

6.-
1) P → ~ Q P
2) ~ Q → ~ R P
3) ~ R → ~ S P
4) P P
~S

7.-
1) R → P P
2) ~ Q → ~ R P
3) S → Q P
4) P Λ Q → T P
5) ~ S ν P P
R ν S → T
8.-
1) S → ( T → U) P
2) U → ~ U P
3) V → S ΛP →T P
V → ~P

9.-
1) P ν Q P
2) P → R P
3) R → S P
4) Q → T Λ T → S P
5) ~ S ν U P
U

25
10.-
1) P → ( R → Q ) P
2) ~ S ν P P
S → Q

Determinación del valor de verdad atribuible a las proposiciones componentes de

una fórmula.- Dada una fórmula cualquiera, partiendo del valor de verdad de una
o mas de las proposiciones componentes o de ningún valor de verdad, se trata en
principio de hallar el valor de verdad de todas las proposiciones de tal modo que
satisfaga, que la fórmula ya sea verdadera o falsa.

Para hallar estos valores se procede de acuerdo a los siguientes principios:

- De la fórmula dada se establece cual es el conectivo principal, se dan los

valores de verdad a las dos partes principales de la fórmula, considerando si
la fórmula dada en principio ha sido establecida que es falsa o verdadera.
- Con esta asignación primaria de valores, se parte del componente de la
fórmula, mas simple, y se determina el valor de las proposiciones
componentes de esta.
- Se procede del mismo modo con la segunda parte de la fórmula, siempre
estableciendo si existen conectivos principales y secundarios, y se determina
el valor del resto de las proposiciones componentes.
- Se debe tomar en cuenta siempre, que si se asume un determinado valor
para una determinada proposición, dicho valor es invariable y no puede ser
modificado, ya que si se incurre en este error los resultados obtenidos serán
erróneos, y no nos permitirán establecer la condición primaria del
problema.

Ejemplo:

(p → q) → { ( q → r ) → ( p → ~r )}

Determinar el valor de verdad de las proposiciones componentes, sabiendo que la

fórmula dada es falsa.

Resolución:

- Establecemos que el conectivo principal es el de la implicación

- Por lo tanto para satisfacer la condición del problema, el antecedente debe
ser Verdadero y el consecuente Falso.
- La porción de fórmula mas simple es el antecedente, entonces procedemos a
fijar los valores de las proposiciones de tal manera que satisfagan la
condición de valor de verdad verdadero de este.

p → q existen tres posibilidades de que la fórmula sea verdadera, de

acuerdo a la tabla de verdad de la implicación, asumimos a priori que:
p= V ; q = V
- Tomando en cuenta estos valores procedemos del mismo modo con el resto de
la fórmula, que en este caso es el consecuente, pero este esta formado por dos
pedazos de fórmula relacionados con el conectivo de la implicación, como el

26
consecuente debe ser Falso, entonces asumimos del mismo modo que el
antecedente de esta es verdadero y el consecuente falso.
- Como q = V, entonces r debe ser verdadero.
- Como p = V, y r = V, entonces la negación de R es falsa, y cumple la condición
de que el consecuente sea falso. Por lo tanto el valor de verdad de las proposiciones
será:
p = V , q = V ; r = V

Ejercicios Propuestos

1.- [ ( A → (( B ν C ) → ( D Λ A)) ] Λ ( A → ( E ν F → A Λ C ))
2.- [ ( A ν B Λ C ) → ( E ν F → A ν B) ] → ( A Λ Λ → D C A Λ C )
3.- [ ( D → ( C → ( A → B Λ E ))) ] ν ~ ( A Λ B → E Λ C )
4.- ( A Λ B → D → E → A ν C ) Λ ( A → B Λ D Λ E )
5.- ( A → B Λ C ) → [ ( B → C ν E) ν ( D → ( C → B Λ A ) ]

Algebra de Proposiciones.- Es un conjunto de reglas, leyes y propiedades que nos

permiten la simplificación de fórmulas y la demostración de deducciones.

A continuación detallamos el conjunto que forma el algebra de proposiciones, y

para algunas detallamos la aplicación sobre una premisa o conjunto de premisas.

Propiedad Conmutativa

A Λ B  B Λ A
A ν B  B ν A

Propiedad Asociativa

( A Λ B ) Λ C  A Λ ( B Λ C )
( A ν B ) ν C  A ν ( B ν C )

Identidad

A  A

Idempotencia

A Λ A → A
A ν A → A

Absorción

A Λ ( A ν B) → A
A ν ( A Λ B) → A

27
Distributiva

A Λ ( B ν C )  ( A Λ B ) ν ( A Λ C )
A ν ( B Λ C )  ( A ν B ) Λ ( A ν C )

Regla del Producto

A,B → A Λ B

Regla de Simplificación

A Λ B → A
A Λ B → B

Regla de Adición

A → A ν B
B → A ν B

Producto Condicional

A → B
A → C
A → B Λ C

Regla de Importación – Exportación

A → ( B → C ) → A Λ B → C
( A Λ B → C ) → A → ( B → C )

Regla del Absurdo

A → B
A → ~ B
~ A

Doble Negación

~ ~ A → A

Leyes de De Morgan

~ ( A Λ B ) → ~ A ν ~ B
~ ( A ν B ) → ~ A Λ ~ B

Reglas de Interdefinición

( A → B ) → ~ A ν B
( A → B ) → ~ ( A Λ ~ B )

28
Ex – Contradictione Quolibet

A Λ ~ A → B

Regla de Contraposición

( A → B ) → ( ~ B → ~ A )

Regla del Modus Ponens

A
A → B
B

Regla Tollendo Ponens

A ν B
~ B
A

Regla del Silogismo

A → B
B → C
A → C
Dilema Disyuntivo Simple

A → C
B → C
A ν B
C

Dilema Disyuntivo Complejo

A → C
B → D
A ν B
C ν D

Demostración de Deducciones por Algebra de Proposiciones

Ejemplo 1

1) A ν ( B Λ C) P
2) A → D P
3) D → C P
 C

29
A partir del conjunto de premisas dadas se debe demostrar la conclusión “ C “, ya
que esta es consecuencia lógica del conjunto de premisas, para ello se hace uso de
las reglas, principios y leyes dadas en el algebra de proposiciones

4) A → C Silogismo ( 2,3 )

Como se puede ver entre la segunda y tercera premisa se puede aplicar el silogismo
ya que el esquema básico de estas dos fórmulas es el del silogismo.

5) ( A ν B ) Λ ( A ν C ) Distributiva ( 1 )

Al tener una fórmula en relación entre dos conectivos como ser el de la disyunción
y el de la conjunción se puede aplicar la propiedad distributiva

6) A ν C Simplificación ( 5 )

Al tener dos fórmulas relacionadas mediante el conectivo de la conjunción es

posible obtener cada una de estas en forma independiente aplicando la propiedad
de la simplificación

7) C ν A Conmutativa ( 6 )

El orden de las proposiciones de una fórmula siempre es posible conmutarlas de

forma que la primera sea la segunda y viceversa, donde el sentido de la fórmula no
cambia

8) ~ C → A Ínter definición ( 7 )

Mediante la regla de ínter definición de conectivas, siempre es posible modificar el

conectivo de relación entre proposiciones distintas o fórmulas

9) ~ C → ~ A Contraposición ( 4 )
La regla o propiedad de la contraposición nos permite alterar el orden de las
proposiciones en una relación dada con el conectivo de la implicación entre
fórmulas dadas

10) ~ ~ C Absurdo ( 8 , 9 )

La regla del absurdo nos indica que dadas dos fórmulas con un mismo antecedente
pero consecuentes contradictorios, se obtiene como fórmula válida la negación del
antecedente de ambas implicaciones

11) C Doble Negación (10)

Negar dos veces es lo mismo que afirmar

30
Ejemplo 2

1) A → ~ B P
2) A P
3) C → ~ D P
4) C P
5) ~ B Λ ~ D → E P
6) C Λ E → ~ F P
 ~ F

7) ~ B Modus Ponens (1,2)

Entre la primera y segunda premisas tenemos el esquema de modus ponens que

aplicamos sobre estas dos premisas de forma de obtener como fórmula válida el
consecuente de la implicación

8) ~ D Modus Ponens (3 ,4)

De la misma manera como se vio en el paso 7, estas dos premisa tiene le mismo
esquema aplicado en el paso anterior, que nos permiten obtener la fórmula ~ D
como fórmula válida

9) ~ B Λ ~ D Producto ( 7 , 8 )

En los paso 7, 8 tenemos dos fórmulas dadas, de acuerdo al esquema de la regla del
producto, es siempre posible asociar dos fórmulas mediante el conectivo de la
conjunción

10) E Modus Ponens (5 ,9)

11) C Λ E Producto ( 4 , 10 )
12) ~ F M. P (6,11)

Ejercicios Propuestos

A) Dadas los siguientes argumentos, formalizar y demostrar que a partir del

conjunto de premisas se infiere la conclusión, demostrar usando algebra de
proposiciones.

1.-
- O hace repara su moto o compra una nueva
- Si hace repara su moto, deberá mucho dinero al taller
- Si debe mucho dinero al taller, tardara en salir de sus deudas
- Si compra una moto nueva, debe entonces pedir un préstamo al banco, tardara
entonces en salir de sus deudas
- O sale pronto de sus deudas o sus acreedores lo llevan a la ruina
Por lo tanto, Sus acreedores lo llevan a la ruina

31
2.-
- Si una persona se lleva siempre por su sentido de la obligación, deberá quitarse
algunos placeres de la vida, y si esta persona se guía por los placeres de la vida, su
sentido de la obligación dejara mucho que desear.
- Las personas están siempre guiadas por su sentido de la obligación o por los
placeres de la vida
- Si una persona esta siempre guiada por su sentido de la obligación, entonces
nunca deja abandonada su obligación, y si siempre esta guiada por su deseo de
placer, entonces no dejara placer sin probar
Por lo tanto, Una persona deberá dejar muchos placeres sin probar si no quiere
dejar abandonado su sentido de obligación

3.-
- Si Cristina esta en lo cierto, entonces Marcos esta equivocado
- Si Marcos esta equivocado, entonces Pablo también esta equivocado
- Si Pablo esta equivocado, entonces el espectáculo no es esta noche
- O el espectáculo es esta noche o Javier no lo vera
- Cristina esta en lo cierto
Por lo tanto, Javier no vera el espectáculo

4.-
- Si voy a mi primera clase mañana tendré que madrugar y si no voy al baile esta
noche me acostare tarde
- Si me acuesto tarde y madrugo tendré que vivir tan solo con cinco horas de sueño
- No puedo vivir con solo cinco horas de sueño
Por lo tanto, O no voy a mi primera clase mañana o no voy al baile esta noche

5.-
- Si nombran a Pérez seré feliz
- Si Pérez es feliz, no hará buena campaña
- Si no le nombran perderá la confianza de su partido
- Si pierde la confianza del partido, no hará buena campaña
- Si no hace buena campaña, debe dimitir en el partido
Por lo tanto, Pérez debe dimitir en el partido

6.-
- Si tomo el autobús y el autobús llega tarde, faltare a mi cita
- Sin falto a mi cita y me siento desmoralizado, no iré a casa
- Si no consigo el empleo, me sentiré desmoralizado y me iré a casa
Por lo tanto, Si tomo el autobús y el autobús llega tarde conseguiré el empleo

7.-
- Una de dos, o X es menor que Z, o bien X es igual a Z
- Si X es igual a Z, necesariamente Z no es igual a cinco
- Si X no es igual a cuatro, entonces no ocurre que X sea menor que Z, y Z sea
igual a cinco, pero Z es igual a cinco
Por lo tanto, X es igual a cuatro

32
8.-
- Si Ana engorda, su novio decididamente la deja plantada
- Ana come mucho cochinillo y adora el vodka con limón
- Si Ana come mucho cochinillo, necesariamente engorda
Luego, Ana adora el vodka con limón y su novio la dejara plantada

9.-
- Miguel tiene una tía en Francia
- Si Miguel no es mayor de 18 años, necesariamente no tiene una tía en Francia
Por lo tanto, Miguel tiene mas de 18 años o su padre le comprara un auto

10.-
- Beatriz solo se queda en cama si tiene gripe
- Si Beatriz no se queda en cama no se curara
- Beatriz no va a trabajar a menos que se cure
- No ocurre que Beatriz haga vida relajada y no se cure
- O va a trabajar o hace vida relajada
Luego, Beatriz tiene gripe o sarampión

B) Mediante tablas de verdad y algebra de proposiciones para cada caso,

demostrar si las siguientes fórmulas son equivalentes
a) P Q R  PQ  PR
b) P  Q  R  P R  Q R
c) P  Q  R   R  (P  Q)
d)  (A  B)  (A  B)   ( B  A)
e)  (A  B)   ( A  B)   (B   A)
f)  (A  B)  (A  B)  ( B  A)
g) (A   B)  ( B  A)  ( A  B)   ( B   A)
h) (A B) (B  C)  (A B) ( B  C)
i) [ A  (  B   A)]  A  (A  A)  A
j) [( A  (B   A)  ( A   B)]  A  B
 ( A  B)  (A  B)
C) Niegue las siguientes fórmulas del Cálculo proposicional, simplifique la fórmula
resultante.

a) [( P Q )  (P  R)]  {[  ( P   Q) 
 ( R   P)]   P  P}
b) [A  B  C ]  {  ( A   C )  [ A   B   C ]
c) { P  R S   P   Q }   (Q  S)
d) [( A   B   C) (A   B)]   ( A   B)  C
e) [P   Q   R   P]  [ P  R  ( P   Q)]
f) [ P  (P  Q  R )  [( R   P)   R

33
 CAPITULO III

TEORIA INTERPRETATIVA

MÉTODO SEMáNTICO

El Método Semántico de demostración de la validez de fórmulas y razonamientos

deductivos se basa en el valor de verdad atribuible alas proposiciones y/o premisa
de una deducción, es decir al valor que asuman estas, dentro de la lógica bivalente
que se estudia, que tan solo acepta dos valores de verdad que puedan asumir las
proposiciones, es decir { V , F }, uno u otro de los valores, pero nunca al mismo
tiempo ambos valores de verdad

Bases de la Teoría

1.- Definición de un Conjunto de Significados

Se basa en el valor de verdad que pueden asumir las proposiciones, o el valor

atribuible a estas, los cuales pueden ser { V } ; { F }

2.- Definición Semántica de Conectivas

Establece la relación entre las proposiciones y las conectivas, mediante la

construcción de tablas de verdad.

Tablas de verdad.- Una tabla de verdad establece la relación entre proposiciones,

construyendo de esta manera una fórmula lógica y permite determinar en que
condiciones esta es verdadera o falsa. Para construir una tabla de verdad es
necesario conocer en forma previa cuantas proposiciones distintas contiene la
fórmula, y mediante que conectivos están relacionadas las proposiciones, en forma
general en este acápite se darán los lineamientos de las tablas de verdad para cada
conectiva.

Tabla Negación

Proposición Negación Valor de Valor de Verdad

Verdad
P ~p V F
~p P F V

Tabla Conjunción

Proposición Proposición Conjunción

P Q pΛq
V V V
V F F
F V F
F F F

34
Como se puede observar en la relación de dos proposiciones mediante el conectivo
de la conjunción, la proposición resultante tan solo es verdadera cuando ambas
proposiciones componentes tiene valor de verdad verdadero, caso contrario la
proposición resultante es falsa.

Tabla Disyunción

Proposición Proposición Disyunción

P Q pνq
V V V
V F V
F V V
F F F

Tal como se observa en el caso de la proposición resultante entre la disyunción de

dos proposiciones, el valor de verdad de esta es tan solo falsa, cunado ambas
proposiciones componentes tiene valor de verdad falso, caso contrario es siempre
verdadera la proposición.

Tabla Implicación

Proposición Proposición Implicación

P Q p→q
V V V
V F F
F V V
F F V

En el caso de la proposición resultante de la relación entre otras dos con el

conectivo de la implicación, tan solo esta es falsa cuando el antecedente es
verdadero y el consecuente falso, caso contrario la proposición resultante es
siempre verdadera.

Tabla Bicondicional

Proposición Proposición Bicondicional

P Q p↔q
V V V
V F F
F V F
F F V

La proposición resultante entre otras dos proposiciones relacionadas mediante el

conectivo bicondicional da como resultado que esta sea verdadera tan solo cuando
el valor de ambas proposiciones sea el mismo, siempre y cunado estas sean
verdaderas o falsas, caso contrario la proposición obtenida es falsa.

35
3.- Definición de Interpretación

Define como una interpretación, la aplicación de valores atribuibles a una

deducción, e indica que una interpretación es un modelo de la misma, si y solo si, el
valor de salida para una línea de la tabla de verdad es verdadero

Evaluación Semántica de Fórmulas

Las reglas descritas en la base de la teoría, permiten la evaluación semántica de

fórmulas, considerando estas como f.b.c (fórmulas bien construidas) del Cálculo
proposicional. El sistema de evaluación de las fórmulas se basa en la construcción
de tablas de verdad de las fórmulas correspondientes, de acuerdo a las siguientes
reglas.

1.- Para la evaluación se identifica claramente el conectivo principal de la fórmula

correspondiente, debajo de este conectivo se obtiene el resultado de la evaluación
2.- Se aplica para la evaluación las tablas de verdad consiguientes en función del
conectivo de relación entre fórmulas o proposiciones en cada caso dado
3.- Se identifica claramente el número de proposiciones distintas componentes de
la fórmula, para poder determinar el número de líneas que debe tener la tabla
consiguiente de la evaluación de la fórmula
4.- Se aplican los valores de verdad a las proposiciones de acuerdo a una regla
dada.

N 0 Líneas de la tabla = 2 n
Donde:
“ 2 “ es la base en función de la lógica bivalente con la que se trabaja que solo
admite dos valores, a saber { V , F }
“ n “ Es el número de proposiciones distintas que conforman la fórmula

Valores de verdad para cada proposición distinta, en función de la siguiente regla

Primera Proposición N/2 { V } ; N/2 { F }
Segunda Proposición N/4 { V } ; N/4 { F } : N/4 { V } ; N/4 { F }
Tercera Proposición N/8 { V } ; N/8 { F } ;……..
Cuarta Proposición N/16 { V } ; N/16 { F } ;…………
Quinta Proposición N/32 { V } ; N/32 { F } ; ……….
…………………… ………………………………..

Clasificación de Fórmulas

Las fórmulas, en función del valor de salida de las líneas de su tabla de verdad se
clasifican en:

B) Tautologías: Una fórmula es una tautología si el valor de salida

para cada una de las líneas de la tabla de verdad es un modelo
interpretativo de la misma, es decir todos los valores de salida
para cada una de las líneas de la tabla correspondiente a la
fórmula dada es verdadera

36
 C) Contingencia: Una fórmula es una contingencia si los valores de
salida para las líneas de la tabla de verdad correspondiente, son
algunos modelos interpretativos y otros contra modelos
interpretativos de la fórmula, es decir existen valores de salida
verdaderos y otros falsos
D) Contradicciones: Una fórmula es una contradicción si todos los
valores de salida para cada una de las líneas de la tabla de verdad
correspondiente a la fórmula dada son contra modelos
interpretativos de la fórmula

Ejemplos:

1.- Tautologías

En si todas las reglas, principios, leyes y propiedades descritas en Algebra de

Proposiciones son tautologías, como ejemplo daremos las siguientes:

A.- A ν B → ~ A → B (Interdefinición)

A B A ν B → ~ A → B
V V V V V V F V V V
V F V V F V F V V F
F V F V V V V F V V
F F F F F V V F F F

Como se puede observar en la tabla correspondiente, el conectivo principal es el de

la implicación, el cual relaciona las dos fórmulas principales constituyentes de la
fórmula dada. Del mismo modo se observa que aplicando los valores de verdad de
acuerdo a los conectivos de relación entre proposiciones, la salida de la fórmula
para cada línea de su tabla de verdad es verdadero, por lo tanto de acuerdo a lo
descrito en la definición de tautología, esta fórmula cumple con la definición, ya
que todos los valores de salida son verdaderos.

B.- ( A → B ) → { ( B → C ) → ( A → C ) } (Silogismo)

A B C A → B → B → C → A → C
V V V V V V V V
V V F V V F V F
V F V F V V V V
V F F F V V F F
F V V V V V V V
F V F V V F V V
F F V V V V V V
F F F V V V V V

37
De acuerdo a los signos de agrupación el conectivo principal es la que relaciona la
primera fórmula con el resto de ella, tal como se observa una vez aplicados los
conceptos y reglas de construcción de fórmulas el resultado para cada línea de
salida de la tabla correspondiente a la fórmula dada es verdadera, por lo tanto se
trata de una tautología

2.- Contingencias

La mayoría de las fórmulas que podemos construir son contingencias, para

determinados valores que asuman las proposiciones, en función del conectivo de
relación podrán ser verdaderas o falsas

A.- { ~ A → ( B Λ C ) } Λ { A → ( C ↔ ~ B ) }

A B C ~ A → B Λ C Λ A → C ↔ ~ B
V V V F V V F F F F
V V F F V F V V V F
V F V F V F V V V V
V F F F V F F F F V
F V V V V V V V F F
F V F V F F F V V F
F F V V F F F V V V
F F F V F F F V F V

Tal como se observa en la salida correspondiente al conectivo principal de la

fórmula dada, existen valores verdaderos y otros falsos, de acuerdo a la definición
de contingencia, se trataría de una fórmula que cumple con esta definición.

B.- { A ↔ ( B → ( A Λ C )) } → { ~ ( A ν B ) Λ ~ C }

A B C A ↔ B → A Λ C → ~ A ν B Λ ~ C
V V V V V V F F V F F
V V F F F F V F V F V
V F V V V V F F V F F
V F F V V F F F V F V
F V V V F F F F V F F
F V F F V F V F V F V
F F V V F F V V F F F
F F F F V F V V F V V

Como resultado de la construcción de la tabla de verdad se observa que la fórmula

dada corresponde de acuerdo a la definición a una contingencia, ya que existen
valores verdaderos y otros falsos correspondientes a las salidas de las líneas de la
tabla de verdad.

3.- Contradicciones

Una contradicción es aquella fórmula para la cual todas las salida de verdad de la
interpretación de esta son contra modelos interpretativos de la misma, el mejor

38
ejemplo es aquel en el cual se niega una tautología, de modo que todas las salidas
correspondientes son falsas

A.- ~ { ( A → B ) → ( ~ A ν B ) }

A B ~ A → B → ~ A ν B
V V F V V F V V
V F F F V F F F
F V F V V V V V
F F F V V V V F

Tal como se puede observar el conectivo principal de salida de la fórmula es la

negación, y en la correspondiente columna a esta los valores para cada línea son
falsa, por lo tanto se trata de una contradicción

B.- ~ { ( A → B ) → ( ~ B → ~ A ) }

A B ~ A → B → ~ B → ~ A
V V F V V F V F
V F F F V V F F
F V F V V F V V
F F F F V V V V

Del mismo modo en la propiedad de la contraposición se puede observar que si

negamos toda la fórmula, los valores de salida correspondientes a cada línea serán
todos ellos falsos, por lo tanto se trata de una contradicción

Ejercicios Propuestos

1.- De dos ejemplos de Tautologías y demuestre los mismos

2.- De dos ejemplos de Contingencias y demuestre los mismos
3.- De dos ejemplos de Contradicciones y demuestre los mismos
4.- De dos ejemplos literales de Tautologías
5.- De dos ejemplos literales de Contingencias
6.- De dos ejemplos literales de Contradicciones

Fórmulas Equivalentes

Dos fórmulas son equivalentes cuando tengan cada una de las fórmulas
correspondientes los mismos valores de salida de la correspondiente tabla, o de
otra manera la relación entre las fórmulas componentes dará como resultado una
tautología.

39
Ejemplos.-

A.- ~ { ( A → ~ B ) Λ ( ~ A → B ) }  A ↔ B

A B ~ A → ~ B Λ ~ A → B  A ↔ B
V V V F F F F V V V
V F F V V V F V V F
F V F V F V V V V F
F F V V V F V F V F

Como se puede observar las salidas correspondientes a cada columna de las

fórmulas consiguientes son iguales y al realizar la equivalencia entre fórmulas se
toma esta como una implicación, como resultado se tiene entonces una tautología,
lo que corrobora que ambas fórmulas son equivalentes

B.- { ~ ( A → B ) Λ ~ ( B → A ) }  { ( A Λ ~ B ) Λ ( B Λ ~ A ) }

Del mismo modo que en el caso anterior se demostrara la equivalencia en función

de la construcción de una tabla de verdad, de manera que en la columna de
equivalencia adra como resultado una tautología.
A B ~ A → B Λ ~ B → A  A Λ ~ B Λ B Λ ~ A
V V F V F F V V F F F F F
V F V F F F V V V V F F F
F V F V F V F V F F F V V
F F F V F F V V F V F F V

Ejercicios Propuestos

Dadas las siguientes fórmulas hallar la fórmula equivalente a esta que no contenga
el conectivo de la implicación.

1.- ( A → ( B → ~ C Λ D )) ↔ A ν B
2.- [ ( A ν C → ( B → ( D ν A )) ] → ~ ( A → ~ ( D Λ B ))
3.- ( A → ~ ( B → ~ C )) ν ( D → (( C Λ B ) → ( A → C ν B )))
4.- [( A → ( ~ B Λ C )) ν ( A ν ( B → C ))] → ~ ( B → D Λ A )
5.- ( B → B ν C ) Λ [ ( B → ~ ( B → ( ~ C Λ D ) ν ( B → ~ A Λ C)) ]

Dadas las siguientes fórmulas hallar una fórmula equivalente que solo contenga los
conectivos de la negación y de la implicación

6.- ( A Λ ~ B ν ~ C ) → ~ ( ( A Λ ~ B Λ ~ C → ( D → B Λ ~ A ))
7.- ( A → ~ B Λ D ν ~ C ) ν ~ ( D → ( C Λ B ))
8.- [ ( A Λ ~ B ) → ~ ( E → ( ~ D Λ B )) ] → ~ ( B Λ ( C ν A ))
9.- ( B → ( ~ C Λ B ) ) → ~ ( A → ( ~ B Λ C Λ ~ A ))
10.- ( B → ( ~ B → ( B Λ C ν ( A → ~ B )))) → ~ A Λ B

Evaluación Semántica de Deducciones

Una deducción es válida en todos los casos, tales que no exista la posibilidad de que
el conjunto de premisas sean todos verdaderos y la conclusión de la deducción

40
falsa, si se da este caso la deducción no será válida. Esta situación quedara
aclarada en la referencia del teorema de la deducción.

P1 ; P 2 ; P 3 ; P 4 ;…….P n – 1 ; P n  Q

V F
F

P1 P2 P3 P4 P5 P6 Q
V V F F F F F
F F F F F F V
F F F F F F F
F F F V V V V
V V V V V V F
V V F F V F F

Estudiando la tabla anterior en virtud de lo señalado en el párrafo anterior

podemos ver que todas las deducciones serán válida o correctas excepto la
correspondiente a la quinta fila, ya que esta parte de un conjunto de premisas
todas ellas verdaderas y arriba a una conclusión falsa, en virtud de lo señalado esta
será la única acepción en la cual la deducción será inválida.

Teorema de la Deducción

El Teorema de la Deducción establece una relación entre las deducciones y las

tautologías, de modo que indica que una tautología es la consecuencia lógica del
conjunto de premisas de una deducción.

A objeto de explicar el alcance del teorema de la deducción, el cual se convierte en

una valiosa arma para la demostración de un conjunto de fórmulas lógicas, que
como se vera, va desde las fórmulas hasta los teoremas, pasando por las
deducciones.

P 1 , P 2 , P 3 , P 4 , P 5 , ….P n – 1 , P n  Q

Aplicando el teorema de la deducción tantas veces como premisas tenga la

fórmula, esta se convierte en un teorema del sistema, que al ser demostrado se
verifica su validez, al aplicar el teorema tantas veces como premisas tenga la
deducción, se logra que el conjunto de premisas sea vacío, y se obtiene una fórmula
que puede demostrarse mediante la construcción de una tabla de verdad asociada
a esta de acuerdo a las reglas descritas

Paso 1: P 1 , P 2 , P3 , P 4 , P 5, …..P n – 1  P n → Q
Paso 2: P 1 , P 2 , P 3 , P 4 , P 5 …… P n – 1 → ( P n → Q )
Paso 3 : P 1 , P 2 , P 3 , P 4 , …. P 5 → ( P n – 1 → ( P n → Q ))

Y así sucesivamente hasta que el conjunto vacío de premisas infiera a una fórmula
demostrable mediante la construcción de su respectiva tabla de verdad

41
Φ  P 1 → ( P 2 → ( P 3 → ( P 4 → ( P 5 → ( P n – 1 → ( P n → Q ))))))

Cuadro de observación del Teorema de la Deducción

P1 P2 P3 P4 P5 P6  Q
V V V V V F V V
V V F F F F V V
V V V V V V V F
F F F F F F V V
V V V V V V F F
V V F F F V V V

Como se puede observar tan solo la fila quinta, donde todas las premisa son
verdaderas y la conclusión falsa nos determina una deducción no válida o
incorrecta.

Tautologías Asociadas a una Deducción Correcta

De acuerdo a lo descrito en el teorema de la deducción, es posible asociar a una

deducción una fórmula, la deducción será válida siempre y cuando la fórmula
resultante de la aplicación del teorema de la deducción tantas veces como premisas
tenga la deducción sea una tautología.

Esta asociación se la puede efectuar de dos maneras, ya sea por implicación o por
conjunción.

1.- Tautología asociada por Implicación

Dada una deducción cualquiera se aplica al conjunto de premisas de esta el

teorema de la deducción, de manera que el conjunto vacío de premisas infiera a
una fórmula, la cual es válida siempre y cuando la fórmula resultante sea una
tautología.

P 1 , P 2 , P3 , P 4 , P 5, …..P n – 1 , P n  Q

Φ  P 1 → ( P 2 → ( P 3 → ( P 4 → ( P 5 → ( P n – 1 → ( P n → Q ))))))

2.- Tautología asociada por Conjunción

Del mismo modo dada una deducción se puede demostrar la validez de esta
transformando la misma a una fórmula, y si se demuestra la validez de esta por
medio de la construcción de una tabla de verdad, entonces la deducción correcta
será válida.

P 1 , P 2 , P3 , P 4 , P 5, …..P n – 1 , P n  Q

P 1 Λ P 2 Λ P 3 Λ P 4 Λ P 5 Λ …..P n – 1 Λ P n → Q

La relación entre las deducciones y las fórmulas esta dada entonces por el teorema
de la deducción, y estable la siguiente relación “ Una deducción es correcta si y solo

42
si la fórmula que se obtiene aplicando el teorema de la deducción tantas veces
como premisas tenga la deducción, es una tautología “

Ejemplos.-

A) Por Implicación

1. P → ( Q → R ) P
2. P Λ Q P
 R

Analizando la deducción planteada, esta tiene dos premisas, por lo tanto podemos
esquematizar la deducción de la siguiente manera y aplicar a esta el teorema de la
deducción, dando como resultado la fórmula siguiente.

P1,P2  Q

 P1→(P2→ Q)
 P→(Q→R) → ( P Λ Q → R)

Construyendo la tabla de verdad de esta fórmula correspondiente a la deducción

dada, se podrá demostrar la validez del argumento si el resultado de la evaluación
semántica de la fórmula da una tautología

P Q R P → Q → R → P Λ Q → R
V V V V V V V V
V V F F F V V F
V F V V V V F V
V F F V V V F V
F V V V V V F V
F V F V F V F V
F F V V V V F V
F F F V V V F V

Tal como se observa de la evaluación de la fórmula mediante la construcción de la

tabla de verdad, el resultado en la columna del conectivo principal nos da valores
de salida verdaderos para cada línea de la tabla de verdad, por lo tanto es una
tautología, entonces la deducción es correcta.

B) Por Conjunción

1. P → ( Q → R ) P
2. P Λ Q P
 R

Analizando la deducción planteada, esta tiene dos premisas, por lo tanto podemos
esquematizar la deducción de la siguiente manera y aplicar a esta el teorema de la
deducción, dando como resultado la fórmula siguiente.

43
P1,P2  Q

 P1Λ P2→ Q)
 P→(Q→R) Λ (P Λ Q)→ R)

P Q R P → Q → R Λ P Λ Q → R
V V V V V V V V V
V V F F F F V V F
V F V V V F F V V
V F F V V F F V F
F V V V V F F V V
F V F V F F F V F
F F V V V F F V V
F F F V V F F V F

Observando la salida en la columna del conectivo principal se ve que todas las

salidas son modelos interpretativos de la fórmula, por lo tanto se trata de una
tautología, entonces la deducción planteada es correcta.

Ejercicios Propuestos

A) Dadas las siguientes deducciones, asociar a cada una de ellas una Tautología
por implicación y por Conjunción y demostrar la misma construyendo la
respectiva tabla de verdad.

1.- P ν Q, Q → R , P → R  R
2.- P → ~ Q , ~ R ν Q , R  ~ P
3.- ~ P → Q, ~ P ν ( R Λ S ), ~ Q Λ ~ T  R
4.- P → Q , Q Λ R → ~ S , ~ T → R Λ S, P  T
5.- T , S Λ T → U , P → ( U → ~ W ) , W , P Λ R  ~ S
6.- ~ S ν ~ T → P Λ Q , ~ P  S ν R
7.- P Λ Q → R , P Λ ~ R ,  ~ Q
8.- ~ P → Q ) Λ ( Q → ~ P ), ~ ( ~ Q ν R ), P ν ~ S  ~ S
9.- P ν Q → R Λ S , ~ ( ~ P ν ~ R ), ~ T → ~ ( P Λ S )  T
10.- P → Q, R ν S, S → ~ Q , ~ R  ~ P

B) Haciendo uso del modelo interpretativo y tablas de verdad de la teoría

semántica, para cada uno de los siguientes ejercicios, indique si los siguientes
razonamientos son validos o no
a) P  Q  R  S, ( P   R), T   (P  S)  T
b) A  B, B   C,  C   D, D   E  A
c) P Q, P  R, Q S, R  (M  A) , (A  B) M,
A  A  A  S  T
d) P  R , R S , T  S , T  Q , Q  P
e) A  B , B C , C  A
f) A C, A B  C , A  D

44
g) P  Q, Q   R , S   ( P  R) , R  S
h) A B , C  D , C  A   ( D  B)
i) P   (Q  R) , T R ,  P  T
j) (S  T)  P  Q , P  S  R
k)  A  B, A  (C  D) ,  (B  E)  C
l) A  B , A  B  C  D , (C  D)  E,
(A  E)  F  F

MÉTODOS DE REFUTACIÓN
Tableaux
Refutación

Los métodos de demostración por refutación pertenecen a los sistemas de

demostración indirectos que, como ya comentamos, son más modernos que los
métodos de demostración axiomáticos y más adecuados para su automatización.
Estos métodos nos proporcionan así una nueva forma de verificar la validez de
fórmulas y de razonamientos.
Un ejemplo de sistema de demostración por refutación es la teoría de los tableaux,
que vamos a estudiar en este apartado.

Vamos ahora a ver cómo se pueden emplear métodos indirectos para verificar la
validez de una fórmula o de un razonamiento.
Procedimiento por reducción al absurdo de demostración de la validez de una
fórmula.
Si la existencia de un modelo de ~ A implica una contradicción, entonces podemos
refutar ~ A ( ~ A es una contradicción) y afirmar la validez de A ( A es una
tautología).
Ejemplo 4.6.1 Si queremos demostrar que la fórmula
A:~(pΛ(p ν q)) ν p
Es una tautología, podemos usar un razonamiento por reducción al absurdo.
Se trata de suponer que exista un modelo para ~ A. Tal modelo es un
contraejemplo para A y, por tanto, tiene que ser tal que ~ ( p Λ ( p_ν q ) ) y p sean
falsas. Pero p Λ ( p ν q) verdadera implica que p es verdadera. Así que p tendría
que ser verdadera y falsa al mismo tiempo y esto es imposible.

Procedimiento por reducción al absurdo de demostración de la validez de un

razonamiento.

El siguiente teorema afirma que A → B es una tautología (una implicación lógica)

si y sólo si no pueden ser simultáneamente verdaderas todas sus premisas y la
negación de su conclusión:

Teorema [HLR] Sean A = ( B1; B2; ….. Bn ) un conjunto finito de fórmulas

proposicionales y B una fórmula. Entonces las siguientes son equivalentes:

(( B1 Λ B2 Λ…….Bn) → B)

45
Es una fórmula válida (una tautología, un razonamiento válido).

(( B 1 Λ B 2 Λ…….B n) Λ ~ ( B ) ) es una contradicción (Reducción al absurdo).

Observación: Se puede notar que, por interdefinición, la fórmula

(( B 1 Λ B 2 Λ…….B n) → B)

es equivalente a la fórmula

( ~ ( B 1 Λ B 2 Λ…….B n) ν B)

Por tanto, su negación es equivalente a la fórmula

(( B 1 Λ B 2 Λ…….B n) Λ ~ ( B ) )

Ejemplo
Para verificar que: ( p → ( q → p)) es una tautología.
Aplicando el teorema (el método de refutación), es suficiente verificar que la
fórmula
p Λ ~ ( q → p ) es insatisfacible (es una contradicción).

Para toda valoración tal que ~ ( q → p ) es falsa, p Λ ~ ( q → p ) es falsa. Si una

valoración es tal que ~ ( q → p ) es verdadera, entonces ( q → p ) es falsa, es
decir, tiene que ser q verdadera y p falsa. También en este caso nuestra fórmula
p Λ ~ ( q → p ) resultaría ser falsa. Se sigue que p Λ ~ ( q → p ) no admite ningún
modelo y, por tanto, es insatisfacible.

Definición de los tableaux

Como veremos, los tableaux son métodos de naturaleza sintáctica, pero se suelen
presentar también por medio de una definición semántica.
Los tableaux semánticos se basan sobre el teorema HLR y son un procedimiento
sistemático para verificar si una fórmula es insatisfacible.
Dada una implicación A → B, su negación A Λ ~ B es insatisfacible si y sólo si
A → B es una implicación lógica.

Más en general, si una fórmula es insatisfacible, su negación es una tautología y,

por tanto, un tableaux permite averiguar si una fórmula es lógicamente válida.

Además, en muchos casos los tableaux son más eficientes que las tablas de verdad
(donde para n proposiciones atómicas tenemos 2n posibles valoraciones),
proporcionan una teoría para programar herramientas de demostración
automática y tienen una extensión natural a la lógica de predicados, que
estudiaremos en la segunda parte de estos apuntes.

Otra aplicaciones de la teoría de los tableaux semánticos son la clasificación de

fórmulas proposicionales (en satisfacibles, insatisfacibles, tautologías o
contingencias) y la obtención de sus formas normales conjuntivas o disyuntivas.

46
Durante el estudio de los tableaux semánticos descubriremos que la verdadera
naturaleza de las reglas que los definen es sintáctica y que, por tanto, la
presentación semántica (y no sintáctica) de la teoría de los tableaux tiene su
justificación en su mayor simplicidad y claridad.
Las principales referencias utilizadas para la siguiente descripción de la teoría de
tableaux son [HLR] y [MH].

Formas Conjuntivas y Disyuntivas

Antes de poder definir la teoría de los tableaux semánticos, necesitamos

profundizar en el análisis semántico de las fórmulas proposicionales.
Se puede demostrar que toda fórmula proposicional equivalente a otra donde
intervienen sólo los conectivos ~ , Λ , ν
Esta propiedad se suele expresar diciendo que el conjunto ( ~ , Λ , ν ) es un
conjunto completo o adecuado de conectivos para la lógica proposicional.
El anterior resultado justifica las siguientes definiciones, que nos permiten
clasificar más fácilmente las fórmulas proposicionales.

Definición (Fórmulas conjuntivas y disyuntivas)

Si una fórmula proposicional A es equivalente a una conjunción de otras dos

fórmulas más sencillas, A1 Λ A2; diremos que es una fórmula conjuntiva (de la
categoría A )

Si una fórmula proposicional B es equivalente a una disyunción de otras dos

fórmulas más sencillas, B1 ν B2; diremos que es una fórmula disyuntiva (de la
categoría B )

Si una fórmula proposicional C es del tipo ~ D , ~ E ~ ~ F diremos que es

simplificable (de la categoría C) y su forma simplificada es C1; que es igual a D ;
E o F respectivamente.

Las fórmulas conjuntivas, disyuntivas y simplificables se llaman fórmulas

reducibles.
Usando las equivalencias lógicas estudiadas, podemos recoger en la siguiente tabla
todas las posibles fórmulas conjuntivas, disyuntivas y simplificables.

Formulas Conjuntivas Formulas Disyuntivas

A A1 A2 B B1 B2
C Λ D C D C ν D C D
~( C ν D) ~C ~D ~(C Λ D) ~C ~D
~( C → D) C ~D C→ D ~C D
C ↔ D C → D D → ~( C ↔ D) ~(C→D) ~(D→ C )
C

47
 Formulas Simplificables
E E1
~F G
~G F
~~C C

Fórmulas Reducibles

Usando árboles con raíz, podemos ahora representar las fórmulas reducibles de la
tabla por medio del esquema de la tabla de reducción de fórmulas que se presenta
a continuación.

Observación. El hecho de que toda fórmula proposicional es equivalente a otra

donde intervienen sólo los conectivos ~ , Λ y ν _ implica que toda fórmula
proposicional es equivalente a una fórmula conjuntiva, a una fórmula disyuntiva o
es simplificable.

Ejemplo
Sea

A → ( B ↔ C)
La fórmula proposicional que se quiere reducir, la regla de interdefinición nos
permite reescribir la fórmula de forma equivalente como una fórmula disyuntiva,
de acuerdo al árbol que se presenta en la tabla siguiente.

E . F. G.

E 1.
F1. F 2.
G 1.
E 2.

48
 CAPITULO IV

TEORIA DE LA DEMOSTRACIÓN

MÉTODOS AXIOMATICOS

Sistema Formal.- Un sistema formal es un artificio matemático aplicado a una

ciencia o a un campo especifico de esta, y que esta compuesto de un conjunto de
enunciados validos aplicados a dicha ciencia o campo de la misma.

Axiomatizar un Sistema.- Dado el conjunto de enunciados validos de la ciencia,

trata de organizar el mismo, de tal forma que partiendo de un conjunto de ellos
llamados axiomas, es posible demostrar el resto de ellos llamados teoremas, por
aplicación de reglas de inferencia sobre los primeros.

Sistema Formal.- Por lo tanto el sistema formal esta constituido de dos diferentes
tipos de enunciados, ambos validos, a saber:
A) Axiomas.- Son fórmulas válidas que no requieren demostración previa para
su aplicación
B) Teoremas.- Fórmulas válidas que para su aplicación requieren de
demostración previa, la cual se ejecuta por aplicación de una regla de
inferencia sobre los axiomas, y sobre los teoremas ya demostrados.

Definición de un Sistema Formal.- Como todo sistema consta de un conjunto de

elementos que permiten definir el sistema, su alcance y el ámbito de su aplicación,
el sistema esta formado por:

S=(A,F,X,R)

A: Alfabeto.- El Alfabeto esta conformado por un conjunto se símbolos y signos,

mediante los cuales se pueden representar y simbolizar las proposiciones
F: Reglas de Sintaxis.- Es el conjunto de reglas y principios que nos permiten
escribir correctamente las fórmulas bien construidas del lenguaje proposicional
(f.b.c)
X: Axiomas.- Es el conjunto de enunciados validos referidos al campo de la lógica
proposicional, mediante los cuales es posible la demostración de cualquier otro
enunciado o teorema del mismo
R: Reglas de Inferencia.- Son reglas de paso que aplicados sobre un conjunto de
fórmulas válidas permiten la demostración y obtención de otras fórmulas válidas

Demostración de Fórmulas.- La demostración de fórmulas es un método que nos

permite la demostración de la misma, a partir de un conjunto finito de fórmulas
Fi, todas estas válidas, tal que cada Fi es:
A) Cada Fi es:
 Un axioma o teorema ya demostrado
 Una fórmula obtenida a partir de las anteriores, por aplicación de
una regla de inferencia
B) El último elemento de la sucesión finita de fórmulas Fi es justamente la
fórmula a demostrar

49
Demostración de Deducciones.- Una deducción es conjunto finito compuesto de
fórmulas o premisas Fi, Pi, tal que
P1 , P2 , P3 , P4 ; Pi, …..Pn-1 ; Pn  Q

F1 , F2 , F3 , F4 ; F5 ; ….Fi,….Fn-1  Q

Donde cada Fi o Pi es:

A) Cada Pi o Fi es :
 Una premisa
 Una fórmula válida, axioma o teorema
 Una fórmula válida obtenida por aplicación de una regla de
inferencia
B) La ultima fórmula Fn o Pn es la conclusión Q a demostrar, por lo que la
conclusión viene a ser consecuencia lógica del conjunto de premisa.

Propiedades de un Sistema Formal

Consistencia.- Un sistema axiomático es consistente cuando a partir del conjunto

de axiomas no es posible obtener una fórmula válida y su contradictoria
Independencia.- El conjunto de axiomas es independiente, es decir que ninguno de
ellos es posible de demostrarlo a partir de los otros
Completud.- Es completo, ya que das dos fórmulas contradictorias, tan solo una de
ellas es demostrable como teorema del sistema
Saturado.- Un sistema es saturado cunado al agregar un nuevo axioma al sistema,
este se convierte en inconsistente

SISTEMAS AXIOMATICOS

En este acápite estudiaremos dos sistemas axiomáticos de demostración de

teoremas, a partir de los cuales es posible la demostración de cualquier otra
fórmula o deducción del Cálculo de proposiciones.

SISTEMA K (Kleene)

K ( A, F, X, R )

A: Símbolos de Alfabeto

A) Símbolos de Proposiciones p, q , r , s , t …….

B) Símbolos de Conectivas ~ , Λ , ν , → , ↔
C) Símbolos de Agrupación ( ) , { } , [ ]

F: Reglas de Sintaxis

A) Los símbolos de proposiciones son f.b.c

B) Si A, B son f.b.c, entonces: ~ A, ~ B, A Λ B , A ν b , A → B , A ↔ B son
f.b.c
C) Todo el conjunto de f.b.c se construye a partir de los puntos anteriores

50
X: Conjunto de Axiomas

├ Este símbolo representa una fórmula válida del sistema

A1: ├ A → (B → A)

A 2 : ├ ( A → B ) → [ (( A → ( B → C ) ) → ( A → C ) ]

A3: ├ A → ( B → A Λ B)

A4: ├ A Λ B → A ├ A Λ B → B

A5: ├ A → A ν B ├ B → A ν B

A6: ├ ( A → C) → [ ( B → C) → ( A ν B) → C]

A7: ├ ( A → B) → [ (A → ~ B) → ~ A]

A8: ├ ~ ~ A → A

R: Reglas de Inferencia

├ A , ├ A → B

├ B Modus Ponens

Interpretación de Axiomas

A1: ├ A → (B → A)

Aplicando el teorema de la Deducción

A  B → A

De una fórmula válida siempre es posible obtener o deducir otra cualquiera que
lleve esta como consecuente de una implicación.

A 2 : ├ ( A → B ) → [ (( A → ( B → C ) ) → ( A → C ) ]

Aplicando el teorema de la Deducción

A → B,A → (B → C),A  C

Siempre que se pueda obtener los elementos de un Modus Ponens, es posible la

demostración de cualquier fórmula

A3: ├ A → ( B → A Λ B)

Aplicando el teorema de la Deducción

51
A,B  A Λ B

Dadas dos fórmulas válidas, siempre es posible obtener la conjunción entre ambas
como fórmula válida

A4: ├ A Λ B → A ├ A Λ B → B

Aplicando el teorema de la Deducción

A Λ B  A

Si la conjunción entre dos fórmulas es una fórmula válida, entonces cada fórmula
componente lo mes

A5: ├ A → A ν B ├ B → A ν B

Basta demostrar que cualquiera de las fórmulas componentes de una disyunción es

válida, para que la disfunción entre estas sea válida

A6: ├ ( A → C) → [ ( B → C) → ( A ν B) → C]

Por el teorema de la deducción

A → C,B → C,A ν B  C

Dadas dos implicaciones con el mismo consecuente, tal que este es la fórmula a
demostrar, y teniendo la disyunción entre los antecedentes de las implicaciones,
siempre es posible demostrar como fórmula válida el consecuente de ambas
implicaciones

A7: ├ ( A → B) → [ (A → ~ B) → ~ A]

Por el teorema de la Deducción

A → B, A → ~ B  ~A

Dadas dos implicaciones de un mismo antecedente, con consecuentes

contradictorios, se obtiene como fórmula válida la negación del antecedente de las
implicaciones

A8: ├ ~ ~ A → A

Negar dos veces, es lo mismo que afirmar, por lo tanto la fórmula es válida

Relacion entre las Deducciones Correctas y los Teoremas del Sistema

Dada una deducción correcta si a esta se le aplica tantas veces el teorema de la

deducción como premisas tenga, entonces se obtiene un teorema del sistema, Si..

52
P 1 , P 2 , P3 , P 4 , P 5, …..P n – 1 , P n  Q

Φ  P 1 → ( P 2 → ( P 3 → ( P 4 → ( P 5 → ( P n – 1 → ( P n → Q ))))))

Es un teorema del sistema, de tal manera que la fórmula solo puede ser:

A) Una premisa
B) Una fórmula deducida de la anterior por aplicación de una regla de
inferencia
C) Una fórmula válida, ya sea axioma o teorema

Analizando el conjunto de posibilidades enumeradas, podemos deducir lo

siguiente:

A) No puede ser una premisa, ya que el conjunto vacío de premisas infiere a la

fórmula
B) No puede ser otra, ya que esta es la única
C) No puede ser un axioma, ya que el número de axiomas no puede variar, sino
el sistema se volvería inconsistente, por lo tanto es un teorema del sistema.

DEMOSTRACIÓN DE TEOREMAS

REGLAS BASICAS DE DEMOSTRACIÓN

A) Siempre y cuando sea posible se aplica el Teorema de la Deducción sobre el

teorema dado, de forma de obtener un conjunto de premisas, las cuales nos
servirán en el proceso de demostración del teorema
B) Al aplicar el Teorema de la Deducción, el último elemento, el cual es la
fórmula a la que induce el conjunto de premisas, se constituye en la fórmula
a demostrar, demostrando esta, demostramos el teorema.
C) Del conjunto de Axiomas y de Teoremas ya demostramos determinamos
cual se ajusta a la fórmula a demostrar, tomando en cuenta que el último
elemento de la sucesión de fórmulas del Axioma o Teorema elegido, el cual
se constituye en Axioma o Teorema principal, es la fórmula a demostrar.
D) A partir de este concepto se deben obtener y/o construir elementos de M.P,
de tal manera que al aplicarse sobre dos fórmulas dadas, nos permita
obtener una nueva fórmula válida.
E) Dependiendo del tipo de fórmula que se debe demostrar, se deben construir
fórmulas, las cuales son Axiomas o teoremas ya demostrados, los cuales se
constituyen en Secundarios en el proceso de demostración del teorema.
F) En cada paso del proceso de demostración, se debe señalar que axioma,
teorema y regla de inferencia se aplica.
G) Se deben elegir los axiomas y teoremas a ser usados en el proceso de
demostración, de tal manera que contengan elementos o fórmulas fáciles de
obtener y demostrar en el proceso.
H) El proceso de demostración del teorema concluye cuando se obtiene dicha
fórmula final del axioma o teorema principal, al ser obtenido este por
aplicación de la regla de inferencia del Modus Ponens.

53
“ Debemos considerar que un axioma o teorema es un modelo, el cual puede ser
modificado o adaptado a las necesidades del proceso de demostración, pero
tomando en cuenta que la estructura del axioma o teorema a ser utilizado no debe
cambiar “, a objeto de ejemplificar esta premisa, se da dos ejemplos , uno en el
cual se observa la regla y otro en el cual no se observa, de tal manera que en este
segundo caso, el uso del axioma es incorrecto.

├ (A → ( B → C )) → [ ( D → E ) → ((A → ( B → C )) Λ [ ( D → E ) ]

Tal como se puede observar, esta aplicación o uso se basa en el Axioma 3, donde se
define:

A = (A → ( B → C ))
B= (D → E)

De tal manera que el uso del mismo guarda relación con la estructura del axioma
tres.

├ (A → B ) → [ ( D → E ) → ((A → ( B → C )) Λ [ ( D → E ) ]

En este caso se observa que el uso del axioma tres, no guarda relación con la
estructura, ya que ( A → B ) es diferente de (A → ( B → C ))

Conjunto de Teoremas del Sistema K

Sabemos que demostrar un teorema equivale a demostrar que la deducción

obtenida aplicando el teorema de la deducción a este teorema es una fórmula
correcta, por lo tanto el teorema es una fórmula válida de teoría de la
demostración.

T1 ├(A → A)
T2 ├(A →B) → [(B → C)→ (A → C)]
T3 ├A →[(A → B) → B]
T4 ├ (A → B) → [(A → C)→(A → B Λ C)]
T5 ├(A → B) → ( ~B → ~A)
T6 ├(A → B) → ~(A Λ ~B)
T7 ├(A → B) → ~A ν B
T8 ├~(A Λ B) → ~A ν ~B
T9 ├~(A ν B) → ~A Λ ~ B
T 10 ├ A Λ B → B Λ A
T 11 ├ A Λ ( B Λ C) → (A Λ B) Λ C
T 12 ├ A Λ ( B ν C) → (A Λ B) ν (A Λ C)
T 13 ├ A Λ A → A
T 14 ├ A Λ (A ν B) → A
T 15 ├ A ν B → B ν A
T 16 ├ A ν( B ν C) → (A ν B) ν C
T 17 ├ A ν (B Λ C) → (A ν B) Λ ( A ν C)
T 18 ├ A ν A → A
T 19 ├ A ν ( A Λ B) → A
T 20 ├ ( A → ( B → C )) → (( A Λ B ) → C )

54
T 21 ├ ( A Λ B → C ) → ( A → ( B → C ))
T 22 ├ ( A ↔ B) → [(B → A) → ( A → B)]
T 23 ├ ( A ↔ B) → ( A → B)
T 24 ├ ( A ↔ B) → (B → A)
T 25 ├ A ↔ A
T 26 ├ ( A ↔ B) → [(B ↔ C) → (A ↔ C)]
T 27 ├ ( A ↔ B) → ( B ↔ A)

Teorema 1 : Teorema de Identidad

├ A → A

En este caso es inaplicable el Teorema de la Deducción, ya que al aplicarse este

quedaría automáticamente demostrado el teorema, por lo tanto debemos
demostrar todo el teorema.

1) ├ ( A → ( A → A )) → [ ( A → ( A → A ) → A) → ( A → A ) ] A 2

De acuerdo al esquema que se ve, el último elemento de la sucesión de fórmulas del

axioma dos, nos permite la demostración del teorema de identidad, ya que se
constituye en este.

En consonancia con las reglas de demostración corresponde construir u obtener

elementos de M.P de tal manera que al aplicarse sobre el axioma principal, nos
permita obtener otra fórmula válida, y así ir paso a paso hasta la obtención del
último elemento de la sucesión de fórmulas del axioma principal, y demostrar el
teorema indicado.

La fórmula que debemos obtener para aplicar como elemento de modus ponens es
(A → ( A → A)), al observar la misma, se ve que tiene la estructura del axioma 1,
por lo tanto podemos hacer uso de este axioma, como axioma secundario del
proceso de demostración, en el cual se ha definido:

A = A ; B= A

2) ├ ( A → ( A → A )) A1

Por lo tanto entre el paso 1 y 2 tenemos la estructura del Modus Ponens, que al ser
aplicada nos permite obtener la siguiente formuela válida del proceso de
demostración.

3) ( A → ( A → A ) → A ) → ( A → A ) M.P ( 1 , 2 )

Al observar el resto de fórmula que queda, luego de la aplicación del M.P en el

paso anterior, vemos que la fórmula ( A → ( A → A ) → A ), es esquema o
tiene estructura de axioma 1, definiendo

A = A ; B= A → A

55
4) ( A → ( A → A ) → A ) A1

Al aplicarse sobre el paso 3, se obtiene la fórmula o teorema a ser demostrado, por

aplicación de la regla de inferencia del M.P

5) A → A M.P ( 3 , 4 )

Con lo que queda demostrado el teorema de identidad

Teorema 2 : Teorema del Silogismo

├ ( A → B) →[(B → C) → (A → C)]

Aplicando el Teorema de la Deducción al teorema dado, tantas veces como

premisas se pueda obtener, obtenemos

A → B, B → C, A  C

Donde el símbolo  : tiene las siguientes acepciones

A) C se obtiene a partir de A → B , B → C , A

B) A → B , B → C , A induce a C

1) A → B P
2) B → C P
3) A P

De tal manera que al aplicar el T.D sobre el teorema dado, se ha obtenido un

conjunto de premisas, las cuales son fórmulas válidas, y que pueden ser usadas en
el proceso de demostración del teorema.

Al observar el conjunto de premisas, se observa que en la premisa 2, la ultima

fórmula de la misma es la fórmula “ C “, es decir la fórmula a demostrar, por lo
tanto no requerimos de un axioma o teorema principal, como medio de
demostración del teorema.
En este caso si se observa los pasos 1 , 2 se ve que tienen la estructura del silogismo,
pero esta propiedad no se la puede usar ya que no ha sido demostrada en forma
previa, y aun mas es el teorema sujeto a demostración.

Si se observa el paso 1 , 3 se ve que tiene la estructura de la regla de inferencia del

M.P, por lo tanto podemos aplicar esta regla.

4) B M.P ( 1 , 2 )

Del mismo modo en el paso ( 2 , 4 ) se tiene nuevamente los elementos de un M.P, el

cual al ser aplicado sobre estos pasos de demostración nos permiten demostrar el
teorema, ya que como consecuencia se obtiene la fórmula “ C “

5) C M.P ( 2 , 4 )

56
Teorema 3 : Teorema del Modus Ponens

├ A → [( A → B) → B]

Aplicando el teorema de la deducción

A , A → B  B

1) A P
2) A → B P
3) B M.P ( 2 , 1 )

Con lo que queda demostrado el teorema del M.P, ya que como se indico al aplicar
el T.D sobre una fórmula o teorema, basta demostrar el último elemento de la
sucesión de fórmulas, de modo que al obtener esta como fórmula válida, queda
demostrado el teorema consiguiente.

Teorema 4 : Ex – Contradictione Quolibet ( E.C.Q )

├ A → ( ~ A → C)

Aplicando el T.D

A, ~ A  C

1) A P
2) ~ A P

Al observar la fórmula a demostrar “ C “, se ve que el único axioma cuya

estructura nos permite obtener como fórmula válida esta, es el axioma 8, el de la
doble negación.

3) ~ ~ C → C A8

Ahora en base al conjunto de premisa y axiomas y/o teoremas ya demostrados

debemos adaptar uno de tal manera que el último elemento de la sucesión de
fórmulas sea ~ ~ C, el único que se adapta a este esquema de negación es el axioma
7, ya que tiene la estructura de obtención de una fórmula negada.

4) ├ ( ~ C → A ) → [ ( ~ C → ~ A ) → ~ ~ C ] A7

Debemos obtener como elemento de M.P la fórmula ~ C → A , esta por si sola no

tiene esquema de ningún axioma o teorema ya demostrado, pero si observamos la
premisa 1 conjuntamente con dicha fórmula, se puede construir el esquema del
axioma 1, y aplicar este sobre el axioma secundario de manera de obtener una
fórmula válida.

5) ├ A → ( ~ C → A ) A1

57
6) ~ C → A M.P ( 5, 1 )

La fórmula obtenida en el paso 6 nos permite aplicar esta, como elemento de M.P
sobre la fórmula del paso 4

7) ( ~ C → ~ A ) → ~ ~ C M.P ( 4 , 6 )

Del mismo modo que en el paso anterior, conjuntamente con la premisa 2, se puede
construir un esquema de axioma 1, para obtener como elemento de M.P la fórmula
~C→ ~A

8) ├ ~ A → ( ~ C → ~ A ) A1
9) ~ C → ~ A M.P ( 8 , 2 )

La fórmula 9 se aplica como elemento de M.P sobre el paso 8

10) ~ ~ C M.P ( 7 , 9 )
11) C M.P ( 3 , 10 )

Teorema 5 : Producto Condicional

├ ( A → B) → [( A → C) → (A → B Λ C)]

T.D A → B , A → C , A  B Λ C

1) A → B P
2) A → C P
3) A P

Al tratarse la fórmula a demostrar de una conjunción entre dos fórmulas, se ve

que el esquema de axioma que se ajusta a esta demostración para obtener la
fórmula es el esquema del axioma 3

4) ├ B → ( C → B Λ C) A3

De tal forma que debemos obtener dos elementos de M.P para poder demostrar la
fórmula, los cuales podemos obtener mediante elementos de M.P entre las tres
premisas obtenidas por aplicación del T.D

5) B M.P ( 1 , 3 )
6) C M.P ( 2 , 3 )
7) C→ B Λ C M.P ( 4 , 5 )
8) B Λ C M.P ( 7, 6)

Con lo que queda demostrado el teorema del producto condicional, ya que se ha

obtenido en el proceso de demostración del teorema la última fórmula, y al obtener
esta, directamente se ha demostrado el teorema.

58
Teorema 6 : Contraposición

├ ( A → B) → ( ~B → ~ A)

T.D A → B , ~ B  ~ A

1) A → B P
2) ~ B P

De acuerdo al tipo de fórmula a obtener en el proceso de demostración del teorema

de contraposición, esta se trata de la negación de una fórmula, en el espectro de
axiomas con los que cuenta el sistema K, cuya estructura nos permite la obtención
de una fórmula negada es el axioma 7

3) ├ ( A → B ) → [ ( A → ~ B ) → ~ A ] A7
4) ( A → ~ B ) → ~ A M.P ( 3 , 1 )

Debemos obtener como elemento de M.P la fórmula ( A → ~ B ), por si sola esta

no es esquema de ninguna axioma o teorema, pero si observamos la premisa 2,
podemos construir con la fórmula a obtener como elemento de M.P el axioma 1

5) ├ ~ B → ( A → ~ B ) A1
6) A → ~ B M.P ( 5 , 2 )
7) ~ A M.P ( 4 , 6 )

Con lo que se demuestra la fórmula, y implícitamente el teorema de

contraposición.

Teorema 7 : Interdefinción → respecto Λ

├ ( A → B) → ~ ( A Λ ~ B)

T.D A → B  ~ ( A Λ ~ B )

1) A → B P

Como en el caso de la demostración del teorema de contraposición, la fórmula a

demostrar es una negación, por lo tanto recurrimos como axioma principal al
axioma 7

2) ├ ( A Λ ~ B → B ) → [ ( A Λ ~ B → ~ B ) → ~ ( A Λ ~ B ) ] A 7

Debemos obtener dos elementos de M.P para obtener la fórmula que se quiere
demostrar, al observar la primera vemos que tiene esquema de axioma 4, pero no
implica a ninguna de las fórmulas componentes de la conjunción, por lo tanto en
este caso podemos recurrir al teorema 2 es decir al silogismo para poder obtener la
fórmula como electo de M.P, en el segundo caso se trata claramente de la
aplicación del axioma 4.

3) ├ ( A Λ ~ B → A ) → [ ( A → B ) → ( A Λ ~ B → B ) T 2

59
4) ├ A Λ ~ B → A A4
5) ( A → B ) → ( A Λ ~ B → B ) M.P ( 3 , 4 )
6) A Λ ~ B → B M.P ( 5 , 1 )
7) ( A Λ ~ B → ~ B ) → ~ ( A Λ ~ B ) M.P ( 2 , 6 )
8) A Λ ~ B → ~ B A4
9) ~ ( A Λ ~ B ) M.P ( 7 , 8 )

Con la obtención de la fórmula ~ ( A Λ ~ B ), queda demostrado el teorema de

ínter definición, como se ha podido observar la obtención, construcción y
aplicación de elementos de M.P sobre el proceso de demostración es la clave de
demostración de un teorema.

Teorema 8 : De Morgan relación entre la conjunción y la disyunción

├ ~( A Λ B) → ~ A ν ~ B

Al observar el esquema del teorema sujeto a demostración se ve que la aplicación

del T.D sobre el teorema dado no es necesario de aplicarse ya que la obtención de
una premisa no se aplicara en el proceso de demostración del teorema, por lo tanto
debemos demostrar todo el teorema, lo que significa que al determinar el axioma o
teorema principal a ser aplicado en el proceso de demostración, este se debe
ajustar al tipo de fórmula a demostrar, observando el esquema se ve que el
teorema de contraposición ya demostrado se ajusta a dicho contexto.

1)├ [ ~ ( ~ A ν ~ B ) → ( A Λ B ) ] → [ ~ ( A Λ B ) → ~ A ν ~ B ] T.C.P

Al observar la fórmula ~ ( ~ A ν ~ B ) → ( A Λ B , la cual debemos construir

como elemento de M.P para ser aplicada sobre el teorema principal, el esquema se
ajusta al teorema del producto condicional ya demostrado

2) ├ ( ~ ( ~ A ν ~ B ) → A ) → [ ~ ( ~ A ν ~ B ) → B ) → ( ~ ( ~ A ν ~ B ) → ( A Λ B ) ] T.P.C

Ahora debemos obtener dos electos de M.P para poder aplicarlos sobre el paso 2 y
así obtener el elemento de M.P a ser aplicado sobre el paso 1, que nos permita
demostrar el teorema en cuestión, observando el esquema de fórmula de la que se
trata ~ ( ~ A ν ~ B ) → A , vemos que tiene el esquema del teorema de
contraposición.

3) ├ ( ~ A → ~ A ν ~ B ) → ( ~ ( ~ A ν ~ B ) → A ) T.C.P

Y la fórmula ~ A → ~ A ν ~ B, es esquema directo del axioma 5, por lo tanto al

construir este elemento podemos utilizarlo como elemento de M.P a ser aplicado
sobre el paso consiguiente.

4) ├ ~ A → ~ A ν ~ B A5
5) ~ ( ~ A ν ~ B ) → A M.P ( 3 , 4 )
6) ~ ( ~ A ν ~ B ) → B ) → ( ~ ( ~ A ν ~ B ) → ( A Λ B ) ) M.P ( 2 , 5 )
7) ├ ( ~ B → ~ A ν ~ B ) → ( ~ ( ~ A ν ~ B ) → B ) T.C.P
8) ├ ~ B → ~ A ν ~ B A 5
9) ~ ( ~ A ν ~ B ) → B M.P ( 7 , 9 )

60
10) ~ ( ~ A ν ~ B ) → ( A Λ B ) ) M.P ( 6, 9 )

Teorema 9 : De Morgan Relación entre la disyunción y la conjunción

├ ~ ( A ν B) → ~A Λ ~ B

T.D ~ ( A ν B )  ~ A Λ ~ B

1) ~ ( A ν B ) P

Al observar el tipo de fórmula demostrar, se ve que se trata de la conjunción entre

dos fórmulas, por lo tanto podemos aplicar el axioma 3 como axioma principal en
el proceso de demostración.

2) ├ ~ A → ( ~ B → ~ A Λ ~ B ) A3

Se debe obtener dos elementos de M.P a ser aplicados sobre el paso 2 del proceso
de demostración, de manera de demostrar el teorema, a saber ~ A ¸~ B, como se
trata de una fórmula única y negada, entonces se puede aplicar como axiomas
secundarios para la obtención de dichas fórmulas el axioma 7.

3) ├ ( A → A ν B ) → [ ( A → ~ ( A ν B ) → ~ A ] A7

En la aplicación del axioma 7 en el proceso de demostración, debemos obtener dos

fórmulas como elementos de M.P para poder obtener la fórmula ~ A, observando
el esquema vemos que podemos aplicar el axioma 5 para la primera fórmula, y el
axioma 1 conjuntamente con la premisa para la obtención de la segunda fórmula
como elemento de M. P a ser aplicados posteriormente en el paso 3.

4) ├ A → A ν B A5
5) ( A → ~ ( A ν B )) → ~ A M.P ( 3 , 4 )
6) ├ ~ ( A ν B ) → ( A → ~ ( A ν B )) A1
7) A → ~(A ν B) M.P ( 6 , 1 )
8) ~A M.P ( 3 , 7 )

La obtención de la fórmula ~ B, al ser esta similar al proceso para la obtención de

~ A seguirá el mismo procedimiento realizado en los pasos anteriores.

9) ├ ( B → A ν B ) → [ ( B → ~ ( A ν B ) → ~ B ] A7
10) ├ B → A ν B A5
11) B → ~ ( A ν B ) → ~ B M.P ( 9 , 10 )
12 ) ├ ~ ( A ν B ) → ( B → ~ ( A ν B )) A1
13) ( B → ~ ( A ν B ) M.P ( 12 , 1 )
14) ~ B M.P ( 11 , 13 )
15) ~ B → ~ A Λ ~ B ) M.P( 2 , 8 )
16) ~ A Λ ~ B ) M.P ( 15 , 14 )

Al aplicar las fórmulas obtenidas en los pasos 8 y 14 sobre el axioma principal

demostramos la fórmula y por ende el teorema de De Morgan

61
Teorema 10 : Inter Definición de la implicación respecto a la disyunción

├ ( A → B) → ~ A ν B

En el proceso de demostración de este teorema no es necesario la aplicación del

T.D ya que no se utilizará la premisa en el proceso de demostración. Como axioma
principal podemos usar dado el esquema de la fórmula a demostrar el teorema del
silogismo.
1)├ [ ( A → B ) → ~ ( A Λ ~ B ) ] → [ ( ~ ( A Λ ~ B ) → ~ A ν B ) →( ( A → B ) → ~ A ν B ) ] T 2 Silogismo

El primer elemento de M.P a obtener se ve que es justamente el teorema de inter

definición de la implicación respecto a la conjunción demostrado con anterioridad
y el que si se puede aplicar en el proceso de demostración

2) ├ ( A → B ) → ~ ( A Λ ~ B ) Interdefincion
3) ( ~ ( A Λ ~ B ) → ~ A ν B ) → (( A → B ) → ~ A ν B ) M.P( 1 , 2)

Al observar la siguiente fórmula que debemos obtener como elemento de M.P en el

proceso de demostración se ve que se trata del esquema del teorema de De Morgan
ya demostrado, por lo tanto podemos construir este esquema y aplicarlo como
elemento de M.P en el paso 3

4) ├ ~ ( A Λ ~ B ) → ~ A ν B De Morgan
5) ( A → B ) → ~ A ν B M.P ( 3 , 4 )

TEOREMAS DE CONJUNCION

Teorema 11 : Conmutativa

├ A Λ B → B Λ A

T.D A Λ B  B Λ A

1) A Λ B P

Como la fórmula a demostrar se trata de la conjunción entre dos fórmulas

podemos hacer uso del axioma 3 en el proceso de demostración y tomar este
axioma como axioma principal

2) ├ B → ( A → B Λ A ) A3

Se debe obtener las fórmula B , A como elementos de M.P para ser aplicados sobre
el axioma principal, se ve que para obtener estas fórmulas podemos aplicar el
axioma 4, ya que este nos permite obtener las fórmulas requeridas, la obtención de
estas fórmulas se facilita si se hace uso de la premisa como elemento de M.P a ser
aplicado sobre los axiomas secundarios

3) ├ A Λ B → B A4
4) B M.P ( 3 , 1 )
5) A → B Λ A M.P ( 2 , 4 )

62
6) ├ A Λ B → A A4
7) A M.P ( 6 , 1 )
8) B Λ A M.P ( 5 , 7 )

Teorema 12 : Asociativa

├ A Λ ( B Λ C) → ( A Λ B) Λ C

T.D A Λ ( B Λ C )  ( A Λ B ) Λ C

1) A Λ ( B Λ C ) P

Como en el caso de la demostración del teorema conmutativo, el axioma principal

se trata del axioma 3, ya que este presenta una estructura de conjunción entre
fórmulas.

2) ├ A Λ B → ( C → (( A Λ B ) Λ C) A3

El primer elemento de M.P a obtener se trata de la conjunción entre dos fórmulas

por lo tanto podemos aplicar nuevamente el axioma 3 para poder construir este
elemento de M.P

3) ├ A → ( B → A Λ B ) A3

En este paso de demostración se deben obtener dos elementos de M.P a saber A ,

B, por lo tanto se puede aplicar el axioma 4 para la obtención de dichas fórmulas,
ya que con la premisa es posible obtener estas.

4) ├ A Λ ( B Λ C ) → A A4
5) A M.P ( 4 , 1 )
6) B → A Λ B M.P ( 3 , 5 )
7) ├ A Λ ( B Λ C ) → B Λ C A4
8) B Λ C M.P ( 7 , 1 )
9)├ B Λ C → B A4
10) B M.P ( 9 , 8 )
11) A Λ B M.P ( 6 , 10 )
12) C → (( A Λ B ) Λ C) M.P ( 2 , 11)
13) ├ B Λ C → C A4
14) C M.P ( 13 , 8 )
15 ) ( A Λ B ) Λ C M.P ( 12 , 14 )

Teorema 13 : Absorción

├ A Λ ( A ν B) → A

T.D A Λ ( A ν B )  A

1) A Λ ( A ν B ) P
2) ├ A Λ ( A ν B ) → A A4
3) A M.P ( 2 , 1 )

63
Teorema 14 : Idempotencia

├ A Λ A → A

T.D A Λ A  A

1) A Λ A P
2) ├ A Λ A → A A4
3) A M.P ( 2 , 1 )

Teorema 15 : Distributiva de la conjunción respecto a la disyunción

├ A Λ ( B ν C) → ( A Λ B ) ν ( A Λ C)

T.D A Λ ( B ν C )  ( A Λ B ) ν ( A Λ C )

1) A Λ ( B ν C ) P

La fórmula a demostrar se trata de una disyunción entre dos fórmulas, por lo que
analizando esta situación nueva que se presenta, podemos aplicar el axioma 6 en
este proceso para la obtención de la fórmula, ya que es el único que nos va a
permitir la obtención del mismo.

2) ├ ( B → ( A Λ B ) ν ( A Λ C ) → [( C → ( A Λ B ) ν ( A Λ C )) → ( B ν C → (( A Λ B ) ν ( A Λ C )) ] A6

Al observar los elementos de M.P que debemos obtener en el proceso de

demostración del teorema vemos que ambos tienen la misma estructura, en forma
directa no es posible obtener estos, por lo que debemos recurrir al teorema del
silogismo, y de esta manera construir estos elementos de M.P .

3) ├ ( B → ( A Λ B ) ) → [ (( A Λ B ) → ( A Λ B ) ν ( A Λ C )) → (( B → ( A Λ B ) ν ( A Λ C )) T 2

El primer elemento de M.P, se trata sin duda de la aplicación del axioma 3, para el
segundo elemento de M.P a obtener podemos aplicar el axioma 5, ya que se trata
de la disyunción entre dos fórmulas.

4) ├ A → ( B → A Λ B ) A3
5) ├ A Λ ( B ν C ) → A A4
6) A M.P ( 5 , 1 )
7) B → A Λ B M.P ( 4 , 6 )
8) (( A Λ B ) → ( A Λ B ) ν ( A Λ C )) → ( B → ( A Λ B ) ν ( A Λ C ) M.P ( 2, 7 )
9) ├ A Λ B ) → ( A Λ B ) ν ( A Λ C ) A5
10) B → ( A Λ B ) ν ( A Λ C ) M.P ( 8 , 9 )
11) ( C → ( A Λ B ) ν ( A Λ C )) → ( B ν C → (( A Λ B ) ν ( A Λ C )) M.P ( 2 , 10 )
12) ├ ( C → ( A Λ C ) ) → [ (( A Λ C ) → ( A Λ B ) ν ( A Λ C )) → (( C → ( A Λ B ) ν ( A Λ C )) T 2
13) ├ A → ( C → A Λ C ) A3
14) C → A Λ C M.P ( 13 , 6 )
15) (( A Λ C )→ (A Λ B ) ν ( A Λ C ))→ ( C → ( A Λ B ) ν ( A Λ C ) M.P ( 12 , 14 )
16) ├ A Λ C ) → ( A Λ B ) ν ( A Λ C ) A5

64
17) C → ( A Λ B ) ν ( A Λ C ) M.P ( 15, 16 )
18) ( B ν C → (( A Λ B ) ν ( A Λ C )) M.P ( 11 , 17 )
19) ├ A Λ ( B ν C ) → B ν C A4
20) B ν C M.P( 19 , 1 )
21) ( A Λ B ) ν ( A Λ C ) M.P ( 18 , 20 )

TEOREMAS DE DISYUNCIÓN

Teorema 16 : Conmutativa

├ A ν B → B ν A

Al tratarse la fórmula a demostrar de una disyunción, se aplica el axioma 6 para

poder construir el esquema de demostración del teorema, de tal manera que el
último elemento de la sucesión de fórmulas sea la fórmula a demostrar.

1) ├ ( A → B ν A ) → [ ( B → B ν A ) → ( A ν B → B ν A ) ] A 6

La obtención de los dos elementos de M.P, pasa como se puede ver por la
construcción del axioma 5, el cual nos va permitir obtener dichos elementos de
M.P .

2) ├ A → B ν A A5
3) ( B → B ν A ) → ( A ν B → B ν A ) M.P ( 1 , 2 )
4) ├ ( B → B ν A ) A5
5) A ν B → B ν A M.P ( 3 , 4 )

Teorema 17 : Asociativa

├ A ν ( B ν C) → ( A ν B) ν C

Como en el anterior caso, la fórmula a demostrar es una disyunción, por lo tanto

podemos aplicar el axioma 6, como axioma principal, de tal manera que el último
elemento de la sucesión de fórmulas, sea la fórmula demostrar.

1) ├ ( A → ( A ν B ) ν C ) → [ (( B ν C ) → ( A ν B ) ν C ) → ( A ν ( B ν C ) → ( A ν B ) ν C ) ] A 6

El primer elemento de M.P en el proceso de demostración, podemos obtenerlo

mediante la aplicación del teorema del silogismo, ya que en forma directa no es
posible la obtención de la fórmula A → ( A ν B ) ν C

2) ├ (A → A ν B ) → [ ( A ν B → ( A ν B ) ν C ) → ( A → ( A ν B ) ν C ) ] T 2

Los dos elementos de M.P a ser requeridos en la obtención de la fórmula contenida

en el teorema secundario entrañan la aplicación del axioma 5

3) ├ A → A ν B A5
4) ( A ν B → ( A ν B ) ν C ) → ( A → ( A ν B ) ν C ) M.P ( 2 , 3 )
5) ├ A ν B → ( A ν B ) ν C A5
6) A → ( A ν B ) ν C M.P ( 4 , 5 )

65
7) ( B ν C ) → ( A ν B ) ν C ) → ( A ν ( B ν C ) → ( A ν B ) ν C ) M.P ( 1 , 6)

La fórmula ( B ν C ) → ( A ν B ) ν C ) es nuevamente una disyunción, por lo tanto

para poder obtener la misma como elemento de M.P se requerirá construir un
axioma 6.

8) ├ ( B → ( A ν B ) ν C ) → [ ( C → ( A ν B ) ν C ) → (( B ν C ) → ( A ν B ) ν C ) ] A 6

Los dos elementos de M. P a obtener para poder ser aplicados sobre el paso 8
entrañan en forma similar la construcción de silogismo y la aplicación del axioma 5

9) ├ (B → A ν B ) → [ ( A ν B → ( A ν B ) ν C ) → ( B → ( A ν B ) ν C ) ] T 2
10) ├ B → A ν B A5
11) ( A ν B → ( A ν B ) ν C ) → ( B → ( A ν B ) ν C ) M.P( 9 , 10 )
12) ├ A ν B → ( A ν B ) ν C ) A5
13) B → ( A ν B ) ν C M.P( 11 , 12 )
14) ( C → ( A ν B ) ν C ) → (( B ν C ) → ( A ν B ) ν C ) M.P ( 8 , 13 )
15) ├ C → ( A ν B ) ν C A5
16) ( B ν C ) → ( A ν B ) ν C ) M.P ( 14 , 15 )
17) A ν ( B ν C ) → ( A ν B ) ν C M.P ( 7 , 16 )

Teorema 18 : Absorción

├ A ν (A Λ B) → A

Al tratarse de la disyunción entre fórmulas, se aplica en forma directa el axioma 6,

construyendo este de forma que el último elemento sea la fórmula a demostrar, en
este caso el teorema de absorción

1) ├ ( A → A ) → [ ( A Λ B ) → A ) → ( A ν ( A Λ B ) → A ) ] A 6
2) ├ A → A T 1 Identidad
3) ( A Λ B ) → A ) → ( A ν ( A Λ B ) → A ) M.P ( 1 , 2)
4) ├ A Λ B → A A4
5) A ν ( A Λ B ) → A M.P ( 3 , 4 )

Teorema 19 : Idempotencia

├ A ν A → A

1) ├ ( A → A ) → [ ( A → A ) → ( A ν A → A ) ] A6
2) ├ A → A T 1 Identidad
3) ( A → A ) → ( A ν A → A ) M.P ( 1 , 2 )
4) A ν A → A M.P ( 3 , 2 )

Teorema 20 : Distributiva de la disyunción respecto a la conjunción

├ A ν ( B ν C) → (A ν B) Λ ( A ν C)

Al tratarse la fórmula a demostrar de la conjunción entre dos fórmulas, y con el

antecedente de la disyunción de la primera, para poder demostrar esta debemos

66
recurrir al teorema del producto condicional, cuya estructura nos permitirá dicha
demostración, tomando por lo tanto este teorema como principal.
1) ├ ( A ν ( B Λ C ) → A ν B ) → [ (( A ν ( B Λ C ) → A ν C ) → ( A ν ( B Λ C ) → ( A ν B ) Λ ( A ν C ) ] T.P.C

Para poder obtener los dos elementos de M.P necesarios para ser aplicados sobre
el paso 1, siendo ambas fórmulas similares, podemos aplicar en forma consecutiva,
los siguientes pasos, construyendo axiomas y teoremas secundarios, a saber axioma
6, teorema del silogismo, axioma 4 y axioma 5, de manera de conseguir elementos
de M.P .

2) ├ ( A → A ν B ) → [ ( B Λ C ) → A ν B ) → ( A ν ( B Λ C ) → ( A ν B ) ] A6
3) ├ A → A ν B A5
4) ( B Λ C ) → A ν B ) → ( A ν ( B Λ C ) → ( A ν B ) M.P ( 2 , 3 )
5) ├ ( B Λ C ) → B ) → [ ( B → A ν B ) → ( B Λ C → A ν B ) ] T 2
6) ├ B Λ C → B A4
7) ( B → A ν B ) → ( B Λ C → A ν B ) M.P ( 5 , 6 )
8) ├ B → A ν B A5
9) B Λ C → A ν B M.P ( 7 , 8 )
10) A ν ( B Λ C ) → A ν B M.P ( 2 , 3 )
11) (A ν ( B Λ C )→ A ν C ) → ( A ν ( B Λ C ) → ( A ν B ) Λ ( A ν C )] M.P ( 1 , 10 )
12) ├ ( A → A ν C ) → [ ( B Λ C ) → A ν C ) → ( A ν ( B Λ C ) → ( A ν C ) ] A6
13) ├ A → A ν C A5
14) ( B Λ C ) → A ν B ) → ( A ν ( B Λ C ) → ( A ν C ) M.P ( 12 , 13 )
15) ├ ( B Λ C ) → C ) → [ ( C → A ν C ) → ( B Λ C → A ν C ) ] T 2
16) ├ B Λ C → C A4
17) ( C → A ν C ) → ( B Λ C → A ν C ) M.P ( 15 , 16 )
18) ├ C → A ν C A5
19) B Λ C → A ν C ) M.P ( 17 , 18 )
20) A ν ( B Λ C ) → ( A ν C ) M.P (14 , 19 )
21) A ν ( B Λ C ) → ( A ν B ) Λ ( A ν C ) M.P ( 11, 20 )

Teorema 21 : Importación

├(A → ( B → C) → (A Λ B→ C)

T.D A → ( B → C ) , A Λ B  C

1) A →(B → C) P
2) A Λ B P
3) A Λ B → A A4
4) A M.P( 3, 2 )
5) B → C M.P ( 1 , 4 )
6) A Λ B → B A4
7) B M.P ( 6 , 2 )
8) C M.P ( 5 , 7 )

Teorema 22 : Exportación

├ ( A Λ B → C ) → ( A → ( B → C ))

67
T.D A Λ B → C,A,B  C

1) A Λ B → C P
2) A P
3) B P
4) A → ( B → A Λ B) A3
5) B → A Λ B M.P ( 4 , 2 )
6) A Λ B M.P ( 5 , 3 )
7) C M.P ( 1 , 6 )

Teorema 23 : Introducción del Co Implicador

├ ( A ↔ B) → [( B → A) Λ ( A → B ]

Esta fórmula o teorema a demostrar entraña la demostración de la conjunción

entre dos fórmulas, es decir la aplicación del axioma 4, con lo que queda
demostrada.

En la demostración de los teoremas del sistema se puede observar una sistemática

en el proceso de demostración, se observa que la aplicación de determinado axioma
o teorema en el proceso se basa en el tipo de fórmula a demostrar, de lo que
podemos inferir las siguientes conclusiones.

A) Cuando la fórmula a demostrar se trata de una conjunción, se debe

utilizar en este caso el axioma tres o el teorema del producto
condicional.
B) Si la fórmula a demostrar entraña la disyunción entre dos fórmulas
se debe aplicar en el proceso de demostración el axioma 6.
C) Si la fórmula a demostrar es una negación, en el caso que se aplica,
se debe utilizar el axioma siete o en su defecto si se trata de la
relación entre dos fórmulas el teorema de contraposición.
D) Si la fórmula a demostrar u obtener no guarda relación alguna entre
el antecedente y el consecuente, se debe recurrir a la construcción de
un silogismo para obtener la misma.

Ejercicios de aplicación del sistema K, en la demostración de deducciones

Se debe tomar en cuenta que un sistema axiomático es un método constructivo de

demostración, es decir se deben construir las fórmulas en base a los axiomas y
teoremas demostrados y a partir de la aplicación de la regla de inferencia del M.P
ir obteniendo en forma sucesiva las diferentes fórmulas válidas del proceso de
demostración de la deducción hasta demostrar la conclusión de esta.

Ejercicio 1:

A → ~ B,~ C ν B,C  ~A

1) A → ~ B P
2) ~ C ν B P

68
 3) C P
 ~ A
4) ├ ( ~ C ν B ) → ( C → B ) Inter Definición
5) C → B M.P ( 4 , 2 )
6) ( A → ~ B ) → ( B → ~ A ) C.P
7) B → ~ A M.P ( 6 , 1 )
8) ( C → B ) → [ ( B → ~ A ) → ( C → ~ A ) T2
9) ( B → ~ A ) → ( C → ~ A ) M.P ( 8 , 5 )
10) C → ~ A M.P ( 9 , 7 )
11) ~ A M.P ( 10 , 3 )

L.Q.Q.D

Ejerecicio 2 :

A → B , B Λ C → ~ D , ~ E → C Λ D, A  E

1) A → B P
2) B Λ C → ~ D P
3) ~ E → C Λ D P
4) A P
 E
5) B M.P ( 1 , 4 )
6) ├ (( B Λ C ) → ~ D ) → ( B → ( C → ~ D )) Exportación
7) B → ( C → ~ D ) M.P ( 6 , 2 )
8) C → ~ D M.P ( 7 , 5 )
9) ├ ( C → ~ D ) → ( ~ C ν ~ D ) Interdeficion
10) ~ C ν ~ D M.P ( 9 , 8 )
11) ├ ( ~ C ν ~ D ) → ~ ( C Λ D ) De Morgan
12) ~ ( C Λ D ) M.P ( 11 , 10 )
13) ├ ( ~ E → C Λ D ) → ~ ( C Λ D ) → E C.P
14) ~ ( C Λ D ) → E M.P ( 13 , 3 )
15) E M.P ( 14 , 12 )

L.Q.Q.D

Ejercicios Propuestos

A) En cada una de las siguientes deducciones planteadas, demostrar la validez de

las mismas, demostrando estas por medio del sistema K

1.- P ν Q, Q → R , P → R  R
2.- P → ~ Q , ~ R ν Q , R  ~ P
3.- ~ P → Q, ~ P ν ( R Λ S ), ~ Q Λ ~ T  R
4.- P → Q , Q Λ R → ~ S , ~ T → R Λ S, P  T
5.- T , S Λ T → U , P → ( U → ~ W ) , W , P Λ R  ~ S
6.- ~ S ν ~ T → P Λ Q , ~ P  S ν R
7.- P Λ Q → R , P Λ ~ R ,  ~ Q
8.- ~ P → Q ) Λ ( Q → ~ P ), ~ ( ~ Q ν R ), P ν ~ S  ~ S

69
9.- P ν Q → R Λ S , ~ ( ~ P ν ~ R ), ~ T → ~ ( P Λ S )  T
10.- P → Q, R ν S, S → ~ Q , ~ R  ~ P
B) Demostrar por medio del sistema K, los siguientes teoremas

1.- ├(A → ~ B)→[(~B → ~ C) → (A → ~C)]

2.- ├( A → (A →( B Λ C) )→ B Λ C)
3.- ├( C ν B) →(~(C ν B) → E)
4.- ├(A →B) → [(A → C Λ D) → ( A → BΛ(C Λ D)]
5.- ├( A → ~B) → (B → ~A)
6.- ├( A → ~( B ν C)) → ( B ν C → ~A)
7.- ├ ( A → ~B) → ~ ( A Λ B)
8.- ├ ~( A Λ ~ B) → ( A → B)
9.- ├ ( A → ~B) → ( ~ A ν ~ B)
10.- ├ ( ~ A ν B) → ( A → B)
11.- ├ ~( A Λ ~ B) → ~A ν B
12.- ├ ~ A ν ~ B → ~(A Λ B)
13.- ├ ~(~A ν ~ B) → A Λ B
14.- ├ ~ A Λ ~ B → ~( A ν B)
15.- ├ A Λ ~( B Λ C) → ~(B Λ C) Λ A
16.- ├ ( A Λ ~ B) Λ C → A Λ ( ~B Λ C)
17.- ├ A → A Λ( A ν B)
18.- ├ A ν( B → C) → (B → C) ν A
19.- ├ ( ~A ν ~B) ν C → ~A ν ( ~B ν C)
20.- ├ ( A Λ B) ν ( A Λ C) → A Λ( B ν C)
21.- ├ (A ν ~B) Λ (A Λ ~ C) → A ν ( ~B Λ ~C)
22.- ├ ~ A → ~A ν ( ~ A Λ ~ B)
23.- ├ ( A ↔ B) → [(B → A) → ( A → B)]
24.- ├ ( A ↔ B) → ( A → B)
25.- ├ ( A ↔ B) → (B → A)
26.- ├ A ↔ A
27.- ├ ( A ↔ B) → [(B ↔ C) → (A ↔ C)]
28.- ├ ( A ↔ B) → ( B ↔ A)

C) Demostrar por medio del Sistema K las siguientes deducciones

a) P  Q  R  S, ( P   R), T   (P  S)  T
b) A  B, B   C,  C   D, D   E  A
c) P Q, P  R, Q S, R  (M  A) , (A  B) M,
A  A  A  S  T
d) P  R , R S , T  S , T  Q , Q  P
e) A  B , B C , C  A
f) A C, A B  C , A  D
g) P  Q, Q   R , S   ( P  R) , R  S
h) A B , C  D , C  A   ( D  B)
i) P   (Q  R) , T R ,  P  T

70
j) (S  T)  P  Q , P  S  R
k)  A  B, A  (C  D) ,  (B  E)  C
l) A  B , A  B  C  D , (C  D)  E,
(A  E)  F  F

SISTEMA L ( Luckasiewicz )

L ( A, F, X , R )

A : ALFABETO

1. Símbolos de proposiciones p, q , r, s , t ,,,,

2. Símbolos de conectivas ~ , →
3. Símbolos de agrupación ( ) , { } , [ ]

F : REGLAS DE SINTAXIS

1. Los símbolos de proposiciones son f.b.c

2. Si A , B son f.b.c ; ~ A , ~ B A → B , B → A son f.b.c
3. El conjunto de f.b.c se obtiene a partir de los puntos anteriores

X : AXIOMAS

A1: ├ A → ( B → A)
A 2 : ├ ( A → ( B → C )) → [ ( A → B ) → ( A → C ) ]
A3:├( ~A→ ~ B) → ( B → A )

R : REGLAS DE INFERENCIA

├ A , ├ A → B

├ B Modus Ponens

Interpretación de Axiomas

A1: ├ A → ( B → A)

T.D A  B → A

Dada una fórmula válida, cualquier otra es deducible si esta esa como consecuente
de una implicación

A 2 : ├ ( A → ( B → C )) → [ ( A → B ) → ( A → C ) ]

T.D A → ( B → C ), A → B , A  C

71
Si se tiene en una fórmula, los elementos de un M.P siempre es posible la
demostración de cualquier fórmula.

A3:├( ~A→ ~ B) → ( B → A )

T.D ~A→ ~ B, B  A

De una implicación verdadera y de la falsedad del consecuente se deduce la

falsedad del antecedente

TEOREMAS DEL SISTEMA L

T1: ├ A → A
T2: ├ ( A → B)→ [( B → C) → ( A → C)]
T3: ├A → ((A → B) → B)
T4: ├ ~ ~A → A
T5: ├ A → ~~A
T6: ├ ( B → ~A) → ( A → ~ B)
T7: ├( ~A → B) → ( ~ B → A)
T 8 : ├ A → ( B → ~ ( A → ~ B ))
T9: ├A → ( ~ A → B)
T 10 : ├ ~ ( A → ~ B ) → A
T 11 : ├ A → ~ ( A → ~ A )
T 12 : ├ ( A → ~ A ) → ~ A
T 13 : ├ ( ~ A → A ) → A
T 14 : ├ ( A → C ) → [ ( B → C ) → ( ( ~ A → B ) → C ) ]
T 15 : ├ ( A → B ) → [ ( A → ~ B ) → ~ A ]
T 16 : ├ ( A → B ) → [ ( ~ A → B ) → B ]
T 17 : ├ ( A → B ) → [ ( A → ( B → C )) → ( A → C ) ]

DEMOSTRACIÓN DE TEOREMAS

Teorema 1 : Identidad

├ A → A

En este caso es inaplicable el T.D debido a que si se aplica, el teorema quedaría

automáticamente demostrado.

1) ├(A → ( A → A) → A) → [(A →( A → A)) → ( A → A)] A2

2) ├ ( A → (( A → A ) → A ) A1
3) (A →( A → A)) → ( A → A) M.P ( 1 , 2 )
4) ├ A → ( A → A) A1
5) A → A M.P ( 3 , 4 )

En la demostración de este teorema, la estructura del axioma 2 nos permite dicha

demostración, definiendo todas las fórmulas como la fórmula A, y de tal manera
que la ultima fórmula en la estructura del axioma es la fórmula a demostrar

72
Teorema 2 : Teorema del Silogismo

├ ( A → B) →[(B → C) → (A → C)]

Aplicando el Teorema de la Deducción al teorema dado, tantas veces como

premisas se pueda obtener, obtenemos

A → B, B → C, A  C

Donde el símbolo  : tiene las siguientes acepciones

A) C se obtiene a partir de A → B , B → C , A
B) A → B , B → C , A induce a C

1) A → B P
2) B → C P
3) A P

De tal manera que al aplicar el T.D sobre el teorema dado, se ha obtenido un

conjunto de premisas, las cuales son fórmulas válidas, y que pueden ser usadas en
el proceso de demostración del teorema.

Al observar el conjunto de premisas, se observa que en la premisa 2, la ultima

fórmula de la misma es la fórmula “ C “, es decir la fórmula a demostrar, por lo
tanto no requerimos de un axioma o teorema principal, como medio de
demostración del teorema.
En este caso si se observa los pasos 1 , 2 se ve que tienen la estructura del silogismo,
pero esta propiedad no se la puede usar ya que no ha sido demostrada en forma
previa, y aun mas es el teorema sujeto a demostración.

Si se observa el paso 1 , 3 se ve que tiene la estructura de la regla de inferencia del

M.P, por lo tanto podemos aplicar esta regla.

4) B M.P ( 1 , 2 )

Del mismo modo en el paso ( 2 , 4 ) se tiene nuevamente los elementos de un M.P, el

cual al ser aplicado sobre estos pasos de demostración nos permiten demostrar el
teorema, ya que como consecuencia se obtiene la fórmula “ C “

5) C M.P ( 2 , 4 )

Teorema 3 : Teorema del Modus Ponens

├ A → [( A → B) → B]

Aplicando el teorema de la deducción

A , A → B  B

1) A P
2) A → B P
3) B M.P ( 2 , 1 )

73
Con lo que queda demostrado el teorema del M.P, ya que como se indico al aplicar
el T.D sobre una fórmula o teorema, basta demostrar el último elemento de la
sucesión de fórmulas, de modo que al obtener esta como fórmula válida, queda
demostrado el teorema consiguiente.

Teorema 4 : Eliminación Doble Negación

├ ~~A → A

T.D ~ ~ A  A

1) ~ ~ A P

El único axioma cuya estructura nos permite la demostración de este teorema es la

del axioma 3, ya que al ser este uno que contiene elementos de negación, se puede
ajustar el mismo de modo que la ultima fórmula sea la fórmula a demostrar.

2) ├ ( ~ A → ~~~A) → ( ~~A → A) A3
3) ├ (~~~~ A → ~~A) → ( ~A →~~~A) A3
4) ├~~A → ( ~~~~A → ~~A) A1
5) ~~~~A → ~~ A M.P ( 4 , 1 )
6) ~ A → ~~~A M.P ( 3 , 5 )
7) ~~A → A M.P ( 2 , 6 )
8) A M.P ( 7 , 1 )

Teorema 5 : Introducción Doble Negación

├ A → ~~ A

Al haber demostrado el teorema de eliminación de la doble negación, es posible

hacer uso de este en el proceso de demostración de este nuevo teorema.

1) ├ ( ~ ~ ~ A → ~ A ) → ( A → ~ ~ A ) A3
2) ├ ~ ~ ~ A → ~ A T4
3) A → ~ ~ A M.P ( 1 , 2 )

Teorema 6 : Contraposición 1

├ ( B → ~ A) → ( A → ~B)

T.D B → ~ A  A → ~B

1) B → ~ A P

Para demostrar el teorema, se hace uso del axioma 3, como axioma principal, de
manera que la ultima fórmula sea la fórmula a demostrar, a saber A → ~ B

2) ├ ( ~ ~ B → ~ A ) → ( A → ~ B ) A3

74
Para obtener el primer elemento de M.P a ser aplicado sobre el axioma principal
es necesario construir un teorema secundario, que incluya como ultima fórmula
ese elemento de M.P, la estructura de esta fórmula es tal, que solo el teorema del
silogismo nos permite la obtención de la misma.

3) ├ ( ~ ~ B → B ) → [ ( B → ~ A ) → ( ~ ~ B → ~ A ) ] T 2

Los dos elementos de M.P a obtenerse para ser aplicados sobre el teorema del
silogismo en forma consecutiva, a objeto de obtener la fórmula ~ ~ B → ~ ~ A, son
el teorema de eliminación de la doble legación, ya demostrado, y el uso de la
premisa del punto 1 del proceso de demostración del teorema.

4) ├ ~~B → B T4
5) ( B → ~A) → ( ~~B → ~A) M.P ( 3 , 4 )
6) ~~B → ~A M.P 8 5 , 1 )
7) A → ~B

Teorema 7 : Contraposición 2

├ ( ~A → B) → ( ~B → A)

T.D ~A → B  ~B → A

1) ~ A → B P

Al ser este teorema similar al anterior, el proceso de demostración sigue la misma

estructura utilizada en el caso anterior.

2) ├( ~ A → ~~B) → ( ~B→ A) A3
3) ├(~A → B) → [(B → ~~B) → ( ~A → ~~B)] T2
4) (B → ~~B) → ( ~A → ~~B) M.P ( 3 , 1 )
5) ├ B → ~~B T5
6) ~A → ~~B M.P ( 4 , 5 )
7) ~B → A M.P ( 2 , 6 )

Teorema 8 :

├ A →[B → ~(A → ~B)]

T.D A , B  ~(A → ~B)

1) A P
2) B P

El teorema que podemos aplicar en este caso para la demostración, como teorema
principal cuya estructura nos permite que el último elemento de la sucesión de
fórmulas del teorema sea la fórmula a demostrar es el teorema de contraposición.

3) ├ ( ( A → ~ B ) → ~ B ) → ( B → ~ ( A → ~ B ) ) T.C.P

75
Debemos obtener la fórmula ( A → ~ B ) → ~ B , como elemento de M.P, si
observamos esta en conjunción con la premisa 1, podemos ver que se puede
construir el teorema del M.P y obtener la fórmula necesaria como elemento de M.P
a ser aplicada sobre el paso 3.

4) ├ A → [( A → ~B) → ~B] T.M.P

5) ( A → ~B) → ~B M.P ( 4 , 1 )
6) ( B → ~(A → ~B)) M.P( 3 , 5 )
7) ~(A → ~B) M.P ( 6 , 2 )

Teorema 9 : Ex Contradictione Quolibet ( E.C.Q )

├ A → ( ~A → C)

T.D A  ~ A → C

1) A P

En el proceso de demostración de este teorema podemos hacer uso del teorema de

contraposición como teorema principal, y para obtener elementos de M.P a ser
aplicados sobre este podemos hacer uso como axioma secundario el axioma 1.

2) ├ ( ~C → A) → ( ~A → C) T.C.P
3) ├A → ( ~C → A) A1
4) ~C → A M.P ( 3 , 1 )
5) ~A → C M.P ( 2 , 4 )

Teorema 10 :

├ ~(A → ~B) → A

T.D ~ ( A → ~ B )  A

1) ~ ( A → ~ B ) P

Al ser el teorema a demostrar uno que contiene elementos de negación, podemos

hacer uso del teorema de contraposición como teorema principal.

2) ├ ( ~ A → ( A → ~ B ) → ( ~ ( A → ~ B ) → A ) T.C.P

Se debe obtener la fórmula ( ~ A → ( A → ~ B ), como elemento de M.P para ser

aplicada sobre el paso2, el tipo de estructura de esta fórmula nos indica que el
teorema a hacer uso como secundario debe ser el teorema del silogismo.

3)├ ( ~ A → ( B → ~ A ) ) → [ (( B → ~ A ) → ( A → ~ B ) ) → (( ~ A → ( A → ~ B )] T 2

El primer elemento de M.P a obtener para ser aplicado sobre el el teorema del
silogismo tiene estructura de axioma 1.

4) ├ ~ A → ( B → ~ A ) A1

76
5) (( B → ~ A ) → ( A → ~ B ) ) → (( ~ A → ( A → ~ B )M.P ( 3 , 4 )

El segundo elemento de M.P a ser obtenido se ve que tiene estructura del teorema
de contraposición.

6) ├ (B → ~A) → (A → ~B) T.C.P

7) ~A → (A → ~B) M.P ( 5 , 6 )
8) ~(A → ~B) → A M.P ( 2 , 7 )
9) A M.P ( 8 , 1 )

Teorema 11 :

├ A → ~(A → ~A)

T.D A  ~ ( A → ~ A )

1) A P

En función de la fórmula a demostrar el teorema que se debe utilzar como

principal en el proceso de demostración de este teorema debido a su estructura es
el teorema 8 ya demostrado.

2) ├ A → [ A → ~ ( A → ~ A ) ] T8
3) A → ~ ( A → ~ A ) M.P (2 , 1 )
4) ~ ( A → ~ A ) M.P ( 3 , 1 )

Teorema 12 :

├(A → ~ A) → ~ A

T.D ( A → ~ A )  ~ A

1) A → ~ A P

En este caso el teorema principal a ser usado es el teorema de contraposición y

para obtener el primer elemento de M.P de este se hace uso del teorema 11 ya
demostrado.

2) ├ ( A → ~( A → ~A) → [( A → ~ A) → ~A] T.C.P

3) ├ A → ~(A → ~A) T 11
4) ( A → ~ A) → ~A M.P ( 2 , 3 )
5) ~A M.P ( 4 , 1 )

Teorema 13 : Teorema del Dilema

├ ( A → C ) → [ ( B → C ) → (( ~ A → B ) → C ) ]

T.D A → C ,B → C ,~A → B  C

1) A → C P

77
2) B → C P
3) ~ A → B P

La demostración del teorema, es decir la obtención de la fórmula C como fórmula

válida, tal que automáticamente se demuestra todo el teorema, presenta una
estructura, la cual nos permite hacer uso del teorema 12 en el proceso de
demostración, usando este teorema como principal.

4) ├ (~C → C) → C T 12

No es posible la obtención directa de una fórmula ~ C → C, por lo tanto

recurrimos al silogismo para poder construir la misma.

5) ├ ( ~ C → A ) → [ ( A → C ) → ( ~ C → C ) ] T2

Para poder obtener el primer elemento de M.P de este teorema secundario es

necesario recurrir nuevamente al silogismo y efectuar una contraposición.

6) ├ ( ~ A → B ) → [(B →C) → ( ~A → C)] T2

7) ( B → C ) → ( ~A → C) M.P ( 6 , 3 )
8) ~A → C M.P ( 7 , 2 )
9) ├ ( ~ A → C ) → ( ~C →A) T.C.P
10) ~ C → A M.P ( 9 , 8 )
11) ( A → C ) → ( ~C → C) M.P ( 5 , 10 )
12) ~ C → C M.P ( 11 , 1 )
13) C M.P ( 4 , 12 )

Teorema 14 : Reducción al Absurdo

├ ( A → B) → [(A → ~B) → ~ A]

T.D A → B , A → ~ B  ~ A

1) A → B P
2) A → ~ B P

La fórmula a demostrar y el conjunto de premisas con los que se cuenta para

poder demostrar este teorema nos permiten hacer uso del teorema 12, como
teorema principal.

3)├ ( A → ~ A ) → ~ A T 12

El elemento de M.P que se debe construir para ser aplicado en el paso 3 , nos
sugiere el uso del teorema del silogismo, ya que es imposible obtener en forma
directa la fórmula A → ~ A

4) ├(A → B) → [(B → ~A) → ( A → ~ A)] T2

5) (B → ~A) → ( A → ~ A) M.P ( 4 , 1 )
6) ├ ( A → ~B) → (B → ~ A) T.C.P
7) B → ~ A M.P ( 6 , 2 )

78
8) A → ~ A M.P ( 5 , 7 )
9) ~ A M.P ( 3 , 8 )

Teorema 15 :

├ ( A → B) → [( ~ A → B) → B]

T.D A → B , ~ A → B  B

1) A → B P
2) ~ A → B P

Al ser este teorema similar al anterior el proceso de demostración por lo tanto

sigue los mismos pasos del anterior.

3) ├ ( ~ B → B) → B T 12
4) ├( ~B → ~A) → [( ~A→ B) → ( ~ B → B)] T2
5) ├( A → B) → ( ~ B → ~ A) T.C.P
6) ~ B → ~ A M.P ( 5 , 1 )
7) ( ~A→ B) → ( ~ B → B) M.P ( 4 , 6 )
8) ~ B → B M.P ( 7 , 2 )
9) B M.P ( 3 , 8 )

Teorema 16 : Autodistribución del Implicador

├ ( A → B) → [( A → ( B → C)) → ( A → C)]

T.D A → B , A → ( B → C ) , A  C

1) A → B P
2) A → ( B → C) P
3) A P
4) B M.P ( 1 , 3 )
5) B → C M. P ( 2 , 3 )
6) C M.P ( 5 , 4 )

Ejercicios Propuestos

Dados los siguientes teoremas, demostrar los mismos mediante el uso del sistema L

T1: ├ ~A →~A
T2: ├ ( A → ~B)→ [(~ B → C) → ( A → C)]
T3: ├ ~A → ((~A → ~B) →~B)
T4: ├ ~ ~A → A
T5: ├ A → ~~A
T6: ├ ( B → ~(A Λ C) → ( A Λ C→ ~ B)
T7: ├( ~A → B Λ C) → ( ~(B Λ C)→ A)
T 8 : ├ ~ A → ( B → ~ ( ~ A → ~ B ))
T9: ├ A → ( ~ A → B)
T 10 : ├ ~ ( ~ A → ~ B ) → ~ A

79
T 11 : ├ ~ A → ~ ( ~ A → ~ A )
T 12 : ├ ( A → ~ A ) → ~ A
T 13 : ├ ( ~ A → A ) → A
T 14 : ├ ( A → ~ C ) → [ ( B → ~ C ) → ( ( ~ A → B ) → ~ C ) ]
T 15 : ├ ( A → B ) → [ ( A → ~ B ) → ~ A ]
T 16 : ├ ( A → B ) → [ ( ~ A → B ) → B ]
T 17 : ├ ( A → ~ B ) → [ ( A → ( ~ B → C )) → ( A → C ) ]

80
 CAPITULO V

DEDUCCION NATURAL

El sistema de demostración de fórmulas y deducciones por deducción natural en

Cálculo de proposiciones, parte de un conjunto de premisas de cuyo valor de
verdad no es posible pronunciarse a priori, si ejecutando el sistema se llega a una
conclusión, esta será válida si y solo si el conjunto de premisas de las que se partió
son válidas.

El proceso de demostración esta basado en el concepto intuitivo de la lógica, y se

asemeja al lenguaje común.

Demostración de Deducciones.- Una deducción podemos representarla como un

conjunto finito de fórmulas Fi, donde cada una de ellas es
1. Una premisa
2. Una fórmula obtenida a partir de las anteriores por una regla de inferencia
3. Donde el último elemento de la sucesión de fórmulas Fi es la conclusión a
demostrar

El sistema de demostración tiene dos rutas o métodos, a saber:

1. Método Directo
2. Método Indirecto

Reglas Basicas del Cálculo por Deduccion Natural

El sistema de demostración por D.N esta basado en un conjunto de reglas de

inferencia o de paso, a aplicarse sobre las fórmulas, este conjunto esta formado por
8 reglas de inferencia, dos para cada conectiva; una de introducción y otra de
eliminación.

Si la regla esta separada tan solo por una raya horizontal, significa que el
consecuente se infiere del antecedente, si la raya horizontal es doble significa que la
regla es válida tanto para el sentido directo, como para el reciproco.

Reglas Básicas

A
B R.I Λ
A Λ B

A Λ B ; A Λ B R.E Λ
A B

A ; B R.I ν
A ν B A ν B

A  C,B  C R.E ν
A ν B  C

81
 A  B,A  ~B R.I ~
~A

~~ A R.E ~
A

A  B R.I →
 A → B

A → B R.E →
A
B

A) Reglas de Conjunción

1) Regla de Introducción ( R.I. Λ )

A
B .
A Λ B
Dada una deducción, si los antecedentes de esta son válidas, entonces la conjunción
entre estas fórmulas es válida.

2) Regla de Eliminación ( R.E.Λ)

A Λ B ; A Λ B
A B
Si una demostración es válida para la conjunción entre dos fórmulas, también es
válida para cada una de las fórmulas componentes de la conjunción.

B) Reglas de Disyunción

1) Regla de Introducción ( R.I.ν )

A ; B .
A ν B A ν B

Si a una fórmula válida se le adiciona otra en disyunción, ya sea esta falsa o

verdadera, la disyunción entre estas fórmulas es válida.

2) Regla de Eliminación ( R.E.ν )

A  C,B  C
A ν B  C

A ν B

A P.A

82
 C

B P.A

C R.E.ν

Si se parte de dos fórmulas relacionadas entre si por el conectivo de la disyunción,

se supone que dicha fórmula es válida, y se toma cada una de las fórmulas
componentes de la disyunción como premisas auxiliares, a partir de estas se inicia
secuencias deductivas auxiliares, si para ambas secuencias deductivas subsidiarias
se llega a la misma fórmula, se introduce la fórmula en la secuencia deductiva
principal por la regla de eliminación de la disyunción.

C) Reglas de Negación

1) Regla de Introducción ( R.I.~ )

A  B,A  ~B
~A

~~A P.A
A R.E ~

B Λ ~ B
~~~A R.I ~
~A R.E ~

La aplicación de la regla de introducción de la negación, es la del absurdo, a partir

de antecedentes iguales, se llega a consecuentes contradictorios, entonces la
fórmula válida es la negación del antecedente.

El sistema supone por el método indirecto de demostración que la fórmula

correcta, no es la negación de la fórmula A, sino la negación de esta, entonces la
premisa auxiliar viene ase ~ ~ A, si a partir de esta premisa auxiliar en una
secuencia deductiva auxiliar se llega a demostrar una contradicción, entonces
nuestra supuesto era incorrecto, y la fórmula correcta por lo tanto debe ser la
negación de nuestro supuesto.

83
 2) Regla de Eliminación ( R.E ~ )

~~ A
A

Esta regla de inferencia, es tan solo la conocida eliminación de la doble negación, la

que indica que negar dos veces es lo mismo que afirmar.

D) Reglas de Implicación

1) Regla de Introducción ( R.I → )

A  B
 A → B

A → B

Se toma como fórmula válida el antecedente de una fórmula, a partir de esta se

inicia una secuencia deductiva auxiliar, si en eses proceso deductivo subsidiario se
llega a l consecuente de la fórmula se introduce la fórmula A → B en al secuencia
deductiva principal.

2) Regla de Eliminación ( R.E → )

A → B
A
B

Esta regla de inferencia de eliminación de la implicación es la conocida regla de

inferencia del Modus Ponens, cuyo uso ya ha sido explicado con anterioridad.

Con el conjunto de reglas explicadas, que comprenden el sistema de demostración

de Cálculo de proposiciones por Deducción Natural, seria suficiente para
demostrar cualquier tipo de fórmula o deducción, pero a objeto de simplificar el
proceso deductivo se va a demostrar un conjunto de reglas derivadas.

Del análisis de las secuencias deductivas con las que trabaja el sistema se deben
hacer las siguientes observaciones:
1) Toda secuencia deductiva auxiliar es independiente de otra, es decir
todas las fórmulas de una secuencia o todo el proceso deductivo que
comprende una secuencia es tan solo de esta, si se requiere en otra
secuencia una fórmula igual o similar, se debe crearla en esa
secuencia y no hacer referencia ala otra secuencia.

84
 2) La demostración por el método indirecto entraña siempre la
consecución de una contradicción, si no se llega a esta no es posible
aplicar el método indirecto, una contradicción es siempre la
conjunción entre dos fórmulas, una afirmada y la otra negada.
3) En caso de realizar varios loops entre las secuencias auxiliares se
debe tomar en cuenta que bajo ninguna circunstancia dos loops se
intersectan o cortan.
4) Los antecedentes de una regla son siempre premisas, y se las debe
usar en el proceso de demostración.

REGLAS DERIVADAS POR DEDUCCION NATURAL

Conjunto de Reglas Derivadas

A → B Silogismo
B → C

A → C

A → ( B → C) Mutación de Premisas
B → (A → C)

A Identidad
A

A Introducción de Antecedente

A → B

A Λ B Conmutativa Conjunción

B Λ A

(A Λ B) Λ C Asociativa Conjunción

A Λ ( B Λ C)

A Λ ( B ν C) Distributiva Λ ν

(A Λ B) ν (A Λ C)

A Λ A Idempotencia
A

A Λ ( A ν B) Absorción

A ν B Conmutativa Disyunción

85
B ν A

(A ν B) ν C Asociativa ν

A ν ( B ν C)

A ν (B ΛC) Distributiva ν Λ

(A ν B) Λ (A ν C)

A ν A Idempotencia ν
A

A ν ( A Λ B) Absorción ν
A

A → B Modus Tollens
~ B
~ A

A → B Contraposición
~B → ~A

A Introducción ~ ~

~~A

A Λ ~A ECQ

A ν B Tollendo Ponens
~ B
A

A → ( B → C) Importación

A Λ B → C

A Λ B → C Exportación

A → ( B → C)

~ A ν B Interdefinción ν →

A → B

~( A Λ ~ B) Interdefinición Λ →

A → B

86
 ~( A Λ B) De Morgan Λ ν

~ A ν ~ B

~ ( A ν B) De Morgan ν Λ

~ A Λ ~ B

A ν B DDS
A → C
B → C

A ν B DDC
A → C
B → D
C ν D

A) REGLAS DERIVADAS DE IMPLICACIÓN

1.- Silogismo

A → B
B → C

A → C

1) A → B P
2) B → C P
3) A P.A
4) B M.P ( 1 , 3 )
5) C M.P ( 2 , 4 )

6) A → C R.I → ( 3 – 5 )

En este caso al observar el tipo de fórmula a desmotar se ve que es una

implicación, por lo tanto en el proceso de demostración se debe hacer uso de la
regla de introducción de la implicación, por lo que se toma el antecedente de la
conclusión como premisa auxiliar y a partir de esta en una secuencia deductiva
subsidiaria se llega al consecuente de la conclusión, por lo tanto se introduce en la
secuencia general de demostración la fórmula, en este caso la conclusión de la regla
derivada.

2.- Mutación de Premisas

A → ( B → C)
B → (A → C)

87
 1) A → ( B → C ) P

2) B P.A

3) A P.A
4) B → C M.P ( 1 , 3 )
5) C M.P ( 4 , 2 )

6) A → C R.I → ( 3 – 5 )

7) B → ( A → C ) R.I → ( 2 – 6 )

Como en el caso anterior la conclusión es una implicación, aunque con la variante

que es una doble implicación, por lo tanto en este caso tomamos los antecedentes
de ambas implicaciones como premisas auxiliares, y a partir de estas iniciamos
secuencias deductivas auxiliares, de modo de alcanzar el consecuente de ambas
implicaciones, e introducir la fórmula en la secuencia general de demostración.

3.- Identidad

A
A

1) A P

2) ~ A P.A
3) A Λ ~ A R.I Λ ( 1 , 2 )
4) ~ ~ A R.I ~ ( 2 )

5) A R.E ~ ( 4 )

Este es un ejemplo de aplicación del método indirecto, o del Absurdo con la

introducción de la regla de introducción de la negación. El sistema de
demostración parte del entendido que la conclusión a la que se desea arribar o
demostrar no es la correcta, sino que la correcta es la negación de esta fórmula, se
inicia una secuencia deductiva auxiliar con esta fórmula supuesta, y se llega a la
contradicción, por lo tanto la fórmula correcta debe ser la negación de nuestro
supuesto, a partir de esta se llega demostrar la fórmula, en este caso la conclusión
de a regla derivada.

88
4.- Introducción de Antecedente

A → B

1) A P

2) B P.A
3) A Identidad ( 1 )

4) B → A R.I → ( 2 – 3 )

B) REGLAS DERIVADAS DE CONJUNCION

1.- Conmutativa

A Λ B

B Λ A

1) A Λ B P
2) A R.E Λ ( 1 )
3) B R.E Λ ( 2 )
4) B Λ A R.I Λ ( 3 , 2 )

En este caso la demostración se la realiza por el método directo partiendo de las

reglas de conjunción, tanto de eliminación, como de introducción.

2.- Asociativa

(A Λ B) Λ C

A Λ ( B Λ C)

1) (A Λ B) Λ C P
2) A Λ B R.E Λ ( 1 )
3) A R.E Λ ( 2 )
4) B R.E Λ ( 2 )
5) C R.E Λ ( 1 )
6) B Λ C R.I Λ ( 4 , 5 )
7) A Λ ( B ΛC) R.I Λ ( 3 , 6 )

3.- Distributiva de la Conjunción respecto de la Disyunción

A Λ ( B ν C)

(A Λ B) ν (A Λ C)

89
 1) A Λ ( B ν C ) P
2) A R.E Λ ( 1 )
3) B ν C R.E Λ ( 1 )

4) B P.A
5) A Λ B R.I Λ ( 2 , 4 )
6) ( A Λ B ) ν ( A Λ C ) R.I ν ( 5 )

7) C P.A
8) A Λ C R.I Λ ( 2 , 7 )
9) ( A Λ B ) ν ( A Λ C ) R.I ν ( 8 )

10) ( A Λ B ) ν ( A Λ C ) R.E ν( 3, 4 - 6,7 - 9 )

Esta es una aplicación de la regla de eliminación de la disyunción, al planear la

solución en el proceso de demostración, se obtiene una fórmula en disyunción, que
determina implícitamente el trabajo de demostración mediante secuencias
deductivas auxiliares, una para cada componente de la disyunción, a partir de esta
fórmulas se debe llegar para ambas a la conclusión de la regla derivada, una vez
que se llega a esta se introduce la fórmula en la secuencia deductiva general
mediante la aplicación de la regla de eliminación de la disyunción.

4.- Idempotencia

A Λ A
A

1) A Λ A P
2) A R.E Λ ( 1 )

5.- Absorción

A Λ ( A ν B)

1) A Λ ( A ν B ) P
2) A R.E Λ ( 1 )

C) REGLAS DERIVADAS DE DISYUNCION

1.- Conmutativa

A ν B

B ν A

1) A ν B P

90
 2) A P.A

3) B ν A R.I ν ( 2 )

4) B P.A
5) B ν A R.I ν ( 4 )

6) B ν A R.E ν(1, 2 – 3 , 4 – 5)

2.- Asociativa

(A ν B) ν C

A ν ( B ν C)

1) ( A ν B ) ν C P

2) A ν B P.A

3) A P.A
4) A ν ( B ν C ) R.I ν ( 3 )

5) B P.A
6) B ν C R.I ν ( 5 )
7) A ν ( B ν C ) R.I ν ( 6 )

8) A ν ( B ν C ) R.E ν(2, 3– 4 ,5 – 7 )

9) C P.A
10) B ν C R.I ν ( 9 )
11) A ν ( B ν C ) R.I ν ( 10 )

12) A ν ( B ν C ) R.E ν(1,2– 8,9 – 11 )

La demostración de fórmulas que conllevan en relación de estas el conectivo de la

disyunción, necesariamente pasan por el proceso de uso de la regla de eliminación
de la disyunción, en la que como se explico, se supone como válida la disyunción
entre fórmulas, a partir de las fórmulas componentes de la disyunción tomadas
estas como premisas auxiliares, se inicia secuencias deductivas subsidiarias, las
cuales deben conducirnos a una misma conclusión, la cual se introduce por la regla
de eliminación de la disyunción.

3.- Distributiva de la Disyunción respecto a la Conjunción

A ν (B ΛC)

(A ν B) Λ (A ν C)

1) A ν ( B Λ C ) P

91
 2) A P.A

3) A ν B R.I ν ( 2 )
4) A ν C R.I ν ( 2 )
5) ( A ν B ) Λ ( A ν C ) R.I Λ ( 3 , 4 )

6) B Λ C P.A
7) B R.E Λ ( 6 )
8) A ν B R.I ν ( 7 )
9) C R.E Λ ( 6 )
10) A ν C R.I ν ( 9 )
11) ( A ν B ) Λ ( A ν C ) R.I Λ ( 8 , 10 )

12) ( A ν B ) Λ ( A ν C ) R.E ν (1,2– 5,6 -11 )

En este caso la demostración, además de hacer uso de la regla de eliminación de la

disyunción, en el sentido que ya se explico, hace uso de la regla de introducción de
la conjunción, de manera que se pueda formar la estructura de la conclusión.

4.- Idempotencia

A ν A
A

1) A ν A P

2) A P.A
3) A Identidad ( 1 )

4) A P.A
5) A Id. ( 4 )

6) A R.E ν(1,2– 3, 4 – 5)

5.- Absorción

A ν ( A Λ B)
A

1) A ν ( A Λ B ) P

2) A P.A
3) A Id ( 2 )

92
 4) A Λ B P.A
5) A R.E Λ ( 4 )

6) A R.E ν (1,2– 3 , 4 – 5 )

D) REGLAS DERIVADAS DE NEGACION

1.- Modus Tollens

A → B
~ B
~ A

1) A → B P
2) ~ B P

3) ~~A P.A
4) A R.E ~ ( 3 )
5) B M.P ( 1 , 4 )
6) B Λ ~B R.I Λ ( 5 , 2 )

7) ~ ~ ~ A R.I ~ ( 3 )
8) ~ A R.E ~ ( 7 )

Este es un clásico ejemplo del método indirecto, el cual parte de la negación de la

conclusión, considerando que esta fórmula negada es la correcta, mediante una
secuencia deductiva auxiliar que se plantea, se llega a una contradicción, lo que
significa que nuestra premisa auxiliar plantead era falsa, por lo tanto la fórmula
correcta debe ser la negación de nuestro supuesto.

2.- Contraposición

A → B
~B → ~A

1) A → B P

2) ~ B P.A

3) ~~A P.A
4) A R.E ~ ( 3 )
5) B M.P ( 1 , 5 )
6) B Λ ~ B R.I Λ ( 6 , 2 )

7) ~ ~ ~ A R.I ~ ( 3 )
8) ~ A R.E ~ ( 8 )

9) ~ B → ~ A R.I → ( 2 – 8 )

93
En este caso la demostración de la conclusión, no solo pasa por la utilización del
método indirecto, sino que también se aplica la regla de introducción de la
implicación.

3.- Introducción de la Doble Negación

A

~~A

1) A P

2) ~ ~ ~ A P.A
3) ~ A R.E ~ ( 2 )
4) A Λ ~ A R.I Λ ( 1 , 3 )

5) ~ ~ ~ ~ A R.I ~ ( 2 )
6) ~ ~ A R.E ~ ( 5 )

4.- Ex – Contradictione Quolibet ( E.CQ )

A Λ ~A

1) A Λ ~ A P

2) ~B P.A
3) A R.E Λ ( 1 )
4) ~A R.E Λ ( 1 )
5) A Λ ~ A R.I Λ ( 3 , 4 )

6) ~ ~ B R.I ~ ( 2 )
7) B R.E ~ ( 6 )

5.- Tollendo Ponens

A ν B
~ B
A

1) A ν B P
2) ~ B P

3) A P.A
4) A Id ( 3 )

5) B P.A
6) B Λ ~ B R.I Λ ( 5 , 2 )
7) A E.C.Q ( 6 )

94
 8) A R.E ν (1,3– 4, 5 – 7 )

La demostración de esta regla derivada implica la aplicación del E.C.Q, esta regla
nos permite obtener a partir de la contradicción entre dos fórmulas, cualquier otra
fórmula, la cual es válida.

E) REGLAS DE INTERDEFINICON DE CONECTIVAS

1.- Importación

A → ( B → C)

A Λ B → C

1) A → ( B → C ) P

2) A Λ B P.A
3) A R.E → ( 2 )
4) B → C M.P ( 1 , 3 )
5) B R.E Λ ( 2 )
6) C M.P ( 4 , 5 )

7) A Λ B → C R.I → ( 2 – 6 )

La demostración de esta regla, observando la conclusión de la regla, pasa por el

uso de la regla de introducción de la implicación.

2.- Exportación

A Λ B → C

A → ( B → C)

1) A Λ B → C P

2) A P.A

3) B P.A
4) A Λ B R.I Λ ( 2 , 3 )
5) C M.P ( 1 , 4 )

6) B → C R.I → ( 3 – 5 )

7) A → ( B → C ) R.I → ( 2 – 6 )

La conclusión a demostrar es una doble implicación, por lo tanto se asume como

premisas auxiliares los antecedentes de ambas implicaciones, y a partir de estas se
llega a los consecuentes respectivos. Se observa del mismo modo la recomendación
de que en caso de existir varios loops, ninguno de estos debe intersectarse.

95
3.- Disyunción - Implicación

~ A ν B

A → B

1) ~ A ν B P
2) A P.A
3) B T.P ( 1 , 2 )
4) A → B R.I → ( 2 – 3 )

La demostración de esta regla derivada de negación, pasa por el uso de la

aplicación directa de la regla del Tollendo Ponens, y de la regla de introducción de
la implicación, al ser la conclusión una implicación, siempre se puede aplicar esta
regla en el proceso de demostración de una fórmula o conclusión.

4.- Conjunción – Implicación

~( A Λ ~ B)

A → B

1) ~ ( A Λ ~ B ) P

2) A P.A

3) ~ B P.A
4) A Λ ~ B R.I Λ ( 2 , 3 )
5) ( A Λ ~ B ) Λ ~ ( A Λ ~ B ) R.I Λ ( 4 , 1 )

6) ~ ~ B R.I ~ ( 3 )
7) B R.E ~ ( 6 )

8) A → B R.I → ( 2 – 7)

Esta demostración conlleva el uso de la regla de introducción de la implicación, al

tratarse de una conclusión que es una implicación, y por otro lado asume que el
consecuente de la conclusión no es la fórmula correcta y demuestra la misma por el
método indirecto.

96
 F) LEYES DE DE MORGAN

1.- Conjunción - Disyunción

~( A Λ B)

~ A ν ~ B

1) ~ ( A Λ B ) P

2) ~(~A ν ~ B) P.A
3) ~(A → ~B) Inter Definición ( 2 )
4) ~~( A Λ B) Inter Definición ( 3 )
5) A Λ B R.E ~ ( 4 )
6) (A Λ B) Λ ~(A Λ B) R.I Λ ( 5 , 1 )

7) ~ ~ ( ~ A ν ~ B ) R.I ~ ( 2 )
8) ~ A ν ~ B R.E ~ ( 7 )

2.- Disyunción – Conjunción

~ ( A ν B)

~ A Λ ~ B

1) ~ ( A ν B ) P

2) ~( ~ A Λ ~ B) P.A
3) ~~A ν ~~B De Morgan ( 2 )
4) A ν B R.E ~ ( 3 )
5) (A ν B) Λ ~( A ν B) R.I Λ ( 4 , 1 )

6) ~ ~ ( ~ A Λ ~ B ) R.I ~ ( 2 )
7) ~ A Λ ~ B R.E ~ ( 6 )

G) DILEMAS

1.- Dilema Disyuntivo Simple

A ν B
A → C
B → C

97
 1) A ν B P
2) A → C P
3) B → C P

4) A P.A
5) C M.P ( 2 , 4 )

6) B P.A
7) C M.P ( 3 , 6 )

8) C R.E ν (1,4 – 5,6 – 7 )

2.- Dilema Disyuntivo Complejo

A ν B
A → C
B → D
C ν D

1) A ν B P
2) A → C P
3) B → D P

4) A P.A
5) C M.P ( 2 , 4 )
6) C ν D R.I ν ( 5 )

7) B P.A
8) D M.P ( 3 , 7 )
9) C ν D R.I ν ( 8 )

10) C ν D R.E ν(1,4 – 6,7 – 9 )

Ejemplos :

1.-

1) A → ( B → C ) P
2) C Λ D → E P
3) ( D → E ) → F
 A → ( B → F)

98
 4) A P.A

5) B P.A
6) B → C M.P ( 1 , 4 )
7) C M.P ( 6 , 5 )
8) ~ ( C Λ D ) ν E Intredeficion ( 2 )
9) ~ C ν ~ D ν E De Morgan ( 8 )
10) ~ D ν E T.P ( 7 , 9 )
11) D → E Interdefinicion ( 10 )
12) F M.P ( 3 , 11 )

13) B → F R.I → ( 5 – 13 )

14) A → ( B → F ) R.I → ( 4 – 13 )

2.-

1) A → B P
2) ~ C → A P
3) D → C P
4) B Λ C → E P
5) ~ D ν B P
A ν D → E

6) A ν D P.A

7) A P.A
8) B M.P ( 1 , 7 )
9) C M.T ( 2 , 7 )
10) B Λ C R.I Λ ( 8 , 9 )
11) E M.P ( 4 , 10 )

12) D P.A
13) B T.P ( 5 , 11 )
14) C M.P ( 3 , 12 )
15) B Λ C R.I Λ ( 13 , 14 )
16) E M.P ( 4 , 15 )

17) E R.E ν(6 ,7-11, 12-16)

18) A ν D → E R.I → ( 6-17)

Ejercicios Propuestos

Dadas las siguientes reglas derivadas, demostrar las mismas aplicando el método
de Deducción Natural.

99
1.- Reglas Derivadas

a)  A   A
b)  A  ( ( B  C )   D )  ( B  C )  ( A   D )
c) A  (B  C )  (B  C)  A
d) (A  B )  C  (A  C )  B
e) A  (B  C )  ( A B )  ( A  C )
f) ( A   B )  [ (  B  (C  D ) )  ( A  ( C  D) ) ]
g) (A  C)  [ ((A  C)  (D  E ))  ( D E)
h)  A ( B  C )   ( B  C )  A
i) ( A  B)   ( A   B )  C  ( D   E)
j)  (A B)  C ,  C   (A  B)
k)  A  ((B C)  D)  A ( B C)   D
Demostrar haciendo uso del Método de Deducción Natural, las siguientes
deducciones

2.- Deducciones por D.N

a) P  Q  R  S, ( P   R), T   (P  S)  T
b) A  B, B   C,  C   D, D   E  A
c) P Q, P  R, Q S, R  (M  A) , (A  B) M,
A  A  A  S  T
d) P  R , R S , T  S , T  Q , Q  P
e) A  B , B C , C  A
f) A C, A B  C , A  D
g) P  Q, Q   R , S   ( P  R) , R  S
h) A B , C  D , C  A   ( D  B)
i) P   (Q  R) , T R ,  P  T
j) (S  T)  P  Q , P  S  R
k)  A  B, A  (C  D) ,  (B  E)  C
l) A  B , A  B  C  D , (C  D)  E,
(A  E)  F  F

Demostrar por Deducción Natural si los siguientes razonamientos, reglas o

argumentos, son validos o no.

3.- Reglas y Deducciones

100
a) A, A     B
B
b) A  B, A   B   A
c) A   B,  B   C  A   C
d) A   B ,A  C,  B   D  C   D
e) A  A  B
f) A  B,  B  A
g) A  ( B  C)  A  B  C
h)  A B  A  B
i)  ( A   B)  A  B
J) A  A
4.- Formalizar y Demostrar por Deducción Natural

a) - Si Cristina esta en lo cierto, Marco esta equivocado

- Si Marco esta equivocado, Pablo también esta equivocado
- Si Pablo esta equivocado, el espectáculo no es esta noche
- O el espectáculo es esta noche o Pablo no lo vera
- Cristina esta en lo cierto

Por lo tanto. Javier ve el espectáculo

b) - O x es menor que z o bien x es igual a z

- Si x es igual a z , necesariamente z no es igual a cinco
- Si x no es igual a cuatro, no ocurre que x sea menor que z y z sea igual a
cinco
- z es igual a cinco

luego. x es igual a cuatro

c) - Si Maria no esta furiosa, no ha descubierto que el jarrón esta roto

- Maria ha descubierto que el jarrón esta roto

Por lo tanto, Maria esta furiosa

d) - Si consigo trabajo iré de vacaciones

- Si voy de vacaciones no podré trabajar
- Dejo de trabajar

Luego, no tendré vacaciones

e) - Gonzáles enuncia : Gómez es culpable y Gutiérrez es inocente

- Gómez enuncia : Gonzáles es culpable solo si Gutiérrez es también
culpable
- Gutiérrez enuncia : yo soy inocente, pero al menos uno de los otros dos es
culpable

101
 Por lo tanto:
a) Si todos son inocentes quien de los tres mintió
b) Si todos dicen la verdad quien es el culpable

f) - Si voy a mi primera lección por la mañana tendré que madrugar y si voy

al cine esta noche me acostare tarde
- Si me acuesto tarde y madrugo, tendré que dormir solo cinco horas
- No puedo dormir solo cinco horas

Por consiguiente. o voy a mi primera lección por la mañana o no voy al cine

esta noche

g) - Si voy al brasil en junio a un curso intensivo, no podré asistir al certamen

de golf y divertirme
- Voy al brasil en junio y no me divirtió

Por lo tanto no me divierto

h) - Juan o Pedro o Lucas aman a Maria

- Si pedro ama a Maria entonces el esta divorciado y si Lucas ama a Maria
hay una tercera mujer entre ellos
- Nadie esta divorciado y Juan no ama a Maria

Luego. Lucas ama a Maria

i) -Si Maria es culpable o Juana es inocente entonces pedro o Juan son

culpables
- Si Juana o Roxana son culpables entonces o pedro es culpable o María es
inocente
- Si Maria es inocente entonces pedro y Roxana son
culpables
- Es falso que si: María y Juan son culpables entonces
Pedro es inocente y Roxana es culpable

Luego:
a) Quienes son inocentes
b) Quienes son culpables

j) - El boliviano o el español o el argentino vendió los documentos de los

archivos x
- Si el español vendió los documentos, entonces el nació en Francia, y si el
argentino vendió los documentos había una mujer de por medio
- Nadie nació en Francia y el boliviano no vendió los documentos

Por lo tanto. el argentino vendió los documentos de los archivos x

k) - Un liquido es un acido si y solo si colorea de azul el papel de tornasol rojo

- Un liquido colorea de azul el papel de tornasol rojo si y solo si tiene iones
hidronio libres en solución

102
 Por lo tanto. un liquido es un acido si y solo si tiene iones hidronio libres

l) - Si soy honrado, soy tonto

- Yo soy honrado o tonto, o Pedro tenía razón y ese vendedor es un ladrón
- Yo no soy tonto y ese vendedor es un ladrón

Por consiguiente . Pedro tenia razón

m) - O hace reparar su automóvil o compra uno nuevo

- Si hace reparar su automóvil, deberá mucho dinero al taller
- Si debe mucho dinero al taller, tardara en salir de sus deudas
- Si compra un automóvil nuevo, debe entonces pedir un préstamo al banco,
y si pide un préstamo al banco, tardara entonces en salir de sus deudas
- O sale pronto de sus deudas o sus acreedores le llevan a la bancarrota

Por lo tanto. Sus acreedores le llevan a la bancarrota

n) - Si lo uno esta en movimiento, este habrá de ser, o de movimiento sin

cambio en el estado, o de alteración
- No puede tratarse de un movimiento de alteración
- Si se tratase de lo primero, tendría que ser, o bien de rotación de lo uno
sobre si mismo o en el propio lugar donde se encuentra, o bien de cambio de
un lugar a otro
- Ninguna de estas dos cosas ocurre

Luego. lo uno no esta sujeto a ningún tipo de movimiento

o) - No llueve y, sin embargo, hace sol

- Si no llueve, hace sol solo si la partida es el viernes y, o Juan es amigo de
Pepe o Pepe no llega tarde
- O Juan es amigo de Pepe y Pepe llega tarde, o hace sol
- no ocurre que la partida sea el viernes haciendo sol, a menos que llueva o
Juan sea amigo de Pepe

Por lo tanto:
a) Juan es amigo de Pepe
b) Pepe llega tarde

p) - El palo empieza a golpear al perro solo si el perro empieza a morder al

gato
- El perro no empieza a morder al gato a menos que este salte por la
ventana
- El palo empieza a golpear al perro

Luego. el gato salta por la ventana

q) - No llora, ríe
- Si no llora, ríe solo si tiene un juguete

103
 - No ocurre que tenga un juguete riéndose, a menos que coma un
chocolate

Por lo tanto. come un chocolate

r) - si ha nevado, será difícil conducir

- si no es fácil conducir, llegare tarde a menos que salga temprano
- ha nevado y no llegare tarde

luego. saldré temprano

s) - Si Juan cometió el crimen, es que no estaba en el apartamento de la

victima o salio antes de las once
- Si salio antes de las once, el portero lo vio
- El estaba en el apartamento y el portero no lo vio
Por tanto. Juan no cometió el crimen

104
 CAPITULO VI

COHERENCIA ENTRE TEORIAS

Se ha visto que existen diversos métodos, mediante los cuales es posible demostrar
la validez de fórmulas y deducciones. Como ser el método semántico, los métodos
axiomáticos y los de deducción natural, en el presente capitulo demostraremos que
los métodos de demostración son equivalentes, vale decir que una fórmula
demostrable por un método es demostrable por otro y viceversa.

Tomaremos para la demostración de la coherencia entre teorías, la demostración

por la teoría interpretativa y por teoría de la demostración.

En Teoría de la Demostración se define un conjunto de fórmulas válidas,

agrupadas en dos grandes campos, unas llamadas axiomas y otras teoremas, a
partir de ambas se logra demostrar cualquier fórmula que comprenda el Cálculo
de proposiciones.

En Teoría Interpretativa, se analizan las tablas de verdad correspondientes tanto a

fórmulas como a deducciones, y se establece que una fórmula o una deducción a la
cual se le ha asociada una fórmula por el teorema de la deducción, es una fórmula
válida si esta es una tautología.

Por lo tanto en los dos acápites siguientes vamos a demostrar que las fórmulas
semánticamente válidas, es decir tautologías son fórmulas demostrables por teoría
de la demostración y por ende las fórmulas válidas de teoría de la demostración
son fórmulas tautológicas por ser demostrables por teoría interpretativa.

A) TEORIA DE LA DEMOSTRACIÓN  TEORIA

INTEPRETATIVA

Teorema de Post.- Toda Fórmula válida (formalmente válida en teoría de la

demostración) es una tautología (fórmula válida en teoría interpretativa)

Demostración:

1) Los Axiomas ( Fórmulas Válidas ) son Tautologías

2) Los Teoremas ( Fórmulas Válidas ) son Tautologías

Recordemos que los teoremas son fórmulas válidas obtenidas a partir de los
axiomas por aplicación de una regla de inferencia, en este caso la Regla del Modus
Ponens.

El proceso de demostración de los axiomas, teoremas y de la regla de inferencia

entraña la construcción de una tabla de verdad, tal que la columna
correspondiente al conectivo principal dará para cada línea de la tabla de verdad
correspondiente un modelo interpretativo de esa fórmula, por lo tanto una
tautología.

105
 A) AXIOMAS  TAUTOLOGIAS

A1: ├ A → (B → A)

A B A → B → A
V V V V
V F V V
F V V F
F F V V

Al ver la columna correspondiente a la salida de este axioma, se observa que para

cada linea el valor de salida es verdadero, por lo tanto se trata de una tautología.

A 2 : ├ ( A → B ) → [ (( A → ( B → C ) ) → ( A → C ) ]

A B C A → B → A → B → C → A → C
V V V V V V V V V
V V F V V F F V F
V F V F V V V V V
V F F F V V V F F
F V V V V V V V V
F V F V V V F V V
F F V V V V V V V
F F F V V V V V V

En el caso de este axioma del mismo modo se observa que cada línea de salida es
un modelo interpretativo de la fórmula, es decir la fórmula es tautológica.
A3: ├ A → ( B → A Λ B)

A B A → B → A Λ B
V V V V V
V F V V F
F V V F F
F F V V F

A4: ├ A Λ B → A

A B A Λ B → A
V V V V
V F F V
F V F V
F F F V

106
A5: ├ A → A ν B

A B A → A Ν B
V V V V
V F V V
F V V V
F F V F

A6: ├ ( A → C) → [ ( B → C) → ( A ν B) → C]

A B C A → C → B → C → A ν B → C
V V V V V V V V V
V V F F V F V V F
V F V V V V V V V
V F F F V V F V F
F V V V V V V V V
F V F V V F V V F
F F V V V V V F V
F F F V V V V F V

En el caso del axioma seis, se observa de igual manera que en la columna

correspondiente al conectivo principal, todos los valores de salida son verdaderos,
por lo tanto este axioma de acuerdo a la teoría interpretativa es una tautología, es
decir una fórmula semánticamente válida.

A7: ├ ( A → B) → [ (A → ~ B) → ~ A]

A B A → B → A → ~ B → ~ A
V V V V F F V F
V F F V V V F F
F V V V V F V V
F F V V V V V V

A8: ├ ~ ~ A → A

A ~~A → A
V V V
F F V

107
REGLA DE INFERENCIA MODUS PONENS

├ A→[(A → B) → B]

A B A → A → B → B
V V V V V
V F V F V
F V V V F
F F V V F

Como se puede observar, también la regla de inferencia del modus ponens es una
tautología, ya que todas las salidas en el conectivo principal son modelos
interpretativos de la fórmula.

B) TEOREMA  TAUTOLOGIAS

Tomaremos algunos de los teoremas a objeto de demostrar que también existe

equivalencia, y que los teoremas son también fórmulas demostrables en teoría
interpretativa.

├ ~(A Λ B) → ~A ν ~ B DE MORGAN

A B ~ A Λ B → ~ A ν ~ B
V V F V V F F F
V F V F V F V V
F V V F V V V F
F F V F V V V V

Se analiza la salida y se ve que todos los valores son verdaderos, por lo tanto este
teorema es también una tautología.

├ A → ( ~A → B) E.C.Q

A B A → ~ A → B
V V V F V
V F V F V
F V V V V
F F V V F

├ (A → B ) → ~ ( A Λ ~ B ) INTER DEFINICIÓN
A B A → B → ~ A Λ ~ B
V V V V V F F
V F F V F V V
F V V V V F F
F F V V V F V

Del mismo modo podemos seguir demostrando el resto de los teoremas del sistema
K, y podemos demostrar que todos ellos en el marco de la teoría interpretativa son
tautologías.

108
De esta manera queda demostrado que todas las fórmulas válidas de teoría de la
demostración, ya sean estos axiomas o teoremas, tomando las correspondientes al
sistema axiomático K son tautologías, es decir son fórmulas semánticamente
válidas en teoría interpretativa

B) TEORIA DE LA DEMOSTRACIÓN  TEORIA INTERPRETATIVA

Teorema de Kalmar.- Toda tautología (fórmula semánticamente válida) en Teoría

Interpretativa es una fórmula válida (formalmente válida) en Teoría de la
demostración.

Lema de Kalmar.- A cualquier Fórmula F puede asociársele un conjunto de

deducciones correctas en Teoría de la demostración, una para cada línea de su
tabla de verdad, construida mediante una Función I k ( P i ) de las proposiciones
componentes, de acuerdo a las siguientes reglas.

1) Si la proposición componente P i de la fórmula aparece en la línea K de la

tabla de verdad con significado Verdadero, en la deducción se introduce
con su propio valor I k ( P i ) = P i
2) Di la proposición componente P i de la fórmula aparece en la línea K de la
tabla de verdad con valor Falso, en la deducción se introduce con valor
negado I k ( Pi ) = ~ P i
3) Si la fórmula de acuerdo a la tabla de verdad, para una línea K de esa es
Verdadera, la conclusión de la deducción es la misma fórmula I k ( F ) = F
4) Si la fórmula para una línea de la tabla de verdad es Falsa, la conclusión de
la deducción para esa línea es la fórmula negada I k ( F ) = ~ F

1) DEMOSTRACIÓN PARA FÓRMULAS CON UN CONECTIVO

~ A A Λ B A ν B A → B

1.- NEGACION F = ~ A

A ~A Ik ( A )  Ik ( F )

V F I1 ( A ) = A  I1 ( F ) = ~ ~ A

F V I2 ( A ) = ~ A  I2 ( F ) = ~ A

Deducciones

1) A  ~ ~ A

Ya demostrada, ya que se trata de la introducción de la doble negación

1) ├ ( ~ ~ ~ A → ~ A ) → ( A → ~ ~ A ) A3
2) ├ ~ ~ ~ A → ~ A T4
3) A → ~ ~ A M.P ( 1 , 2 )

109
2) ~ A  ~ A

Ya demostrada, se trata del teorema de identidad

1) ├ ( ~A → ( ~ A → ~A )) → [ ( ~A → ( ~A → ~A )→ ~A) → ( ~A → ~A ) ] A 2
2) ├ ( ~ A → ( ~ A → ~ A )) A1
3) ( ~ A → ( ~ A → ~ A ) → ~ A ) → ( ~ A → ~ A ) M.P ( 1 , 2 )
4) ( ~ A → ( ~ A → ~ A ) → ~ A ) A1
5) ~ A → ~ A M.P ( 3 , 4 )

2.- CONJUNCION F= A Λ B

A B A Λ B Ik(A) Ik8B)  Ik(F)

V V V V V A Λ B
V F F V F ~(A Λ B)
F V F F V ~(AΛB)
F F F F F ~(A Λ B)

Deducciones

1) A , B  A Λ B

1) A P
2) B P
3) ├ A → ( B → A Λ B) A3
4) B → A Λ B M.P ( 3 , 1 )
5) A Λ B M.P ( 4 , 2 )

2) A , ~ B  ~ ( A Λ B )

1) A P
2) ~ B P
3) ├ ~ A ν ~ B → ~(A Λ B) De Morgan
4) ├ ~ B → ~ A ν ~ B A5
5) ~ A ν ~ B M.P ( 4 , 2 )
6) ~( A Λ B) M.P ( 3 , 5 )

3) ~ A , B  ~ ( A Λ B )

1) ~A P
2) B P
3) ├ ~ A ν ~ B → ~(A Λ B) De Morgan
4) ├ ~ A → ~ A ν ~ B A5
5) ~ A ν ~ B M.P ( 4 , 1 )
6) ~ ( A Λ B) M.P ( 3 , 5 )

4) ~ A , ~ B  ~( A Λ B)

1) ~ A P

110
2) ~ B P
3) ├ ~ A ν ~ B → ~(A Λ B) De Morgan
4) ├ ~ A → ~ A ν ~ B A5
5) ~ A ν ~ B M.P ( 4 , 1 )
6) ~ ( A Λ B) M.P ( 3 , 5 )

Con lo que queda demostrado que para fórmulas relacionadas con el conectivo de
la conjunción en el marco de fórmulas correspondientes de la teoría interpretativa,
es posible demostrar estas por medio de la teoría de la demostración, asociando a
cada línea de la tabla de verdad correspondiente de esa fórmula una deducción, y
demostrar esta por medio de la teoría de la demostración.

3.- DISYUNCION F= A ν B

A B A ν B Ik(A) Ik8B)  Ik(F)

V V V V V A ν B
V F V V F A ν B
F V V F V AνB
F F F F F ~(A ν B)

Deducciones

1) A , B  A ν B
1) A P
2) B P
3) ├ A → A ν B A5
4) A ν B M.P ( 3 , 1 )

2) A , ~ B  A ν B

1) A P
2) ~ B P
3) ├ A → A ν B A5
4) A ν B M.P ( 3 , 1 )

3) ~ A , B  A ν B
1) ~ A P
2) B P
3) ├ B → A ν B A5
4) A ν B M.P ( 3 , 2 )

4) ~ A , ~ B  ~ ( A ν B )

111
1) ~ A P
2) ~ B P
3) ├ ~ A Λ ~ B → ~ ( A ν B ) De Morgan
4) ├ ~ A → ( ~ B → ~ A Λ ~ B ) A3
5) ~ B → ~ A Λ ~ B M.P ( 4 , 1 )
6) ~ A Λ ~ B M.P ( 5 , 2 )
7) ~ ( A ν B ) M.P ( 3 , 6 )

Con lo que queda demostrado que para fórmulas relacionadas con el conectivo de
la disyunción, fórmulas que se han demostrado que son semánticamente válidas en
teoría interpretativa, al asociárseles una deducción a cada línea de la tabla de
verdad, demostramos que son válidas en teoría de la demostración.

4.- IMPLICACIÓN F= A → B

A B A → B Ik(A) Ik8B)  Ik(F)

V V V V V A → B
V F F V F A → B
F V V F V A → B
F F V F F ~( A → B)

Deducciones
1) A , B  A → B

1) A P
2) B P
3) ├ B → ( A → B ) A1
4) A → B M.P ( 3 , 1 )
2) A , ~ B  ~ ( A → B )
1) A P
2) ~ B P

3) ~ ~ ( A → B ) P.A
4) ├ ~ ~ ( A → B ) → ( A → B ) A8
5) A → B M.P ( 4 , 3 )
6) B M.P ( 5 , 1 )
7) ├ B → ( ~ B → B Λ ~ B ) A3
8) ~ B → B Λ ~ B M.P ( 7 , 6 )
9) B Λ ~ B M. P ( 8 , 2 )

112
 10) ~ ~ ~ ( A → B ) Absurdo ( 9 )
11) ├ ~ ~ ~ ( A → B ) → ~ ( A → B ) A8
12) ~ ( A → B ) M.P ( 11, 10 )

3) ~ A , B  A → B

1) ~ A P

2) B P

3) ├ B → ( A → B ) A1

4) A → B M.P ( 3 , 2 )

4) ~A , ~ B  A → B

1) ~ A P

2) ~ B P

3) ├ ~ A ν B → ( A → B ) Inter Definción

4) ~ A → ~ A ν B A5

5) ~ A ν B M.P ( 4 , 1 )

6) A → B M.P ( 3 , 5 )

También las fórmulas construidas mediante el conectivo de la implicación, válidas

en teoría interpretativa, se ha demostrado que también asociándoles una
deducción para cada línea de la tabla de verdad de acuerdo a teoría interpretativa,
son válidas en teoría de la demostración.

Al haber realizado las demostraciones en ambas teorías y demostrado la

equivalencia y demostración de las fórmulas mediante ambas teorías,
demostramos que existe coherencia entre ambas teorías.

Ejercicios Propuestos

A)Demostrar que lo siguientes teoremas del sistema K son coherentes respecto a la

Teoría Interpretativa

T1 ├(A → A)
T2 ├(A →B) → [(B → C)→ (A → C)]
T3 ├A →[(A → B) → B]
T4 ├ (A → B) → [(A → C)→(A → B Λ C)]
T5 ├(A → B) → ( ~B → ~A)
T6 ├(A → B) → ~(A Λ ~B)
T7 ├(A → B) → ~A ν B
T8 ├~(A Λ B) → ~A ν ~B

113
T9 ├~(A ν B) → ~A Λ ~ B
T 10 ├ A Λ B → B Λ A
T 11 ├ A Λ ( B Λ C) → (A Λ B) Λ C
T 12 ├ A Λ ( B ν C) → (A Λ B) ν (A Λ C)
T 13 ├ A Λ A → A
T 14 ├ A Λ (A ν B) → A
T 15 ├ A ν B → B ν A
T 16 ├ A ν( B ν C) → (A ν B) ν C
T 17 ├ A ν (B Λ C) → (A ν B) Λ ( A ν C)
T 18 ├ A ν A → A
T 19 ├ A ν ( A Λ B) → A
T 20 ├ ( A → ( B → C )) → (( A Λ B ) → C )
T 21 ├ ( A Λ B → C ) → ( A → ( B → C ))
T 22 ├ ( A ↔ B) → [(B → A) → ( A → B)]
T 23 ├ ( A ↔ B) → ( A → B)
T 24 ├ ( A ↔ B) → (B → A)
T 25 ├ A ↔ A
T 26 ├ ( A ↔ B) → [(B ↔ C) → (A ↔ C)]
T 27 ├ ( A ↔ B) → ( B ↔ A)

B)Demostrar que lo siguientes teoremas del sistema L son coherentes respecto a la

Teoría Interpretativa

T1: ├ A → A
T2: ├ ( A → B)→ [( B → C) → ( A → C)]
T3: ├A → ((A → B) → B)
T4: ├ ~ ~A → A
T5: ├ A → ~~A
T6: ├ ( B → ~A) → ( A → ~ B)
T7: ├( ~A → B) → ( ~ B → A)
T 8 : ├ A → ( B → ~ ( A → ~ B ))
T9: ├A → ( ~ A → B)
T 10 : ├ ~ ( A → ~ B ) → A
T 11 : ├ A → ~ ( A → ~ A )
T 12 : ├ ( A → ~ A ) → ~ A
T 13 : ├ ( ~ A → A ) → A
T 14 : ├ ( A → C ) → [ ( B → C ) → ( ( ~ A → B ) → C ) ]
T 15 : ├ ( A → B ) → [ ( A → ~ B ) → ~ A ]
T 16 : ├ ( A → B ) → [ ( ~ A → B ) → B ]
T 17 : ├ ( A → B ) → [ ( A → ( B → C )) → ( A → C ) ]

114