capitulo 1 lógica

I.N.T. “SAN FERNANDO REY – Prof. en Matemática para el tercer ciclo de E.G.B y Polimodal – ÁLGEBRA -2003

CAPITULO 1 : LÓGICA PROPOSICIONAL

INTRODUCCIÓN:

Todo desarrollo matemático exige razonar en forma válida de cosas trascendentes y particularmente abstractas. Hay que comenzar por eliminar las ambigüedades del lenguaje ordinario, introduciendo símbolos y conectivos cuyo uso adecuado descarte las contingencias, aporte claridad y economía de pensamiento.

La lógica es el estudio del razonamiento; en particular, se analiza si un razonamiento es correcto. La lógica se centra en las relaciones entre los enunciados y no en el contenido de un enunciado en particular.

PROPOSICIONESConsideremos las siguientes oraciones:

a) Juan es inteligente.b) Pedro lee.c) 3 es un número par.d) 7 es un número primo.e) Deténgase.f) Buenos días.g) ¿Hacia donde va?

De estas siete oraciones diferentes, cuatro son declarativas, una orden, un saludo y una interrogación. De la cuatro primeras, que son declarativas, tiene sentido decir si son verdaderas o falsas. De las tres últimas no podemos decir que sean verdaderas o falsas, ya que una orden puede formularse o no, y una orden puede ser o no cumplida, pero no nos dan información. A las primeras las llamamos proposiciones.

Definición:Proposición es toda oración respecto de la cual puede decirse si es verdadera o falsa.

Es decir, proposición es toda oración declarativa. Toda proposición está asociada a un valor de verdad, el cual puede ser verdadero (V) o falso (F)

NOTACIONES Y CONECTIVOS

Así como en aritmética y álgebra se estudian operaciones entre números, en lógica proposicional se estudian operaciones con proposiciones.

Las proposiciones genéricas son denotadas con las letras p, q, r, etc. A partir de proposiciones simples es posible generar otras, simples o compuestas. Es decir, se puede operar con proposiciones, y según sean tales operaciones se utilizan ciertos símbolos, llamados conectivos

Conectivo Operación asociada Significado– ; Negación no p o no es cierto que p

Conjunción o producto lógico p y q Disyunción o suma lógica p o q ( en sentido incluyente) Implicación p implica q o si p entonces q Doble implicación p si y sólo si

Diferencia simétrica p o q ( en sentido excluyente)

OPERACIONES PROPOSICIONALES

NEGACIÓN :Definición:

Negación de la proposición p es la proposición p (no p), cuya tabla de verdad es:

p pV FF V

Se trata de una operación unitaria, pues a partir de una proposición se obtiene otra, que es su negación.Ejemplo P: 8 es un número primo p: no (8 es un número primo) = 8 no es un número primo o bien p: no es cierto que 8 es un número primoDe acuerdo al uso corriente de la negación parece claro que si p es V, su negación p es F.

1


CONJUNCIÓN. Definición:

Conjunción de las proposiciones p y q es la proposición p q (p y q), según sabemos la proposición p puede ser V o F y lo mismo sucede con q; esto significa que las dos posibilidades de V o F de la proposición p se combina con las dos posibilidades de q, lo que nos da 2 x 2 = 4 posibilidades para p q; esto significa que una tabla de verdad para dos proposiciones tiene 22 = 4 filas. Si tuviéramos n proposiciones tendríamos 2 n filas

La tabla de valores de verdad es: p q p qV V VV F FF V FF F F

La conjunción de dos proposiciones, p y q, es un enunciado compuesto, cuyo valor de verdad es intuitivo es claro ya que será verdadera si tanto p como q son verdaderas.

Las expresiones “pero”, “sin embargo”, “también” y “aunque” usadas para unir dos proposiciones tienen el mismo sentido conjuntivo de “y”, y por lo tanto pueden ser representadas por el símbolo conectivo.

También es conveniente señalar que no todo uso de “y” puede interpretarse como el conectivo conjunción. Por ejemplo “Newton y Laibniz fueron contemporáneos”.

Ejemplo:p: 1+1=3 q: un decenio tiene 10 añosp q : 1 + 1 = 3 y un decenio tiene 10 años.Como vemos p es F y q es V, entonces p q será F

Ejemplo:p: 3 es un número imparq: 2 es un número primop q : e es un número impar y 2 es un número primoEn este caso p es V y q es V, entonces p q será V.

DISYUNCIÓN : Definición:

La disyunción de dos proposiciones es una proposición compuesta que resulta verdadera cuando lo es al menos una de las dos proposiciones que la constituyen, y falsa en caso contrario, es decir, cuando las dos son falsas.

Se representa por (p q) y se lee “ p o q”.Su tabla de verdad es:

p q p qV V VV F VF V VF F F

Ejemplos:i) Hoy es lunes o martes. Representa la disyunción de las proposiciones: p: hoy es lunes q: hoy es martes.El sentido de la conjunción o es excluyente, ya que p y q no pueden ser simultáneamente

verdadera, y su valor de verdad deberá analizarse, a través de los tres últimos renglones, y será falsa sólo si las dos lo son.

ii) regalo los libros viejos o que no me sirven Representa la disyunción de las proposiciones: p: regalo los libros viejos q: regalo los libros viejos que no me sirvenEl sentido del o es incluyente, pues si en efecto regalo un libro que es viejo, y que además no

me sirve, entonces p q es V.

IMPLICACIÓN O CONDICIONAL: Definición:

Implicación de las proposiciones p y q es la proposición p q ( p implica q, si p entonces q) cuya tabla de verdad es:

2


p q p qV V VV F FF V VF F V

Las proposiciones p y q se llaman antecedente y consecuente de la implicación o condicional. La implicación usual en matemática es material, en el sentido de que no es necesario que el consecuente derive lógicamente del antecedente; cuando esto ocurre, la implicación se llama formal y queda incluida en la primera.

Las tablas de valores de verdad se definen arbitrariamente, pero respetando el sentido común.

Sea la siguiente proposición:“Si apruebo el examen, entonces te presto el apunte” (1)

Siendo:p: apruebo el examenq: te presto el apunte.

Interesa inducir la verdad o falsedad de la implicación (1), en términos de la V o F de p y q. Dicho enunciado puede pensarse como un compromiso, condicionado por p, y podemos asociar su verdad al cumplimiento del compromiso. Es obvio que si p es F, es decir, si no apruebo el examen, quedo liberado del compromiso, y preste o no preste el apunte la proposición (1) es V. Es decir, si el antecedente es F, la implicación es V.

Si p es V, en cuyo caso apruebo el examen, y no presto el apunte, el compromiso no se cumple, y la proposición (1) es F. Si p y q son V, entonces la implicación es V porque el compromiso se cumple.

Ejemplos:i) Si hoy es lunes, entonces mañana es martes. p: hoy es lunes. q: mañana es martes.Como no puede darse antecedente V y consecuente F, la implicación es V.

ii) 1 = –1 12 = (–1)2

es V por ser el antecedente F.

DOBLE IMPLICACIÓN O BICONDICIONAL: Definición

Doble implicación de las proposiciones p y q es la proposición p q (p si y solo si q), cuya tabla de verdad es:

p q p qV V VV F FF V FF F V

La doble implicación puede definirse como la conjunción de una implicación y su recíproca. De este modo, la tabla de valores de verdad de p q, pueden obtenerse mediante la tabla de (pq) (qp), como sigue.

p q pq qp (pq) (qp)V V V V VV F F V FF V V F FF F V V V

Ejemplos:i) T es equilátero sí y solo si T es equiángulo p: T es equilátero q: T es equiánguloToda vez que p sea V, también lo es q, y análogamente, si p es F, q es F. De modo que la doble

implicación es V.

ii) a = b si y sólo si a2 = b2

p : a = b q : a2 = b2

la doble implicación propuesta es falsa si p es F y q es V. En los demás casos es V.

3


DIFERENCIA SIMÉTRICA O DISYUNCIÓN EXCLUYENTE: Definición:

Diferencia simétrica o disyunción excluyente de las proposiciones p y q es la proposición (p o q en sentido excluyente, es decir o bien p, o bien q pero no ambas) cuya tabla de valores de verdad es:

p q

V V FV F VF V VF F F

La verdad de está caracterizada por la verdad de una y sólo una de las proposiciones componentes.

Es claro que equivale a la negación de p q.

Ejemplo:p: hoy a las 18hs vamos a claseq: hoy a las 18 hs vamos a remar : hoy a las l8hs vamos a clase o a remar

CONDICIONES NECESARIAS Y SUFICIENTES Consideramos la tabla de valores de verdad de la implicación:

p q p qV V VV F FF V VF F V

Hay tres casos en que p q es V.En el primer caso p es V, en cual resulta q es V, se tiene pq es V. Se dice entonces que el

antecedente p es condición suficiente para el consecuente q.En cambio, si p es F, nada podemos decir de q, puesto que puede ser V o F. Por otra parte, cuando

p q es V, si q es V, entonces p puede ser V o F; mas para que p sea V se necesita que q lo sea. Se dice entonces que q es condición necesaria para p.

Estas condiciones suelen expresarse así:q si p (condición suficiente)p sólo si q (condición necesaria)La proposición p antecedente (es la hipótesis) y la proposición q consecuente (es la conclusión).

Ejemplo:La siguiente implicación es V:

“Si T es equilátero, entonces T es isósceles”p: T es equiláteroq: T es isósceles

y p es condición suficiente para q, es decir, que un triángulo sea equilátero es suficiente para asegurar que sea isósceles. Por otra parte, T es equilátero sólo si es isósceles; es decir, que un triángulo sea isósceles es necesario para que sea equilátero.

Sea ahora la doble implicación p q, es decir (pq) (qp). Si p q es V, entonces pq es V y qp es V. Se tiene, atendiendo a la primera, que p es condición suficiente para q; y, teniendo en cuenta la segunda implicación, ocurre que p es condición necesaria para q.

Es decir, si p q es V, entonces el antecedente p es condición necesaria y suficiente para el consecuente q.

Análogamente, en el caso de doble implicación verdadera, el consecuente q es también condición necesaria y suficiente para el antecedente p.

Ejemplo:T es equilátero sí y solo si T es equiángulop: T es equiláteroq: T es equiánguloes V, y cualquiera de los dos proposiciones es condición necesaria y suficiente para la otra.

TAUTOLOGÍAS, CONTRADICCIONES Y CONTINGENCIAS

Una proposición es una tautología cuando todos los valores de su tabla de verdad son verdaderos. Por tanto, la tautología es una proposición siempre verdadera independientemente de los valores de verdad o falsedad de las proposiciones simples que las constituyen.

4

contrarios

contrarios


Una proposición es una contradicción cuando todos los valores de su tabla de verdad son falsos. Por tanto, es falsa, independientemente de los valores de verdad o falsedad de las proposiciones simples que la constituyen. Una proposición es una contingencia cuando en su tabla de verdad hay valores verdaderos y falsos. Por tanto, su valor lógico depende de los valores de verdad o falsedad de las proposiciones simples que la constituyen.

LEYES LÓGICASConsideremos la proposición

cuya tabla de valores de verdad es:

p q p q (p q) p

V V V V VV F F F VF V V F VF F V F V

Como observamos en la tabla la proposición (1) es una tautología o ley lógica.En el cálculo proposicional se utilizan las siguientes leyes o tautologías cuya demostración se

reduce a la confección de la correspondiente tabla de valores de verdad:

DISYUNCIÓN LEYES CONJUNCIÓNp p p Idempotencia p p pp q q p Conmutativa p q q pp (q r) (p q) r Asociativa p(q r) (p q) rp (p q) p Absorción p (p q) pp (q r) (p q) (p r)Disyunción respecto conjunción

Distributivap (q r) (p q) (p r)Conjunción respecto disyunción

p –p To Negación p –p Cp C pC es el elem. neutro de Identidad

p To pTo es el elem. neutro de

Involución (doble negación)

Leyes de Morgan

IMPLICACIONES ASOCIADASSea el condicional , que llamamos directo; en conexión con él, se presentan otros tres,

obtenidos por permutaciones o negaciones del antecedente y consecuente recíproco contrario contrarrecíproco

Las cuatro implicaciones propuestas se llaman conjugadas, y cualquiera de ellas puede tomarse como directa. El siguiente esquema nos proporciona la relación que las vincula.

recíprocos

recíprocos

Es fácil verificar que las implicaciones contrarrecíprocas son equivalentes, es decir, los siguientes bicondicionales son tautologías:

5


Si la implicación directa es V, también lo es la contrarrecíproca, y no podemos afirmar la verdad de la recíproca o de la contraria. Pero si son verdaderos un condicional y su recíproco o contrario, entonces son verdaderos los cuatro, y las proposiciones antecedente y consecuente son equivalentes.

Se presenta continuamente la necesidad de demostrar la verdad de , y de acuerdo con lo expuesto se presentan dos métodos:

i) directo. Si p es F, nada hay que probar, pues en este caso es V. Si p es V hay que establecer que el valor de verdad de q es V.

ii) indirecto. Si q es V queda establecida la verdad de . Pero si q es F hay que examinar p y llegar a establecer que su valor de verdad es F.

NEGACIÓN DE UNA IMPLICACIÓN

Las proposiciones y son equivalentes, como lo muestra la siguiente tabla:

(p q) (p q)V V V V V V F FV F F V F V V VF V V V V F F FF V F V V F F V

En consecuencia, la negación de la primera equivale a la negación de la segunda es decir

Por Involución, se tiene:

Es decir, la negación de una implicación no es una implicación, sino la conjunción del antecedente con la negación del consecuente.

FUNCIONES PROPOSICIONALES

Sea x un objeto determinado perteneciente a un cierto conjunto. Llamamos a x variable o indeterminada,

El símbolo P(x) representa una propiedad relativa a la indeterminada x Ejemplo:

Esta expresión se llama función proposicional en una variable.Como vemos no es una proposición, pues a menos que se especifique x, nada podemos decir

acerca de su valor de verdad. Pero para cada especificación de x, la función proposicional se transforma en proposición

Definición:

Función proposicional en una variable o indeterminada x es toda oración en la que figura x como sujeto u objeto directo, la cual se convierte en proposición para cada especificación de s.

Por ejemplo: (función proposicional) P(-2): -2 es impar proposición F P (5) : 5 es impar proposición V

Se presentan también funciones proposicionales con dos variables o indeterminadas. P(x, y) : x es divisor de y P(-2, 6) : -2 es divisor de 6 V P(12,6) : 12 es divisor de 6 F

CUANTIFICADORES

Mediante un proceso llamado de cuantificación podemos, a partir de funciones proposicionales obtener proposiciones generales.

Asociados a la indeterminada x, introducimos los símbolos , llamados cuantificadores universal y existencial de x, respectivamente.

Cuantificador UniversalSea P una función proposicional con dominio de discurso D. La afirmación para toda x, P(x) es una

afirmación cuantificada universalmente.

El símbolo significa “para toda”. Así, la afirmación para toda x, P(x), puede escribirse como .

6


. Se lee: Para todo x, se verifica P(x)

La afirmación es V si P(x) es verdadera para toda x en D.

La afirmación es F si P(x) es falsa para al menos una x en D.Por ejemplo: “Cualquiera que sea x, x es impar” F

Cuantificador ExistencialSea P una función proposicional con dominio de discurso D. La afirmación para alguna x, P(x) es

una afirmación cuantificada existencialmente.

El símbolo significa “para alguna”. Así, la afirmación para alguna x, P(X) puede escribirse como .

. Se lee: Existe x, tal que se verifica P(x).

La afirmación es V si P(x) es verdadera para alguna x en D.

La afirmación es F si P(x) es falsa para toda x en D.Por ejemplo: “Existe x, tal que x es impar” V

Negación de los cuantificadoresSea la afirmación “para cada número real x, x2 ≥ 0”En forma simbólica:

es verdadera

Su negación: es falsa

Entonces, para negar una función proposicional cuantificada universalmente se cambia el cuantificador en existencial, y se niega la función proposicional.

Para negar una función proposicional cuantificada existencialmente se cambia el cuantificador en universal, y se niega la función proposicional.

MÉTODOS DE DEMOSTRACIÓN

Un sistema matemático consta de axiomas, definiciones y términos no definidos. Se supone verdaderos los axiomas. Las definiciones se utilizan para crear conceptos nuevos en términos de los existentes. Algunos términos no se definen en forma explícita mediante los axiomas. Dentro de un sistema matemático es posible deducir teorema. Un teorema es una proposición cuya verdad se ha demostrado. Algunos tipos especiales de teoremas se conocen como lemas y corolarios. Un lema es un teorema que por lo general no es interesante en sí mismo sino que es útil par demostrar otro teorema. Un corolario es un teorema que se sigue rápidamente de otro teorema.

Un argumento que establece la verdad de un teorema es una demostración. La lógica es una herramienta para el análisis de las demostraciones

a) Método de demostración directa : Con frecuencia, los teoremas tienen la forma:Para toda x1, x2, ........,xn, si p(x1, x2, ........,xn), entonces q(x1, x2, ........,xn).Esta afirmación cuantificada universalmente es verdadera siempre que la proposición condicional

si p(x1, x2, ........,xn), entonces q(x1, x2, ........,xn)sea verdadera para toda x1, x2, ........,xn en el dominio de discurso.Una demostración directa supone que p(x1, x2, ...,xn) es verdadera y entonces utilizando p(x1, x2, .....,xn) y otros axiomas, definiciones o teoremas demostrados con anterioridad, muestra directamente que q(x1, x2,

........,xn) es verdadera.

Ejemplo:Demostrar el siguiente teorema:

Suponga que a y b son números pares pEntonces, según la definición de número par, 2 \ a y 2 \ b p p1

Esto significa que a = 2.m y b = 2.n para dos enteros m y n,según la definición de lo que significa un número entero di-

7


vide a otro. p1 p2

Pero, si a = 2.m y b = 2.n, entonces a + b = 2.m + 2.n == 2. (m + n), por la propiedad distributiva p2 p3

Como a + b = 2. (m + n) y m + n es un entero, 2 \ (a + b) p3 p4

Si a + b es divisible por 2, esto quiere decir que es par,según la definición de número par p4 q Por tanto, a + b es un número par q

b) Método de demostración por contradicción :

Una demostración por contradicción establece, suponiendo que la hipótesis p es verdadera y que la conclusión q es falsa, para entonces, utilizando p y q, así como otros axiomas, definiciones y teoremas demostrados con anterioridad, deducir una contradicción. Una contradicción es una proposición de la forma r r ( r puede ser cualquier proposición. Una demostración por contradicción se llama a veces demostración indirecta, pues para establecer mediante una demostración por contradicción, se sigue un camino indirecto: se deduce r r y se concluye que es verdadera. La demostración por contradicción puede justificarse observando que las proposiciones.

p q r p q p q r r p q r rV V V V F F VV V F V F F VV F V F V F FV F F F V F FF V V V F F VF V F V F F VF F V V F F VF F F V F F V

Ejemplo:Demostrar el siguiente teorema:

Demostrar por el contrarrecíproco.

Suponemos Entonces, por ley de tricotomía en el primer caso, se tendría a + c = b + c en el segundo caso b + c < a + c en cualquier caso se tiene que Por tanto si En consecuencia

Ejemplo:

Este teorema es de la forma

Su negación es

Demostración:

Esto nos condujo a la contradicción – s r – r, por tanto, es falsa. Lo cual demuestra el teorema.

c) Método de demostración por contraejemplo .

8


Para demostrar la negación de una implicación se debe dar un contraejemplo, es decir, un ejemplo en el cual p y –q son simultáneamente verdaderas.

Ejemplo:

d) Método de demostración por inducción completa .e)

El principio de inducción completa proporciona un método de demostración por recurrencia, de vastas aplicaciones en matemática. No es constructivo, en el sentido de generar propiedades; pero hace posible la demostración de éstas cuando son relativos al conjunto los números reales.

Teorema de inducción completaSi A es un subconjunto de

i)ii)

El principio de inducción completa es un proceso que se enuncia así:Sea A un subconjunto de los números reales que cumple estas condiciones:

a. El primer elemento tiene una determinada propiedadb. Si un elemento cualquiera tiene esa propiedad y la tiene también el elemento siguiente.c. Entonces todos los elementos del subconjunto tienen esa propiedad.

Para aplicar el principio de inducción completa se precisa :1. Un conjunto numérico.2. Una propiedad que pueda expresarse en una fórmula.3. Hacer tres verificaciones:a) Que la propiedad la cumpla el primer elemento del conjunto.b) Que la cumpla un elemento cualquiera bien por comprobación o suposición. A tal elemento

es usual denominarlo elemento h, es nuestra Hipótesis.c) Verificar que el siguiente elemento, esto es (h+1), cumple también esa propiedad, es nuestra

Tesis. Si se verifica la Tesis se puede concluir que todos los elementos del conjunto cumplen esa propiedad.

d)Ejemplo:Demostrar por inducción que “La suma de los n primeros números naturales consecutivos es igual a la mitad del producto del último número considerado por su siguiente”.¿Se puede aplicar el principio de inducción? Para ellos comprobamos los pasos enunciados.

1. ¿Tenemos un conjunto numérico? Si, el conjunto de los números naturales

2. La expresión general de la propiedad es:

NOTA:Σ es la letra griega sigma mayúscula y en matemáticas simboliza la suma.i es un contador que va dándole a n valores sucesivos:1, 2, 3, 4, .... hasta el valor n

3. Hacemos tres verificaciones:

a) Que la propiedad la cumpla el primer elemento del conjunto

b) Que la cumpla un elemento cualquiera

Hipótesis)

c) Verificar que el siguiente elemento, es decir (h+1), cumple también esa propiedad.

Tesis)

9


Demostración) Teniendo en cuenta la hipótesis inductiva, el primer miembro de la tesis se transforma en:

Conclusión: la fórmula anterior es válida para todo número natural n.

10

capitulo 1 lógica

Documents