Derechos

Matem´tica Discreta - IIC 2252 a Clase 11 Demostraci´n de teoremas. o ´ Algebras de Boole.

1

Demostraci´n de teoremas o
Una de las aplicaciones m´s importantes de la l´gica est´ dada por una a o a variedad de t´cnicas para la demostraci´n de teoremas. Mencionaremos e o s´lo tres: o Demostraci´n de implicaciones. o Demostraciones por contradicci´n. o Demostraci´n por casos. o

2

Laimplicaci´n o
Consideremos la implicaci´n P → Q. Hay otras tres proposiciones o (todas implicaciones) muy relacionadas a ´sta: e Su proposici´n rec´ o ıproca, Q → P . Su proposici´n contraria, ¬P → ¬Q. o Su proposici´n contrarec´ o ıproca, ¬Q → ¬P . De estas tres, s´lo la ultima es l´gicamente equivalente a la primera; las o ´ o otras dos son l´gicamente equivalentes entre s´ o ı. As´ cuandoqueramos demostrar un teorema de la forma P → Q, ı, podemos equivalentemente demostrar el contrarrec´ ıproco (pero no el rec´ ıproco o el contrario).

3

Demostraciones por contradicci´n (reductio o ad absurdum).
Supongamos que queremos demostrar P . Ya que P ⇔ (¬P → Fo ), podemos equivalentemente demostrar que ¬P → Fo , o sea, que si se supone que P es falso se deduce una contradicci´n. o Enparticular, para demostrar una implicaci´n de la forma P → Q, o o basta probar que de P ∧ ¬Q se deduce una contradicci´n.

4

Ejemplo de demostraci´n por contradicci´n o o
La siguiente es una demostraci´n, debida a Arqu´ o ımedes, de que los primos son un conjunto infinito. Supongamos que no es as´ Sea P el ı. conjunto de todos los primos, y supongamos que dicho conjunto es finito, digamos P ={p1 , p2 , . . . , pn } . Consideremos el n´mero u N = p1 p2 · · · pn + 1. Claramente, N no es divisible por ninguno de los elementos de P. Pero N debe ser divisible por alg´n primo q (¿por qu´?), de donde se u e desprende que dicho primo q no pertenece a P. Pero entonces q es un primo que no pertenece a P, lo cual contradice la hip´tesis de que P es o el conjunto que contiene a todos los primos.
5Demostraci´n por casos o
La equivalencia l´gica o (P ∨ Q) → R ⇔ (P → R) ∧ (Q → R) nos sugiere que, en vez de demostrar (P ∨ Q) → R, podemos demostrar equivalentemente que: (P → R), y (Q → R). En particular, como P ⇔ To → P ⇔ (Q ∨ ¬Q) → P, podemos demostrar P probando que Q → P y que ¬Q → P .

6

Ejemplo de demostraci´n por casos o
Para demostrar que n ∈ Z → n2 − 3 no es m´ltiplo de 4 ubasta probar que, si n es par, entonces n2 − 3 no es m´ltiplo de 4, y u que si n es impar, entonces n2 − 3 no es m´ltiplo de 4. u

7

´ Definici´n de Algebra de Boole o
´ Un Algebra de Boole es una estructura B, , , (·) , ˆ ˆ , 0, 1 donde B es un conjunto (el dominio o universo) (·) : B −→ B , : B × B −→ B

´ ˆ ˆ ∈ B (los elementos distinguidos del Algebra de Boole). 0, 1 que tiene lassiguientes propiedades:

8

´ Propiedades de las Algebras de Boole
AB1 Conmutatividad a AB2 Asociatividad (a (a AB3 Distributividad a a AB4 Elementos neutros a AB5 Complementos a a =ˆ 1
9

Para todo a, b ∈ B: b=b a a b=b a

b) b)

c=a c=a

(b (b

c) c)

(b (b

c) = (a c) = (a ˆ=a 0

b) b)

(a (a ˆ=a 1 a =ˆ 0

c) c)

a

a

Observaciones:
AB1 - AB5 son los axiomas dela teor´ de las ´lgebras de Boole ıa a Ejercicio: Verificar que cada una de las tres estructuras que presentamos antes son AB Hay que interpretar los s´ ımbolos de los axiomas en la forma correspondiente a cada estructura en cuesti´n, por ejemplo, en el o caso de los conjuntos, AB5 se interpreta en la forma: A ∪ Ac = U , etc. ´ La teor´ de Algebra de Boole est´ formada por las proposiciones ıa aque se deducen matem´ticamente a partir de los axiomas: los a teoremas.

10

´ Teoremas del Algebra de Boole
TEOREMA 1: IDEMPOTENCIA 1. a Observaciones: El teorema dice que en toda AB y para todo elemento a en su dominio se cumple la propiedad. ¿De donde sale el teorema? Se cumple en una AB particular y se conjetura que puede ser verdadero en toda AB. Se intuye directamente de los axiomas....