Logica

L´gica Proposicional, Teoremas y Demostraciones o
Manuel Maia 30 de septiembre de 2011

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 exclusivamente proposicionesmatem´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 no son 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 entero y u consideremos P : 2x + 1 es unentero 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´n cuando le otorguemos un valor a x (y as´ podremosdeterminar 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

Y, o, no

Podemos usar la palabra “y” para conectar dos proposiciones y crear una nueva proposici´n. o Por ejemplo, podemos conectar las proposiciones P : El n´mero 4 es unentero 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´ dadas dos 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. De o otra manera, es falsa. Esto se resume en la siguiente tabla de verdad. P V V F F Q V F V F P ∧Q V F F F

En cada fila aparece una de las cuatro posibles combinaciones de valores de verdad para P y Q. Por ejemplo, siP 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 que una o ambas proposiciones son verdaderas. Esto difiere del significado usual que tiene “o” en el lenguaje cotidiano, donde significa una alternativa o la otra, demanera excluyente, cuando hay dos alternativas. De esta manera, 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 ∨ Q significa “P o Q”. La tabla ı, de verdad para P ∨ Q es la siguiente. P V V F F Q V F V F P ∨Q V V V 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) o 3

“El n´mero entero 3 es impar”, u podemos formar la nueva proposici´n o “No es verdadero que el n´mero entero 3 es impar”, u la cual evidentemente es falsa. Se usa el s´ ımbolo ¬ para indicar la frase “no es verdadero que”....