algebra proposicional bueno modulom dos
Post on 27-Sep-2015
269 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
LGEBRA DE PROPOSICIONES
1
CAPTULO I
LGEBRA DE PROPOSICIONES
1.1 PROPOSICIN
Proposicin (o enunciado) es una afirmacin verbal a la que puede
asociarse un valor de verdad, es decir, puede ser verdadera o falsa, por
ejemplo:
Hace calor Jos estudia El es feliz Oruro es una ciudad con clima fro
Las proposiciones pueden ser simples como las de los ejemplos anteriores
o compuestas, que se pueden unir a travs de conectores (conectivas)
Jos estudia y es feliz Hace calor o estoy muy abrigado Si llueve entonces me mojo
El lgebra proposicional es la representacin del lenguaje usual tomando
como elemento bsico una representacin matemtica de las frases
declarativas que definen las operaciones bsicas del lgebra
proposicional.
Para representar proposiciones se utilizarn letras: p, q, r, s,.Las operaciones bsicas son:
Negacin ~ () Conjuncin. Disyuncin
Disyuncin exclusiva Condicional Bicondicional Negacin conjunta
j.sabiNota adhesivasacado de http://docentes.uto.edu.bo/alvargaso/wp-content/uploads/2algebra_de_proposiciones.pdf
-
LGEBRA I 2
1.2 NEGACIN ~p
Permite negar un enunciado o proposicin, su tabla de verdad es falsa
cuando p es verdadera y viceversa:
No p No es verdad que p Es falso que p No es cierto que p
1.3 CONJUNCIN p q
Dos proposiciones pueden ser unidas con la conjuncin, lo cual puede
interpretarse como:
p y q p pero q p sin embargo q p no obstante q p a pesar de q
La tabla de verdad de la conjuncin es verdadera, solamente cuando los
dos enunciados son verdaderos.
1.4 DISYUNCIN p q
La disyuncin permite unir dos proposiciones
con el equivalente a la letra o
p o q o p o q o ambas cosas como mnimo p o q
La tabla de verdad de la disyuncin es falsa solamente cuando los dos
enunciados son falsos.
1.5 DISYUNCIN EXCLUSIVA p q
La disyuncin exclusiva equivale a unir dos
enunciados con un conector equivalente a
p o q pero no ambos, su tabla de verdad es
verdadera cuando un enunciado es verdadero
y el otro falso o viceversa.
p ~p
V F
F V
p q
V V V
V F F
F F V
F F F
p q
V V V
V V F
F V V
F F F
p Q
V F V
V V F
F V V
F F F
-
LGEBRA DE PROPOSICIONES
3
1.6 CONDICIONAL (IMPLICACIN) pq
Es una relacin de causa a efecto
p implica a q si p entonces q p es suficiente para q q es necesario para p q si p
La tabla de verdad del condicional tiene valor falso cuando el primer
enunciado es verdadero y el segundo falso.
1.7 BICONDICIONAL (DOBLE IMPLICACIN) pq
Se lee p si y slo si q, su tabla de verdad exige que ambos enunciados
sean verdaderos o ambos falsos para ser verdadera.
p si y slo si q p necesario y suficiente para q
1.8 NEGACIN CONJUNTA pq
Se lee ni p ni q y es verdadero cuando p es falso y q es falso
1.9 TABLAS DE VERDAD DE PROPOSICIONES
Cuando se construye una tabla de verdad se puede clasificar la misma, si
la ltima columna tiene todos los valores de verdad verdaderos, se trata
de una Tautologa, si son falsos es una Contradiccin y, si los valores
de verdad estn combinados una Contingencia.
p q
V V V
V F F
F V V
F V F
p q
V V V
V F F
F F V
F V F
p q
V F V
V F F
F F V
F V F
-
LGEBRA I 4
Para asignar los valores de verdad a una proposicin que contiene dos
enunciados p y q empiece por dar a p dos valores verdaderos y dos falsos
e intercale entre verdadero y falso los de q. Si se tienen tres enunciados p,
q, r asigne a p cuatro valores verdaderos y luego cuatro falsos, a q dos
verdaderos, dos falsos, dos verdaderos y luego dos falsos, finalmente
intercale los valores de verdad de r entre verdadero y falso. Siguiendo
sta lgica no existe ninguna dificultad para construir una tabla de verdad
de n enunciados, respete el orden alfabtico de las letras para empezar a
asignar los valores de verdad correspondientes.
Ntese que el nmero de lneas de una tabla de verdad vendr dado por
el nmero dos elevado al nmero de enunciados de la tabla. As por
ejemplo, una proposicin de cuatro enunciados tendr 24 =16 filas
Construya la tabla de verdad de las siguientes proposiciones e indique si
se trata de una tautologa, contradiccin o contingencia
Ejemplo 1
~ (p v q) v ~p ^ ~q
F V V V F F F F
F V V F F F F V
F F V V F V F F
V F F F F V V V
Es una contradiccin
Ejemplo 2
(p q) (r ^ ~p)
V V V F V F F
V V V F F F F
V F F V V F F
V F F V F F F
F V V V V V V
F V V F F F V
F V F V V V V
F V F F F F V
Es una contingencia
-
LGEBRA DE PROPOSICIONES
5
Ejemplo 3
{(p q) (~r ^ s)} V (~q v r)
V V V F F F V V F V V
V V V F F F F V F V V
V V V V V V V V F F F
V V V F V F F F F F F
V F F V F F V F V V V
V F F V F F F F V V V
V F F F V V V V V V F
V F F V V F F F V V F
F V V F F F V V F V V
F V V F F F F V F V V
F V V V V V V V F F F
F V V F V F F F F F F
F V F F F F V V V V V
F V F F F F F V V V V
F V F V V V V F V V F
F V F F V F F V V V F
Es una contingencia
Ejemplo 4
[(p q) ^ (q r)] (p r)
V V V V V V V V V V V
V V V F V F F V V F F
V F F V F V V V V V V
V F F F F F F V V F F
F V V V V V V V F V V
F V V F V F F V F V F
F V F V F V V V F V V
F V F V F V F V F V F
Es una tautologa
-
LGEBRA I 6
Ejemplo 5
(r v q) {(~p v s) (~q ~r)}
V F V F F V V V F V F
V F V F F F F V F V F
F V V V F V V V F V V
F V V F F F F V F V V
V V F F F V V F V F F
V V F V F F F V V F F
F F F F F V V V V V V
F F F F F F F V V V V
V F V F V V V V F V F
V F V F V V F V F V F
F V V V V V V V F V V
F V V V V V F V F V V
V V F F V V V F V F F
V V F F V V F F V F F
F F F F V V V V V V V
F F F F V V F V V V V
Es una contingencia
1.10 PARADOJAS LGICAS1
Existen acertijos lgicos que permiten matizar el aprendizaje del lgebra
de proposiciones, dando un contenido entretenido al tema. La mayor
parte de los acertijos se origina en lo que se ha dado a llamar la falacia del circulo vicioso, que es debida al hecho de despreciar el principio fundamental de que lo que se involucra al todo de una totalidad dada no
puede ser parte de la totalidad por ejemplo, el acertijo de Epimnides referente al cretense que dice que todos los cretenses son mentirosos. Otros ejemplos sencillos de esto son aquellas frases pontificiales,
familiares en todo el mundo, que parecen tener mucho significado, pero
que en realidad no tienen ninguno, tales como: nunca digas nunca o toda regla tiene excepciones. Entre otras paradojas interesantes estdiese la siguiente:
1 Kasner Edgard y Newman James, LAS MATEMTICAS Y LA IMAGINACIN Pub.Sociedad Matemtica Mexicana 1967
-
LGEBRA DE PROPOSICIONES
7
La caza esta prohibida en el territorio de un prncipe, quien fuera
sorprendido en este delito sera castigado con la muerte, el infractor deba
formular una proposicin, si era falsa se le ahorcaba y si era verdadera se
le decapitaba. Un bribn, ducho en lgica se vali de esta prerrogativa
diciendo: Ser ahorcado, si se le ahorcaba la proposicin era verdadera y contradeca la Ley y si era decapitado entonces la proposicin era falsa,
lo cual tambin iba en contra de la Ley.
Invitamos al lector a debatir sobre el valor de verdad de la siguiente
proposicin: El barbero de la aldea afeita a todos los hombres de la misma que no se afeitan a si mismos (analice la situacin del barbero)
1.11 APLICACIONES CON DERIVE
Derive es un formidable asistente matemtico que permite realizar
muchas operaciones en el campo de la matemtica, una de ellas el la
construccin de tablas de verdad, para ello el usuario deber tener cierta
familiaridad con el derive, la siguiente es la pantalla principal.
-
LGEBRA I 8
Ejemplo 6
Utilizando el asistente matemtico Derive
Ingrese la siguiente expresin en la barra de entrada
TRUTH_TABLE (p, q, r, s, ((p q) ( r s)) ( q v r))
Haciendo click en introducir y simplificar obtendr
p q r s (p q r ^ s) ( q v r) true true true true true true true true false true
true true false true false
true true false false false
true false true true false
true false true false false
true false false true true
true false false false false
false true true true true
false true true false true
false true false true false
false true false false false
false false true true true false false true false true
false false false true false
false false false false true
Resultar muy til a la formacin del estudiante, familiarizarse con el uso
del asistente matemtico Derive, el mismo cuenta con aplicaciones
matemticas de todas las asignaturas que le corresponder cursar a todo
estudiante de ingeniera, por ello se recomienda tomarse un tiempo para
trabajar con este asistente que no requiere mayores explicaciones que una
clase introductoria para familiarizarse con la pantalla principal.
Posteriormente, utilizando adecuadamente la ayuda se puede concretar
fcilmente un autoaprendizaje.
El asistente matemtico Derive permite construir tablas de verdad de una
forma muy simple, para ello basta con que se introduzca en la barra de
entrada de expresiones la proposicin cuya tabla se desea encontrar. Los
tres ltimos ejemplos pueden resolverse del siguiente modo;
-
LGEBRA DE PROPOSICIONES
9
Ejemplo 7
Introduzca la siguiente expresin
TRUTH_TABLE(p,q,r,((p q) ^ (q r)) (p r))
Se simplificar a:
p q r (p q) ^ (q r) (p r) true true true true
true true false true
true false true true
true false false true
false true true true
false true false true
false false true true
false false false true
Ejemplo 8
Introduzca lo siguiente:
TRUTH_TABLE(p, q, r, s, (r q) ^ (( p v s) (q r))) Luego de introducir y simplificar obtendr la siguiente tabla:
p q r s (r q) ^ ( p v s q r) true true true true false
true true true false false
true true false true true
true true false false false
true false true true true
true false true false false
true false false true false
true false false false false
false true true true false
false true true false false
false true false true true
false true false false true
false false true true true
false false true false true
false false false true false
false false false false false
-
LGEBRA I 10
1.12 LEYES DEL ALGEBRA DE PROPOSISIONES
Las proposiciones, bajo la ley de equivalencia lgica (), cumplen las siguientes leyes:
1.12.1 LEYES DE IDEMPOTENCIA
pppppp
1.12.2 LEYES ASOCIATIVAS
)()()()( rqprqprqprqp
1.12.3 LEYES CONMUTATIVAS
pqqppqqp
1.12.4 LEYES DE IDENTIDAD
ffppvpvvppfp ;;;
1.12.5 LEYES DE COMPLEMENTACIN
vffv
fppppvpp
~;~
~;~~;~
1.12.6 LEYES DE MORGAN
q~~)(~~~)(~ pqpqpqp
1.12.7 LEYES DISTRIBUTIVAS
)()()()()()( rpqprqprpqprqp
1.12.8 LEYES DE ABSORCIN
( )
( )
p p q p
p p q p
1.12.9 DEFINICIN DE CONDICIONAL Y BICONDICIONAL
( ) ( )
( ) ( )
p q p q
p q p q q p
p q p q q p
-
LGEBRA DE PROPOSICIONES
11
1.13 LGEBRA DE PROPOSICIONES
Ejemplo 9 Mediante las leyes del lgebra de proposiciones y sin utilizar la ley de
absorcin, simplificar las siguientes expresiones:
a) ( ) (~ )p q p f
qp
qpf
qppp
qpp
pqp
fpqp
~
)~(
)~()~(
)(~
~)(
)~()(
b)
p
vp
qvp
qpvp
qpp
fqpp
)((
)()(
)(
])[(
c)
p
fp
qfp
qpfp
qpp
vqpp
)((
)()(
)(
])[(
d)
Def. condicional, De Morgan
= Conmutativa
= Distributiva
= Complementacin
Identidad
Conmutativa
Distributiva
Complementacin
Identidad
Identidad
Identidad
Distributiva
Identidad
Identidad
Identidad
Identidad
Distributiva
Identidad
Identidad
-
LGEBRA I 12
= Identidad
= Def. Condicional
= De Morgan
Idempotencia complementacin
Ejemplo 10
Determinar el valor de verdad de los siguientes enunciados:
Si 1 1a
a entonces
22 2 2x x
V V V
Como el primer enunciado es verdadero, el segundo tambin, y el
conector es el condicional deducimos que el enunciado es verdadero
3 8 2 y 9 3
V F F
En este caso el primer enunciado es verdadero y el segundo falso, el
conector es la conjuncin, por tanto, el enunciado es falso
0 1 10 1x o x
F V V V
Ahora el primer enunciado es falso y el segundo verdadero, el
conector en la disyuncin, por tanto, el enunciado es verdadero.
2 2 2( )x y x y si y slo si sin45 cos45
V V El primer enunciado es verdadero y el segundo verdadero, el conector
es el bicondicional, en consecuencia el enunciado es verdadero.
Ejemplo 11
Conociendo que p, q, r, s son proposiciones verdaderas determine el
valor de verdad de:
( ) ( )p q r s p
-
LGEBRA DE PROPOSICIONES
13
( ) ( )
( )
V V V V V
V F F
V F
V
Si p,q son verdaderas y r,s,t falsas, hallar el valor de verdad de:
( ) ( ) ( )r q s t q p s
( ) ( ) ( )F V F F V V F
( ) ( ) ( )F F V V
V F
F
1.14 ENUNCIADOS CONDICIONALES Y VARIACIONES
El condicional qp tiene las siguientes proposiciones derivadas de
ella
Converso o recproco pq
Inverso o contrario qp ~~
Contrapositivo o contrarecproco pq ~~
Cuyas tablas de verdad son las siguientes:
Ntese que el enunciado condicional qp y su contrapositivo
pq ~~ son lgicamente equivalentes, de la misma manera el
converso pq y el inverso qp ~~ son tambin lgicamente
equivalentes.
Ejemplo 12
p q ~p ~q pq qp ~p~q ~q~p
V V F F V V V V
V F F V F V V F
F V V F V F F V
F F V V V V V V
-
LGEBRA I 14
Sea el enunciado condicional Si estudio matemticas aprobar la materia escriba en forma simblica y literal el condicional, converso, inverso contrapositivo.
Sea p estudio matemticas q aprobar la materia Condicional
qp Si estudio matemticas aprobar la materia
Converso
pq Si apruebo la materia entonces estudi matemticas
Inverso
qp ~~ Si no estudio matemticas, entonces no aprobar la
materia Contrapositivo
pq ~~ Si no apruebo la materia, entonces no estudi
matemticas Ejemplo 13
Sea el enunciado condicional Si me caso muy joven, ser infeliz, escriba en forma simblica y literal el condicional, converso, inverso y
contrapositivo.
Sea p me caso muy joven q ser infeliz Condicional
qp Si me caso muy joven, ser infeliz
Converso
pq Si soy infeliz entonces me cas muy joven
Inverso
qp ~~ Si no me caso muy joven entonces ser feliz
Contrapositivo
pq ~~ Si soy feliz entonces no me cas muy joven
1.15 ARGUMENTOS E IMPLICACIN LGICA
Argumento (razonamiento deductivo vlido) es una afirmacin de que un
conjunto dado de proposiciones
P1, P2, P3, Pn, denominadas premisas, producen como consecuencia lgica otra proposicin Q llamada conclusin, se
representa por:
P1, P2, P3, Pn, Q
-
LGEBRA DE PROPOSICIONES
15
Un argumento P1, P2, P3, Pn, Q es vlido si la conclusin es verdadera cuando todas las premisas son verdaderas; de otra manera es
falso.
Un argumento P1, P2, P3, Pn, Q es vlido si y slo si la proposicin (P1 ^P2^ P3^^ Pn) Q es una tautologa.
Ejemplo 14
Determine la validez del siguiente argumento
P1 : Estudio o voy a la fiesta
P2 : Si estudio aprobar el examen
P3 : Fui a la fiesta
.. Q : Reprob el examen
Sea p estudio; q voy a la fiesta; r aprob el examen
Estudio o voy a la fiesta p q
Si estudio aprobar el examen p r
Fui a la fiesta q
Reprob el examen ~ r
(p v q) ; (p r) ; q ~r
V V V V V V V F
V V V V F F V V
V F F V V V F F
V F F V F F F V
F F V F V V V F
F F V F V F V V
F F F F V V F F
F F F F V F F V
Solamente en la primera fila las premisas son verdaderas y la conclusin
es falsa, por tanto, el argumento no es vlido.
Tambin es posible determinar la validez del argumento construyendo la
siguiente tabla de verdad:
-
LGEBRA I 16
[(p V q) (p r) q] ~r
V V V V V V V V V F F
V V V F V F F F V V V
V F F F V V V F F V F
V F F F V F F F F V V
F F V F F V V F V V F
F F V F F V F F V V V
F F F F F V V F F V F
F F F F F V F F F V V
Como la tabla de verdad no es una tautologa, entonces el argumento no
es vlido
Ejemplo 15 Determine la validez del siguiente argumento
P1 : Si nieva har mucho fro
P2 : Hace mucho fro y me enfermo
P3 : No nev sin embargo me enferm
.. Q : No hizo mucho fro
Sea p nieva; q hace mucho fro; r me enfermo.
Si nieva har mucho fro p q
Hace mucho fro y me enfermo q r
No nev sin embargo me enferm p r
No hizo mucho fro ~ q
(p q) ; (q ^ r) ; p ^ r ~q
V V V V V V V V V F
V V V V F F V F F V
V F F F F V V V V F
V F F F F F V F F V
F V V V V V F F V F
F V V V F F F F F V
F V F F F V F F V F
F V F F F F F F F V
En la primera fila las premisas son verdaderas y la conclusin es falsa,
por tanto, el argumento no es vlido.
-
LGEBRA DE PROPOSICIONES
17
{[(p q) ^ (q ^ r)] ^ (p ^ r)} ~q
V V V V V V V V V V V F F
V V V F V F F F V F F V F
V F F F F F V F V V V V V
V F F F F F F F V F F V V
F V V V V V V F F F V V F
F V V F V F F F F F F V F
F V F F F F V F F F V V V
F V F F F F F F F F F V V
Tambin es posible determinar la validez del argumento construyendo la
tabla de verdad:
Como la tabla de verdad no es una tautologa el argumento no es vlido.
1.16 MODUS PONENS
,p p q q
Observe el razonamiento deductivo vlido
1.17 MODUS TOLLENS
(p q) ; ~q ~q
Observe el razonamiento deductivo vlido
1.18 CIRCUITOS LGICOS
Todas las proposiciones mostradas anteriormente, pueden ser traducidas a
p ; pq q p pq q
V V V V V V V V
V F F V F F V F
F V V F F V V V
F V F F F V V F
Pq ; ~q ~q pq ~q ~q
V F F V F F V F
F V F F F V V V
V F V V F F V F
V V V V V V V V
-
LGEBRA I 18
un circuito lgico, el cual muestra a travs de una lmpara encendida o
apagada la condicin de verdadero o falso respectivamente.
Cuando un circuito lgico requiere el uso de un mismo enunciado se
establece que si p es verdadero (interruptor cerrado), entonces ~p
(interruptor abierto) es falso y viceversa.
Todos los circuitos lgicos utilizan interruptores en serie para la
conjuncin y en paralelo para la disyuncin, las dems conectivas se
reducen a estos operadores para construir sus circuitos lgicos.
1.18.1 CONJUNCIN
1.18.2 DISYUNCIN
p ^ q
V V V
V F F
F F V
F F F
P v q
V V V
V V F
F V V
F F F
P q
-
LGEBRA DE PROPOSICIONES
19
1.18.3 NEGACIN CONJUNTA
1.18.4 CONDICIONAL O IMPLICACIN
V F V
V F F
F F V
F V F
~p ^ ~q
F F F
F F V
V F F
V V V
~p V q
F V V
F F F
V V V
V V F
P q
V V V
V F F
F V V
F V F
q
~p
q
~p
q
~p
~p
q
p
p
q
q
~q
~q
~p
~p
~p q p q
-
LGEBRA I 20
1.18.5 BICONDICIONAL O DOBLE IMPLICACIN
1.18.6 DISYUNCIN EXCLUSIVA O DIFERENCIA SIMTRICA
P q
V V V
V F F
F F V
F V F
p v q
( ) ~ ( )
( ) ~ (( ) ( ))
( ) ~ ( ) ~ ( )
( ) ( ~ ) ( ~ )
( ) ( ) ( ~ ) (~ ) (~ ~ )
( ) ( ) (~ ~ )
p q p q
p q p q q p
p q p q q p
p q p q q p
p q p q p p q q q p
p q p q p q
~q
p
q
~p
q
~p
~q
p
~q
p
q
~p
q
~p
~q
p
~ ~
p q p q q p
p q p q q p
-
LGEBRA DE PROPOSICIONES
21
p q p q p q
Ejemplo 16
Si se tiene el siguiente circuito lgico
a) Determinar la proposicin correspondiente
b) Simplificar y obtener la proposicin resultante ms simple del mismo
a) ( ) ( )p q p p q
V F V
V V F
F V V
F F F
~p
p
~q
q
~p
p
~q
q
~p
p
~q
q
~p
p
~q
q
q ~p
~q
p
p
-
LGEBRA I 22
La tabla de verdad correspondiente al circuito es:
(p V q) V (p (~p V ~q)
V V V V V F F F F
V V F V V V F V V
F V V V F F V V F
F F F F F F V V V
Puede observarse que las columnas de ( p V q ) y el resultado final de la
tabla son idnticas confirmando la reduccin efectuada
( ) ( ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( )
p q p p q
p q p p p q
p q f p q
p q p q
p q p p q q
p q p v
p q v
p q
-
LGEBRA DE PROPOSICIONES
23
Ejemplo 17
En el siguiente circuito lgico
La proposicin equivalente ser:
( ) ( ) ( )p p q r p r q r
Efectuando las reducciones se tiene:
(( ) ) (( ) ) ( ) ( )
(( ) ( ) (( ) ( ) ( ) ( )
p p q r p q p r q r r
p p r q r p p q p r q F
(( ) ( ) (( ) ( ) )
( ) ( ) ( )
p p r q r F q p r q
p p r q r q p
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
p p p r p q p r p q p p
F p r p q p r p q V
( ( )) (( ) )
( )
F p r p q V
F p q
p q
q q
~r
~p
r
p
p
r
-
LGEBRA I 24
La tabla de verdad es:
p V [((~p V q) (r V p)) V (r (q V ~r))] V V F V V V V V V V V V V V F
V V F V V V F V V V F F V V V
V F F F F F V V V F V F F F F
V F F F F F F V V F F F F V V
F F V V V V V V F V V V V V F
F F V V V F F F F V F F V V V
F F V V F V V V F F V F F F F
F F V V F F F F F F F F F V V
Que es equivalente a la tabla de verdad de
p q V V V
V V V
V F F
V F F
F F V
F F V
F F F
F F F
Y verifica la reduccin efectuada
top related