3 LÓGICA

MATEMÁTICA
Analiza y resuelve problemas computacionales
utilizando las técnicas básicas de lógica e DURACIÓN: 15 HORAS

inducción matemática.
 CONTENIDO TEMÁTICO
1. Lógica proposicional.
2. Lógica de predicados.
1. Proposiciones simples y compuestas.
1. Cuantificadores.
2. Tablas de verdad.
2. Representación y evaluación de
3. Tautologías, contradicción y contingencia.
predicados.
4. Equivalencias lógicas.
3. Algebra declarativa.
5. Reglas de inferencia.
4. Inducción matemática
6. Argumentos válidos y no válidos.
5. Aplicaciones de la lógica matemática en la
7. Demostración formal.
computación.
TABLA DE ACTIVIDADES

ACTIVIDAD VALO FECHA DE

R ENTREGA
EF7.- Mapa mental 50%
de la unidad
temática
EF8.- Evaluación 50%
escrita de unidad
 Lalógica proposicional o lógica
de orden cero esunsistema
formal cuyos elementosmás
simples representan
proposiciones, y cuyas

3.1 LÓGICA PROPOSICIONAL. constantes lógicas,llamadas

conectivas, representan
operaciones sobre
proposiciones, capacesde
formar otras proposiciones de
mayorcomplejidad.
La lógica estudia la forma del razonamiento, es una disciplina que por Lalógica proposicional trata con
sistemaslógicos que carecen de
medio de reglas y técnicas determina si un teorema es falso o verdadero, cuantificadores, ovariables
interpretables como entidades.
además de que es ampliamente aplicada en filosofía, matemáticas,
Enlógica proposicional si bien
computación y física. no hay signos para variablesde
tipo entidad, sí existen signos
para variables proposicionales
(es decir, que pueden ser
interpretadas como
proposiciones con un valor de
verdad definido), de ahí el
nombre proposicional.
Lalógica proposicional incluye
además devariables
interpretables como
proposiciones simples signos
para conectivas lógicas, por lo
que dentro de este tipo de
lógica puede analizarse la
inferencia lógicade
proposiciones apartir de
proposiciones, pero sin tener en
cuenta la estructura internade
las proposiciones mássimples.
 En matemáticas la lógica es una
herramienta útil para demostrar
teoremas e inferir resultados, así
comopara resolver problemas.
Enla computación la lógica se
aplica en la elaboración y
revisión de programas, en el
estudio de lenguajes formales y
la relación existente entre ellos,
así como en la obtención de
resultados en forma recursiva.
Con el apoyo de la lógica, en el
área de la inteligencia artificial
se logra que una máquina tome
decisiones precisas.
LA LÓGICA EN LA
COMPUTACIÓN
 3.1.1 PROPOSICIONES SIMPLES Y
COMPUESTAS.
Una proposición o enunciado es una oración, frase o expresión matemática que
puede ser falsa o verdadera, pero no ambas a la vez.
La proposición es un elemento fundamental de la lógica matemática.
Ejemplo. Proposiciones válidas y no válidas.
p: Estados Unidos es el país territorialmente más extensodel
Nombre de la
continente americano. proposición
(minúscula)
q: -19+ 50 = 31.
r: x> (y - 13)7.
s: Carlos Salinas de Gortari fue presidente de España,
p: hoy esjueves
t: Querétaro será campeón en la presente temporada de
fútbol, Enunciado de la proposición
(oración)
u: ¿Cómoestás? Tiene que tener un valor FALSOo
v: Formatea el disco antes de usarlo. VERDADEROal evaluarla
 PROPOSICIONES COMPUESTAS
Una proposición es compuesta cuando está integrada por dos o más proposiciones
simples conectadas por medio de operadores lógicos.

〜,⌐,¯,´
 Fue desarrollada por Charles
Sanders Peirce por los años
1880, pero el formato más
popular es el que
introdujo Ludwig

3.1.2 TABLAS DE VERDAD. Wittgenstein en su Tractatus

logico-philosophicuss,
publicado en 1921.

Tabla de verdad o tabla de valores de verdad; es una tabla que muestra el

valor de verdad de una proposición compuesta, para cada combinación
de valores de verdad que se pueda asignar a sus componentes.
es usada en el ámbito de la lógica, para obtener la verdad (V) o falsedad (F),
valores de verdad, de una expresión o de una proposición.
Además sirven para determinar si es que un determinado esquema de
inferencia es formalmente válido como un argumento, llegando a la
conclusión de que este es una tautología.
Las tablas de valores son, por una parte, uno de los métodos más sencillos
y conocidos de la lógica formal, pero la mismo tiempo también uno de los
más poderosos y claros. Entender bien las tablas de verdad es, en gran
medida, entender bien a la lógica formal misma.
 TABLAS DE VERDAD
(continuación…)
Fundamentalmente, una tabla de verdad es un dispositivo para demostrar ciertas
propiedades lógicas y semánticas de enunciados del lenguaje natural o de fórmulas
del lenguaje del cálculo proposicional:
1. Si son tautológicas, contradictorias o contingentes
2. Cuáles son sus condiciones de verdad
3. Cuál es su rol inferencial, es decir, cuáles son sus conclusiones lógicas y de qué
otras proposiciones se siguen lógicamente.
Estas tablas pueden construirse haciendo una interpretación de los signos lógicos
como: no, o, y, si…entonces, sí y sólo si.
La interpretación corresponde al sentido que estas operaciones tienen dentro del
razonamiento. Puede establecerse una correspondencia entre los resultados de
estas tablas y la deducción lógico matemática. En consecuencia, las tablas de
verdad constituyen un método de decisión para chequear si una proposición es o no
un teorema.
Para la construcción de la tabla se asignará el valor 1(uno) a una proposición cierta
y 0 (cero) a una proposición falsa.
EJEMPLOS: PROPOSICIONES COMPUESTAS
Y TABLAS DE VERDAD
Considérese el enunciado
“Es buen estudiante, si y sólo si, tiene promedio de diez.”
Calcular las proposiciones, la notación lógica del enunciado, la tabla de verdad.
EJEMPLOS: PROPOSICIONES COMPUESTAS Y TABLAS DE VERDAD

Considérese el enunciado
“Si no estudio matemáticas para
computación y no hago la tarea de
fundamentos de programación, entonces
reprobaré el semestre o no podré ir de
vacaciones a Cancún.”
Calcular las proposiciones, la notación
lógica del enunciado, la tabla de verdad.
EJEMPLOS: PROPOSICIONES COMPUESTAS Y TABLAS DE VERDAD

Considérese el enunciado
“Si no estudio matemáticas para
computación y no hago la tarea de
fundamentos de programación, entonces
reprobaré el semestre o no podré ir de
vacaciones a Cancún.”
Calcular las proposiciones, la notación
lógica del enunciado, la tabla de verdad.
EJEMPLOS: PROPOSICIONES COMPUESTAS Y TABLAS DE
VERDAD
Considérese el enunciado
“Si no pago el teléfono, entonces me cortarán el servicio telefónico. Ysi pago el teléfono,
entonces me quedaré sin dinero o pediré prestado. Ysi me quedo sin dinero y pido prestado,
entonces no podré pagar la tarjeta de crédito, si sólo si soy una persona desorganizada.”
Calcular las proposiciones, la notación lógica del enunciado, la tabla de verdad.
EJEMPLO CONSTRUCCIÓN DE TABLAS DE VERDAD

Construir la tabla de verdad de la siguiente proposición:

[(p → q) v (q’ ^ r)] (r → q)
3.1.3 TAUTOLOGÍAS, CONTRADICCIÓN
Y CONTINGENCIA.
Tautología es aquella proposición (compuesta) que es cierta para todos los valores
de verdad de susvariables.
Un ejemplo típico es (p' v p), ya que el resultado es verdadero para todos los
valores que puede tener p.

p p´ p v p´
(p → q) (q'→ p’)
Comprueba si es unatautología
TAUTOLOGÍAS
COMUNES
CONTRADICCIÓN

Se dice que una proposición es una contradicción o “absurdo” si al evaluar esa

proposición el resultado es falso, para todos los valores de verdad.
La contradicción más conocida es (p a p’).

p p´ p ^ p´
CONTINGENCIA
Una proposición compuesta cuyos valores, en sus diferentes líneas de la tabla de
verdad, dan como resultado unos y ceros se llama contingencia, inconsistencia o
falacia.
Prácticamente cualquier proposición que se invente por lo general es una
contingencia.
 3.1.5 REGLAS DE INFERENCIA.
Los argumentos basados en tautologías representan métodos
de razonamiento universalmente correctos. Su validez
depende solamente de la forma de las proposiciones que
intervienen y no de los valores de verdad de las variables que
contienen.
A esos argumentos y a la forma en que se relacionan entre sí se
les llama reglas de inferencia, y éstas permiten relacionar dos
o más proposiciones para obtener una tercera que es válida en
una demostración.
 EJEMPLO DE INFERENCIA LÓGICA

Considérese el siguienteargumento: Calcular las proposiciones

Representar la notación lógica

Si es un gato, entonces come carne.

hipótesis
Si come carne, entonces es felino.
conclusión Si es un gato, entonces esfelino.
 EJEMPLO DE INFERENCIA LÓGICA

Calcular las proposiciones

Considérese el siguienteargumento:
Representar la notación lógica

hipótesis
Bajan los impuestos.
Si bajan los impuestos, entonces el ingreso se eleva.
conclusión El ingreso se eleva.
REGLAS DE
INFERENCIA
3.1.4 EQUIVALENCIAS LÓGICAS.
Se dice que dos proposiciones son lógicamente equivalentes, o simplemente
equivalentes, si coinciden susresultados para los mismos valores le verdad, y se
indican como p ≡ q o bien como p q.
PROPIEDADES EQUIVALENTES
Esposible demostrar que dos proposiciones son lógicamente equivalentes, no sólo por
medio de una tabla de verdad, sino también con apoyo de las propiedades de
equivalencias lógicas.
Usando equivalencias lógicas demostrar que:
(p q) ≡ [(p → q) ^ (q → p)]

p q p q ≡ [(p → q) ^ (q → p)]
0 0
0 1
1 0
1 1
 Esposible demostrar que dos proposiciones son lógicamente equivalentes, no sólo por
medio de una tabla de verdad, sino también con apoyo de las propiedades de
equivalencias lógicas.
Usando equivalencias lógicas demostrar que:
(p q) ≡ [(p → q) ^ (q → p)]

Demostración:
(p q) ≡ [(p → q) ^ (q → p)]
Usando equivalencias 25b (izquierdo)

Usando equivalencias 24a (derecho)

[(p → r) ^ (q → r)] ≡ [( p ^ q) → r]
[p ^ (s v r’)] ≡ [ p → ( s v r’)’]’
3.1.6 ARGUMENTOS VÁLIDOS Y NO
VÁLIDOS.
Un argumento es una secuencia de afirmaciones, todas las
afirmaciones excepto la última se llamarán premisas, suposiciones
o hipótesis, la declaración final se llamará conclusión.
Argumentar consiste en deducir una conclusión a partir de una
premisa que se tienen por verdaderas. Un argumento, por lo tanto,
estará compuesto de unas premisas y de una conclusión
Lo que hace que podamos hablar de razonamiento es la relación que
existe entre los enunciados que llamamos premisas y la conclusión.
Un argumento consiste en una o mas hipótesis y una conclusión,
de forma que la conclusión se apoye en las hipótesis.
También se puede considerar a un argumento como una serie de
proposiciones interrelacionadas que conforman una proposición mas
compleja, a la cual se le llama teorema.
Todos los argumentos necesitan de una o mas proposiciones iniciales, y a
estas proposiciones iniciales se les llama hipótesis.
La conclusión de un argumento o teorema es una consecuencia de las
hipótesis, por esa razón se requiere que las hipótesis sean convincentes y
explicitas.
En general los argumentos lógicos a tratar tienen la siguiente
forma:
P Q

La proposición P esta integrada por proposiciones mas simples llamadas

hipótesis, las cuales se encuentran relacionadas por el operador lógico ^, y Q
es la conclusión del teorema que también puede estar conformada por una o
mas proposiciones simples, de tal manera que el argumento puede tener la
siguiente forma:
(p1 ^ p2 ^...^ pn) q
en donde p1, p2 ,... , pn son las hipótesis y q es la conclusión
del razonamiento.
La validez del argumento depende de la estructura existente
entre las hipótesis y la conclusión, ya sea por la forma de
conectar las hipótesis con la conclusión o por la veracidad de la
conclusión misma.
La validez es una propiedad de los argumentos. Un argumento
puede tener otras propiedades como claro, confuso, endeble,
convincente, grande, pequeño, feo o bonito y sin embargo
puede no ser valido.
Hay argumentos que son validos, mientras que otros no lo son.
Un argumento es argumento válido si para cualquier valor de las
variables proposicionales involucradas en las fórmulas que hacen
verdaderas las premisas la conclusión es verdadera.

Argumento: Conjunto de formulas para el razonamiento lógico.

Argumento Valido: Un argumento es valido si se cumple:
❑ Un argumento puede ser válido con premisas y conclusión
verdaderas.
❑ Pero también puede ser válido con premisas falsas y conclusión
verdadera, o incluso con premisas y conclusión falsas.

Lo que NUNCA será es válido con premisas verdaderas y conclusión

falsa.
De la propia definición de argumento válido se puede deducir una metodología
para verificar la validez de un argumento:
1. Identificar las premisas y la conclusión
2. Construir una tabla de verdad que incluya las premisas y la conclusión
3. Señalar de la tabla sólo aquellos renglones que hacen que todas las premisas
sean verdaderas.
Estos se llamarán renglones críticos
4. Verificar que para los renglones críticos, la conclusión es verdadera. En tal
caso se tiene un Argumento válido.
5. Detectar si existe un renglón crítico con conclusión falsa. En cuyo caso se
dirá Argumento inválido.

Las premisas pueden ser verdaderas o falsas, la conclusión puede ser verdadera
o falsa, y el argumento puede ser válido o inválido.
EVALUACIÓN DE LOS ARGUMENTOS MEDIANTE
TABLAS DE VERDAD
Todos los argumentos pueden convertirse en un condicional, pues después de todo lo que un argumento esta
afirmando, es que si las premisas son verdaderas, entonces la conclusión también lo es.

Dicho de otro modo :

p1 ^ p2 ^... ^pn → C

Es decir, un argumento es, en realidad, un condicional en el que en antecedente es la conjunción de todas las
premisas (p1 ^ p2 ^... ^ pn) y el consecuente es la conclusión.

Como sabemos, la tabla de verdad del condicional nos dice que este solo es falso cuando el antecedente
es verdadero y el consecuente es falso, y verdadero en el resto de los casos.

Esto coincide completamente con la definición de argumento valido, según la cual un argumento será válido
exactamente en los mismos casos en que el condicional que le corresponde lo sea. Como un condicional no
puede ser verdadero si el antecedente es verdadero y el consecuente falso, un argumento no podrá ser válido si las
premisas son verdaderas y la conclusión falsa.
No siempre es fácil averiguar intuitivamente si un argumento es válido o no, por lo
que en ocasiones es necesario recurrir a métodos más fiables que la intuición.

Dado que podemos convertir cualquier argumento en un condicional, podemos

usar el método de las tablas de verdad para averiguar si un argumento
dado es válido o no.

Evidentemente, un argumento sólo será válido cuando el condicional

correspondiente sea una tautología y no será válido en el resto de casos (si
es una contradicción o si es una contingencia).

Premisa 1: Si estudio entonces aprobaré

Premisa 2: No he estudiado
Conclusión: No aprobaré
 Lo primero que debemos hacer para evaluar o decidir si el argumento es
válido o no, es formalizarlo:
Formalización de la premisa 1: p → q (si estudio entonces aprobaré)
Formalización de la premisa 2: ¬p (no estudio)
Formalización de la concusión: ¬q (no apruebo)

En segundo lugar, tenemos que convertir el argumento en un condicional. El

antecedente del condicional estará formado por la conjunción de todas las
premisas, y el consecuente por la conclusión, de modo que obtenemos lo
siguiente:
[( p → q ) ᶺ ¬p] → q

Éste es, en consecuencia, el condicional que le corresponde al argumento del

ejemplo. Su tabla de verdad, que quedará como sigue:

La tabla de verdad revela que el condicional analizado es una

contingencia, lo que significa que puede ser verdadero o no, es
decir, que es posible que sus premisas sean verdaderas y su
conclusión falsa. Por lo tanto el argumento correspondiente no
será válido.
 ESTRUCTURA EXISTENTE ENTRE LA HIPÓTESIS Y LA CONCLUSIÓN

A) Caso en el que el argumento es valido, y tanto las hipótesis como la conclusión

son verdaderas.
Considere lo siguiente:
“Las aves son ovíparas. El gorrión es ave. Por lo tanto; el gorrión es ovíparo.”

Considerar que: De esta forma el enunciado anterior se puede

p1: Las aves son ovíparas. representar con notación lógica de la siguiente manera:
p2: El gorrión es ave. p1 ^ p2 → q
q: El gorrión es ovíparo. Como tanto hipótesis como conclusión son
verdaderas (p1 =1, p2 =1, q =1)
Toda la información que se encuentra antes del termino “Por lo entonces se trata de un argumento valido ya
tanto”, conforma las hipótesis. que:
Lo que separa a una hipótesis de otra es el punto 1 ^1 → 1
y seguido, el cual se representa por una intersección entre cada una de las
hipótesis.
1 →1
Por otro lado, la parte que esta entre la palabra “Por lo tanto” y el 1
punto final del enunciado, es lo que se conoce como conclusión. Dicha
conclusión puede estar integrada también por mas de una proposición.
 ESTRUCTURA EXISTENTE ENTRE LA HIPÓTESIS Y LA CONCLUSIÓN

B) Caso en el que el argumento es valido, cuando todas o alguna de las hipótesis es

falsa, y la conclusión es verdadera.
Considere lo siguiente:
“Las mujeres son jóvenes. Miss universo es mujer. En conclusión, miss universo es joven.”

entonces se puede decir que p1 es “ falsa” , porque

A partir de esto se definen: hay mujeres que no son jóvenes; p2 es “verdadera” y
q es “verdadera”.
p1: Las mujeres son jóvenes. Aunque se tienen hipótesis falsas (con una que sea falsa es
p 2: Miss universo es mujer. suficiente) y la conclusión verdadera, entonces el argumento es
q: Miss universo es joven. completamente valido. Considerando p1 =0, p2 =1, q =1 se tiene:
0 ^1 → 1
En el enunciado anterior la característica de joven es difícil de evaluar, ya que 0 →1
depende con quien se compare, pero suponiendo que una mujer es joven si tiene
entre 17 y 30 años.
1
 ESTRUCTURA EXISTENTE ENTRE LA HIPÓTESIS Y LA CONCLUSIÓN

C) Caso en el que el argumento es valido y, las hipótesis y la conclusión son falsas.

Considere lo siguiente:
“Los alemanes son de raza negra. George Bush es de raza negra. Por lo tanto; George Bush
es alemán.”

En este caso las hipótesis p1, p2, y la conclusión q son falsas,

A partir de esto se definen: sin embargo el argumento se considera valido.
p1: Los alemanes son de raza negra.
p2: George Bush es de raza negra,
q: George Bush es alemán. Utilizando notación lógica, el argumento anterior se puede
evaluar de la siguiente forma:
0 ^0 → 0
0 →0
1
 PUNTOS CLAVE

Un argumento no se considera valido, si esta integrado por hipótesis verdaderas y conclusión falsa.
Cuando los argumentos se expresan en nuestro propio lenguaje se debe de tomar en cuenta el contexto, ya
que se dan muchos supuestos.
Cuando no se sabe si las proposiciones que integran un argumento son falsas o verdaderas, es necesario
probarlo en todos los casos posibles, teniendo en cuenta que un argumento no es valido solamente cuando a
partir de hipótesis verdaderas se desprende una conclusión falsa
La forma mas fácil de determinar si un argumento es valido o no, cuando no se tienen los valores de las
proposiciones, es por medio de la tabla de verdad. Si se trata de una tautología se dice que el argumento es
valido, en caso contrario el argumento es invalido.
 TIPOS DE ARGUMENTOS

Básicamente existen dos tipos de argumentos lógicos: deductivos e inductivos.

• En un argumento deductivo se va de lo general a lo particular, se trata de un
procedimiento que parte de un teorema que esta formado por hipótesis y una
conclusión.
➢Se puede decir que se inicia con un explicación razonable para describir el comportamiento de
un conjunto de datos, y que esa explicación se representa por medio de un teorema que
deberá demostrarse formalmente por medio de leyes y reglas conocidas (tautologías, reglas de
inferencia y equivalencias lógicas en el caso de lógica matemática).
➢El argumento podrá ser valido o invalido.
➢Un argumento deductivo valido se define como aquel que siendo sus hipótesis ciertas, la
conclusión también lo es.
TIPOS DE ARGUMENTOS

Básicamente existen dos tipos de argumentos lógicos: deductivos e inductivos.

•En un argumento inductivo se va de lo particular a lo general, se puede
decir que es el conjunto de observaciones y datos cuya tendencia permite
visualizar o generalizar el comportamiento de un evento.
➢La veracidad de sus conclusiones se va reforzando con la generación de
mas y
mas datos que apuntan en una misma dirección.

En la practica existen formas de argumentación que no cumplen con requisitos

de los argumentos deductivos o inductivos, la demostración formal se utiliza
para argumentos deductivos e inductivos debido a que son considerados como
los mas rigurosos y confiables.
 3.1.7 DEMOSTRACIÓN FORMAL.
Un sistema matemático consta de axiomas, definiciones y términos no definidos.
Se suponen verdaderos los axiomas.
Las definiciones se utilizan para crear conceptos nuevos en términos de los existentes.
Algunos términos no se definen en forma explicita, sino que se definen en forma implícita
mediante los axiomas.
Dentro de un sistema matemático es posible deducir teoremas.
Un Teorema es una proposición cuya verdad se ha demostrado. Es decir, resulta del
planteamiento del problema, también se le llama argumento.
Un argumento que establece la verdad de un teorema es una demostración. Los argumentos
lógicos son razonamientos resultantes del enunciado de un problema que es posible
representar, usando notación lógica
La lógica es una herramienta para el análisis de las demostraciones.
Los teoremas representados con notación lógica, producto de un razonamiento, se pueden
demostrar usando los métodos: Directo y por contradicción. Métodos de demostración deductivos
DEMOSTRACIÓN POR EL
MÉTODO DIRECTO
Una demostración directa comienza con las hipótesis consideradas verdaderas, seguidas de las
tautologías y reglas de inferencia necesarias, hasta llegar a la conclusión, para demostrar la
validez del teorema.
En la demostración se deben de colocar primero las hipótesis, seguidas de las proposiciones
obtenidas al aplicar reglas de inferencia, tautologías y equivalencias lógicas, hasta llegar a la
conclusión.
Todas las líneas de la demostración se deben de numerar, con el fin de evitar
confusiones en la obtención de nuevas proposiciones que se deben considerar
verdaderas.
1.- p1
proposiciones
iniciales
2.- p2 …..
proposiciones
obtenidas de aplicar

….. (m-1).- pm-1

reglas, tautologías,
consideradas equivalencias lógicas
Verdaderas
(hipótesis)
n.- pn m.- q conclusión
 EJEMPLO DE MÉTODO DIRECTO

“Si trabajo o ahorro, entonces comprare una casa. Si compro una casa, entonces
podre guardar el coche en mi casa. Por consiguiente, si no puedo guardar el coche en mi casa,
entonces no ahorro.”
Proposiciones: [(p v q) → r] ^[r→s] [s' →q']
p: Trabajo,
q: Ahorro. hipótesis conclusión
r: Comprare una casa.
s: Podre guardar el coche en mi casa. 1. (p v q) →r hipótesis
2. r →s hípótesis
3.
4.
5.
6.
7.
DEMOSTRACIÓN POR CONTRADICCIÓN

El procedimiento de la demostración por contradicción es semejante al del método directo, con la

diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino
que además se incluye una línea con la negación de la conclusión.
Se debe de tener presente que el objetivo de la demostración es llegar a una
contradicción de la forma

(p ^ p’ ) ≡ 0
La demostración por contradicción del teorema

[(p v q) → r] ^ [r→s] [s' →q']

1 (p v q) → r Hipótesis
2 r →s Hipótesis
3 (s' →q’)’ Negación de la conclusión
4 3; variante de la condicional (24b)
5 4; doble negación (17)
6 5; simplificación (11) izq
7 5; simplificación (11) der
8 1,2; silogismo hipotético (13)
9 8; contrapositiva (23
10 9; ley de De Morgan (22a)
11 6,10; modus ponens (15)
12 11; simplificación (11)
13 7,12; conjunción (14)
14 0 14; contradicción (26
REPRESENTAR EL SIGUIENTE ENUNCIADO EN FORMA DE TEOREMA USANDO NOTACIÓN LÓGICA, Y HACER
LA DEMOSTRACIÓN FORMAL MEDIANTE EL MÉTODO DIRECTO Y POR CONTRADICCIÓN.

“Si no le acelero al automóvil, entonces el automóvil no correrá. Si no le freno al

automóvil, entonces el automóvil no se detendrá. Si el automóvil no corre o no se detiene,
entonces el automóvil esta fallando. De tal manera que si el automóvil no esta fallando,
entonces puedo acelerar y frenar el automóvil. ”
“Si el mar está tranquilo, entonces el cielo está despejado y hace calor. Si el
cielo está despejado o viajare en lancha, entonces se verán las estrellas en la
noche. Viajaré en lancha o el mar esta tranquilo. Por tanto, se verán las
estrellas en la noche”
“Si tengo mucho dinero o estoy muy carita, entonces las
muchachas me quieren. Ninguna quiere salir conmigo. Si las
muchachas me quieren, entonces todas quieren salir conmigo. Por
lo tanto, no tengo mucho dinero."
DEMOSTRAR POR EL MÉTODO DIRECTO EL TEOREMA
3.2 LÓGICA DE PREDICADOS.
La lógica de proposiciones es muy buena para inferir información cuando es posible determinar
claramente si una proposición es falsa o verdadera, pero en la vida real prácticamente nada es totalmente
falso o totalmente verdadero, ya que influyen muchos factores.
El problema de la lógica de proposiciones es que no puede trabajar con proposiciones en donde una
gran cantidad de elementos cumplen con ciertas características y otros no.
La lógica de predicados o lógica de conjuntos, se basa en que las proposiciones son conjuntos de
elementos que tienen una propiedad o característica llamada “predicado”, y en este
contexto una proposición puede ser verdadera para un grupo de elementos de un conjunto, pero falsa
para otro.
 EJEMPLO
Definir el conjunto universo, dominio o universo del discurso

Sean:

U = {x | x es un habitante del continente africano}

p: “Hablan francés"
A partir de esto se tiene que
p(x): “x habla francés” predicado
o bien

Cuantificador p(x): “Todos los africanos hablan francés”

universal
“Para toda” x x p(x): “Todos los africanos hablan francés” x p(x) x ∈U
x p(x): “Algún o algunos africanos hablan francés” ” x p(x) x ∈U
Cuantificador
existencial
“Existe algún” x
 p(x,y): “ x asalta a y”
“Todos los ladrones de México, asaltaron a todas las personas
victimas de asalto en México”

EJEMPLO
A = {x | x es un ladrón de México}
B = {y | y es una persona que ha sido asaltada en México}
Permiten saber el significado correcto de los
p: “Asaltaron a” enunciados y no el orden de los cuantificadores
(indican solamente la cantidad de elementos del
A partir de aqui se plantea que: Posición de losparámetros
dominio que están sometidos al predicado)
x y p(x, y): Todos los ladrones de México asaltaron a todas las victimas de asalto en México
y x p(x, y): Todos los ladrones de México asaltaron a todas las victimas de asalto en México
y x p(y, x): Todas las victimas de asalto en México asaltaron a todos los ladrones de México
x y p(x, y): Todos los ladrones de México asaltaron a algunas victimas de asalto en México
y x p(y, x): Algunas victimas de asalto de México asaltaron a todos los ladrones de México
y x p(y, x): Algunas victimas de asalto de México asaltaron a algunos ladrones de México
 EJERCICIO
U= {x,y | x ∈ Z+ ^ y ∈Z+}
p: (x-1) ≤ y p(x): “ x, y ∈ Z+ que cumplen (x-1) ≤ y”
“Toda x y toda y ∈ Z+ que cumplen (x-1) ≤ y”
Escribe el enunciado de cada una de las siguientes notaciones y evalúalas (Verdadero o Falso)

E)∃ x ∃ y [p(x,y)] ≡ ∃ y ∃ x[p(x,y)] x,y ∈U

A) ∀y ∃ x [p(x,y)] x,y ∈U

F) ∀x ∀y [p(x,y)] ≡ ∀ y ∀ x [p(x,y)] x,y ∈U

B) ∃ y ∀x[p(x,y)] x,y ∈U

C) ∀x ∃ y [p(x,y)] x,y ∈U

D) ∃ y ∀x [p(x,y)] x,y ∈U
CONSIDERACIONES

A diferencia del calculo de proposiciones, el calculo de predicados utilizan variables.

Encalculo de predicados se tienen elementos mas simples para formar expresiones
atómicas, a diferencia de una proposición simple donde suvalor es verdadero falso
de acuerdo a una interpretación, en calculo de predicados el valor de verdad
depende de los componentes que forman el predicado.
Ejemplo: Juan es padre de Pedro es una expresión en calculo de predicados, que en
general podría ser: x es padre de y o simplemente p(x,y)
Entonces, se tiene una proposición abierta que depende de dos variables, y que por
supuesto el valor de verdad depende de los valores que le demos a las variables.
Un predicado puede tener una o mas variables y las variables pueden tomar valores
de un conjunto especificado llamado DOMINIO.
CONSIDERACIONES

Cuando se trata del mismo cuantificador y el conjunto del discurso es el mismo tanto para x como para y
no importa el orden en que sean colocados los cuantificadores, ya que el significado es el mismo siempre
y cuando no cambien de posición los parámetros dentro del paréntesis.
CONSIDERACIONES

Se debe tener cuidado cuando se tienen cuantificadores Universal y

existencial en un mismo predicado, pero donde x, y no pertenecen al mismo
conjunto del discurso, ya que el resultado no necesariamente se conserva.
El numero de argumentos de un predicado debe ser constante de tal forma
que p(a, b) es diferente de p(a, b, c). Sin embargo p(x) es equivalente a
p(w), siempre y cuando x y w pertenezcan al mismo universo del discurso.
No siempre se tienen frases que contengan las palabras “todos”
o “algunos” , a veces existen enunciados con la palabra
“ninguno” , de forma que ninguno de los elementos del universo
del discurso cumple con la condición.
EJEMPLO

U = {x | x es alumno de la materia de matemáticas para computación}

p: Aprobó el examen de matemáticas para computación
p(x): Todos los alumnos de matemáticas para computación aprobaron
el examen

El enunciado “Ningún alumno aprobó el examen de matemáticas para

computación", se puede representar como:
VARIABLES LIBRES Y VARIABLES LIGADAS

En los predicados pueden existir variables libres y variables ligadas.

Las variables ligadas a un cuantificador se consideran locales a ese predicado,
mientras que las que no tienen cuantificador se consideran libres.
Por ejemplo, en el siguiente predicado:

Son variables libres “w ” y “y".

Se consideran variables ligadas a “x ” y “z ” .
3.2.2 REPRESENTACIÓN Y
EVALUACIÓN DE PREDICADOS.
Para poder asignar un valor de verdad a una
proposición debemos conocer el predicado y
los valores de las variables
VARIABLES Y PARTICULARIZACIONES

En cálculo de predicados tenemos expresiones con variables, las variables pertenecen a un conjunto o
dominio previamente determinado. Por lo que es muy importante definir el dominio cuando
interpretamos una fórmula mediante un predicado específico.
Ejemplo: “x es alumno del ITSJR”
a(x): “alumno del ITSJR”
U={x| x es alumno del ITSJR} a: “es alumno”

La variable, en este caso x, representa un valor cualquiera del dominio dado, y cuando le asignamos un
valor especifico a la variable se llama instancia o lo que en programación se menciona como
particularización.
Juan Pérez es alumno del ITSJR, es la instancia del ejemplo.
Es importante especificar con toda claridad el dominio
3.2.1 CUANTIFICADORES.
Dos casos centrales en el cálculo de predicados se presentan cuando se analiza si el predicado se
cumple para la población completa y cuando se analiza para ver si cumple para un caso en particular al
menos.
Estos dos casos de llaman Universal y Particular o Existencial vienen a ser la interpretación o la
semántica de los símbolos de cuantificadores.
Cuantificador Universal. El cuantificador universal para todo asociado a una expresión de cálculo de
predicados p se representa por la expresión ∀x p(x) y es verdadera cuando todas las instancias de la
fórmula son verdaderas al sustituir la variable x en la fórmula por cada uno de los valores posibles del
dominio.
Cuantificador Existencial. El cuantificador existencial al menos uno o existe uno asociado a una
expresión de cálculo de predicados p se representa por la expresión ∃ x p(x) y es verdadera cuando por
lo menos una instancia de la fórmula es verdadera al sustituir por la variable x uno de los valores
posibles del dominio.
Hay expresiones dentro del español que son muy utilizadas comopor ejemplo:
Todos los alumnos son estudiosos,
Todos los hombres son mortales, o
Todos los alumnos de ISC estudian lógica.
En este caso estamos tomando una parte del dominio para establecer un característica universal, esto se puede
hacer mediante la combinación de dos predicados de una variable conectados mediante una condicional y
tomando el cuantificador universal.
Así por ejemplo: Todos los alumnos son estudiosos se puede representar mediante
∀x [a(x) → e(x)]
donde el predicado
a: alumno, a(x): x es un alumno
e: estudioso, e(x): x es estudioso

x es un elemento de un dominio general que podría ser el de las personas

o cualquier subconjunto deseado.
El dominio juega un papel preponderante, ya que en un conjunto todos los alumnos podrían ser estudiosos y si
cambiamos el conjunto puede ser que ya no sea verdad.
Todos los hombres son mortales se puede representar por
∀x [h(x) → m(x)]
donde
h: es hombre, h(x): “x es hombre”
m: (el predicado) mortal, m(x): “x es mortal”

Todos los pericos son verdes es:

∀x [p(x) → v(x)]
con
p: perico; y p(x): “x es perico”
v: verde. v(x): “x es verde”

A una expresión como las anteriores se le llama Universal Afirmativa.

La expresión Universal Negativa , se representa por
∀x [p(x) → ¬ q(x)]
y en español se lee ningún p cumple q o sea que los que cumplen el predicado p(x) no cumplen el
predicado q(x).
Ejemplo: Ningún alumno llegó tarde se puede representar por
∀x [a(x) → ¬ t(x)]
Donde a: es alumno y t: llegó tarde.

Las siguientes expresiones corresponden a casos particulares y para formarlas se utiliza el cuantificador
existencial, y en lugar del operador condicional se usa la conjunción, así
∃ x [p(x) → q(x)] llamado ParticularAfirmativa y
∃ x [(p(x) → ¬ q(x)] que es la Particular Negativa.
En el primer caso se indica un elemento que cumple las dos condiciones dadas por los predicados y en el
segundo se asegura que hay un elemento que cumple la primera condición pero no la segunda.
Una manera muy simple de combinar estas expresiones mediante una propiedad es utilizando la negación,
pues dos de ellas son las negaciones de las otras dos, de ahí sus nombres de afirmativas y negativas.
REGLAS GENERALES CON UN PREDICADO SIMPLE
Propiedad:
¬ [∀x p(x)] es equivalente a ∃ x [¬ p(x)]
¬ [∀x p(x)] es equivalente a ∀x [¬p(x)]
Ahora, se pueden combinar estos dos resultados con las Universales y Particulares Afirmativas y Negativas y
tenemos lo siguiente.
Teorema:
La negación de la Universal Afirmativa es la Particular Negativa y La negación de la Particular Afirmativa es la
Universal Negativa.
¬ [∀x (p(x) → q(x))] es equivalente a ∃ x [p(x) ^ ¬ q(x)]
¬ [∃x (p(x) ^ q(x))] es equivalente a ∀x [p(x) → ¬q(x)]
De una manera más simple lo que dice la primera fórmula es que la negación de Todos es Alguno No y que la
negación de Alguno es Ninguno
Esto es muy útil en matemáticas y en computación, por ejemplo si se quiere demostrar que no es cierto que todas las
funciones integrables son continuas, basta encontrar una que sea integrable y que no sea continua.
 3.3 ALGEBRA DECLARATIVA.
Lo que algunos llaman álgebra declarativa no es otra cosa que el álgebra
proposicional, o sea, la estructura algebraica que se forma con expresiones
utilizando los conectivos lógicos.

El álgebra declarativa, es poder razonar con una proposición.

En la lógica podemos utilizar operadores y usar nuestro razonamiento para

evaluar estas proposiciones.
Se pueden clasificar en 3 tipos de proposiciones:
1) Lógicas
2) Abiertas
3) Indeterminadas

Empezaremos por definir formalmente cómo se construye una fórmula en lógica.

 CONSTRUCCIÓN DE UNA FORMULA EN LÓGICA
Una expresión sintácticamente correcta se le llama fórmula bien formada (fbf) o
simplemente fórmula y su definición es:
Una fórmula en lógica de proposiciones/predicados se obtiene al aplicar una o más veces
las siguientes reglas:
i. si p es una proposición lógica, es una fbf.
ii. p(x1, x2,…, xn) donde p es un símbolo que representa un predicado y x1, x2,…, xn son
símbolos de variable
iii. si F es una fórmula bien formada (fbf) de lógica de predicados, también lo es (¬F).
iv. si p(x) ,q(x) son fbf de lógica de predicados, entonces también lo es (p(x)*q(x)) donde
* es uno de los operadores binarios: ^, v, →, .
v. ∀x F, donde F es un fórmula en lógica de predicados.
vi. ∃x F, donde F es un fórmula en lógica de predicados. Nota: Cualquier expresión que no se pueda obtener
mediante una aplicación finita de las reglas anteriores,
no es una fórmula bien formada en lógica de
proposiciones
Para saber si una expresión en lógica es una fórmula bien formada construimos su árbol
sintáctico aplicando recursivamente un árbol con una raíz y dos nodos para un
conectivo lógico binario y un árbol con la raíz y un sólo nodo para la negación.
Si las hojas son proposiciones simples o atómicas y cada rama es la aplicación de una
regla recursiva (R ) entonces es una fórmula bien formada (fbf).

ALGORITMO PARA CONSTRUIR UN ARBOL SINTACTICO DE

UNA FÓRMULA EN LÓGICA DE PROPOSICIONES.
1.Escribir la fórmula con un número arriba de cada operador que indique su jerarquía. Se escriben los enteros
positivos en orden, donde el número 1 corresponde al operador de mayor jerarquía. Cuando dos operadores tengan
la misma jerarquía, se le asigna el número menor al de la izquierda.
2.Construir el árbol sintáctico empezando con la fórmula en la raíz y utilizando en cada caso el operador de menor
jerarquía. O sea, del número mayor al menor.
EJEMPLO
1. Compruebe que (p → ¬ q) v (¬ p v r) es una fórmula.
Solución:
i) Seguir los pasos del algoritmo con la fórmula (p → ¬ q) v (¬ p v r)
1. Vemos que los operadores de los paréntesis tienen mayor jerarquía, empezamos por el paréntesis
izquierdo por lo que la fórmula con jerarquías marcadas sería:

2 1 5 3 4
(p → ¬ q) v (¬ p v r)
2. Construir el árbol Sintáctico empezando a descomponer por el operador con el número mayor, seguir
en orden descendiente hasta el último que es el que tiene el número 1.

(p → ¬ q) v (¬ p v r)

(p → ¬ q) (¬ p v r)

p ¬q ¬p r

q p
 Si tenemos las siguientes proposiciones
p: Hoy estudiaré matemáticas
EJEMPLO q: Hoy iré al juego de básquetbol
r: Mañana iré al cine
s: Mañana tendré sesión extra de problemas
Entonces podemos formar las proposiciones compuestas
p ^ q: Hoy estudiaré matemáticas e iré al juego de básquetbol
q v r: Hoy iré al juego de básquetbol o mañana iré al cine
(p ^ q) → r: Si hoy estudio matemáticas y no voy al juego de básquetbol entonces mañana iré al cine
q ^ r: Hoy no iré al juego de básquetbol ni mañana al cine

Genera el árbol sintáctico para la tercera expresión.

 Represente las siguientes expresiones del español utilizando operadores lógicos. Y genera su árbol
sintáctico.
EJEMPLO i) Si voy al teatro o me quedo estudiando en la biblioteca no llegaré temprano a casa.
ii) Hoy llegaré temprano a casa o si compro un libro estudiaré inglés.
iii) Si resuelvo el problema entonces iré al juego de básquetbol o compro un libro.
Sean
p: voy al teatro
q: me quedo estudiando en la biblioteca
r: llegaré temprano a casa
s: compro un libro
t: estudio inglés
u: resuelvo el problema
w: iré al juego de básquetbol

Las expresiones en forma simbólica quedan:

i) (p v q) → ¬r
ii) r v (s → t)

ii) u → (w v s)
3.4 INDUCCIÓN MATEMÁTICA
Una proposición es una oración, frase, igualdad o desigualdad, que puede ser falsa o
verdadera, pero no ambas a la vez.
La inducción matemática se utiliza cuando se desea probar si una expresión matemática
(igualdad o desigualdad) es falsa o verdadera, sin necesidad de representarla con notación
lógica.
Guiseppe Peano (1858–1932) propuso cinco propiedades fundamentales que caracterizan a
los números naturales, conocidos como Axiomas de Peano.
Una de ellas conocida como el Principio de Inducción Matemática es actualmente una
herramienta de uso práctico y teórico principalmente para matemáticos y personas que
trabajan en Ciencias Computacionales.
El principio lo enunciaremos para los enteros positivos Z+, pero bien se puede ampliar a los
números naturales o a cualquier subconjunto de los enteros mayores o iguales a un entero
fijo.
Principio de Inducción Matemática.
Si S en un conjunto de enteros positivos tal que
(B) 1 e S
(I) k e S → (k+1) e S
entonces S contiene todos los enteros positivos.
En el principio de Inducción Matemática son muy importantes los
nombres asociados y en la literatura técnica, como es costumbre,
no se presenta con detalle los pasos, por lo que resulta
indispensable conocer la nomenclatura.
Nomenclatura de Inducción Matemática.
(B) se llama Caso Base o caso inicial
(I) se llama Paso de Inducción
k e S se llama Hipótesis de Inducción
Y todo junto se llama Principio de Inducción Matemática.
Es importante que se comprenda y memorice cada uno de estos conceptos y su
participación directa en la propiedad.
Esencialmente lo que enuncia el principio de inducción matemática es, si logramos
establecer que el primer entero positivo cumple, una propiedad, y si partiendo de que
un entero arbitrario también la cumple, se puede comprobar que el entero siguiente
también tiene la propiedad entonces concluimos que todos los enteros positivos
tienen la propiedad indicada.
Por lo que otra forma de enunciar el Principio de Inducción Matemática es:
Si F(n) es una proposición abierta que involucra enteros y se tiene
(B) F(1) es verdadera; o sea, se que cumple para n=1
(I) F(K) → F(k+1); Si se cumple para n = k entonces también se
cumple para n=k+1.

Concluimos que la proposición es verdadera para todos los enteros positivos.

El Principio de Inducción Matemática se utiliza para demostrar
propiedades, formulas, validarlas y probar que son verdaderas,
usualmente en el conjunto de los números enteros positivos.
Muchas propiedades que incluyen la definición de factorial se
pueden probar por Inducción Matemática, como el Teorema del
Binomio de Newton, el Triángulo de Pascal y algunas
propiedades de combinatoria que involucran combinaciones y
permutaciones.
Otra forma de utilizarla es para proporcionar definiciones y
formalizar conceptos.
EJEMPLO
Demostrar por Inducción Matemática que:
F(n):
Consideremos el conjunto S de los enteros para los cuales la propiedad es cierta.
[B] Si n=1; tenemos:

entonces 1 está en S o sea que se cumple el caso base.

[M] Debemos de llegar a que para n=k+1 también se cumple:
[I] Inducción
[H] Suponemos que cumple para n=k;

[H → M] Sumamos (k+1) de los dos lados de la igualdad

Por lo tanto, podemos concluir que la formula (1) es valida para todos los enteros positivos
Para realizar el Paso de Inducción se debe de partir del caso n=k y llegar mediante pasos válidos al caso n=k+1.
EJEMPLO
Demostrar por Inducción Matemática que:

Σ Es la letra griega sigma mayúscula y en matemáticas significa suma

• [B] Si n=1; tenemos: (6(1)-2) = 1(3(1)+1)
(6-2) = 1(3+1)
4 = 4
entonces 1 está en S o sea que se cumple el caso base.
[M] Debemos de llegar a que para n=k+1 también se cumpla:
[I] Inducción
[H] Suponemos que cumple para n=k;
4+10+16+…+(6k-2)= k(3k+1)
[H→M] Sumando (k+1) a ambos lados
[(6k-2)+(6(k+1))-2] = k(3k+1) + [6(k+1))-2]
6k- 2+6k+6-2 = 3k2+k+6k+6-2
= 3k2 + 7k +4
= (k+1)(3k+4)
= (k+1) (3 (k+1) +1)

Por lo tanto, podemos concluir que la formula es valida para cualquiera que sea el valor
de n
3.5 APLICACIONES DE LA LÓGICA
MATEMÁTICA EN LA COMPUTACIÓN.
La lógica matemática no es de reciente creación, no surgió
con el uso de las computadoras, por el contrario se ha
consolidado en nuestro tiempo porque es una
herramienta fundamental para mejorar el software y
hardware que conocemos.
La historia de la lógica tiene sus inicios en el siglo III a. C.
con la “Teoría silogísta” de Aristóteles, quien introdujo
los cuantificadores y , así
como reglas de inferencia.
APLICACIÓN DEL SILOGISMO HIPOTÉTICO

Esta regla se aplica en matemáticas y programación, algunas veces sin saber que se
trata del silogismo hipotético:

También se encuentra disfrazada en algunas líneas de código de la siguiente manera:

En tiempos remotos Crisipo de Sodi (281-206 a. C.)
introdujo los operadores lógicos de la conjunción ( ^ ), la
disyunción ( v ) , la implicación (→), la disyunción exclusiva
(⊕) y la complementación ('), así como los valores de
“falso” o “verdadero”.
Con esos operadores lógicos, muchos siglos después Augustus De
Morgan (1806-1871) enuncio sus famosas leyes de De Morgan;
que tienen aplicación no solo en lógica matemática sino también
en teoría de conjuntos.
A partir de esta información George Boole (1815-1864) creo el
algebra booleana, la cual tiene amplias aplicaciones en la
construcción de computadoras, robótica y automatización de
sistemas eléctricos, mecánicos y electrónicos.
La lógica matemática también proporciona elementos para la
creación de nuevos lenguajes de programación, al permitir
estructurar sintáctica y semánticamente el lenguaje que se esta
desarrollando.
Otra aplicación importante de la lógica
matemática se encuentra en las bases de
datos, en donde se consideran los archivos
como relaciones que pueden manipularse
por medio de operadores lógicos para
obtener nuevos reportes de información,
dando origen a lo que se conoce como
“algebra relacional” en la cual se basan
todos los manejadores de bases de datos
conocidos.

Las redes de computadoras también utilizan

el concepto de relación para representar la
comunicación entre computadoras, de forma
que es posible realizar operaciones lógicas
entre matrices booleanas para obtener
características necesarias en una red.
La lógica matemática es esencial en la computación ya que permite
sentar las bases para el entendimiento formal de prácticamente todas
las áreas de esta:
➢ bases de datos,
➢ programación,
➢ Inteligencia artificial,
➢ lenguajes formales,
➢ sistemas digitales,
➢ redes, …
La lógica llena el mundo; los
limites del mundo son
también sus limites.
Ludwig Wittgenstein