Unidad I:
FUNDAMENTOS DE
LA LÓGICA
Estructuras Discretas
Ing. Nelsymar Millán
Lógica proposicional
Área de la matemática que trata las
proposiciones y el razonamiento lógico
matemático.
La lógica son reglas que…
• Dan significado a enunciados y sentencias
matemáticas.
• Distinguen argumentos validos y no validos.
• Seaplican en la construcción de programas y
circuitos de computadores.
Proposición
Puede ser
Oración declarativa
Simple Compuesta
Tiene un único valor lógico
Sin Con
conectivos conectivos
Verdadero Falso lógicos lógicos
Ejemplo: Ejemplo:
Pero El Sol es una El Sol es una
estrella estrella y la Tierra
gira alrededor del
No ambos a la vez Sol
Las oraciones que no son falsas ni
verdaderas, las que son falsas y
verdaderas al mismo tiempo, o lasque
carecen de sentido (o presentan algún
tipo de imprecisión) no son
consideradas proposiciones. Las
proposiciones se denotan con letras
minúsculas: p, q, r, s.
Ejemplos:
• Maracaibo es la capital del Zulia.
• LaTierra gira alrededor del Sol.
• El Zulia es la capital deVenezuela.
• 1 +1 =2
• 2 +2 =3
No son proposiciones:
• ¿Qué hora es?
• ¡Siéntate!
• Lee esto con atención.
• X+ 1 = 2
• X+ Y = Z
Valor de verdad
Llamaremos valor verdadero o valor de
verdad de una proposición a su
veracidad o falsedad. El valor de
verdad de una proposición verdadera
es verdad (1) y el de una proposición
falsa es falso (0).
Ejemplo: Diga cuáles de las siguientes afirmaciones son
proposicionesy determinarel valorde verdadde aquellasque
losean.
• p: Existe el premio Nobel deInformática.
• q: Teclee ESCpara salir de la aplicación.
• r: Cinco más siete esgrande.
Respuestas:
• p es Proposición. Su valor es«Falso».
• q no es proposición. No es Verdadera ni Falsa.
• r no es proposición. Carece de contexto, esambiguo.
Tabla de verdad
Es una tabla que muestra el valor de
verdad de una proposición compuesta, para
cada combinación de verdad que se pueda
asignar.
La tabla de verdad de una proposición
compuesta P enumera todas las posibles
combinaciones de los valores de verdad
para las proposiciones p, q, r, s,…
Tabla de verdad
Por ejemplo, si P es una proposición
compuesta por las proposiciones simples p, q y r,
entonces la tabla de verdad de P deberá recoger
los siguientes valores de verdad.
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
Proposición compuesta
Si las proposiciones p, q, r, s, …se combinan
para formar la proposición P, diremos que Pes una
proposición compuesta de p, q, r, s, …
Ejemplo: Sean los enunciados
p: Estructuras Discretas es mi asignatura preferida.
q: Mozart fue un grancompositor.
r: Él es inteligente.
s: Él estudia todos los días.
Ejemplos deProposiciones
compuestas:
«Estructuras discretas es mi
asignatura preferida y Mozart fue
un gran compositor»
«Él es inteligente o estudia todos
los días»
Proposición compuesta
La propiedad fundamental de una
proposición compuesta es que su valor
de verdad está completamente
determinado por los valores de verdad
de las proposiciones que la componen
junto con la forma en la que están
conectadas.
Operadores y Conectivos
Lógicos
OPERADORES:
Se aplican a las proposiciones para
generar proposiciones nuevas.
CONECTIVOSLÓGICOS:
Operadores lógicos que se usan para
formar nuevas proposiciones a partir de dos
o más proposiciones existentes.
TIPOS DE OPERADORESLÓGICOS
NEGACIÓN
Sea p una proposición, el enunciado <<no
se cumple p>> es otra proposición llamada
“Negación de p”. Sedenota: ¬p y selee
<<no p>>. Su tabla de verdades:
p ¬p
1 0
0 1
NEGACIÓN.Ejemplo:
p: «El Pentium es un microprocesador.»
¬p: «El Pentium no es un microprocesador.»
¬p: «Es falso que el Pentium sea un
microprocesador.»
q: « 2 + 2 = 5 »
¬q: «Es falso que 2 + 2 =5»
¬q: « 2 + 2 ≠ 5 »
CONJUNCIÓN
Sean p y q proposiciones. La proposición << p
y q >>, denotada por p q, es la proposición
que es verdadera cuando tanto p como q son
verdaderas y falsa en cualquier otro caso. Su
tabla de verdad es:
p q p q
0 0 0
0 1 0
1 0 0
1 1 1
CONJUNCIÓN.Ejemplo:
p: «Hoy es viernes.»
q: «Hoy llueve.»
p q: «Hoy es viernes y hoy llueve.»
VERDADERA:Los viernes con lluvia.
FALSA:Cualquier día diferente de
viernes y los viernes que no llueve.
DISYUNCIÓN
Sean p y q proposiciones. La proposición << p o q
>>, denotada por p q, es la proposición que es
falsa cuando tanto p como q son falsas y
verdadera en cualquier otro caso. Su tabla de
verdad es:
p q p q
0 0 0
0 1 1
1 0 1
1 1 1
DISYUNCIÓN.Ejemplo:
p: «Hoy es viernes.»
q: «Hoy llueve.»
p q: «Hoy es viernes u hoy llueve.»
VERDADERA: Cualquier día que sea
viernes o llueva, incluyendo los viernes
con lluvia.
FALSA:Los días que ni son viernes, ni
llueve.
DISYUNCIÓNEXCLUYENTE
Sean p y q proposiciones. La proposición << p o q
(pero no ambas) >>, denotada por p q, es la
proposición que es verdadera cuando solo una de
las dos proposiciones p y q es verdadera; y es falsa
cuando ambas son verdaderas o ambas son falsas.
Su tabla de verdades:
p q p q
0 0 0
0 1 1
1 0 1
1 1 0
DISYUNCIÓNEXCLUYENTE.
Ejemplo:
p: «Hoy es viernes.»
q: «Hoy llueve.»
p q: «Hoy es viernes u hoy llueve.»
VERDADERA:Cualquier día que sea
viernes o llueva, pero noambos.
FALSA:Los viernes con lluvia, y los
otros días que no llueve.
IMPLICACIÓN OCONDICIONAL
Sean p y q proposiciones. La implicación pq es
la proposición que es falsa cuando p es verdadera
y q es falsa; y es verdadera en cualquier otro caso.
pq
(Hipótesis o Causa) (Conclusión o Consecuencia)
p q pq
0 0 1
0 1 1
1 0 0
1 1 1
IMPLICACIÓN OCONDICIONAL
FORMAS DEEXPRESARELCONDICIONAL
EN LENGUAJENATURAL:
• «Si p, entonces q»
• «p implica q»
• «q si p»
• «p solo si q»
• «p siempre que q»
IMPLICACIÓN O
CONDICIONAL.Ejemplo:
p: «Soy elegido como Presidente.»
q: «Bajaré los impuestos.»
p q: «Si soy elegido como Presidente,
entonces bajaré los impuestos.»
Si el político es elegido (p es verdadera) y
no baja los impuestos (q es falsa), las
expectativas son falsas.
BICONDICIONAL O DOBLE
IMPLICACIÓN
Sean p y q proposiciones, el Bicondicional o
Doble Implicación, p q es la proposición que es
verdadera cuando p y q tienen los mismos valores
de verdad y falsa en los otros casos.
Su tabla de verdades:
p q pq
0 0 1
0 1 0
1 0 0
1 1 1
BICONDICIONAL O DOBLE
IMPLICACIÓN
FORMAS DEEXPRESARELBICONDICIONAL
EN LENGUAJENATURAL:
• «p si, y solo si q»
• «p es necesario y suficiente para q»
• «p sii q»
BICONDICIONAL O DOBLE
IMPLICACIÓN.Ejemplo:
p: «Puedes tomar el vuelo.»
q: «Compras un pasaje.»
p q: «Puedes tomar el vuelo si,y
solo si, compras un pasaje»
Esta expresión es verdadera si p y q son
ambas verdaderas o ambas falsas.
Precedencia de Operadores
Lógicos.
Orden Operador Nombre
1 ¬ Negación
2 Conjunción
3 Disyunción
4 Implicación
5 Bicondicional
Formalización
Consiste en pasar del lenguaje natural al
lenguaje formal.
Ejemplo:
p
«Puedes acceder a internet desde el LC1
solo si estudias Computación o no eres
q alumno del primer período.»
r
p q ¬r)
Equivalencias Proposicionales
Dos formulas son lógicamente
equivalentes si tienen los mismos
valores de verdad en todos los
casos. También se dice que p y q
son lógicamente equivalentes si p
q es una tautología y se denota
por p q.
Tautologías y Contradicciones
Sea Puna proposición compuesta de las
proposiciones simples p, q, r,…
Pes una Tautología si es verdadera para todos
los valores de verdad que se asignen a p, q, r, …
Pes una Contradicción si es falsa para todos los
valores de verdad que se asignen a p, q, r,…
Una proposición Pque no es tautología ni
contradicción se llama, usualmente,
Contingencia.
Tautologías y Contradicciones
Tautología Contradicción
p ¬p p¬p p¬p
1 0 1 0
0 1 1 0
Ejercicios:
• ¿Cuál es la negación de cada uno de los siguientes
enunciados?
a) Hoy es martes.
b) No hay contaminación en CiudadOjeda.
c) 2 + 1 = 3.
d) El clima en Mérida es cálido y soleado.
• Sean los enunciados p: «Tienes fiebre», q: «Suspendes el
examen final» y r: «Apruebas el curso». Expresa cada una
de las siguientes fórmulas en lenguaje natural.
a) p q
b) ¬p r
c) q ¬r
d) p q r
e) (p ¬r) q ¬r)
• Sean p y q los enunciados «Conduces a mas de 100 Km. por
hora» y «Te multan por exceso de velocidad», respectivamente.
Escribe los siguientes enunciados usando p, q y conectivos
lógicos:
a) No conduces a más de 100 Km. por hora.
b) Conduces a más de 100 Km. por hora, pero no te multan
por exceso de velocidad.
c) Temultaran por exceso de velocidad si conduces a más de
100 Km. Por hora.
d) Si no conduces a mas de 100 Km. por hora no te multarán
por exceso de velocidad.
• Determina si las siguientes implicaciones son verdaderas o falsas:
a) Si 1 + 1 = 2, entonces 2 + 2 = 5.
b) Si 1 + 1 = 3, entonces 2 + 2 = 4.
c) Si 1 + 1 = 3, entonces 2 + 2 = 5.
d) Si los cerdos vuelan, entonces 1 + 1 = 3.
• Sean las proposiciones p: «Tienes fiebre», q: «No
suspendes el examen final» y r: «Apruebas la
asignatura», expresa en lenguaje natural la
expresión:
((p q) (p r))
• Simboliza las siguientes proposiciones:
a) No vi la película pero leí lanovela.
b) Ni vi la película ni leí lanovela.
c) No es cierto que viese la película y leyese la
novela.
d) Vi la película aunque no leí la novela.
• Sean p, q y r las proposiciones «El número N es par», «La
salida va a la pantalla» y «Los resultados se dirigen a la
impresora», respectivamente. Enunciar en Lenguaje Natural
las siguientes proposiciones:
a) q p
b) ¬ q r
c) r p q)
• Tomando en cuenta las proposiciones del ejercicio anterior,
escribir, usando conectivos lógicos, una proposición que
simbolice cada una de las siguientes afirmaciones:
a) Si el número N es par, los resultados se dirigen a la impresora y
la salida va a la pantalla.
b) La salida va a la pantalla si, y solo si, los resultados se dirigen a
la impresora.
c) No es cierto que el número N sea par o la salida no va ala
pantalla.
d) Si el número N es par, la salida va a la pantalla y los resultados
se dirigen a la impresora, pero no ambas cosas a la vez.
