logica

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

1

Proposiciones

Una proposici´n es una oraci´n declarativa o una expresi´n matem´tica que es verdadera
o
o
o
a
o es falsa, pero no ambas. De esta manera, una proposici´n tiene un valor de verdad,
o
que puede ser V, si es verdadera o puede ser F, si es falsa. Consideraremos exclusivamenteproposiciones matem´ticas. Algunos ejemplos de proposiciones verdaderas son:
a
• “4 es un n´mero entero par”.
u
• “15 ≤ 15”.
• “La soluci´n de 2x − 3 = 1 es 2”.
o
• “18 es m´ltiplo de 3”.
u
Algunos ejemplos de proposiciones falsas son:
• “144 es un n´mero entero impar”.
u
• “2 = 17”.
• “La soluci´n de 2x − 3 = 1 es 0”.
o
• “16 es m´ltiplo de 5”.
u
Algunos ejemplos de expresiones que noson proposiciones son:
• “ 73”.
• “2x − 1 = 3”.
• “¿Cu´l es la soluci´n de 2x − 3 = 1?”.
a
o
1

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

2

Conectivos L´gicos
o

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

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

Q

P ∧Q

V

V

VV

F

F

F

V

F

F

F

F

En cada fila 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´n podemos conectar dos proposiciones usando la palabra “o” para crear una nueva
e
proposici´n. Dadas dos proposiciones cualesquiera P y Q, la afirmaci´n “P o Q” significa
o
o
queuna o ambas proposiciones son verdaderas. Esto difiere del significado 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´n
o
“El n´mero entero 4 es par o el n´mero entero 3 es par”
u
u
es verdadera.
Se usa el s´
ımbolo ∨ para indicar la palabra “o”. As´ P ∨ Qsignifica “P o Q”. La tabla
ı,
de verdad para P ∨ Q es la siguiente.
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´n cualquiera P, podemos formar una nueva proposici´n “no es
o
o
verdadero que P ”. Por ejemplo, si consideramos la proposici´n (verdadera)...