ESTRUCTURA DISCRETA CON ISA JACKSON

Este es un espacio para compartir conocimientos acerca del tema de estructura discreta... espero sea de mucho agrado y pueda aportar el proceso de aprendizaje.

martes, 25 de octubre de 2016

DEDUCCIÓN PROPORCIONAL

Deducción proposicional
Hemos aprendido algunas reglas de buena inferencia que permiten pasar lógicamente de un conjunto de afirmaciones a otra afirmación. De la proposición
P —> Q y la proposición P, por ejemplo, se puede deducir la proposición
Q.
Se ha visto también que se puede demostrar que una conclusión se deduce lógicamente de un conjunto de premisas, aun cuando no se pueda ir directamente de las premisas a la conclusión en un solo paso. Yendo por pasos sucesivos, cada uno permitido por una regla, es posible alcanzar la conclusión deseada.
Si es así, se ha demostrado que la conclusión es consecuencia lógica de las premisas dadas.
Con el manejo de unas pocas reglas, empezamos a aprender el método de las deducciones formales. Es decir, hemos aprendido el camino preciso de demostrar que los razonamientos son válidos. Un razonamiento es simple mente un conjunto de proposiciones como premisas y una conclusión deducida de estas premisas. Cuando decimos que es válido entendemos que la conclusión es consecuencia lógica de las premisas. Una deducción formal es una serie de proposiciones o pasos, en la cual cada paso o es una premisa o está deducido directamente de los pasos que le preceden por medio de una determinada regla.

En la introducción a este capítulo, se comparaban las reglas de la Lógica a las de un juego; y se puede imaginar la deducción como la realización de un juego. Se han aprendido reglas suficientes para hacer una deducción simple. La deducción o demostración es el juego y las reglas del juego son precisamente las reglas de inferencia. Se puede hacer cualquier movimiento, dar cualquier paso que está permitido por una regla, y se ha de poder justificar cada paso dado indicando la regla seguida. El objetivo que nos proponemos alcanzar en este juego es la conclusión establecida. El propósito de cada movimiento que se hace, es avanzar un paso acercándose al objetivo.

La posición de partida con la que se inicia el juego es un conjunto de premisas.
Las premisas están justificadas por la regla de premisas que es:
Una premisa puede ser introducida en cualquier punto de una deducción.
La aplicación de las reglas no depende del uso que se haya hecho de las mismas en líneas anteriores.

La regla de las premisas se ha utilizado ya al principio de las deducciones.
Como esta regla es familiar, la P para la regla de premisas se omitirá corrientemente cuando se da un problema en forma simbolizada. En deducciones formales, sin embargo, se escribirá una P antes de cada premisa dada, para indicar que las líneas están justificadas por la regla de premisas.

Resumiendo, se empieza con un conjunto de premisas y el objeto es pasar de estas premisas a una conclusión particular. Cada movimiento que se hace, cada línea que se escribe debajo, ha de ser permitido por una regla de inferencia definida.
Hemos aprendido a efectuar deducciones simples. Ahora se considerarán algunas deducciones complicadas.

Consideremos el razonamiento del siguiente ejemplo:

Ejemplo a.
Si la ballena es un mamífero entonces toma oxígeno del aire. Si toma su oxígeno del aire, entonces no necesita branquias. La ballena es un mamífero y vive en el océano. Por tanto, no necesita branquias.

La conclusión que se desea demostrar o deducir es la proposición «no necesita branquias». (La palabra, «por tanto», pone de manifiesto que la proposición final es la conclusión del razonamiento.) El primer paso en este proceso es simbolizar el razonamiento de manera que la deducción sea perfectamente clara.

Sea
W= «La ballena es un mamífero»
0 = «Toma su oxígeno del aire»
G= «Necesita branquias»
H= «Habita en el océano».

Entonces
la primera premisa es                     W —• O
la segunda premisa es                  O —> —iG
la tercera premisa es                      W & H
la conclusión es                             -iG.


La deducción proposicional se puede escribir como se indica a continuación

(1) W —• O                           p
(2) O — - i G                         p
(3) W & H                              p
(4) W                                      S 3
(5) O                                      pp 1, 4
(6) i G                                    pp 2,5

Los tres primeros pasos son premisas. Los pasos 4, 5 y 6 están justificados
por reglas de inferencia aplicadas a líneas anteriores. A la derecha de cada
paso o línea, se indica la manera como se justifica aquella línea. Por ejemplo,
puesto que las tres primeras líneas son premisas, se escribe la letra P a la derecha de aquellas líneas. Estas líneas son dadas y no deducidas y, por tanto, no necesitan ninguna otra justificación.

La línea 4 se deduce de la línea 3 por la regla de simplificación. Por tanto, se escribe la abreviatura de la regla S a la derecha de aquella línea, seguida del número de la línea de la que se ha deducido. La línea 5 se obtiene de las líneas 1 y 4 por modus ponendo ponens. Considerando la línea 1, W —> O, y la línea 4, W, se puede ver rápidamente que modus ponendo ponens nos permite obtener O- Este movimiento se indica por la abreviatura del nombre de la regla PP, y el número de las líneas de las que se ha deducido la línea 5. De forma análoga se indica que la línea 6 se ha deducido por modus ponendo ponens de las líneas 2 y 5.

Puesto que la línea 6 representa la conclusión deseada, objetivo de nuestra deducción, la deducción es completa. Se ha demostrado que —iG es consecuencia lógica de las tres premisas del razonamiento. Así, puesto que  iG representa la proposición «No necesita branquias» en el razonamiento puesto como ejemplo se ha demostrado que la conclusión de aquel razonamiento es válida. Este es un ejemplo de una deducción formal

A fin de que cada paso de la demostración resulte perfectamente claro a todos aquellos que lo lean, nos atendremos estrictamente a la forma indicada para hacer deducciones. No se olvide que un objetivo de la Lógica es ser preciso. Para estar seguro de la precisión, anótese cada paso que se efectúe y el por qué está permitido. Para cada paso, escríbase primero el número de aquella línea, después la proposición misma, y finalmente lo que justifica aquel paso por la abreviatura de la regla que lo ha permitido. Si el paso está deducido de otras líneas por una regla, entonces añádase el número o números de las líneas de las que se ha deducido.

Consideremos el siguiente razonamiento:

Ejemplo b.
Si la enmienda no fue aprobada entonces la Constitución
queda como estaba. Si la Constitución queda como estaba
entonces no podemos añadir nuevos miembros al comité.
O podemos añadir nuevos miembros al comité o el informe
se retrasará un mes. Pero el informe no se retrasará
un mes. Por tanto la enmienda fue aprobada.

Sea,
A = «La enmienda fue aprobada»
C = «La Constitución queda como estaba»
M = «Podemos añadir nuevos miembros al comité»
R = «E1 informe se retrasará un mes».

Entonces;
(1) —«A —• C                      P
(2) C —• —iM                       P
(3) M V R                              P
(4) —iR                                 P
(5) M                                      TP 3, 4
(6) —«C                                T T 2, 5
(7) A                                       T T 1, 6

La conclusión del razonamiento es «La enmienda fue aprobada». El objetivo entonces es mostrar que la conclusión es consecuencia lógica de las cuatro premisas del razonamiento. Primero se indican las letras con que se simboliza cada una de las proposiciones atómicas. Después se simboliza cada una de las cuatro premisas y se indica que están justificadas en la demostración poniendo junto a cada una la letra «P». Las premisas son las cuatro primearas líneas en la demostración.

El movimiento siguiente es el intentar obtener la conclusión, que es A,
utilizando las reglas aprendidas. La línea 5 se obtiene de las líneas 3 y 4
por modus tollendo ponens, TP. La línea 6 se deduce de las líneas 2 y 5 por
modus tollendo tollens, TT. La línea 7 se obtiene de las líneas 1 y 6 por
modus tollendo tollens. Se ha mostrado que la conclusión del razonamiento

se deduce de las premisas por medio de una deducción formal.

jueves, 20 de octubre de 2016

MODUS TOLLENDO PONENS

Modus Tollendo Ponens. La regla anteriormente sugerida es la que se denomina
modus tollendo ponens. Una vez más, el nombre latino dice algo acerca
de la regla. Dice que negando (tollendo) un miembro de una disjunción se
afirma (ponens) el otro miembro.
Simbólicamente, el modus tollendo ponens se puede expresar-

De la premisa                      P V O
y la premisa                          ¬P
se puede concluir               Q

De la premisa                      P V Q
y la premisa                          ¬Q
se puede concluir                P


La abreviatura para modus tollendo ponens es TP.
Añadiendo paréntesis, modus tollendo ponens se puede escribir:

De                  (P) V Q
y                     ¬(P)
se deduce     ( Q)


D e                 (P) V (Q)
y                      ¬(Q)
se deduce     (P)

Supóngase que se tiene como premisa la disjunción

O esta sustancia contiene hidrógeno o contiene oxígeno

La segunda premisa dice

Esta sustancia no contiene hidrógeno.

Por medio de el modus tollendo ponens se puede concluir:

Esta sustancia contiene oxígeno.

Para aclarar la forma de esta inferencia, se puede simbolizar el ejemplo
anterior. Sea

P = «Esta sustancia contiene hidrógeno»
Q = «Esta sustancia contiene oxígeno».

La demostración de la conclusión es:

Obsérvese que una premisa (la negación) niega una parte de la disjunción. La
conclusión afirma precisamente la otra parte. No importa cual sea el miembro
negado, el derecho o el izquierdo. La disjunción dice que por lo menos un
miembro se cumple; por tanto, si se encuentra que uno de los miembros no
se cumple, se sabe que el otro ha de cumplirse.

Una disjunción en Lógica significa que por lo menos una de las dos
proposiciones es cierta y quizá ambas. Supuesto que se tiene una premisa
que dice que un miembro de la disjunción es cierto, ¿se puede concluir algo
sobre el otro miembro? Por ejemplo, considérese la proposición anterior sobre
oxígeno e hidrógeno. Si la segunda premisa hubiera sido «La sustancia tiene
hidrógeno», ¿qué se podría concluir del oxígeno, en caso de poder concluir
algo? No se podría concluir nada.

Véanse los ejemplos que siguen. Son ejemplos del uso de la regla modus
tollendo ponens. Estas reglas no están limitadas a proposiciones atómicas.
Igual que los otros tipos de proposiciones, la disjunción tiene lugar entre
proposiciones moleculares de igual manera que entre proposiciones atómicas.
Obsérvese que en muchas proposiciones se necesitan paréntesis para indicar
cuál es el término de enlace dominante.

(1)    P V Q                            P
(2) ¬P                                    P
(3)   Q                                   TP 1, 2


(1) Q V R                   P
(2) ¬R                        P
(3) Q                         TP 1, 2


b. (1) (P & Q) V S                            P
    (2) -»S                                           P
    (3) P & Q                                       TP 1, 2


c. (1) n S V T            P                                 d. (1) - n P V n Q                 P
   (2) i T                      P                                    (2) -r-nP                            P
   (3) -nS                    TP 1, 2                          (3) -nQ                               TP 1, 2





ADJUNCION Y SIMPLIFICACIÓN

Se suponen dadas dos proposiciones como premisas.
La primera es

Jorge es adulto.

La segunda es
María es adolescente.

Si ambas proposiciones son verdaderas, entonces se podrían juntar en una
proposición molecular utilizando el término de enlace «y» y se tendría una
proposición verdadera que se leería
Jorge es adulto y María es adolescente.
Si ambas premisas son ciertas, entonces la conclusión tendría que ser cierta.
La regla que permite pasar de las dos premisas a la conclusión se denomina
regla de adjunción. Se indica abreviadamente por A.

De manera simbólica se puede ilustrar la regla así:

Con paréntesis, la regla se representa de la siguiente manera:

De las premisas                     (P)
                                                 (Q)
Se puede concluir                 (P) ^  (Q)
O se puede concluir              (Q) ^ (P)

Los peréntesis en la conclusión son necesarios sólo si P o Q son proposiciones
moleculares que no sean negaciones.
El orden de las premisas es indiferente. En el primer ejemplo se hubiera
podido concluir «María es adolescente y Jorge es adulto». El significado
no cambiaría. Si se tiene la proposición Q como una premisa, seguida de la
proposición P como una premisa, la conclusión puede muy buen serp & Q.
ya que por una parte el orden de las líneas a las que se aplica la regla es
indiferente, y también porque en la conjunción se puede alterar el orden.
A continuación se dan varios ejemplos en los que se utiliza la regla de
adjunción.

a. (1) P                                                           p                    
   (2) ~~iR                                                      p
   (3) P & -»R                                                A 1, 2


b. (1) Q & S                                       P
    (2) ¬T                                             P
    (3) ¬T & (Q & S)                          A 1, 2 

c. (1) T                                                          p
    (2) U                                                          p
    (3) U & T                                                  A 1, 2

d. (1) P V Q                                      P
     (2) Q V R                                     P
     (3) (P V Q) & (Q V R)                  A 1, 2

Disjunciones como premisas. Quizá se ha observado que en las reglas estudiadas
hasta ahora, se han estado utilizando conjunciones, condicionales, y negaciones. En las reglas dadas aparecen los términos de enlace: «y», «si...
entonces...», y «no». Sin embargo, no se ha considerado, ni se ha dado ninguna
regla en la que interviniera el término de enlace «o». No se han utilizado
disjunciones en las premisas cuando se deseaba mostrar el uso de una regla de inferencia.
Antes de introducir una regla conviene, sin embargo, considerar el significado
de una disjunción en Lógica. En el lenguaje corriente hay dos maneras posibles de usar la palabra «o». Algunas veces se quiere significar que se presenta una u otra de dos cosas, pero no las dos a la vez. Este es el sentido excluyente de «o». Por ejemplo, en la proposición:

Juan vive en el norte de España o vive en el sur de España

Se expresa que una de las dos proposiciones atómicas es cierta y la otra es
falsa.
En Lógica, sin embargo, daremos un significado más amplio a la disjunción.
Se denomina sentido incluyente. En el sentido inclusivo, cuando se utiliza la palabra «o», se supone que por lo menos un miembro de la disjunción se presenta y quizá ambos. Supóngase un cartel en una de las entradas de un estadio que diga:

Los periodistas o fotógrafos han de entrar por aquí.
El significado de la proposición es la disjunción:

Los periodistas han de entrar por aquí, o los fotógrafos
han de entrar por aquí.

Es una disjunción en sentido incluyente o sea, que por lo menos es cierto un miembro de la disjunción y pueden serlo ambos. En el ejemplo, la proposición significa que si una persona es un periodista ha de entrar por dicha puerta o si es un fotógrafo ha de entrar por dicha puerta. Además, los fotógrafos de la prensa, que sean a la vez periodistas, también entrarán por la misma puerta.

En Lógica, una disjunción significa que por lo menos un miembro de la disjunción es cierto y quizá ambos lo son. Se ha de tener presente que en Lógica se utiliza la palabra «o» en sentido incluyente y así se evitará el error de creer que si un miembro de una disjunción es cierto el otro ha de ser falso. Ambos pueden ser ciertos. La disjunción dice simplemente que por lo menos uno es cierto.

Con el significado lógico de una disjunción puesto en claro, ¿puede pensarse
en una posible regla de inferencia que se aplique a una disjunción?
Consideremos la siguiente proposición como premisa:

O la producción aumenta o el precio aumenta.

Veamos si se puede imaginar una segunda premisa de manera que de las dos
se pueda deducir una conclusión válida. La conclusión será válida cuando
resulte de las premisas utilizando una «buena» regla de inferencia; y una
regla es «buena» si equivale simplemente a asegurar que siempre que las
premisas sean proposiciones ciertas la conclusión que resulta por aquella
regla es una proposición cierta. Esto significa que reglas válidas de deducción
nunca permiten pasar de premisas ciertas a conclusiones falsas.