Tema-1-Logica-de-proposiciones.

pdf

clara_vb01

Lógica

2º Grado en Ingeniería Informática

Escuela Superior de Ingeniería Informática

Universidad de Castilla-La Mancha

Reservados todos los derechos.

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
 Proposiciones

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
Una proposición es una expresión tal que:
i. Tiene sentido
ii. Afirma o niega algo
iii. De la que se puede saber inequívocamente su verdad
Interesan los enunciados declarativos expresados en el modo indicativo en presente, aunque también en pasado o futuro

Las proposiciones se pueden simbolizar mediante una variable proposicional p, q r, s…

Denotaremos por al conjunto de todas las proposiciones

= { p : p es proposición}
Toda proposición admite dos valores de verdad: Verdadero (V) y Falso (F)
Para expresar que una proposición p es (o se interpreta) como verdadera o falsa escribiremos:

Reservados todos los derechos.

Una proposición es verdadera (1) / falsa(0)

Una proposición simple o anatómica puede considerarse como una unidad mínima de lenguaje con
un contenido información:
 Siete es un número primo -> Proposición simple
 Juan y José son médicos ≡ Juan es médico y José es médico.

Una proposición compuesta es un enunciado formado por proposiciones simples que se unen
mediante conectivos (caracteres matemáticos que permiten unir varias proposiciones)

El valor de verdad de una proposición compuesta está determinado por la verdad de las
proposiciones simples que la componen y de los conectivos que unen dichas proposiciones.
Cuando dos proposiciones (simples o compuestas) p y q tienen siempre el mismo valor de verdad
escribimos p = q o p ≡ q p q r
Para obtener el valor de verdad de una proposición V V V
compuesta se construya su tabla de verdad, un esquema V V F
tabular que expresa el valor de verdad de una proposición V F V
V F F
compuesta a partir del valor de verdad de las proposiciones F V V
simples. La tabla de verdad de una proposición compuesta F V F
por n proposiciones simples tiene 2n filas. F F V
F F F
Conectivos. Propiedades
Dadas las proposiciones p, q  formamos la expresión
‘p y q’ tal que:
i. Tiene sentido
ii. Afirma o niega algo
iii. Su verdad viene dada por la tabla
Se simboliza por ∧, de manera que para cualesquiera p, q , también p∧q . Por tanto ∧ es
una operación interna en ∧: x →

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3263831
  2 y½
 Todo triángulo es un polígono y algún polígono tiene cuatro lados.
∧ recoge el sentido de la conjunción ‘y’ usual, pero formaliza también expresiones del tipo:
 No abre la escuela, aunque es lunes
 p es proposición simple, pero p y q es compuesta.
 Hoy no es festivo, mañana tampoco.

Dadas las proposiciones p, q  formamos la expresión

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
‘p o q’ tal que:
i. Tiene sentido
ii. Afirma o niega algo
iii. Su verdad viene dada por la tabla
Se simboliza por ∨, de manera que para cualesquiera p, q , también
p∨q . Por tanto ∨ es una operación interna en ∨: x →

 2 o½
 Todo triángulo es un polígono o algún polígono es redondo.
∧(AND): P x P → p

Reservados todos los derechos.

(p,q) → p∧q
∨ recoge el sentido de la conjunción ‘o’ inclusiva usual, pero no formaliza
expresiones del lenguaje ordinario del tipo (disyunciones exclusivas): ∨(OR): P x P → p
 o bien dentro o bien fuera. (p,q) → p∨q
 o culpable o inocente.

Dada la proposición p  formamos la expresión ‘no p’ tal que:

i. Tiene sentido
ii. Afirma o niega algo
iii. Su verdad viene dada por la tabla
Se simboliza por p’, de manera que, para cualquier p , p’ . Por tanto, ‘ es una aplicación
‘: →
Leyes de morgan
Dadas p, q  , se verifican las Leyes de Morgan:
p q p ∧ q (p ∧ q)’ p’ q’ p’ ∨ q ‘
 (p ∧ q)’ = p’ ∨ q ‘ V V V F F F F
V F F V F V V
F V F V V F V
F F F V V V V
p q p ∨ q (p ∨ q)’ p’ q’ p’ ∧ q ‘
 (p ∨ q)’ = p’ ∧ q’ V V V F F F F
V F V F F V F
F V V F V F F
F F F V V V V

Descarga la app de Wuolah desde tu store favorita

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3263831
 Pueden generalizarse a un número finito arbitrario de proposiciones:
 (p1 ∧ p2 ∧ … ∧ pn)’ = p’1 ∨ p’2 ∨ … ∨ p’n
 (p1 ∨ p2 ∨ … ∨ pn)’ = p’1 ∧ p’2 ∧ … ∧ p’n

Propiedad involutiva de la negación

p p’ p’’
Dadas p  , se verifica la propiedad involutiva de la negación: V F V
F V F
 p’’ = p

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
Álgebra de Boole de Proposiciones
Los conectivos ∧,∨ satisfacen las propiedades:
1) Idempotente: ∀ p , p ∧ p = p, p ∨ p = p
2) Conmutativa: ∀ p, q , p ∧ q = q ∧ p, p ∨ q = q ∨ p
3) Asociativa: ∀ p, q, r , p ∧ (q ∧ r) = (p ∧ q) ∧ r, p ∨ (q ∨ r) = (p ∨ q) ∨ r,
4) Absorción: ∀ p, q , p ∧ (p ∨ q) = p, p ∨ (p ∧ q) = p
5) Distributiva: ∀ p, q, r , p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r)
6) Existencia de elemento neutro: O / ∀p , p ∧ O = O, p ∨ O = p

Reservados todos los derechos.

7) Existencia de elemento universal: I / ∀p , p ∧ I = p, p ∨ I = I
8) Existencia de complementario: ∀p / p’ / p ∧ p’ = O, p ∨ p’ = I

Tautología p q r p ∧ q(AND) (p ∧ q) ∨ r q ∨ r(OR) p ∧ (q ∨ r)

V V V V V V V
Proposición siempre verdadera que se
denota por I. (T) V V F V V V V
V F V F V V V
Contradicción
V F F F F V F
Proposición siempre falsa que se
F V V F V V F
denota por O. (⊥) F V F F F V F
Complementario de p F F V F V F F
Negación de una proposición p (p’). F F F F F F F
Para cada proposición p , su complementario es único.
Dadas dos proposiciones p,q , si se verifica que p ∧ q = O y p ∨ q = I, entonces q = p’.

∧ ∨ ‘ En el que:
 es el conjunto de proposiciones.
 ∧, ∨ son operaciones internas en .
 ‘ es una aplicación de en .
 O es una proposición siempre falsa.
 I es una proposición siempre verdadera.
Se llama Algebra de Boole de proposiciones por verificarse las propiedades mencionadas.

Descarga la app de Wuolah desde tu store favorita

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3263831
  (p ∧ q) ∧ (p’ ∨ q’) = O
(p ∧ q) ∧ (p’ ∨ q’) =(5) ((p ∧ q) ∧ p’) ∨ ((p ∧ q) ∧ q’) =(2)(3) ((p ∧ p’) ∧ q) ∨ (p ∧ (q ∧ q’)) =(8)

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
(O ∧ q) ∨ (p ∧ O) =(6) O ∨ O =(6) = O

 (p ∧ q) ∨ (p’ ∨ q’) = I
(p ∧ q) ∨ (p’ ∨ q’) =(5)(2)(3) (p’ ∨ q’ ∨ p) ∧ (p’ ∨ q’ ∨ q) =(2)(8) (I ∨ q’) ∧ (p’ ∨ I) = I

Implicación Lógica. Expresiones asociadas

… … Dadas las proposiciones p, q  formamos la
expresión ‘si p entonces q’ tal que:
i. Tiene sentido
ii. Afirma o niega algo
iii. Su verdad viene dada por la tabla

Reservados todos los derechos.

Se simboliza por ⇒, de manera que para cualesquiera p, q , p ⇒ q
A p ⇒ q se le denomina condicional o implicación.
p⇒q
p se denomina hipótesis o antecedente y q se denomina tesis o consecuente.
También se dice que p es condición suficiente para q y que q es condición necesaria para p.

 Si 3 es un número natural entonces 3 es

un número entero. La señora White es culpable w
 Si hoy es martes entonces mañana es La señorita Scarlet es culpable s
jueves. El Coronel Mustard es culpable m
 Todo número real es un cuadrado, si es
positivo. Al menos uno de ellos es culpable w∨s∨m
No todos son culpables (w ∧ s ∧ m)’
 Cuando Pavarotti cante la Traviata, iré Si la señora White es culpable, entonces el Coronel
al Palacio Real. Mustard también es culpable w⇒m
 Siempre que llega el domingo, aprovecho Si la señorita Scarlet es inocente, entonces el
para leer. Coronel Mustard también es inocente s’ ⇒ m’

Si la hipótesis es falsa, la implicación es verdadera independientemente de la verdad de la tesis.

 Si 2+3=6, el Tajo pasa por Albacete.

Algunas frases para expresar p ⇒ q // (p (llueve), q (hay nubes))

 Si p, entonces q.  Cuando p, q.  p es una condición
 p implica q.  q siempre que p. suficiente para q.
 No p a menos que q.  p es suficiente para q.  q es una condición
 q si p.  q es necesaria para p. necesaria para p.

Condición necesaria y suficiente (implicación para ambos sentidos)

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3263831
 Se verifica que: p ⇒ q = p’ ∨ q
En consecuencia su negación viene dada por: (p ⇒ q)’ = (p’ ∨ q)’ = p’’ ∧ q’ = p ∧ q’
p q p ⇒ q p’ q p’ ∨ q
⇒ V V V F V V
 Recíproca: q ⇒ p V F F F F F
 Contraria: p’ ⇒ q’ F V V V V V
 Contrarrecíproca: q’ ⇒ p’ F F V V F V
 Negación: p ∧ q’

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
q’ ⇒ p’ = (q’)’ ∨ p’ = q ∨ p’ = p’ ∨ q
Se verifica que
 Directa = Contrarrecíproca  Recíproca = Contraria
p⇒q = q’ ⇒ p’ q⇒p = p’ ⇒ q’

p ⇒ q ≡ p’ ∨ q
i. p⇒p (p ⇒ q)’ ≡ (p’ ∨ q)’ ≡ p ∧ q’
p⇒p ≡ p’ ∨ p =(8) I

ii. p∧q⇒p // p ∧ q ⇒ q La conjunción de dos proposiciones implica cualquiera de ellas

Reservados todos los derechos.

(p ∧ q) ⇒ p ≡ (p ∧ q)’ ∨ p ≡ p’ ∨ q’ ∨ p ≡ q’ ∨ p’ ∨ p ≡ q’ ∨ I ≡ I

iii. p⇒p∨q
p ⇒ p ∨ q ≡ p’ ∨ (p ∨ q) ≡ I ∨ q ≡ I

iv. p ⇒ I, O ⇒ p
p⇒I Como la tesis (I) es verdadera, la implicación siempre es verdadera
p ⇒ I ≡ p’ ∨ I ≡ I
O⇒p Si la hipótesis es falsa, la implicación es siempre verdadera
O ⇒ p ≡ O’ ∨ p ≡ I ∨ p ≡ I

v. [(p ⇒ q) ∧ p] ⇒ q (Modus Ponens)

p⇒q q Si estudio entonces apruebo Apruebo
p He estudiado
[(p ⇒ q) ∧ p] ≡ (p’ ∨ q) ∧ p ≡(5) (p’ ∧ p) ∨ (q ∧ p) ≡(8) O ∨ (q ∧ p) ≡(6) (q ∧ p) ⇒ q(ii)

vi. [(p ⇒ q) ∧ q’] ⇒ p’ (Modus Tollens)

p ⇒ q p’ Si estudio entonces apruebo No he estudiado
q’ No he aprobado
[(p ∨ q) ∧ q’] ≡ (p’ ∨ q) ∧ q’ ≡(5) (p’ ∧ q’) ∨ (q ∧ q’) ≡(8) (p’ ∧ q’) ∨ O ≡(6) (p’ ∧ q’) ⇒ p’(ii)

vii. [(p ∨ q) ∧ p’] ⇒ q (Ley del Silogismo Disyuntivo)

p∨q q Pasa p o q Entonces pasa q
p’ Si no pasa p
(p ∨ q) ∧ p’ ≡(5) (p ∧ p’) ∨ (q ∧ p’) ≡(8) O ∨ (q ∧ p’) ≡(6) (q ∧ p’) ⇒ q(ii)

Descarga la app de Wuolah desde tu store favorita

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3263831
 viii. [(p ∨ q) ∧ (p ⇒ r) ∧ (q ⇒ r)] ⇒ r (Dilema)
p∨q Pasa p o q
p⇒r r Si pasa p entonces r Pase lo que pase, r
q⇒r Si pasa q entonces r
(p ∨ q) ∧ (p ⇒ r) ∧ (q ⇒ r) ≡ (p ∨ q) ∧ (p’ ∨ r) ∧ (q’ ∨ r) ≡(5) (p ∨ q) ∧ ((p’ ∧ q’) ∨ r)
≡(Leyes de Morgan) (p ∨ q) ∧ ((p ∨ q)’ ∨ r) ≡(5) ((p ∨ q) ∧ (p ∨ q)’) ∨ ((p ∨ q) ∧ r) ≡(8)
≡(8) (O ∨ ((p ∨ q) ∧ r) ≡(7) ((p ∨ q) ∧ r) ⇒ r (ii)

ix. [(p ∨ q) ∧ (p ⇒ r) ∧ (q ⇒ s)] ⇒ (r ∨ s) (Dilema Constructivo)

p∨q Pasa p o q

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
p⇒r r∨s Si pasa p pasa r Va a pasar alguna de las dos (r o s)
q⇒s Si pasa q pasa s
[(p ∨ q) ∧ (p ⇒ r) ∧ (q ⇒ s)] ⇒ (r ∨ s) ≡ ((p ∨ q) ∧ (p’ ∨ r) ∧ (q’ ∨ s))’ ∨ (r ∨ s) ≡
≡(Leyes de Morgan) ((p ∨ q)’ ∨ (p’ ∨ r)’ ∨ (q’ ∨ s)’) ∨ (r ∨ s) ≡
≡(Leyes de Morgan), p’’ = p ((p ∨ q)’ ∨ (p ∧ r’) ∨ (q ∧ s’)) ∨ (r ∨ s) ≡
≡(2)(3) (p ∨ q)’ ∨ ((p ∧ r’) ∨ r) ∨ ((q ∧ s’) ∨ s) ≡(5)(8)(7) (p ∨ q)’ ∨ (p ∨ r) ∨ (q ∨ s) ≡
≡(2)(3) (p ∨ q)’ ∨ (p ∨ q) ∨ (r ∨ s) ≡(8) I ∨ (r ∨ s) ≡(7) I

x. [(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r) (Transitiva)

Reservados todos los derechos.

p⇒q p⇒r Si pasa p pasa q entonces si pasa p pasa r
q⇒r Si pasa q pasa r
(A partir de xi) se sigue que:
[[(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r)] ≡ [[(p ⇒ q) ∧ (q ⇒ r) ∧ p] ⇒ r]
Por Modus Ponens de p ⇒ q y p se deduce la proposición q y de q ⇒ r y q se deduce r.

xi. [p ⇒ (q ⇒ r)] = [(p ∧ q) ⇒ r] Premisa 1 Premisa 1

Premisa 2 (H ⇒ T) ≡ Premisa 2
p ⇒ (q ⇒ r) ≡ p ∧ q ⇒ r
…………. …………… T
Se lleva la hipótesis con las premisas
Premisa n Premisa n
p ⇒ (q ⇒ r)] ≡ p’ ∨ (q’ ∨ r) ≡ p’ ∨ q’ ∨ r H
(p ∧ q) ⇒ r ≡ (p ∧ q)’ ∨ r ≡ p’ ∨ q’ ∨ r Se lleva la hipótesis con las premisas
… …
Dadas las proposiciones p, q  formamos la p⇒q [r’ ∧ s ⇒ p’]
expresión ‘p si, y solo si, q’ tal que: q ⇒r ∨s
i. Tiene sentido Que es igual a
ii. Afirma o niega algo p⇒q Si q implica r ∨ s
iii. Su verdad viene dada por q ⇒ r ∨ s p’ y no ocurre q,
la tabla r’ ∧ s’ entonces p’
↑(r ∨ s)’

Se simboliza por ⇔, de manera que para cualesquiera p, q , p ⇔ q

p ⇔ q es una doble implicación, pues
p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p) ≡ (p’ ∨ q) ∧ (q’ ∨ p)
Si p ⇔ q diremos que p equivale a p o que p y q son lógicamente equivalentes. También que p
es condición necesaria y suficiente para q.

Descarga la app de Wuolah desde tu store favorita

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3263831
 Negación de la equivalencia lógica:
(p ⇔ q)’ ≡ [(p ⇒ q) ∧ (q ⇒ p)]’ ≡ (p ⇒ q)’ ∨ (q ⇒ p)’ ≡ (p ∧ q’) ∨ (q ∧ p’)

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
… …
p ⇒ q y p’ ∨ q son equivalentes
Dadas las proposiciones p, q  formamos la expresión ‘o p ⇒ q y q’ ⇒ p’ son equivalentes
p o q tal que: q ⇒ p y p’ ⇒ q’ son equivalentes
i. Tiene sentido
ii. Afirma o niega algo
iii. Su verdad viene dada por la tabla

Se simboliza por , de manera que para cualesquiera p, q , p q

p q es una disyunción exclusiva: es cierta cuando una y sólo una de las proposiciones p, q es
cierta. Formaliza expresiones del tipo:

Reservados todos los derechos.

 o dentro o fuera
 o culpable o inocente
Por p q pueden formalizarse también expresiones del tipo ‘o bien p o bien q’
Observar que:
p q ≡ (p ⇔ q)’ ≡ (p ∧ q’) ∨ (q ∧ p’) p q ≡ (p ⇔ q)’
p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p) ≡ (p’ ∨ q) ∧ (q’ ∨ p) (p q) ∧ (p ⇔ q) ≡ O

Formas de demostración Matemática

Un razonamiento formalmente válido es una implicación verdadera del tipo
p1 ∧ p2 ∧ … ∧ pn ⇒ q
Con p1, p2, …, pn verdaderas simultáneamente. En está situación, p1, p2, …, pn se denominan
premisas y q conclusión.
También diremos que q es consecuencia lógica o que se deduce de p1, p2, …, pn
Decir que p1 ∧ p2 ∧ … ∧ pn ⇒ q es un razonamiento formalmente válido, es equivalente a decir
que es una tautología.

 ⇒ ’⇒ ∨
(p ⇒ q)’ ≡ (p’ ∨ q)’ ≡ (p ∧ q’) ⇒(ii)p ⇒(iii) p ∨ r
p ∧ q’ ⇒ p
p ⇒p ∨r

También se puede demostrar comprobando que (p ⇒ q)’ ⇒ (p ∨ r) es una tautología:

((p ⇒ q)’ ⇒ (p ∨ r)) ≡ ((p’ ∨ q)’) ⇒ (p ∨ r)) ≡ p’ ∨ q ∨ p ∨ r ≡ I ∨ q ∨ r ≡ I

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3263831
 Un condicional p ⇒ q es un teorema si es verdadero siempre que p es verdadera, es decir, si es
un razonamiento formalmente válido.
Formas de demostrar un teorema p ⇒ q y ejemplos:
 Directa: Consiste en probar que si p es cierta, entonces también lo es q.
p ∧ q ⇒p ∨q ∨r
p ∧ q ⇒(II) p ⇒(III) p ∨ q ⇒(III) p ∨ q ∨ r

 Contrarrecíproca: Consiste en probar que si q es falsa, entonces también lo es p.

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
(p ⇒ q)’ ⇒ (p ∨ r) Para ello probaremos que: (p ∨ r)’ ⇒ (p ⇒ q)
(p ∨ r)’ ⇒ (p ⇒ q) ≡ (p ∨ r) ∨ (p’ ∨ q) ≡ p ∨ p’ ∨ r ∨ q ≡ I ∨ r ∨ q ≡ I

 Reducción al absurdo: Consiste en obtener una contradicción de suponer que p es verdadera

y q es falsa. Es decir, viendo que p y q’ no pueden ser ciertas simultáneamente.
[(p ⇒ q) ∧ q’] ⇒ p’ (Modus Tollens)

Supongamos que p’ es falsa (p verdadera). Junto con la premisa (p ⇒ q) ∧ q’ esto es

(p ⇒ q) ∧ q’ ∧ p ≡ (p’ ∨ q) ∧ (q’ ∧ p) ≡ (p’ ∨ q) ∧ (q ∨ p’)’ ≡ (p’ ∨ q) ∧ (p’ ∨ q)’ ≡ O

Reservados todos los derechos.

Sintaxis: Alfabeto, fórmulas
El lenguaje de la lógica de proposiciones se denota por .
El alfabeto de la lógica proposicional tiene por símbolos:
 Variables proposicionales: p, q, r, …
 Conectivos: ∨, ∧, ‘, ⇒, ⇔, , …
 Símbolos impropios, como símbolos de puntuación, paréntesis, etc.

Una fórmula proposicional es cualquier expresión escrita con variables proposicionales

unidas mediante conectivos.
El conjunto de fórmulas proposicionales del lenguaje de la lógica proposicional se obtiene
conforme las reglas:
Las variables proposicionales son fórmulas.
Si A y B son fórmulas, también lo son A ∨ B, A ∧ B, A‘, A ⇒ B, A ⇔ B, A B, …

El empleo de paréntesis y corchetes permite definir con precisión la

proposición compuesta de que se trata y evitar así confusiones. Cuando la proposición compuesta
está escrita sin paréntesis, el órden de prioridad de las operaciones es:
‘ , {∨, ∧}, {⇒, ⇔}

n
Una función proposicional f de n variables es una aplicación f : →
tal que f(p1, p2, …, pn) es una fórmula proposicional.

Descarga la app de Wuolah desde tu store favorita

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3263831