Download Apuntes de Matematicas Discretas

LOGICA MATEMÁTICA
Introducción.
Aprender matemáticas, física y química “es muy difícil”; así se expresan la
mayoría de estudiantes de todos los niveles, sin embargo pocas veces se busca
una explicación del porqué no aprenden las ciencias exactas los alumnos.
Nuestra teoría es la siguiente: “Los alumnos no aprenden ciencias exactas,
porque no saben relacionar las conocimientos que se proporcionan en la
escuela (leyes, teoremas, formulas) con los problemas que se le presentan
en la vida real”. Otro problema grave es que el aprendizaje no es significativo. El
presente trabajo pretende motivar a los estudiantes para que con ayuda de la
“lógica matemática”, él sea capaz de encontrar estos relacionamientos entre los
diferentes esquemas de aprendizaje, para que de esta manera tenga una buena
estructura cognitiva. Consideramos que si el alumno sabe lógica matemática
puede relacionar estos conocimientos, con los de otras áreas para de esta
manera crear conocimiento.
La lógica estudia la forma del razonamiento, es una disciplina que por medio de
reglas y técnicas determina si un argumento es válido. La lógica es ampliamente
aplicada en la filosofía, matemáticas, computación, física. En la filosofía para
determinar si un razonamiento es válido o no, ya que una frase puede tener
diferentes interpretaciones, sin embargo la lógica permite saber el significado
correcto. En las matemáticos para demostrar teoremas e inferir resultados
matemáticas que puedan ser aplicados en investigaciones. En la computación
para revisar programas. En general la lógica se aplica en la tarea diaria, ya que
cualquier trabajo que se realiza tiene un procedimiento lógico, por el ejemplo;
para ir de compras al supermercado una ama de casa tiene que realizar cierto
procedimiento lógico que permita realizar dicha tarea. Si una persona desea
pintar una pared, este trabajo tiene un procedimiento lógico, ya que no puede
pintar si antes no prepara la pintura, o no debe pintar la parte baja de la pared si
antes no pintó la parte alta porque se mancharía lo que ya tiene pintado, también
dependiendo si es zurdo o derecho, él puede pintar de izquierda a derecha o de
derecha a izquierda según el caso, todo esto es la aplicación de la lógica.
El orden en que se presenta el documento es el siguiente:
Primeramente se establece la importancia de la lógica matemática, después
definimos el concepto de proposición. Se establece el significado y utilidad de
conectivos lógicos para formar proposiciones compuestas. Más tarde
abordamos las proposiciones condicionales y bicondicionales. Definimos
tautología, contradicción y contingente, y proporcionamos una lista de las
tautologías más importantes, así mismo explicamos a que se le llama
proposiciones lógicamente equivalente apoyándonos de tablas de verdad.
Para finalizar; abordamos los métodos de demostración: directo y por
contradicción, en donde incluye reglas de inferencia.
Es importante mencionar que en las demostraciones no hay un solo camino para llegar
al resultado. El camino puede ser mas largo o más corto dependiendo de las reglas de
inferencia y tautologías que el alumno seleccione, pero definitivamente deberá llegar al
resultado.
La lógica de proposiciones es el antecedente histórico del Álgebra de Boole
y está basada en la lógica clásica o tradicional. Se explicarán algunos
conceptos básicos tendientes a establecer una expresión lógica simbólica a
partir de un enunciado.
Desarrollo.
La lógica matemática es la disciplina que trata de 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; en las ciencias física y
naturales, para sacar conclusiones de experimentos; y en las ciencias sociales
y en la vida cotidiana, para resolver una multitud de problemas. Ciertamente se
usa en forma constante el razonamiento lógico para realizar cualquier actividad.
Proposiciones y operaciones lógicas.
Una proposición o enunciado es una oración 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.
A continuación se tienen algunos ejemplos de proposiciones válidas y no
válidas, y se explica el porqué algunos enunciados no son proposiciones. Las
proposiciones se indican por medio de una letra minúscula, dos puntos y la
proposición propiamente dicha. Ejemplo.
p:
La tierra es plana.
q:
-17 + 38 = 21
r:
x > y-9
s:
El Morelia será campeón en la presente temporada de Fut-Bol.
t:
Hola ¿como estas?
w:
Lava el coche por favor.
Los incisos p y q sabemos que pueden tomar un valor de falso o verdadero;
por lo tanto son proposiciones validas. El inciso r también es una proposición
valida, aunque el valor de falso o verdadero depende del valor asignado a las
variables x y y en determinado momento. La proposición del inciso s también
esta perfectamente expresada aunque para decir si es falsa o verdadera se
tendría que esperar a que terminara la temporada de fut-boll. Sin embargo los
enunciados t y w no son válidos, ya que no pueden tomar un valor de falso o
verdadero, uno de ellos es un saludo y el otro es una orden.
Conectivos lógicos y proposiciones compuestas.
Existen conectores u operadores lógicas que permiten formar proposiciones
compuestas (formadas por varias proposiciones). Los operadores o conectores básicos
son:
Operador and (y)
Se utiliza para conectar dos proposiciones que se deben cumplir para que se
pueda obtener un resultado verdadero. Si símbolo es: {, un punto (.), un
paréntesis}. Se le conoce como la multiplicación lógica:
Ejemplo.
Sea el siguiente enunciado “El coche enciende cuando tiene gasolina en el
tanque y tiene corriente la
q
r
p=qr
batería”
1
1
1
1
0
0
Sean:
0
1
0
0
0
0
p: El coche enciende.
q: Tiene gasolina el tanque.
r: Tiene corriente la batería.
De tal manera que la representación del enunciado anterior usando simbología
lógica es como sigue:
p= qr
Su tabla de verdad es como sigue:
Donde.
1 = verdadero
0 = falso
En la tabla anterior el valor de q=1 significa que el tanque tiene gasolina, r=1
significa que la batería tiene corriente y p = q  r=1 significa que el coche
puede encender. Se puede notar que si q o r valen cero implica que el auto no
tiene gasolina y que por lo tanto no puede encender.
Operador Or (o)
Con este operador se obtiene un resultado verdadero cuando alguna de las
proposiciones es verdadera. Se eindica por medio de los siguientes símbolos:
{,+,}. Se conoce como las suma lógica. Ejemplo.
Sea el siguiente enunciado “Una persona puede entrar al cine si compra su
boleto u obtiene un pase”. Donde.
p: Entra al cine.
q: Compra su boleto.
r: Obtiene un pase.
q
r
q
1
1 1
1 0
0 0
0
1
0
1
0
La única manera enla que no puede
ingresar al cine (p=0), es que no
compre su boleto (q=0) y que no
obtenga un pase (r=0).
r
p=qr
p =q
1 r
1
1
0
0
11
0
01
0
0
Operador Not (no)
Su función es negar la proposición. Esto significa que sí alguna proposición es
verdadera y se le aplica el operador not se obtendrá su complemento o
negación (falso). Este operador se indica por medio de los siguientes símbolos:
{‘, ,}. Ejemplo.
La negación de estálloviendo en este momento (p=1), es no está lloviendo en
este momento(p’=0)
p
1
0
p’
0
1
Además de los operadores básicos (and, or y not) existe el operador xor, cuyo
funcionamiento es semejante al operador or con la diferencia en que su
resultado es verdadero solamente si una de las proposiciones es cierta, cuando
ambas con verdad el resultado es falso.
En este momento ya se pueden representar con notación lógica enunciados
más complejos. Ejemplo
Sean las proposiciones:
p: Hoy es domingo.
q: Tengo que estudiar teorías del aprendizaje.
r: Aprobaré el curso.
El enunciado: “Hoy es domingo y tengo que estudiar teorías de aprendizaje o
no aprobaré el curso”. Se puede representar simbólicamente de la siguiente
manera:
p  q r
Por otro lado con ayuda de estos operadores básicos se pueden formar los
operadores compuestos Nand (combinación de los operadores Not y And), Nor
(combina operadores Not y Or) y Xnor (resultado de Xor y Not).
LENGUAJE PROPOSICIONAL
Sintaxis
El primer paso en el estudio de un lenguaje es definir los símbolos básicos que lo
constituyen (alfabeto) y cómo se combinan para formar sentencias. Está
constituido por:




Símbolos de veracidad: V para verdadero y F para falso.
Símbolos de variables: p, q, r, s, ...
Símbolos de conectivas:
Negación
 NO
Y
Conjunción

O
Disyunción inclusiva

Disyunción exclusiva
 O..O
 SI..ENTONC Condicional
ES
Bicondicional
 SI Y SOLO
SI
Símbolos de puntuación: ( , ), para evitar ambigüedades.
Reglas de formación
Las clases de sentencias bien formadas se definen por reglas puramente sintácticas,
llamadas reglas de formación, y que son:






Una variable proposicional es una sentencia bien formada.
Una sentencia bien formada precedida de la negación es una sentencia bien formada.
Dos sentencias bien formadas unidas por una de las partículas conectivas binarias
constituye una sentencia bien formada.
Se pueden omitir los paréntesis que encierran una sentencia completa.
El estilo tipográfico de los paréntesis se puede variar para hacerlos más evidentes
usando corchetes y llaves.
A las conjunciones y disyunciones se les puede permitir tener más de dos
argumentos.
Conectivas
Las conectivas se dividen por su aplicación en:


Singulares: se aplican a una única sentencia.
Binarias: se aplican a dos sentencias.
Por su definición, también se pueden dividir en:

Primitivas: las variables proposicionales, los paréntesis y las conectivas NO y O.
Definidas: las conectivas Y, SI ... ENTONCES, ... SI Y SOLO SI ... y O ... O.
Proposiciones condicionales.
Una proposición condicional, es aquella que está formada por dos
proposiciones simples (o compuesta) p y q. La cual se indica de la siguiente
manera:
pq
Se lee “Si p entonces q”
Ejemplo.
El candidato del PRI dice “Si salgo electo presidente de la República recibirán
un 50% de aumento en su sueldo el próximo año”. Una declaración como esta
se conoce como condicional. Su tabla de verdad es la siguiente:
Sean
p: Salió electo Presidente de la República.
q: Recibirán un 50% de aumento en su sueldo el próximo año.
De tal manera que el enunciado se puede expresar de las siguiente manera.
pq
Su tabla de verdad queda de la siguiente manera:
p
1
1
0
0
q
1
0
1
0
pq
1
0
1
1
La interpretación de los resultados de la tabla es la siguiente:
Considere que se desea analizar si el candidato presidencial mintió con la
afirmación del enunciado anterior. Cuando p=1; significa que salió electo, q=1
y recibieron un aumento de 50% en su sueldo, por lo tanto p  q =1; significa
que el candidato dijo la verdad en su campaña. Cuando p=1 y q=0 significa que
p  q =0; el candidato mintió, ya que salió electo y no se incrementaron los
salarios. Cuando p=0 y q=1 significa que aunque no salió electo hubo un
aumento del 50% en su salario, que posiblemente fue ajeno al candidato
presidencial y por lo tanto; tampoco mintió de tal forma que p  q =1.
APLICACIONES
1.1
NEGACIÓN
p p'
F V
V F
1.2
CONJUNCIÓN
p q pvq
F
F
V
V
1.3
DISYUNCIÓN INCLUSIVA
F
V
F
V
F
F
F
V
p q pwq
F
F
V
V
1.4
DISYUNCIÓN EXCLUSIVA
p q pq
F
F
V
V
1.5
F
V
F
V
F
V
V
F
CONDICIONAL
p q p6q
F
F
V
V
1.6
F
V
F
V
V
V
F
V
BICONDICIONAL
F
V
F
V
F
V
V
V
p q pq
F
F
V
V
F
V
F
V
V
F
F
V
Proposición bicondicional.
Sean p y q dos proposiciones entonces se puede indicar la proposición
bicondicinal de la siguiente manera:
pq
Se lee “p si solo si q”
Esto significa que p es verdadera si y solo si q es también verdadera. O bien p
es falsa si y solo si q también lo es. Ejemplo; el enunciado siguiente es una
proposición bicondicional
“Es buen estudiante, si y solo si; tiene promedio de diez”
Donde:
p: Es buen estudiante.
q: Tiene promedio de diez.
por lo tanto su tabla de verdad es.
p
1
1
0
0
q
1
0
1
0
pq
1
0
0
1
La proposicióncondicional solamente
es verdadera si tanto p como q son
falsas o bien ambasverdaderas
A partir de este momento, ya se está en condiciones de representar cualquier enunciado
con conectores lógicos.
Ejemplo.
Sea el siguiente enunciado “Si no pago la luz, entonces me cortarán la
corriente eléctrica. Y Si pago la luz, entonces me quedaré sin dinero o pediré
prestado. Y Si me quedo sin dinero y pido prestado, entonces no podré pagar
la deuda, si solo si soy desorganizado”
Donde:
p: Pago la luz.
q: Me cortarán la corriente eléctrica.
r: Me quedaré sin dinero.
s: Pediré prestado.
t: Pagar la deuda.
w: soy desorganizado.
(p’  q)  p  (rs)   (r s)  t’   w



Tautología: es la sentencia que es verdadera.
Contradicción: es la sentencia que es falsa.
Indeterminación: es la sentencia que ni es verdadera ni falsa
Tablas de verdad.
En estos momentos ya se está en condiciones de elaborar cualquier tabla de verdad. A
continuación se presenta un ejemplo para la proposición [(pq) (q’r)  (rq).
p
0
0
0
0
1
1
1
1
q
0
0
1
1
0
0
1
1
r
0
1
0
1
0
1
0
1
q’ pq (q’r)
1
1
0
1
1
1
0
1
0
0
1
0
1
0
0
1
0
1
0
1
0
0
1
0
(pq) (q’r)
1
1
1
1
0
1
1
1
rq
1
0
1
1
1
0
1
1
[(pq) (q’r)  (rq)
1
0
1
1
0
0
1
1
El
número de líneas de la tabla de verdad depende del número de variables de la
expresión y se puede calcular por medio de la siguiente formula.
No de líneas = 2n
Donde n = número de variables distintas.
Es importante destacar a medida que se avanza en el contenido del material el
alumno deberá participar activamente. Estos significa que cuando se esta
definiendo proposiciones y características propias de ellas, además de los
ejemplos que el maestro explique, el alumno deberá citar proposiciones
diferentes, deberá entender el porque un enunciado no es válido. Cuando se
ven conectores lógicos, los alumnos deberán saber emplearlos en la
representación de proposiciones más complejas. Pero algo muy importante, es
que los ejemplo que el maestro y los alumnos encuentren en la clase, deben
ser de interés para el estudiante. Cuando se ven tablas de verdad el alumno
deberá saber perfectamente bien el porque de cada uno de los resultados. En
pocas palabras el conocimiento deberá ser significativo.
.
La tabla de verdad para 2 letras sentenciales es:
p q
F
F
V
V
F
V
F
V
Lo cual indica que dadas dos letras sentenciales hay para ellas 22 posibles
combinaciones y en general para n letras, hay 2n combinaciones.
.
La tabla de verdad de p 6 q :se
p q p6q
F
F
V
V
F
V
F
V
V
V
F
V
Sólo en este caso, a la letra sentencial p se le denomina antecedente y a la
letra sentencial q se le denomina consecuente.
Tautología y contradicción.
Tautología, es aquella proposición (compuesta) que es cierta para todos los
valores de verdad de sus variables. Un ejemplo típico es la contrapositiva cuya
tabla de verdad se indica a continuación.
p
0
0
1
1
q
0
1
0
1
p’
1
1
0
0
q’
1
0
1
0
pq
1
1
0
1
q’p’
1
1
0
1
(pq)(q’p’)
1
1
1
1
Note que en las
tautologías
para
todos los valores de verdad el resultado de la proposición es siempre 1. Las tautologías son
muy importantes en lógica matemática ya que se consideran leyes en las cuales nos podemos
apoyar para realizar demostraciones.
A continuación me permito citar una lista de las tautologías más conocidas y
reglas de inferencia de mayor uso en las demostraciones formales que
obviamente el autor no consideró..
1.- Doble negación.
a).
p''Ûp
2.- Leyes conmutativas.
a).
(pÚq)Û(qÚp)
b).
(pÙq)Û(qÙp)
c).
(p«q)Û(q«p)
3.- Leyes asociativas.
a).
[(pÚq)Úr]Û[pÚ(qÚr)]
b.
[(pÙq)Ùr]Û[pÙ(qÙr)]
4.- Leyes distributivas.
a).
[pÚ(qÙr)]Û[(pÚq)Ù(pÚr)]
b.
[pÙ(qÚr)]Û[(pÙq)Ú(pÙr)]
5.- Leyes de idempotencia.
a).
(pÚp)Ûp
b).
(pÙp)Ûp
6.- Leyes de Morgan
a).
(pÚq)'Û(p'Ùq')
b).
(pÙq)'Û(p'Úq')
c).
(pÚq)Û(p'Ùq')'
b).
(pÙq)Û(p'Úq')'
7.- Contrapositiva.
a).
(p®q)Û(q'®p')
8.- Implicación.
a).
(p®q)Û(p'Úq)
b).
(p®q)Û(pÙq')'
c).
(pÚq)Û(p'®q)
d).
(pÙq)Û(p®q')'
e).
[(p®r)Ù(q®r)]Û[(pÙq)®r]
f).
[(p®q)Ù(p®r)]Û[p®(qÙr)]
9.- Equivalencia
a).
(p«q)Û[(p®q)Ù(q®p)]
10.- Adición.
a).
pÞ(pÚq)
11.- Simplificación.
a).
(pÙq)Þp
12.- Absurdo
a).
(p®0)Þp'
13.- Modus ponens.
a).
[pÙ(p®q)]Þq
14.- Modus tollens.
a).
[(p®q)Ùq']Þp'
15.- Transitividad del «
a).
[(p«q)Ù(q«r)]Þ(p«r)
16.- Transitividad del ®
a).
[(p®q)Ù(q®r)]Þ(p®r)
17.- Mas implicaciones lógicas.
a).
(p®q)Þ[(pÚr)®(qÚs)]
b).
(p®q)Þ[(pÙr)®(qÙs)]
c).
(p®q)Þ[(q®r)®(p®r)]
18.- Dilemas constructivos.
a).
[(p®q)Ù(r®s)]Þ[(pÚr)®(qÚs)]
b).
[(p®q)Ù(r®s)]Þ[(pÙr)®(qÙs)]
Se puede observar que al construir las tablas de verdad en los ejemplos anteriores, se
presentaron tres casos:
1. La tabla de verdad de la fórmula dada contenía tantos verdaderos (V) como falsos (F)
2. La tabla de verdad de la fórmula dada contenía sólo falsos (F)
3. La tabla de verdad de la fórmula dada contenía sólo verdaderos (V)
La fórmula del primer tipo se denomina indeterminada. Las fórmulas del segundo tipo se
denominan contradicciones y las del tercer tipo se denominan tautologías o fórmulas
sentencialmente válidas.
i.
ii.
iii.
IDENTIDAD:
CONTRADICCIÓN:
TERCERO EXCLUIDO:
p6p;pp
[p v (p')]'
[p w (p')]
Lo cierto es que en esta parte, la tautología se usará para determinar la validez de un
argumento.
Un argumento es un enunciado en el cual, de un conjunto de premisas (A, B, C, D,...,
etc.), se obtiene una premisa llamada conclusión Q. Cada premisa puede estar formada por
una o más proposiciones.
Luego entonces, se dice que un argumento es válido si la tabla de verdad formada de la
siguiente manera:
(A v B v C v D
)... 6 Qse ; anu
aígolotuat
Contradicción es aquella proposición que siempre es falsa para todos los valores de verdad,
una de las mas usadas y mas sencilla es pp’ . Como lo muestra su correspondiente tabla de
verdad.
p
0
1
p’
1
0
pp’
0
0
Si en el ejemplo anterior
p: La puerta es verde.
La proposición pp’ equivale a decir que “La puerta es verde y la puerta no es
verde”. Por lo tanto se esta contradiciendo o se dice que es una falacia.
Una proposición compuesta cuyos resultados en sus deferentes líneas de la
tabla de verdad, dan como resultado 1s y 0s se le llama contingente.
Equivalencia lógica.
Se dice que dos proposiciones son lógicamente equivalentes, o simplemente
equivalentes. Si coinciden sus resultados para los mismo valores de verdad.
Se indican como p  q.
Considero que un buen ejemplo es el que se estableció para ilustrar la
tautología en donde se puede observar que las columnas de (pq) y (q’p’)
para los mismo valores de verdad, por lo tanto se puede establecer que (pq)
 (q’p’)
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 se les llama reglas de inferencia.
Las reglas de inferencia permiten relacionar dos o más tautologías o hipótesis
en una demostración.
Ejemplo 1
¿Es valido el siguiente argumento?.
Si usted invierte en el mercado de valores, entonces se hará rico.
Si se hace usted rico, entonces será feliz.
____________________________________________________
Si usted invierte en el mercado de valores, entonces será feliz.
Sea:
p: Usted invierte en el mercado de valores.
q: Se hará rico.
r: Será feliz
De tal manera que el enunciado anterior se puede representar con notación
lógica de la siguiente manera:
pq
qr
______
pr
Ejemplo 2.
¿Es valido el siguiente argumento?.
1. Reglas de inferencia.- Las reglas de inferencia pueden ser aplicadas a
ciertas fbf's y un conjunto de fbf's para producir nuevas fbf's.
o Modus Ponens Es la operación que produce la
fórmula bien formada , de la fbf y de la fbf
.
o
Especialización Universal. Es la operación que
produce la fbf
de la de fbf
, cuando A es
cualquier símbolo constante. Usando Modus Ponens
y Especializaciín Universal producimos la fbf
de las fbf
y
.
o
Las reglas de inferencia, entonces, producen nuevas fbf's derivadas de algunas
otras fbf's y las denominamos en el cálculo de predicados teoremas. Una
secuencia de aplicaciones de reglas de inferencia constituyen una prueba del
teorema.
TIPOS DE REGLAS DE INFERENCIA
La deducción directa
Un argumento es un conjunto de enunciados o proposiciones entre los cuales una proposición final, llamada
conclusión, se sigue de las otras proposiciones o premisas. Pues bien, llamamos deducción a un modo de argumentar
tal que el paso de las premisas a la conclusión es necesario.
La deducción formal o lógica consiste en que a partir de unas premisas, representadas con símbolos, y a través de
unas reglas, obtenemos una conclusión (deducimos la conclusión).
Los símbolos en la lógica de enunciados pueden ser:
Los conectores o juntores: ¬, &, V, ->, <->
Letras enunciativas: p, q, r...etc, que representan los enunciados de la argumentación.
Símbolos auxiliares: ( ), I- (este último signo se utiliza para indicar formalmente la conclusión):
Ejemplo: "si graniza (g) o nieva (n) entonces, uso paraguas (p) o no salgo de casa (¬s) . Se da el caso de que graniza
(g) . Por lo tanto, no salgo de casa (¬s) ".
La formalización de este argumento es la siguiente:
( g V n ) -> ( p V ¬s ) , g I- ¬s
Ahora bien; la deducción puede ser directa e indirecta.
Por deducción directa entendemos aquella en la cual, a través de las premisas, obtenemos la conclusión de un modo
directo:
Ejemplo: Si vienes pronto, podremos ir al cine. Has venido pronto. Conlusión: vamos al cine.
Formalicémoslo: p -> c, p I- c
Ahora bien ¿Cómo se lleva a cabo la deducción formal o derivación?
El primer paso consiste en escribir las premisas iniciales con las que contamos, numerándolas y anteponiendo a la
numeración un guión horizontal.
En el segundo paso, aplicando sobre las premisas las reglas de derivación que luego veremos, numeramos las
derivaciones que se extraigan de ellas, pero en este caso no le antecedemos a los níumeros que le correspondan
ningún guión. El último número corresponde con la obtención de la conclusión deseada. Veámoslo:
Tomando como ejemplo la formulación anterior, tendremos que derivar c (la conclusión), de las premisas p -> c y c
-1 p -> c
-2 p
3 c MP 1,2
Las letras que siguen a la línea de derivación tres se corresponden con las iniciales de la regla de cálculo utilizada, en
este caso, el Modus Ponens: dada una implicación cualquiera, si se da el antecedente, entonces necesariamente
podemos inferir el consecuente (esto se verá en el próximo capítulo). La numeración que sigue al nombre de la regla
se refiere a las líneas sobre las que se ha aplicado dicha regla .
Derivemos la siguiente fórmula utilizando el Modus Ponens: p -> ( q -> r ), p -> q, p I- r
- 1 p -> ( q -> r )
- 2 p -> q
-3p
4 q -> r MP 1,3
5 q MP 2,3
6 r MP 4,5
La deducción indirecta o reducción al absurdo ( reductio ad absurdum)
En este tipo de deducción obtenemos la conclusión de modo indirecto, negando la misma conclusión
hasta llegar a una contradicción.
Los pasos de la reducción al absurdo son los siguientes:
1.
2.
3.
4.
Suponemos hipotéticamente la falsedad de la conclusión: ¬p
Esta suposición nos conduce a una contradicción: ( q & ¬q )
Negamos, por lo tanto, la falsedad de la suposición: ¬ ( ¬p )
Afirmamos la conclusión deseada: p
Antes de realizar un ejemplo concreto sobre la reducción al absurdo conviene que veamos las reglas
en las que se fundamenta la deducción: las llamadas reglas de inferencia.
SEMANTICA
Negación (NO)
Consiste en cambiar el valor de verdad de una variable proposicional.
p
p
========
V
F
F
V
Disyunción inclusiva (O)
La sentencia será verdadera cuando una o ambas variables proposicionales sean
verdaderas.
p q
pq
=============
V V
V
V F
V
F V
V
F F
F
Conjunción (Y)
Es una conectiva definida por:
p  q   ( p  q )
La sentencia será verdadera sólo cuando ambas variables proposicionales sean
verdaderas.
p q
pq
=============
V V
V
V F
F
F V
F
F F
F
Condicional (SI ... ENTONCES)
Es una conectiva definida por:
pq ¬pq
La sentencia será verdadera cuando se cumpla si es válido p entonces lo es q.
p
q
p q
=====================
V
V
V
V
F
F
F
V
V
F
F
V
Bicondicional (... SI Y SOLO SI ...)
Es una conectiva definida por:
p  q  ( ( p  q ) ( q  p ) )
La sentencia será verdadera cuando ambas variables proposicionales sean iguales.
p
q
p q
==================
V
V
V
V
F
F
F
V
F
F
F
V
Disyunción exclusiva (O ... O)
Es una conectiva definida por:
p  q  ( p q )
La sentencia será verdadera sólo cuando una de las dos variables proposicionales sea
verdadera.
p q
pq
=============
V V
F
V F
V
F V
V
F F
F
Axiomas y reglas
Los axiomas para el cálculo proposicional son:




(pp)p
q  ( p q )
(pq)(qp)
(pq)[(rp)(rq)]
A partir de estos axiomas y aplicando las dos reglas de transformación siguientes se
puede demostrar cualquier teorema:


Regla de sustitución: el resultado de reemplazar cualquier variable en un teorema
por una sentencia bien formada es un teorema.
Regla de separación: si S y ( S  R ) son teoremas, entonces R es un teorema.
Relativo a un criterio de validación, un sistema axiomático debe cumplir las siguientes
propiedades:




Debe ser lógico o razonable: en el sentido de que todo teorema es una tautología.
Completo: toda sentencia bien formada v lida es un teorema y se debe poder
demostrar a partir de los axiomas.
Consistente: no se pueden demostrar como teoremas, sentencias bien formadas que
no sean tautologías.
Deben ser independientes: ningún axioma debe ser derivable a partir de los otros.
Concepto de Relación
Una relación puede considerarse como un cuadro que muestra las
correspondencias de unos elementos con respecto a otros.
Se establecen relaciones entre elementos de dos conjuntos, desde el conjunto
de partida hacia el conjunto de llegada.
Relación Binaria
Una relación binaria R de un conjunto X a un conjunto Y es un subconjunto
del producto cartesiano X x Y. Si (x,y) Î R se escribe xRy y se dice que x está
relacionado con y. En el caso X=Y se afirma que R es una relación binaria
sobre X.
El conjunto
{x Î X | (x,y) Î R para algún y Î Y} ,
se llama dominio de R.
El conjunto
{y Î Y | (x,y) Î R para algún x Î X},
se llama contradominio o ámbito de R.
Ejemplo:
Sea R la relación sobre X={1,2,3,4} definida por (x,y) Î R si x <= y, x, y Î X.
Entonces
R={(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
Representación de una relación binaria mediante su respectivo grafo
dirigido
Para establecer el digrafo de una relación en un conjunto X, se marcan
primero los puntos o vértices que representan los elementos de X. A
continuación, si el elemento (x,y) está en la relación, se traza una flecha (arco
dirigido) desde x hasta y.
La gráfica correspondiente al ejemplo mencionado es: