Download lógica proposicional

MATEMÁTICA I AÑO
LÓGICA
PROPOSICIONAL
LÓGICA PROPOSICIONAL
Nadie aprende si no se ha equivocado al intentarlo...
-¿DE QUÉ TRATA LA LÓGICA?
La lógica investiga la relación de consecuencia que se da entre una serie de premisas y la
conclusión de un argumento correcto. Se dice que un argumento es correcto (válido) si su
conclusión se sigue o es consecuencia de sus premisas; de otra forma es incorrecto.
Ya claro el concepto de lógica, voy a proceder a la definición de varias palabras que no serán de
gran utilidad en el proceso de lectura y comprensión de este trabajo.
-Argumento: es un razonamiento que quiere probar una proposición o afirmación.
Debe estar fundamentado, pero sólo será correcto cuando esa fundamentación sea adecuada.
-Premisa: es una proposición que se dice con anticipación a algo.
-Inducción: es una forma de razonamiento en la que, a partir de unas observaciones o
experiencias determinadas, sacar una conclusión final.
-Deducción: es una forma de razonamiento en la que, partiendo de unas premisas y utilizando
reglas de derivación (reglas de inferencia) se llega a sacar una conclusión final.
-Derivación: es separar cosas de un todo, dividirlo.
1
-Reglas de inferencia: son reglas ya determinadas, por medio de ellas podemos hacer una
deducción correcta.
ARISTÓTELES
Filósofo griego, considerado el más influyente en la filosofía occidental.
En la lógica, Aristóteles desarrolló reglas para el razonamiento encadenado, llamadas reglas de
validez, que dicen que no se producen nunca falsas conclusiones si la
reflexión parte de premisas verdaderas. Empezó con silogismos, y su
ejemplo más famoso es el de:
“todos los humanos son mortales”
“todos los griegos son humanos”, luego
“todos los griegos son mortales”
El distinguía entre dialéctica y analítica. Para él la dialéctica solo
comprueba las opiniones por su consistencia lógica, y la analítica trabaja de forma deductiva a
partir de principios que descansan sobre la experiencia y una observación precisa.
4) LA LÓGICA SIMBÓLICA
El ser humano, a través de su vida diaria, se comunica con sus semejantes a través de un lenguaje
determinado (oral, escrito, etc.) por medio de las denominadas frases u oraciones. Estas pueden
tener diferentes significados pero siempre van a resumirse a las formas de verdaderas o falsas,
siendo éste el precedente fundamental para el desarrollo humano. Lo importante en el presente
estudio es el hecho de que, a partir de los enunciados y de acuerdo a su significado es posible
establecer una proposición y a partir de un conjunto de éstas podemos llegar a una conclusión o
inferencia, siendo la lógica la ciencia encargada del estudio de éstas.
2
Hoy en día, la lógica proposicional que estudiaremos en este capítulo, tiene una importancia
singular dada su aplicación en los llamados "circuitos lógicos" de uso en la electrónica y la
informática.
LOGICA PROPOSICIONAL
La proposición es el significado de una idea, enunciado, conjunto de palabras o letras a las que se
les puede asignar uno y sólo uno de los valores de verdad, que pueden ser:
VERDADERO (V) o FALSO (F)
En resumen, podemos dar la siguiente definición: Proposición es toda oración declarativa.
Por lo general, a las proposiciones se las representa por las letras del alfabeto desde la letra p, es
decir, p, q, r, s, t, ... etc. Así, por ejemplo, podemos citar las siguientes proposiciones y su valor de
verdad:
p : 15 + 5 = 21 (F)
q: Cojutepeque es un municipio de Cuscatlán. (V)
r: El número 15 es divisible por 3. (V)
s: El perro es un ave. (F)
EXPRESIONES NO PROPOSICIONALES
Son aquellos enunciados a los que no se les puede asignar un valor de verdad. Entre ellos tenemos a
los exclamativos, interrogativos o imperativos.
Así tenemos, por ejemplo:
– ¿Cómo te llamas?
– Prohibido pasar
– Borra el pizarrón
3
ENUNCIADOS ABIERTOS
Si en la proposición: "cinco es mayor que tres" (en símbolos: 5 > 3) reemplazamos al número 5 por
la letra x, se obtiene la expresión "x es mayor que tres" (x > 3), y si convenimos que x no
represente necesariamente al número 5, sino a un número cualquiera, entonces al enunciado x > 3
se le denomina enunciado abierto.
CLASIFICACIÓN DE LAS PROPOSICIONES
Aquellas proposiciones que constan o se les puede representar por una sola variable, se llaman
proposiciones simples o atómicas. Por ejemplo, sea la proposición "p: 3 + 6 = 9" es una proposición
simple o atómica.
Cuando una proposición consta de dos o más enunciados simples, se le llama proposición compuesta
o molecular.
Así, por ejemplo:
Pitágoras era griego y era geómetra.
Encontramos dos enunciados. El primero (p) nos afirma que Pitágoras era griego y el segundo (q)
que Pitágoras era geómetra.
Ejercicios:
4
NOTACIÓN Y CONECTIVOS LÓGICOS
A partir de proposiciones simples es posible generar otras, simples o compuestas. Es decir que se
puede operar con proposiciones, y para ello se utilizan ciertos símbolos llamados conectivos
lógicos. A continuación vemos una concreta definición de cada uno:
Símbolo Operación asociada
Significado
no p o no es cierto que p
~
Negación

Conjunción o producto lógico

Disyunción o suma lógica
pyq
p o q (en sentido incluyente)

Implicación
p implica q, o si p entonces
q

Doble implicación
p si y sólo si q

Diferencia simétrica
p o q (en sentido
excluyente)
OPERACIONES PROPOSICIONALES
Definiremos las operaciones entre proposiciones en el sentido siguiente: dadas dos o más
proposiciones, de las que se conoce los valores veritativos, se trata de caracterizar la proposición
resultante a través de su valor de verdad. A tal efecto, estudiaremos a continuación el uso y
significado de los diferentes conectivos lógicos mencionados arriba:
NEGACIÓN
Dada una proposición p, se denomina la negación de p a otra proposición denotada por ~ p (se lee
"no p") que le asigna el valor veritativo opuesto al de p. Por ejemplo:
p: Diego estudia matemática
~ p: Diego no estudia matemática
Por lo que nos resulta sencillo construir su tabla de verdad:
5
Observamos aquí que al valor V de p, la negación le hace corresponder el valor F, y viceversa.
Se trata de una operación unitaria, pues a partir de una proposición se obtiene otra, que es su
negación.
Ejemplo: La negación de " p: todos los alumnos estudian matemática" es
~ p: no todos los alumnos estudian matemática
o bien:
~ p: no es cierto que todos los alumnos estudian matemática
~ p: hay alumnos que no estudian matemática
CONJUNCIÓN
Dadas dos proposiciones p y q, se denomina conjunción de estas proposiciones a la proposición p ∧
q (se lee "p y q"), cuya tabla de verdad es:
La tabla que define esta operación, establece que la conjunción es verdadera sólo si lo son las dos
proposiciones componentes. En todo otro caso, es falsa.
Ejemplo: Sea la declaración:
i) Vemos que está compuesta de dos proposiciones a las que llamaremos p y q, que son
p: 5 es un número impar
q: 6 es un número par
6
Por ser ambas verdaderas, la conjunción de ellas (que no es sino la declaración i) es verdadera.
Ahora bien, sea la declaración
ii) Hoy es el día 3 de noviembre y mañana es el día de 5 de noviembre
Esta conjunción es falsa, ya que no pueden ser simultáneamente verdaderas ambas proposiciones.
DISYUNCIÓN
Dadas dos proposiciones p y q, la disyunción de las proposiciones p y q es la proposición p Ú q cuya
tabla de valor de verdad es:
La disyunción o es utilizada en sentido excluyente, ya que la verdad de la disyunción se da en el
caso de que al menos una de las proposiciones sea verdadera. En el lenguaje ordinario la palabra o
es utilizada en sentido incluyente o excluyente indistintamente. Para agotar toda posibilidad de
ambigüedades, en matemática se utiliza la disyunción definida por la tabla precedente, que nos
muestra que la disyunción sólo es falsa cuando ambas proposiciones son falsas.
Ejemplo:
Sea i) Tiro las cosas viejas o que no me sirven
El sentido de la disyunción compuesta por p y q (p: tiro las cosas viejas, q: tiro las cosas que no me
sirven) es incluyente, pues si tiro algo viejo, y que además no me sirve, la disyunción es V.
7
IMPLICACIÓN O CONDICIONAL
Implicación de las proposiciones p y q es la proposición p ⟹ q (si p entonces q) cuya tabla de
valores de verdad es:
La proposición p se llama antecedente, y la proposición q se llama consecuente de la implicación o
condicional. La tabla nos muestra que la implicación sólo es falsa si el antecedente es verdadero y
el consecuente es falso.
Ejemplo: Supongamos la implicación
Si apruebo, entonces te presto el libro.
La implicación está compuesta de las proposiciones
p: apruebo
q: te presto el libro
Nos interesa conocer la verdad o falsedad de la implicación i), en relación a la verdad o falsedad
de las proposiciones p y q. El enunciado puede pensarse como un compromiso, condicionado por p, y
podemos asociar su verdad al cumplimiento del compromiso. Es evidente que si p es F, es decir si
no apruebo el examen, quedo liberado del compromiso y preste o no el apunte la implicación es
verdadera.
Si p es verdadera, es decir si apruebo el examen, y no prestó el libro, el compromiso no se cumple
y la proposición i) es falsa. Si p y q son verdaderas, entonces la proposición i) es verdadera pues el
compromiso se cumple.
Ejemplo: 1 = –1 Þ 1² = (–1)² (F)
La proposición resulta ser falsa por ser el antecedente (1 = –1) falso.
8
DOBLE IMPLICACIÓN O BICONDICIONAL
Doble implicación de las proposiciones p y q es la proposición p ⟺ q (se lee "p si y sólo si q") cuya
tabla de valores de verdad es:
La doble implicación o bicondicional sólo es verdadera si ambas proposiciones tienen el mismo valor
de verdad.
La doble implicación puede definirse como la conjunción de una implicación y su recíproca. De este
modo, la tabla de valores de verdad de p⟺ q puede obtenerse mediante la tabla de:
(p ⟹ q) ∧(q ⟹ p), como vemos:
Ejemplo: Sea i) a = b si y sólo si a2 = b2
El enunciado está compuesto por las proposiciones:
p: a = b
q: a2 = b2
Esta doble implicación es falsa si p es F y q es V. En los demás casos es V.
9
DIFERENCIA SIMÉTRICA
Diferencia simétrica o disyunción en sentido excluyente de las proposiciones p y q es la
proposición p ∨q (se lee "p o q en sentido excluyente") cuya tabla de valores de verdad es:
p
q
p ∨q
V
V
F
V
F
V
F
V
V
F
F
F
La verdad de p ∨ q está caracterizada por la verdad de una y sólo una de las proposiciones
componentes.
Ejemplo: Sea i) o vamos a Santa Ana o vamos a San Miguel
Queda claro que sólo podremos ir a uno de los dos lugares, y sólo a uno. Es decir que el enunciado
i) es verdadero sólo si vamos a una de las dos ciudades. En caso de ir a ambas, o de no ir a ninguna,
el enunciado es Falso.
Ejemplos:
1. Determinar el valor de verdad de las siguientes proposiciones compuestas:
10
2. En los problemas siguientes considere:
p: Panamá está en América Central.
q: Colombia está al sur de Venezuela.
r: Quito es la capital de Ecuador.
Observe que p y r son verdaderas, pero q es falsa. Escriba las proposiciones dadas en forma
simbólica, y determine en cada caso si la proposición es verdadera o falsa.
a. Panamá está en América Central y Colombia está al sur de Venezuela.
b. Colombia no está al sur de Venezuela.
c. Colombia está al sur de Venezuela y Quito es la capital de Ecuador, o Panamá no está en América
Central.
d. Quito no es la capital de Ecuador ni Panamá está en América Central.
e. Si panamá está en América Central y Colombia no está al sur de Venezuela, entonces ni Panamá está en
América Central ni Quito es la capital de Ecuador.
PROPOSICIONES LOGICAMENTE EQUIVALENTES.
Dos proposiciones p y q se llaman equivalentes si sus tablas de verdad son idénticas. De ser así se
denota: p  q
Ejemplo: Sea
p: p  q, recordamos su tabla de verdad:
p q pq
Ahora bien, si analizamos la proposición
V V
V
V F
F
F V
V
F F
V
q: ~ p  q, su tabla de verdad resulta:
p q ~pq
11
V V
V
V F
F
F V
V
F F
V
Como vemos, luego de realizar las tablas de valor veritativo encontramos que ambas proposiciones
tienen el mismo resultado final. Con esto, decimos que ambas proposiciones son lógicamente
equivalentes, y en este caso particular lo simbolizamos: (p  q)  (~ p  q)
TAUTOLOGÍA, CONTRADICCIÓN Y CONTINGENCIA
Al conjunto de proposiciones, conectivos lógicos y símbolos de agrupación lo denominamos fórmula lógica.
Por ejemplo: ~ {(p  q)  (s  t)}
Si al evaluar una fórmula lógica, resulta que todos los valores de verdad resultantes son siempre V para
cualquier combinación de sus valores de verdad, decimos que dicha fórmula es una Tautología o Ley lógica.
Ejemplo: Si analizamos la proposición
t: p  ~ p realizando su tabla de verdad:
p ~p p~p
V
F
V
F
V
V
Vemos que para cualquier combinación de las proposiciones p y su negación ~ p, la proposición t:
siempre verdadera. Entonces, la proposición t es una tautología
12
p  ~ p es
Ejemplo: Analicemos ahora la fórmula lógica
{(pq)p}q
p q pq qp {(pq)p}q
V V
V
V
V
V F
F
F
V
F V
V
F
V
F F
V
F
V
En este caso comprobamos también que independientemente de la combinación de valores de verdad de las
proposiciones p y q, el resultado de la fórmula lógica es siempre V. Decimos, aquí también, que esta fórmula
es una tautología o ley lógica.
Si al estudiar una fórmula lógica, a diferencia de los ejemplos anteriores resulta que para cualquier valor de
verdad de las proposiciones intervinientes el resultado de dicha fórmula es siempre falso, decimos que
dicha fórmula es una Contradicción.
Ejemplo: Analicemos la fórmula lógica
p~p
p ~p p~p
V
F
F
F
V
F
Encontramos que la fórmula es siempre falsa, es entonces una Contradicción.
Si una proposición no es una tautología ni una contradicción (es decir que contiene al menos un valor V y otro
F) es una contingencia.
Ejemplos: Construya tablas de verdad para las siguientes proposiciones. ¿Cuáles de ellas son
tautolog
ías,
contradi
cciones
o
continge
ncias
13
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 válido 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
14
Ejemplo 2.
¿Es válido el siguiente argumento?
Si bajan los impuestos, entonces se eleva el ingreso
El ingreso se eleva.
_________________________________________
Los impuestos bajan
Solución: Sea p: Los impuestos bajan; q: El ingreso se eleva.
p  q
q
_____
p
El aplicar la regla de inferencia es lo que le cuesta más al alumno y se deberá poner mucha
atención para que el alumno aprenda a aplicar dicha regla.
En una demostración no solamente hay tautologías e hipótesis, también existen reglas de
inferencia que permiten obtener nuevas líneas válidas, esta es la parte en donde la mayoría de
alumnos tienen problemas y en donde no sabe que regla aplicar para resolver un determinado
problema. Ejemplos:
15
CUANTIFICADORES
A partir de funciones proposicionales es posible obtener proposiciones generales mediante un proceso
llamado de cuantificación. Asociados a la indeterminada x, introducimos los símbolos  x y  x, llamados
CUANTIFICADOR UNIVERSAL Y CUANTIFICADOR EXISTENCIAL respectivamente. Las expresiones

Cualquier operador lógico de la forma “para todo”, “para cada”, “todo” o “cada”,
es un CUANTIFICADOR UNIVERSAL y se representa de la siguiente manera:
Para todo x, se verifica p(x) se denota por  x: p(x)

Los operadores de la forma “existe”, “algún”, “por lo menos un”, son CUANTIFICADORES
EXISTENCIALES y se representan como: Existe x, tal que se verifica p(x) se denota por

x / p(x).
Ejemplos: represente, aplicando el cuantificador apropiado, las siguientes expresiones en forma
simbólica:
a) Hay animales carnívoros : ∃𝒙 𝑪 𝒙
b) Todos somos inteligentes: ∀𝒙 𝑰 𝒙
c) Hay números impares : ∃𝒙 𝑰 𝒙
d) Existe al menos un volcán: ∃𝒙 𝑽 𝒙
e) Cada número natural es entero: ∀𝒙 𝑬 𝒙
f) Hay palomas blancas: ∃𝒙 𝑩 𝒙
g) Algunas personas son artistas: ∃𝒙 𝑨 𝒙
h) Todos amamos la naturaleza:∀𝒙 𝑵 𝒙
Una función proposicional cuantificada universalmente es V si y sólo si son V todas las proposiciones
particulares asociadas a aquella. Para asegurar la verdad de una proposición cuantificada
universalmente es suficiente que sea verdadera alguna de las proposiciones asociadas a la función
proposicional.
Un problema de interés es la negación de funciones proposicionales cuantificadas. Por ejemplo, La
negación de "Todos los enteros son impares" es "Existen enteros que no son impares" y en símbolos: 
x / ~ p(x)
Entonces, para negar una función proposicional cuantificada universalmente se cambia el cuantificador
en existencial, y se niega la función proposicional.
Ejemplo: Supongamos la proposición: Todos los alumnos de mi colegio son aplicados
La vamos a escribir en lenguaje simbólico, negarla y retraducir la negación al lenguaje ordinario.
16
Nos damos cuenta pronto que se trata de la implicación de dos funciones proposicionales:
p(x): es alumno de mi colegio
q(x): es aplicado
Tenemos:
 x: p(x)  q(x)
Teniendo en cuenta la forma de negar una función proposicional cuantificada universalmente y una
implicación resulta:  x / p(x)  ~ q(x)
Y traduciendo al lenguaje ordinario resulta: Existen alumnos de mi colegio que no son aplicados.
La siguiente tabla nos muestra la negación de proposiciones que contienen alguno de los cuantificadores
anteriores:
PROPOSICIÓN
∀…
NEGACIÓN
∃…
∃…
Algunos
Todos
∀…
Ningún
Algunos no …
Algunos no …
Ningún
Todos
Algunos
Ejemplos: Considere los enunciados:
a)
b)
c)
d)
Todos los ángulos son congruentes (F)
Algunos ángulos son rectos (V)
Existen ángulos no obtusos (V)
Ningún ángulo mide 30º (F)
La representación simbólica de cada enunciado y su negación están dadas por:
A) ∀ 𝒙𝑪 𝒙 ∶
C : ángulos congruentes
Negación: ∃ 𝒙 ~ 𝑪 𝒙
Traducción: algunos ángulos no son congruentes (V)
B) ∃𝒙𝑹 𝒙 ∶
R : ángulos rectos
Negación: ∀ 𝒙 ~ 𝑹 𝒙
Traducción: Ningún ángulos es recto (F)
17
C) ∃ 𝒙 ~𝑶𝒙 ∶
O : ángulos obtusos
Negación: ∀ 𝒙 𝑶 𝒙
Traducción: todo ángulo es obtuso (F)
D) ∀ 𝒙~𝑴 𝒙 ∶
M: ángulo mide 30º
Negación: ∃ 𝒙 𝑴 𝒙
Traducción: algún ángulo mide 30º (V)
EJERCICIO:
I.
Expresar simbólicamente mediante cuantificadores y funciones proposicionales, negar y
traducir cada uno de los siguientes enunciados:
1) Hay mujeres hermosas
2) Existen conjuntos unitarios
3) Muchas personas viven en la pobreza absoluta
4)
Existen países en vía de desarrollo.
5) Ningún número natural es negativo
6) Algunos estudiantes tienen dificultad en el aprendizaje
7) Todos los países latinoamericanos tienen deuda externa
8) No todos son números primos.
9) Algunos números no son primos.
10) Es falso que existan números primos.
II. ESCRIBA LOS PREDICADOS SIGUIENTES EN FORMA SIMBÓLICA:
1) No todas las piedras preciosas son bonitas.
2) Existe un número positivo que es el menor.
3) Nadie ama a todo el mundo
4) Existe un único presidente de El Salvador
5) Existe un número que es más grande que cualquier solución conocida para el problema o
no hay solución.
6) En forma simbólica escriba la negación de los predicados dados en el ejercicio anterior.
18
III.
CONSIDERE LOS ENUNCIADOS ABIERTOS O PREDICADOS DADOS.
P(x,y): x es más rápido que y ; Q(x,y): y es más alto que x ; R(x): x pesa más de 200
libras
Escriba las siguientes expresiones:
1) P(x, José)
6) ∀𝒙, ∀𝒚 Q(x,y) ⟶P(x,y)
2) Q(Miguel, Luis) ∧ R(Juan)
7) ∀𝒙, P(x,José)⟷ R(x)
3) P(x,y) ⟶ Q(x,y)
8) ∃𝒙, R(x) ∧ ∀𝒚 P(x,y)
4) Q(x,y) ⟶ R(x)
9) ∃𝒚, ∀𝒙,P(x,y) ⟶R(x)
5) P(Miguel, José) ∨ [Q(Miguel,
10) ∀𝒚, R(Miguel) v Q(Miguel,y
José) ∧ R(José)]
IV.
Escribir la negación de cada una de las proposiciones siguientes
v. Escriba la negación de cada una de las siguientes proposiciones
19
RESOLVER LOS SIGUIENTES EJERCICIOS.
20