EQUIVALENCIAS LÓGICAS-IMPLICACIONES LÓGICAS

Vista previa del material en texto

Tecnólogo en Informática 
Sede Paysandú 
Matemática Discreta y Lógica I. Primer semestre. 
Prof. Fernando Gerfauo Año 2015.- 
 
 
FICHA Nº 11. EQUIVALENCIAS LÓGICAS-IMPLICACIONES LÓGICAS 
 
 
Actividad 1. 
Sean qp, y ,r proposiciones primitivas. 
Utilizando tablas de verdad, verifica las siguientes equivalencias lógicas: 
a) qppqqp ↔⇔→∧→ )()( 
b) ( ))()( pqqp ¬→¬⇔→ 
c) ( ) rqprqp ∨∧¬⇔→∧ )()( 
d) ( ) ( ) qpqppqp ∧⇔∧∧∧∨¬ )()( 
 
Actividad 2. Reglas de sustitución. 
Sean qp, y ,r proposiciones primitivas. 
a) La proposición compuesta :P ))(()( qpqp ∨¬↔→ es una tautología. Si en esta 
tautología se remplaza cada ocurrencia de p por la proposición compuesta )( rq ¬∧ se 
obtiene una nueva proposición: )))(((()))(((:' qrqqrqP ∨¬∧¬↔→¬∧ 
Comprueba, mediante tablas de verdad, que 'P es una tautología. 
 
Regla 1. 
Sea P una tautología y p una proposición primitiva que aparece en .P 
Si en la proposición P se remplaza cada ocurrencia de p por otra proposición ,α la 
nueva proposición compuesta que se obtiene, también es una tautología. 
 
b) Considera la proposición rqpP →→ )(: . Si en ella se sustituye la proposición 
qp →:α por la proposición :β ,)( qp ∨¬ se obtiene una nueva proposición 
.))((:' rqpP →∨¬ Verifica, mediante tablas de verdad, que P y 'P son lógicamente 
equivalentes, esto es '.PP ⇔ 
 
Regla 2. 
Sea P un proposición compuesta donde α es una proposición arbitraria que aparece 
en ella, y sea β otra proposición tal que .βα ⇔ Si en P se remplaza una (o más) 
ocurrencia de α por ,β entonces, la nueva proporción 'P que así se obtiene, es 
lógicamente equivalente a la primera, o sea '.PP ⇔ 
 
Actividad 3. 
Sean srqp ,,, y ,t proposiciones primitivas. 
Utilizando las reglas de sustitución planteadas en la actividad anterior, verifica que 
cada una de las siguientes proposiciones es una tautología: 
 
a) ( ) ( )))(()( rqprqp ∧∨¬∨∧∨ 
b) ( ) ( )( )( )))(()( rqprqp ∧→¬∧∧→¬ 
c) ( ) ( ) ( )( )trqpsrqptsrqp ∨→∨∧∨→∨↔∧∨→∨ ))(())(()())(( 
d) ( ) ( ))())(()()( trqptrqp ∧∨∨¬↔∧→∨ 
Tecnólogo en Informática 
Sede Paysandú 
Matemática Discreta y Lógica I. Primer semestre. 
Prof. Fernando Gerfauo Año 2015.- 
 
Actividad 4. 
Cita las razones para cada paso de las siguientes simplificaciones: 
 
a) 
( ) qqpqp ∨¬∨∧∨ ))(()( Razones 
( ) qqqp ∨¬∧∨⇔ ))(( 
( ) qFp ∨∨⇔ 0 
qp ∨⇔ 
 
b) 
( ) ( ) qprqpqp ∧⇔∧∧→¬∨¬ )()( Razones 
)())()(( rqpqp ∧∧∨¬∨¬¬⇔ 
( ) )())(())(( rqpqp ∧∧∨¬¬∧¬¬⇔ 
( ) ( )rqpqp ∧∧∨∧⇔ 
qp ∧⇔ 
 
Actividad 5. 
Sean qp, y ,r proposiciones primitivas. Utilizando las leyes de la lógica y las reglas de 
sustitución, prueba que: 
i) ( ) pqpqp ⇔∧¬¬∧∨ ))(()( 
ii) rqprqp →¬∧⇔∨→ ))(()( 
iii) ( )( ) qqqpp ⇔∧→¬∧ )( 
iv) ( )( )( ) rqqrqp ∧⇔¬∨∧∨¬¬ )()( 
v) ( )( )( ) rqqrqp ∧⇔¬→∧∨¬ )()( 
 
Actividad 6. Implicaciones lógicas. 
Si α y β son proposiciones arbitrarias, tales que βα → es una tautología, entonces 
se dice que α implica lógicamente a ,β y se escribe .βα ⇒ 
 
Sean qp, y ,r proposiciones primitivas. Comprueba, utilizando tablas de verdad, que: 
a) qpqp ⇒∧→ )( 
b) )()()( pqqp ¬⇒¬∧→ 
c) rprqqp →⇒→∧→ )()( 
d) qpqp ⇒¬∧∨ )()( 
e) rqprqrp →∨⇒→∧→ )()()( 
 
 
Fuentes consultadas: 
∗ http://www.fing.edu.uy/inco/cursos/logica/teorico/2011/02_11_Induccion.pdf 
∗ Grimaldi, Ralph P. Matemáticas Discretas y Combinatoria. Tercera edición, 1994. Editorial: 
 Addison-Wesley Iberoamericana.