Logica Proposicional, Teoremas y Demostraciones

L´ogica Proposicional, Teoremas y Demostraciones
Manuel Maia
19 de marzo de 2012

1

Proposiciones

Una proposici´
on es una oraci´on declarativa o una expresi´on matem´atica que es verdadera
o es falsa, pero no ambas. De esta manera, una proposici´on tiene un valor de verdad,
que puede ser V, si es verdadera o puede ser F, si es falsa. Consideraremos exclusivamente
proposicionesmatem´aticas. Algunos ejemplos de proposiciones verdaderas son:
• “4 es un n´
umero entero par”.
• “15 ≤ 15”.
• “La soluci´on de 2x − 3 = 1 es 2”.
• “18 es m´
ultiplo de 3”.
Algunos ejemplos de proposiciones falsas son:
• “144 es un n´
umero entero impar”.
• “2 = 17”.
• “La soluci´on de 2x − 3 = 1 es 0”.
• “16 es m´
ultiplo de 5”.
Algunos ejemplos de expresiones que no son proposicionesson:
• “ 73”.
• “2x − 1 = 3”.
• “¿Cu´al es la soluci´on de 2x − 3 = 1?”.
1

• “x es m´
ultiplo de 3”.
Generalmente, para referirnos a proposiciones espec´ıficas se usan letras may´
usculas. Por
ejemplo,
P : 25 es un n´
umero entero par.
Q : 3 + 4 = 7.
R : 2x + 3 es una ecuaci´on.
Las proposiciones pueden contener variables. Por ejemplo, sea x un n´
umero entero y
consideremos
P: 2x + 1 es un entero impar.
Esta es una proposici´on que es verdadera no importa que n´
umero entero sea la variable x.
Entonces podemos denotarla por
P (x) : 2x + 1 es un entero impar.
Hay oraciones o expresiones matem´aticas que contienen variables y no son proposiciones.
Por ejemplo,
Q(x) : El n´
umero entero x es m´
ultiplo de 3.
S´olo ser´a una proposici´on cuando le otorguemos unvalor a x (y as´ı podremos determinar
si es verdadera o falsa). Por ejemplo, Q(13) es falsa y Q(21) es verdadera. Una expresi´on
como Q(x), cuyo valor de verdad depende de una o m´as variables, es lo que se llama una
expresi´
on abierta.

2

Conectivos L´
ogicos

Podemos usar la palabra “y” para conectar dos proposiciones y crear una nueva proposici´on.
Por ejemplo, podemos conectarlas proposiciones
P : El n´
umero 4 es un entero par.
Q : El n´
umero 5 es un entero impar.
para formar la nueva proposici´on
2

R : El n´
umero 4 es un entero par y el n´
umero 5 es un entero impar.
La proposici´on R afirma que P y Q son ambas verdaderas. Como P y Q, en efecto son
verdaderas, la proposici´on R tambi´en lo es.
As´ı, dadas dos proposiciones cualesquiera P y Q, podemoscombinarlas para formar una
nueva proposici´on “P y Q”. Se usa el s´ımbolo ∧ para indicar la palabra “y”. De esta
manera, P ∧ Q significa “P y Q”.
La proposici´on P ∧ Q es verdadera si ambas proposiciones P y Q son verdaderas. En
cualquier otro caso, es falsa. Esto se resume en la siguiente tabla de verdad.
P

Q

P ∧Q

V

V

V

V

F

F

F

V

F

F

F

F

En cadafila aparece una de las cuatro posibles combinaciones de valores de verdad para P
y Q. Por ejemplo, si P es falsa y Q es verdadera, entonces P ∧ Q es falsa.
Tambi´en podemos conectar dos proposiciones usando la palabra “o” para crear una nueva
proposici´on. Dadas dos proposiciones cualesquiera P y Q, la afirmaci´on “P o Q” significa
que una o ambas proposiciones son verdaderas. Esto difiere delsignificado usual que tiene
“o” en el lenguaje cotidiano, donde significa una alternativa o la otra, de manera excluyente,
cuando hay dos alternativas. De esta manera, por ejemplo, la proposici´on
“El n´
umero entero 4 es par o el n´
umero entero 3 es par”
es verdadera.
Se usa el s´ımbolo ∨ para indicar la palabra “o”. As´ı, P ∨ Q significa “P o Q”. La tabla
de verdad para P ∨ Q es lasiguiente.
P

Q

P ∨Q

V

V

V

V

F

V

F

V

V

F

F

F

Otra manera de obtener nuevas proposiciones a partir de otras es usando la palabra
“no”. Dada una proposici´on cualquiera P, podemos formar una nueva proposici´on “no es
verdadero que P ”. Por ejemplo, si consideramos la proposici´on (verdadera)
3

“El n´
umero entero 3 es impar”,
podemos formar la...