Download RECESION (Reseña)

Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
TEMA 1: LOGICA
Introducción
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áticas, para demostrar
teoremas e inferir resultados matemáticos que puedan ser aplicados en
investigaciones. En la computación para desarrollar o 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, un 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 (según el tipo de
pintura), 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.
La lógica permite resolver incluso problemas a los que nunca se ha enfrentado
el ser humano, utilizando solamente su inteligencia y apoyándose de algunos
conocimientos acumulados, se pueden obtener nuevos inventos innovaciones a
los ya existentes o simplemente utilización de los mismos.
Su estudio es importante pues nos ayuda a razonar de forma correcta y con
ello, no incurrir en las llamadas falacias argumentativas. Las leyes de la
deducción son innatas en los seres humanos, sin embargo, su uso no es obligado
y pueden ser ignoradas, incluso sin darnos cuenta.
Terminología
En matemática se tienen algunas palabras “no definidas”, cuyo significado
suponemos conocido y que sirven para definir otras palabras, que reciben el
nombre de términos primitivos; como por ejemplo “punto”.
Por otra parte, se entiende por definición el significado que se le da a una
palabra o noción, con el fin de que todos universalmente entendamos lo mismo
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
cuando ésta se utiliza. Es decir, la definición describe y caracteriza los objetos
matemáticos a tratar.
Los términos primitivos y los definidos se combinan (mediante un conjunto de
reglas) para formar oraciones o expresiones a las cuales se les puede asignar un
“valor de verdad”, verdadero (V) o falso (F), y que reciben el nombre de
proposiciones.
La proposición que se da como verdadera (sin demostrar), a fin de que sirva de
base para construir un determinado sistema matemático, recibe el nombre de
axioma o postulado.
El teorema es una proposición cuya validez se verifica como consecuencia lógica
de los axiomas; se debe probar a partir de los axiomas y definiciones o de otros
teoremas. Aquellos teoremas que no son relevantes en el desarrollo de una
teoría se acostumbra denominarlos simplemente proposiciones.
El corolario es un teorema que se deduce fácilmente de un teorema anterior o
es un caso particular de un teorema general.
El lema es un teorema que es necesario para la demostración de un resultado
posterior, pero que se sale del contexto de la teoría que se está desarrollando.
El escolio es un resultado que se obtiene en el desarrollo de una demostración,
que no tiene relación con la teoría que se está estudiando.
Una conjetura es una proposición de la que no se puede asegurar su validez.
Por ejemplo, la Conjetura de Goldbach.
Una paradoja es una proposición contradictoria en sí misma: no puede ser ni
falsa, ni verdadera. Por ejemplo: la Paradoja del Barbero.
Se da el nombre de falacia a una conclusión falsa, a partir de proposiciones
verdaderas llamadas premisas, como por ejemplo, una falacia es la siguiente:
Premisas: Todo perro es un mamífero
Todo gato es un mamífero
Conclusión: Luego, todo perro es un gato
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
LÓGICA PROPOSICIONAL
Se puede entender las “proposiciones” como “oraciones” o “expresiones a las que
se les puede asignar un valor de verdad”.
Toda proposición debe cumplir con los siguientes principios fundamentales:
1. Principio de identidad: si una proposición es verdadera, entonces siempre es
verdadera.
2. Principio de no-contradicción: ninguna proposición puede ser verdadera y
falsa, simultáneamente.
3. Principio del tercero excluido: una proposición es verdadera ó es falsa.
A partir de las proposiciones simples (o atómicas) obtenemos las proposiciones
compuestas (o moleculares) mediante la aplicación de las conectivas lógicas.
Ejemplo de proposición simple: el gato tiene ojos verdes.
Ejemplo de proposición compuesta: el gato tiene ojos verdes y el ratón ve
al gato.
Las proposiciones se denotan usualmente con letras minúsculas del alfabeto: p,
q, r,...
A continuación se tienen algunos ejemplos de proposiciones válidas y de
proposiciones 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:
q:
r:
s:
t:
w:
La tierra es plana.
-17 + 38 = 21
x>y–9
El Carmelita será campeón en la presente temporada de Fútbol.
¡Hola!, ¿cómo estás?
Lave el carro, por favor.
Las proposiciones p y q pueden tomar un valor de falso o un valor de verdadero;
por lo tanto son proposiciones validas.
La proposición 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”.
La proposición s también válida, aunque para decir si es falsa o verdadera se
tiene que esperar a que termine la temporada de fútbol.
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.
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
Algebra de proposiciones
Así como en la aritmética los números se combinan mediante operadores
elementales, como “más” (+), “menos” (-), etc. para obtener otros números
mediante las reglas aritméticas respectivas, así en la lógica, las proposiciones
se combinan mediante los “operadores” llamados “conectivas lógicas” para
obtener las llamadas “proposiciones moleculares” o “proposiciones compuestas”.
Las proposiciones compuestas pueden ser conjuntivas, disyuntivas,
condicionales, negativas, etc.
En una proposición compuesta, es importante conocer el valor de verdad de
cada una de las proposiciones que se ligan con las conectivas lógicas (llamadas
variables proposicionales) puesto que el valor de verdad de la proposición
compuesta depende del valor de verdad de las variables proposicionales.
Una proposición compuesta recibe el nombre de:
Tautología sí y sólo sí su valor de verdad es verdadero,
independientemente del valor de verdad de sus variables
proposicionales.
Contradicción sí y sólo sí su valor de verdad es falso,
independientemente del valor de verdad de sus variables
proposicionales.
Sintética o Contingente sí y sólo sí la proposición compuesta
no es una tautología ni contradicción.
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
CONECTIVAS LÓGICAS
Conectiva lógica de Conjunción: Operador And (y)
Se utiliza para conectar dos proposiciones que se deben
cumplir para que se pueda obtener un resultado
verdadero. Su símbolo es “”. Se le conoce como la
multiplicación lógica.
Si p y q son dos proposiciones, la proposición compuesta
“p y q” se escribe “
” y se llama conjunción de p y q.
Conectiva lógica de Disyunción: Operador Or (o)
Con este operador se obtiene un resultado verdadero cuando alguna de las
proposiciones es verdadera. Se simboliza con “”. Se conoce como la suma
lógica.
Si p y q son proposiciones, la proposición
compuesta “p o q” se escribe “p  q” y se llama
disyunción de p y q. La disyunción indicada
se conoce como “o incluyente”, es decir, que
permite que ocurran a la vez p y q.
Conectiva lógica de Disyunción Exclusiva: Operador Xor (ó)
Su 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 son verdad el resultado es falso. Se simboliza con “  ”.
Si p y q son proposiciones, la proposición compuesta “p o q” se escribe “p  q” y
se llama disyunción exclusiva de p y q. La disyunción indicada se conoce como
“o excluyente”, es decir, no permite que ocurran a la vez p y q.
Conectiva lógica de Negación: Operador Not (no)
Su función es negar la proposición. Esto significa que si alguna
proposición es verdadera, se obtendrá falsa, viceversa. La negativa de cualquier
proposición “p” se llama negación y se simboliza por p, ~p,  p, p , p ' .
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
NOTA: 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).
En el lenguaje cotidiano la negación de una proposición compuesta se escribe
“No es cierto que...”.
Ejemplo
Sea el enunciado “Como espinacas o no estoy fuerte
Donde:
p: como espinacas.
q: estoy fuerte.
”.
Su negación se expresa
lo que nos dice que “No es cierto que
como espinacas o no estoy fuerte”.
NOTA: Se debe tener cuidado al negar proposiciones que contienen las palabras
“todos”, “ninguno” o “algunos”, que se resume en este cuadro:
Proposición
Todos p
Algunos p
Algunos...no p
Ningún p
Negación
Algunos (~p)
Por lo menos (~p)
Ningún p
Todos p
Algunos p
Ejemplos:
Proposición
Todas las personas tienen
compasión
Algunos animales son sucios
Algunos alumnos no estudian
Ningún estudiante es soltero
Negación
Algunas personas no tienen compasión
Ningún animal es sucio
Todos los estudiantes estudian
Algunos estudiantes son solteros
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
Proposiciones condicionales:
Si p y q son proposiciones, la proposición compuesta “si p
entonces q” se llama condicional de p y q, se denota “p
 q”; p se llama hipótesis o antecedente y q se llama
tesis o consecuente.
Dada la condicional p  q (llamada proposición directa), se definen la
proposición:
a) Recíproca por q  p
b) Contradirecta o inversa por p  q
c) Contrarrecíproca o contraposición por q  p
Considerando la proposición “Si estudio, voy al cine”,
entonces la proposición:
Directa es:” Si estudio entonces voy al cine”
Recíproca es:”Si voy al cine entonces estudio”
Contradirecta es:”Si no estudio entonces no voy al cine”
Contrarrecíproca es:”Si no voy al cine entonces no estudio”
Proposiciones bicondicionales:
Si p y q son proposiciones, la proposición compuesta “Si
p entonces q y si q entonces p” se llama bicondicional de
p y q, se denota p  q . Su tabla de verdad es la de
 p q    q  p  :
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
Resumen de las tablas de verdad

Negación:
p
V
F

Conjunción:
p
V
V
F
F

pq
V
F
F
F
q
V
F
V
F
pq
p  q
V
V
V
F
F
V
V
F
Condicional:
p
V
V
F
F

q
V
F
V
F
Disyunción:
p
V
V
F
F

-p
F
V
q
V
F
V
F
p q
V
F
V
V
Bicondicional:
p
V
q
V
p q
V
F
F
F
V
F
F
F
V
V
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
Operadores adicionales
Ocasionalmente se hallan otras conectivas que también requieren definiciones
precisas. Se les define en términos de las conectivas anteriores y se detallan a
continuación:
a) Ni p ni q se define p  q . Por ejemplo: Ni voy al cine ni voy al estadio.
b) P a menos que q se define q  p . Por ejemplo: Voy a estudiar a la
universidad a menos que no me den beca, se expresa: Si me dan beca
entonces estudio en la universidad.
c) P debido a que q se define q  p
d) Ningún p es q se define p  q
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. Todo esto 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
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
Resumen sobre lenguaje
p, q
y
p, q
o
~ p;
 p ; - p; p ; p’
pq
pq
p

q
Nombre
Se lee o escribe en el
lenguaje como...
No p
Algunos(no q) o
por lo menos(no q)
Ningún q
Todos q
Algunos q
No es cierto que...
Conjunció
n
No
Notación
pyq
Tanto p como q
P o q, p y/o q (o inclusiva)
p ó q; o p o q (o exclusiva)
p  q (directa)
q p
p, q
Si....entonces
p q
(recíproca)
(contradirecta)
Condicional
OPERADORES LÓGICOS
p
p: Todos q
p: Algunos q
p: Algunos...no
q
p: Ningún q
Compuesta
Conectiva
Disyunció
n
Proposición(es)
Negación
Por ser tan importantes las conectivas y su uso en el lenguaje común es que
podemos resumirlas en el siguiente cuadro:
q p
Si p entonces q
q si p
p sólo si q
p es suficiente para q
q es necesario para p
q con la condición de que p
q cuando p
q siempre que p
OPERADORES
ADICIONALES
p, q
Sí sólo sí
sii
p q
Bicondicional
(contrarrecíproca)
p sí sólo si q
q sí sólo si p
Si p entonces q y recíprocamente
Si q entonces p y recíprocamente
p condición necesaria y suficiente
para q
q condición necesaria y suficiente
para p
p, q
pq
Ni p ni q
p, q
q p
P a menos que q
p, q
q p
P debido a q
p, q
p q
Ningún p es q
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
Resumen de las tablas de verdad

Negación:
p
V
F

Conjunción:
p
V
V
F
F

pq
V
F
F
F
q
V
F
V
F
pq
p  q
V
V
V
F
F
V
V
F
Condicional:
p
V
V
F
F

q
V
F
V
F
Disyunción:
p
V
V
F
F

-p
F
V
q
V
F
V
F
p q
V
F
V
V
Bicondicional:
p
V
q
V
p q
V
F
F
F
V
F
F
F
V
V
Matemática Discreta
M.Ed. Ana Magali Salazar Ávila
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)
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.
Nº de líneas = 2n
donde
n = número de variables distintas
En este caso hay 3 variables distintas (p, q, r), por lo tanto tenemos 8 filas (23 = 8). La mitad de las filas de la primera
columna (23
2 = 4) se llenarán con “V”, la otra mitad con “F”. En la segunda columna se escribirá “V” en (23 22 =
2) casillas, el resto con “F”. En la tercera se escribirá (23
21 = 1) casillas con “V”, el resto con “F”. Se hará
sucesivamente hasta que la última columna que se alterne “V” y “F”.
p
q
r
q’ pq (q’r) (pq) (q’r) rq
[(pq) (q’r)  (rq)