• Author / Uploaded
• Marco Miranda

• Categories
• Proposición
• Cálculo
• Validez
• Lógica
• Argumento

Citation preview

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

CAP.3 LÓGICA PROPOSICIONAL

3.1. INTRODUCCION. Al tratar de la lógica, es muy común utilizar frases como: "Es lógico", "hablando con lógica", o, "hay que ponerle lógica al asunto", las mismas que pueden ser objetivamente reemplazadas por expresiones como: "Es correcto", "hablando con corrección", y "hay que ponerle cuidado y corrección al tema". Por tanto, la lógica trata sobre la corrección, y ésta se refiere de alguna manera, al pensamiento. Y es en este sentido que los tratadistas tradicionales definieron la lógica como la ciencia que enseña a pensar correctamente. Pero debemos distinguir entre el pensamiento como facultad y/o función del pensamiento como producto. Pues, cuando utilizamos el término "pensamiento" podemos significar, según las circunstancias, la facultad y/o función o el producto, lo que equivale a distinguir entre el pensar y lo pensado. Por tanto, la lógica no trata sobre le pensamiento como facultad y/o función, sino como resultado de la función de pensar, es decir, de lo que generalmente llamamos en plural: pensamientos. Consecuentemente, al abordar la lógica proposicional, debemos reconocer que una proposición es una cadena de palabras con sentido completo, calificable de cierta o falsa, así, por ejemplo, en la proposición: "Sucre es la Capital de Bolivia". Si se mantienen independientes, son proposiciones atómicas; pero si se relacionan con alguna conjunción (u otras partículas) el resultado es una proposición molecular, por ejemplo, “Juan y Pedro son alumnos de Sistemas”. Corrientemente, las personas, al expresar ciertos razonamientos en el lenguaje natural, se incurre en el empleo de aspectos subjetivos y ambiguos, La parte de la lógica simbólica que se ocupa del cálculo de proposiciones o enunciados es la llamada lógica de proposiciones o lógica proposicional. La lógica de proposiciones se _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

1

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

ocupa de las operaciones entre proposiciones, sin tener en cuenta la estructura interna de las mismas. Las proposiciones lógicas son expresiones que cumplen con una función informativa, de la cual se puede decir, que sean verdaderas o falsas. Toda proposición lógica cumple con una función o valor de verdad, ya sea éste verdadero o falso. Las proposiciones se abstraen o simbolizan mediante las letras proposicionales tales comos p, q, r, e, ...y las mismas con subíndices de ser necesario. Así por ejemplo: La lógica es una ciencia formal.

P

3.2. USO DEL LENGUAJE. Entre las formas de utilizar el lenguaje podemos mencionar las siguientes como funciones básicas: 3.2.1. LENGUAJE COMO MEDIO DE COMUNICACIÓN DE INFORMACIÓN. Un uso muy importante del lenguaje es aquel referido a la comunicación de información, lo cual se realiza mediante la formulación y la afirmación o la negación de proposiciones. Por ello se dice que el lenguaje usado para afirmar o negar proposiciones o para mostrar razonamientos cumple una función informativa. El discurso informativo es utilizado para describir el mundo y para razonar acerca de él; pues el lenguaje sirve para suministrar a los demás informaciones, definiendo, declarando, aclarando, describiendo, etc. los hechos; así, el lenguaje es usado informativamente. 3.2.2. LENGUAJE COMO MEDIO EXPRESIVO. El lenguaje cumple una función expresiva particularmente en la poesía; pues se emplea para dar rienda suelta a nuestros sentimientos, emociones, deseos y para despertar en los demás estados anímicos análogos a los que vivimos. _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

2

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

El verso no pretende transmitir información alguna, sino expresar ciertas emociones que el poeta experimenta muy agudamente y anhela despertar en el lector sentimientos similares. El lenguaje expresivo es utilizado para dar expansión a sentimientos y emociones, o para comunicarlos. Pero no sólo el lenguaje poético es expresivo, también expresamos pena cuando exclamamos: ¡Qué desgracia! o ¡Dios mío! o cuando expresamos nuestra alegría al decir: ¡Bravo! o ¡Felicitaciones! El discurso expresivo no puede ser ni verdadero ni falso; pues si alguien pretendiera aplicar tales criterios al discurso expresado en un poema o en un verso, juzgará erróneamente y perderá mucho de su valor. El lenguaje expresivo puede ser descompuesto en dos componentes: a. Cuando el lenguaje expresa o revela su propia actitud pero no está destinado a despertar una actitud similar en algún otro, como cuando una persona se maldice a sí misma en momentos de soledad, cuando un poeta escribe poemas que no muestra a nadie o cuando un hombre ora en soledad; b. Cuando el lenguaje usado no sólo pone de manifiesto las actitudes de los que hablan, sino que pretende también despertar las mismas actitudes en sus oyentes, como cuando un orador trata de instar a su auditorio, no a la acción, sino a que comparta su entusiasmo, cuando un enamorado corteja a su amada en lenguaje poético, o cuando una multitud vitorea a su equipo deportivo preferido. 3.2.3. LENGUAJE COMO MEDIO PRESCRIPTIVO. Finalmente el lenguaje cumple una función prescriptiva o directiva cuando es utilizado con el propósito de originar o impedir una acción manifiesta; es el caso de las órdenes y los pedidos. Se ejerce mediante leyes, decretos, mandatos, ruegos, etc. Quien tiene autoridad

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

3

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

emite órdenes sin pretender comunicar información alguna ni

manifestar o despertar

alguna emoción particular. Lo que se busca es motivar o causar una acción. Cuando se plantea una pregunta, se pide una respuesta que debe ser emitida. Esto conlleva que la diferencia entre una orden y un pedido sea bastante sutil, ya que cualquier orden puede traducirse en un pedido agregando las palabras "por favor" o mediante cambios adecuados en el tono de voz o en la expresión facial. Una orden no puede ser verdadera o falsa en ningún sentido literal. Y que la orden sea o no obedecida, no afecta ni determina su valor de verdad, pues no tiene ningún valor de verdad. Se puede no estar de acuerdo acerca de si una orden fue o no obedecida, si debe ser o no obedecida; pero nunca podemos diferir acerca de si una orden es verdadera o falsa, pues puede no ser ninguna de ambas. Las órdenes tienen ciertas propiedades que muestran alguna analogía con la verdad o falsedad del discurso informativo: son las cualidades de ser "razonables" o "adecuadas", y "no razonables" o "inadecuadas". 3.3. LENGUAJES NATURALES Y LENGUAJES ARTIFICIALES: Los lenguajes naturales, se construyen como producto de la relación. entre los hombres y su mundo, los matices, la ambigüedad y vaguedad son el resultado de esta relación. la lengua natural, heredada, creada, y recreada a través del tiempo, es el instrumento de comunicación, y una forma de vida. Los lenguajes artificiales o formales son lenguajes construidos por la cienda,como resultado de la necesidad de controlar científicamente el mundo. Es un lenguaje de precisión que formulan con mayor justeza las relaciones entre los objetos y las ciencias respectivas. El lenguaje científico debe ser objetivo para tener 'consenso público' dentro de una comunidad científica. La objetividad significa que las _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

4

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

correspondencias léxicas son establecidas explícitamente, que.el vocabulario es restringido a la ciencia en cuestión, y que la sintaxis se simplifica. El lenguaje artificial en general es un lenguaje con estructura de cálculo, el cálculo es un sistema de relaciónes compuesto por un conjunto de términos primitivos, o símbolos elementales definidos por enumeración o por propiedades; un conjunto de reglas de formación o construcción que determina las posibles combinaciones correctas de losímbolos, y un conjunto de reglas de transformación que determina las posibilidades de reemplazar una combinacíón correcta entre símbolos por otra combinación igualmente correcta. Así por ejemplo en el agedrez: las piezas son los símbolos primitivos, las instrucciones sobre la posición de las piezas, son las reglas de formación, y las reglas del movimiento de las piezas, son las reglas de transformación. Cálculos y juegos se parecen en que son autárquicos, es decir, carecen de otra finalidad que no sea calcular o jugar. Lo esencial del cálculo es su carácter exclusivamente formal, su naturaleza puramente sintáctica. No es un lenguaje en tanto medio de comunicación, sino una pura estructura sintáctica. Sus elementos carecen de significado, son entidades opacas que se manipulan con una serie de reglas. Sin embargo, un cálculo se puede transformar en un lenguaje ¿cómo?, interpretando sus simbolos, proporcionando a éstos, un significado. Al interpretar los simbolos, el cálculo se convierte en un lenguaje, éste no es un lenguaje natural, sino un lenguaje formalizado, es decir, un lenguaje con estructura de cálculo.Un lenguaje donde no solo es artificial su vocabulario, sino"también la sintaxis del mismo. A partir del siglo XIX Boole y Frege (1854-1879) se piensa que la lógica es un lenguaje formalizado, o un conjunto de cálculos a los que se da una interpretación determinada en el ámbito de la investigación. 3.4. PROPÓSITO DE LA LOGICA.Si se toma como punto de partida de que la Lógica Formal estudia la formalización del lenguaje natural en un lenguaje formal y los principios de la inferencia valida, entonces un propósito fundamental

en el proceso de formalización del lenguaje natural es la

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

5

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

formulación de un lenguaje formal que se debe emplear

para el estudio de los

razonamientos. La Lógica Proposicional

enfoca el estudio de la formulación de un lenguaje formal

tomando como elemento central a la “proposición” o enunciado simple, que puede ser verdadero o falso. No enfatiza en los componentes internos de las proposiciones como el sujeto y predicado, mas bien considera a la proposición como un todo indivisible.

3.5. PROPOSICIONES. Una proposición es una frase declarativa simple que puede ser verdadera o falsa. Es la unidad mínima del lenguaje con contenido de información. Las proposiciones, según la lógica proposicional, pueden ser simples o atómicas, y compuestas o moleculares. Las proposiciones simples o atómicas son aquellas proposiciones que no admiten dentro de si, más que una sola proposición, así por ejemplo: La aritmética, el álgebra y la geometría comparten las matemáticas. Juan, Pedro y María son hermanos. En cada uno de estos casos, se trata de una sola proposición, pues “y” no cumple con la función de unir o de conjunción, sino que cumple con la función de relacionar, como se verá más adelante en la lógica de predicados. Razón por la cual éstos ejemplos se simbolizan con la letra 'p'. En cambio si decimos: La aritmética, el álgebra y la geometría son disciplinas matemáticas

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

6

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Se trata de una proposición compuesta por tres proposiciones tales como: La aritmética es una disciplina matemática.

p

El álgebra es una disciplina matemática.

q

La geometría es una disciplina matemática

r

Y la simbolización correspondiente a las mismas será mediante las letras proposicionales p, q, r, respectivamente, con lo cual la simbolización correspondiente en es: p . q . r En este ejemplo (1) “y” cumple con la función de unir o nexo conjuntivo de las tres proposiciones. Las proposiciones compuestas o moleculares son proposiciones que admiten dentro de sí, dos o más proposiciones; o también, las proposiciones moleculares son aquellas compuestas por dos o más proposiciones atómicas, relacionadas entre sí mediante expresiones lingüísticas llamadas conectivas. En el ejemplo último dado, la conectiva que se ha utilizado es la conjunción.

3.5.1. TIPOS DE PROPOSICIONES. Dependiendo del tipo de información que se quiera representar, las proposiciones pueden ser de diferente tipo: a) De acción.- Expresa la ocurrencia de un hecho y no hace referencia a algún objeto o individuo especifico. Ej: -

Hace calor.

-

Llueve.

-

Es viernes.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

7

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

b) De atribución de propiedades a sujetos específicos.- Este tipo de proposiciones describen una propiedad o característica que tiene un objeto o individuo especifico. Ej: -

Juan juega futbol.

-

La casa es verde.

-

Pedro es bueno.

c) De Relación: Relacionan sujetos u objetos, se debe tener cuidado en que la proposición no se constituya en una proposición molecular o la combinación de dos proposiciones atómicas (frases declarativas simples). Ej: -

Juan y Pedro son primos.

-

Juan esta sentado entre luis y Jaime.

3.6. CONECTIVAS. las elementos que relacionan unas proposiciones con otras se denominan conectivas (conectores), pues toda proposición molecular necesariamente está determinada o afectada por una o varias conectivas. Si se considera los siguientes ejemplos de proposiciones moleculares: •

Melgar Y Vallejo son dos grandes hombres.

•

Juan sabe francés Y inglés.

•

Juan se casa O termina su noviazgo.

•

Si es estudioso, ENTONCES aprobará el examen.

•

Manuel irá al estadio SI, Y SÓLO SI, juega San José.

•

NO es cierto que Luis Y Ana sean buenos estudiantes.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

8

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Se puede observar que los elementos (resaltados con mayúsculas) son conectivas porque relacionan unas proposiciones con otras. Es importante notar que el elemento NO, en lógica es considerado una conectiva, pues, aunque no conecta, afecta negativamente tanto a proposiciones atómicas por separado como a relaciones entre proposiciones. Ello significa que la parte de la lógica que estudia los diversos modos de relación de las proposiciones en un discurso, sin intentar ingresar en un análisis de la estructura de las mismas, se denomina lógica proposicional, sentencial o de enunciados; pues, proposición, sentencia, o enunciado son términos sinónimos.

CONECTIVA NEGACION

SIMBOLO

EXPRESION EN LENGUAJE NATURAL

~p

NO p no ocurre que p no es cierto que p es falso que p etc. P y/e q p aunque q p pero q p sin embargo q p no obstante q p a pasar de q etc. p o/u q o bien p o bien q al menos p o q como minimo p o q etc. si p entonces q solo si q entonces p p suficiente para q q necesario para p no p a menos que q etc. p si y solo si q p necesario y suficiente para q

CONJUNCION

p∧q

DISYUNCION

p∨q

IMPLICACION

p→q

BICONDICIONAL

p↔q

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

9

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

3.7. DEFINICIÓN FORMAL DEL LENGUAJE PROPOSICIONAL. El punto de partida para la definición de un lenguaje formal es el establecimiento del alfabeto del lenguaje, todos los lenguajes comportan un conjunto finito de símbolos que permiten la formación de las estructuras del lenguaje, es decir, la formación de palabras oraciones, etc. El lenguaje natural, castellano en nuestro caso, considera un conjunto de símbolos (letras) mediante las cuales es posible construir las palabras y oraciones, las cuales contienen alguna información. 3.7.1. ALFABETO DEL LENGUAJE. Constituyen el conjunto de símbolos que el lenguaje requiere, el lenguaje para una Lógica Proposicional requiere tres tipos de símbolos: 1. Símbolos para proposiciones.: llamados también letras proposicionales son codificaciones de proposiciones atómicas o frases declarativas simples. Se recomienda emplear letras minúsculas a partir de la letra p, por ejemplo p, q, r, s, ...... para grupos pequeños y letras subindicadas para grupos grandes, por ejemplo p1, p2, p3, p4, ................. Al conjunto de de símbolos para las letras proposicionales se las denota con la letra P. Por ejemplo: P = { p, q , r, s ,t } 2. Símbolos para Conectivos lógicos: elementos de conexión que permiten formar estructuras complejas del lenguaje: (negación) ¬; (disyunción) ∨ ; (conjunción) ∧ ; (implicación) → ; (doble implicación) ↔.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

10

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

3. Símbolos de paréntesis o de puntuación: para el establecimiento de subestructuras y niveles de prioridad : ( , ) Ej:

p : Juan juega futbol. r : Juan es bueno. s : Pedro es bueno t : Llueve

Observaciones: •

Los conjuntos 2. y 3. son comunes para todo lenguaje proposicional, es decir no cambian.

•

El conjunto 1. varia de acuerdo al fenómeno o razonamiento que se esta modelando, es decir cada razonamiento proporciona un conjunto P diferente cuyas letras proposicionales codifican proposiciones diferentes aun cuando las letras sean las mismas.

Por ejemplo: r1

P={p, q, r, s, t}

r2

P={p, q, r}

r3

P={a, b, c, d, e, f, g}

Como el conjunto P es variable, por lo tanto el lenguaje proposicional a desarrollar esta en función del conjunto P y se lo denota como sigue:

L(P)

3.7.2. SINTAXIS DEL LENGUAJE PROPOSICIONAL: Tomando como base el conjunto de símbolos del lenguaje (alfabeto) se debe establecer el conjunto de reglas para la obtención de formulas bien construidas (fbc) del lenguaje, porque _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

11

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

la simple combinación de proposiciones y conectivas no garantiza la obtención de frases sintacticamente correctas.. Definición.- Las Formulas Bien Construidas (fbc) del lenguaje proposicional se definen recursivamente con la aplicación de las siguientes reglas: 1. Toda Letra Proposicional es una formula bien construida del lenguaje. A estas formulas se las denomina Formulas Atómicas. 2. Si A y B son fórmulas del lenguaje , entonces: ¬A ,¬ B , (A ∧ B) , (A ∨ B ) , (A → B), (A ↔ B ) también son fórmulas del lenguaje. 3. Son fórmulas del lenguaje únicamente las obtenidas con la aplicación de las reglas 1 y 2. La descripción de estas tres reglas contempla una definición recursiva. CASO BÁSICO: Regla 1. PROCESO INDUCTIVO: Reglas 2 y 3 Ej: Dado el conjunto P de letras proposicionales: P{p, q, r, s} Son formulas del lenguaje: -

p

-

¬s,

(formula atómica) por la regla 1. (p→q) ∧ r , ((p→q) →r) →t ( por la regla 2.)

El uso adecuado de paréntesis es muy importante para definir las sub estructuras del una formula. Por lo tanto: p ∧ q

→ r

es diferente a (p ∧ q) → r

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

12

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

El empleo del alfabeto del lenguaje y de las reglas sintácticas establecidas permiten formar proposiciones complejas que se las desglosa de la siguiente manera: Proposiciones conjuntivas: Las proposiciones conjuntivas surgen de la unión de dos proposiciones atómicas, que se denominarán componentes conjuntivos, y la alteración de la ubicación de los mismos no incide en la función de la conjunción, que es unir. La condición que hace una conjunción verdadera, es que ambos componentes conjuntivos sean verdaderos, en caso contrario la conjunción es falsa. Así por ejemplo: p∧ q

Locke y Hume son representantes del empirismo inglés Los componentes conjuntivos son: Locke es representante del empirismo inglés

p

Hume es representante del empirismo inglés

q

Descartes es racionalista, pero Hume es empirista

p ∧q

Donde : p: Descartes es racionalista. q: Hume es empirista. Aunque Descartes es idealista, Hume es empirista

p∧ q

Donde :

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

13

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

p: Descartes es idealista. q: Hume es empirista. Proposiciones disyuntivas: Las proposiciones disyuntivas surgen de la inclusión o no de dos alternativas. las proposiciones que las componen, se denominarán componentes disyuntivos, y como en el caso de la conjunción, la alteración de la ubicación de los mismos no incide en la función de la disyunción. Así por ejemplo en la disyunción inclusiva: •

A menos que se tomen medidas, el Riachuelo seguirá contaminado. pvq donde: p: se toman medidas. q: el riachuelo seguirá contaminado.

•

Las becas de investigación son para Francia y/o Alemania p vq donde: p: las becas de investigación son para Francia. q: las becas de investigación son para Alemania.

Un ejemplo de disyunción exclusiva: •

La tarifa aérea incluye un viaje de cabotaje o a Bariloche o a cataratas pvq donde: p: la tarifa aérea incluye un viaje de cabotaje a Bariloche. q: la tarifa aérea incluye un viaje a cataratas.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

14

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

•

O bien descartes es racionalista, o bien es empirista p vq donde: p: Descartes es racionalista. q: Descartes es empirista.

La condición que hace una disyunción verdadera, radica en que siempre al menos uno de los componentes sea verdadero. Solamente en la disyunción inclusiva también es verdadera cuando ambos componentes sean verdaderos, en caso contrario es falsa. Se utilizará la disyunción inclusiva, para todos los ejemplos posteriores, en todos los casos de disyunción que se encuentren en las operaciones entre proposiciones y/o razonamientos. Proposiciones condicionales: las proporciones condicionales presentan una estructura muy peculiar, en la cual los elementos (antecedentes y consecuentes), que las componen no puedan alterar su ubicación, pues esto modificaría la función de la misma. En las proposiciones condicionales, la ubicación de las proposiciones que la componen (antecedentes y consecuente) se determina por la estructura misma. La única condición que hace un condicional falso, radica en el caso de un antecedente verdadero y un consecuente falso, por cuanto será verdadero en todos los otros casos. Así por ejemplo: •

Si los pasajes se reservan con tiempo, viajaremos en primera. Antecedente p: Los pasajes se reservan con tiempo. consecuente p

•

q: viajaremos en primera. q

Viajaremos en primera, Si los pasajes se reservan con tiempo. Consecuente p:viajaremos en primera. Antecedente q: Los pasajes se reservan a tiempo. q

p

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

15

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

•

Iremos al campo, Solo si hace buen tiempo. Antecedente p: hace buen tiempo. Consecuente q: Iremos al campo. p

q

Cabe señalar, que este tipo de proposiciones condicionales se denominan también materiales, se caracterizan por tener los verbos en modo indicativo. Pero hay otro tipo de proposición condicional que se denomina contra fáctico y se caracterizan por tener verbos en modo subjuntivo, con lo cual no es posible determinar el valor de verdad de las proposiciones que lo componen, ya que éstas refieren a situaciones que no existen. Por lo tanto los condicionales contra fácticos exceden el ámbito de la lógica, y ésta no se ocupa de ellos. Así por ejemplo: Si San Martín no se hubiera muerto, seguiría vivo. A partir de lo visto en los ejemplos de proposiciones condicionales materiales, es importante tener en cuenta que: si bien la asignación de las letras proposicionales es arbitraria, en la simbolización de las proposiciones, sin embargo es conveniente seguir un orden determinado. Por lo tanto se sugiere que la adjudicación de las letras siga la secuencia de las mismas: p, q, r, s, t y en función del orden en que vayan apareciendo las proposiciones, una vez simbolizadas las proposiciones, se procede a abstraer la forma proposicional según lo indique la conectiva en cuestión. Así por ejemplo: •

Descartes es idealista, si Locke es realista y Hume es realista. P q r (q ∧ r)

•

p

(1)

Según Kant, si la intuición se constituye de materia y de forma, p q entonces la materia es la sensación y la forma es Espacio – tiempo. r s

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

16

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

(p ∧ q)

(r ∧ s)

(2)

En la simbolización correspondiente a las formas proposicionales compuestas, se utilizan los signos de puntuación tales como el paréntesis, corchete y llave, en el mismo sentido con que operan en las matemáticas, es decir, determinan el alcance de una operación, en este caso la operación, que se lleva a cabo por una conectiva. En el ejemplo (1), el si indica el antecedente de la construcción principal que es el condicional, dicho antecedente, es a su vez una proposición compuesta conjuntiva, por lo tanto, el paréntesis nos indica el alcance de la conjunción y a su vez, el antecedente del condicional. En el ejemplo (2), el si nos indica el antecedente – proposición conjuntiva – y el entonces nos indica el consecuente – proposición conjuntiva- en cada uno de ellos el paréntesis indica el alcance de la conjunción respectiva, y además determina el antecedente por un lado, y el consecuente del condicional, por el otro. Otro aspecto que se debe tener en cuenta en la simbolización, es que cuando una proposición atómica se repite, también debe repetirse la letra proposicional adjudicada en la simbolización de la misma. Así por ejemplo: O Descartes es idealista, o Descartes no es idealista. p -p p w -p

Proposiciones Bicondicionales: Las proposiciones bicondicionales son las proposiciones construidas por la equivalencia ( o mutua implicación) entre las proposiciones que la componen. Los componentes del bicondicional se denominan:

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

17

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Componente izquierdo y componente derecho. Un bicondicional es un condicional doble, esto quiere decir, que la proposición bicondicional “p = q”, es equivalente a la conjunción de dos condicionales, donde el antecedente del primero es consecuente del segundo, y el consecuente del primero es antecedente del segundo. La condición que hace una proposición bicondicional, verdadera, es que ambos componentes tengan el mismo valor de verdad, ya sea éste verdadero, o falso. Así por ejemplo: •

Ingresa a la facultad si y solo si aprueba el ciclo básico Componente izquierdo componente derecho P q P↔ q

Bicondicional o doble implicación: Si ingresa a la facultad, aprobó el ciclo básico. Y si aprueba el ciclo básico, ingresa a la facultad P q q p (p

q) ∧ ( q

p)

Así como en las proposiciones condicionales vimos que hay casos de condicionales contra fácticos, en las proposiciones bicondicionales también se dan las bicondicionales contra fácticas como por ejemplo: Habría alcanzado el triunfo si y solo si se hubiera esforzado. La lógica solo se interesa por las proposiciones bicondicionales materiales, y no se ocupa de las bicondicionales contra fácticas pues de éstas no es posible determinar su valor de verdad. Como la definición de las reglas sintácticas

contempla una definición recursiva o

inductiva, entonces es posible aplicar la inducción para demostrar propiedades y conceptos acerca de las formulas del lenguaje.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

18

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

INDUCCIÓN SOBRE FÓRMULAS.La definición inductiva de las reglas sintácticas permiten aplicar la inducción matemática para la demostración de propiedades del lenguaje, en este proceso puede existir mas de un caso básico. Ejemplo: Definir una función para determinar el número de conectivos que aparecen en una fórmula ‘A’ La función a definir es numconect( - ) que da como resultado el numero de conectivos que tiene una formula arbitraria. CASO BÁSICO.- Si A es una fórmula atómica. numconect(A) = 0 Ya que una fórmula atómica está formada por una letra proposicional. PROCESO INDUCTIVO.-Si A es de la forma ¬B numconect(A) = 1+numconect(B) -Si A es de la forma (B*C) donde * puede ser{∨, ∧, →, ↔}entonces: numconect(A)=1+numconect(B)+numconect(C) SEGUIMIENTO DE LA FUNCION INDUCTIVA: Sea la formula A = ¬(p ∧ q) → r _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

19

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

3

Numconect (¬(p ∧ q) → r)

= 1+ numconect (¬(p ∧ q)) + numconect(r) 2

0

1 + numconect(p ∧ q) 1

1 + numconect(p) + numconect( q) 0

0

Numconect (¬(p ∧ q) → r) = 3

3.7.3. SEMANTICA DEL LENGUAJE PROPOSICIONAL.Si bien se tiene estructurado en conjunto de reglas de correcta escritura de las formulas del lenguaje, es con la semántica que se proporciona el significado y el valor de verdad que se asumirá para los procesos de validación de argumentos. PROPÓSITO.El propósito de la semántica del lenguaje proposicional se puede resumir en los siguientes aspectos: -

Dar significado a los elementos del lenguaje.

-

Definir el concepto de verdad.

-

Definir el concepto de consecuencia lógica.

a) Definir el conjunto de significados.La definición de significados consiste en establecer el conjunto de posibles valores que pueden tomar las letras proposicionales y las formulas del lenguaje. La Lógica _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

20

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

proposicional al ser parte del razonamiento matemático, contempla un conjunto de valores que puede ser Verdadero o Falso. Conjunto de significados = {V , F } o {1 , 0} Todas las letras proposicionales toman valor de dos posibles, es por este motivo que corresponde a una lógica bi- valente. b) Definición semántica de conectivos.Se debe establece un r el significado de estructuras formadas por la relación de proposiciones atómicas y conectivos lógicos. Se lo muestra en las siguientes tablas:

Disyunción Conjunción Implicación Bi condicional Negación

p q

p∨q

p∧q

p→q

p↔q

P

¬q

V V

V

V

V

V

V

F

V F

V

F

F

F

F

V

F V

V

F

V

F

F F

F

F

V

V

c) Letras Proposicionales: Las letras proposicionales representan información diferente en función al fenómeno que se está representando. Es decir: -

Codificación de proposiciones (frases declarativas simples).

-

Representan información.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

21

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Ej: Si Manuel juega fútbol y no estudia entonces reprobará el examen . p:

Manuel juega futbol.

q : Manuel estudia. r : Reprueba el exámen. Y su representación simbólica es: (p∧¬q) → r 3.7.3.1. CONCEPTO DE VERDAD.Todo lo visto hasta este momento supone que no se ha establecido un valor de verdad para las diferentes letras proposicionales, es decir, las letras proposicionales solo son codificaciones de frases declarativas simples que pueden ser verdaderas o falsas, la definición del concepto de verdad se establece asignando valores de verdad a los elementos fundamentales del lenguaje, las letras proposicionales. La asignación de valores de verdad a las letras proposicionales se lleva a cabo por medio de una función de asignación de valores de verdad, a esta función se la denomina función ‘a’. Función de asignación de valores de verdad. La función ‘a’ asigna valores de verdad al conjunto de letras proposicionales del lenguaje. Cada letra proposicional toma un valor de dos posibles, el universo o conjunto de significados se ha establecido previamente y esta formado por {Verdadero, Falso} y se denota como sigue: a: p → {V,F} Ej:

Sea P={p, q, r} el conjunto de letras proposicionales del lenguaje.

Se puede establecer las siguientes funciones de asignación de valores de verdad: _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

22

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

a1= {p=V, q=F, r =V}

Conjunto de significados

a2= {p=F , q = F , r= V}

V=1

.

F =0

. an= {p=V , q= V , r=v} Observaciones: -

A una función de asignación de valores de verdad se las denomina también VALUACIONES.

-

Si P contiene n letras proposicionales entonces se tiene 2n valuaciones diferentes.

-

Toda letra proposiocional toma 1 valor de 2 posibles.

3.7.3.2. INTERPRETACIÓN DE FÓRMULAS.Una valuación asigna valores de verdad a los elementos atómicos del lenguaje, letras proposicionales, sin embargo el lenguaje esta conformado por estructuras mas complejas llamadas formulas que representan información resultante de la combinación de letras proposicionales y conectivos lógicos. Por lo tanto es importante definir claramente la forma en que una estructura compleja, una formula, toma un valor de verdad determinado, a este proceso se lo denomina interpretación de formulas del lenguaje. En resumen la interpretación de formulas tiene por objetivo: Determinar el valor de verdad de una fórmula para una valuación especifica. Como se mostró en la definición de la Sintaxis del lenguaje proposicional, la definición de una formula contempla una definición inductiva, es decir, la construcción de una formula, tiene una definición recursiva, por lo tanto, la interpretación de formulas, para determinar su valor de verdad para una valuación especifica, se lo realiza por medio de una definición inductiva.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

23

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

DEFINICIÓN INDUCTIVA PARA INTERPRETACIÓN DE FORMULAS. Sea la Fórmula A. Una formula arbitraria del lenguaje proposicional. Se define la función a(...)

:El valor de verdad de ...

La función a() se aplica a un parámetro que es la formula que se quiere evaluar. CASO BÁSICO.- Si A es una fórmula atómica. a(A) =

valor asignado por una función de asignación de valores de verdad (VALUACIÓN) a las letras proposicionales.

PROCESO INDUCTIVO.- Si A es de la forma ¬B: a(A) = 1- a(B) -Si A es de la forma (B∨ C) a(A) = max (a(B), a(C)) -Si A es de la forma (B∧ V) a(A) = min (a(B), a(C)) -Si A es de la forma (B→C) a(A)= 0 si a(B) = 1 y a(C) = 0 1

en caso contrario

-Si A es de la forma (B↔C) a(A) =

1 si a(B) = a(C) 0

en caso contrario.

Ej: Determinar el valor de verdad de la siguiente fórmula: A = (p ∧ ¬q ) → (¬r → ( p ∨ q )) para a: {p=1 ; q=0; r=1} _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

24

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

primero el paréntesis interno: A = (p ∧ ¬q ) → (¬r → ( p ∨ q )) a() = max(a(p),a(q)) a() = max(1,0) A = (p ∧ ¬q ) → (¬r → 1) Luego el paréntesis de la izquierda: A = (p ∧ ¬q ) → (¬r → 1) a() = min(a(p),a(¬ q)) a() = 1-a(q) a() = 1 – 0 a() = min (1,1) A = 1 → (¬r → 1) Ahora el paréntesis de la derecha: A = 1 → (¬r → 1) a() = (1-a(r)) → 1 a() = (1 – 1) → 1 a() = 0 → 1 a() = 1 A =1→1 Finalmente: a(A) = 1 Para la valuación establecida la formula es verdadera.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

25

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

La determinación del valor de verdad de una formula para una valuación determinada aplicando la definición inductiva de la función es un poco larga, es por este motivo que se puede recurrir a procesos que simplifican dicha evaluación pero aplicando la función inductiva como sigue: Se debe descomponer la formula en subformulas hasta encontrar elementos atómicos, es decir letras proposicionales en una estructura ramificada, donde en las ramas inferiores aparecen únicamente letras proposicionales y en función al valor que tienen estas, por medio de una asignación de valores de verdad, se procede a evaluar la formula de abajo hacia arriba. (p ∧ ¬q ) → (¬ r → (q ∨ q)) = 1 p ∧ ¬q =1 p=1

¬ r →(p ∨ q) =1

¬q = 1 q=0

¬r = 0 p ∨ q =1 r=1

p=1

q=0

-De otro modo: Sin necesidad de descomponer en subformulas, únicamente se desarrolla la evaluación en función de los valores de verdad de las letras proposicionales: (p ∧ ¬q) → (¬r → (p∨q) ) 1

0

1

1 0

1

1

0

1

1

1 1

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

26

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

3.7.3.3. EVALUACIÓN SEMÁNTICA DE FORMULAS. La evaluación semántica de formulas supone determinar el valor de verdad de la formula para todas las posibles valuación, es decir, se debe establecer el valor de verdad para todas las posibles combinaciones existentes. Este proceso se lo lleva a cabo por medio de tablas de verdad. Normalmente una formula, por la definición inductiva en su construcción, contiene subformalas, es decir, esta formada por otras formulas mas simples, por lo tanto se debe establecer el valor de verdad , en forma gradual, de todas las subformulas hasta, finalmente, obtener la evaluación de la formula completa. La siguiente tabla ilustra este proceso:

A = (p ∧ ¬q ) → (¬r → ( p ∨ q )) p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

R ¬q ¬r ( p ∨ q ) 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0

(p ∧ ¬q ) 0 0 1 1 0 0 0 0

(¬r → ( p ∨ q ) (p ∧ ¬q ) → (¬r → ( p ∨ q )) 1 1 1 1 1 1 1 0

1 1 1 1 1 1 1 1

FÓRMULAVÁLIDA.Es cuando para cualquier valuación el valor de verdad de la fórmula es V. (tablas de verdad). La columna de la formula en la tabla de verdad es siempre 1 o V. _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

27

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Estas formulas se denominan TAUTOLOGIA. Ej: ((p → q) ∧p) → q P

Q

p→q

(p → q) ∧ p

((p → q) ∧ p) → q

V

V

V

V

V

V

F

F

F

V

F

V

V

F

V

F

F

V

F

V

FÓRMULA SATISFASCIBLE: Una formula es satisfascible si es verdadera por lo menos para una valuación. Estas formulas se llaman también CONTINGENCIA. El siguiente ejemplo muestra esta situación. A = (p ∧ (¬r → ( p ∨ q )) p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

R ¬r ( p ∨ q ) 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0

(¬r → ( p ∨ q )

(p ∧ (¬r → ( p ∨ q ))

1 1 1 1 1 1 1 0

1 1 1 1 0 0 0 0

FÓRMUAL INSATISFASCIBLE: Una formula es insatisfascible si es falsa para cualquier valuación. Estas formulas se llaman también CONTRADICCIÓN.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

28

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

3.7.3.4. EVALUACIÓN SEMÁNTICA DE DEDUCCIONES. Una deducción o razonamiento se compone de un conjunto de premisas, que es la información conocida respecto a algún fenómeno, y una conclusión, que es la información que se trata de obtener a partir del conjunto de premisas. -Conjunto de premisas => lo conocido -Conclusión:

=> lo que se quiere conocer.

{p1, p2, p3, ......................,pn} => Q ∑

≠

Q

La verdad de la conclusión se sigue a partir de la verdad del conjunto de premisas. Si la conclusión se puede obtener a partir del conjunto de premisas, entonces se dice que la conclusión es consecuencia lógica del conjunto de premisas, en caso contrario se dice que la conclusión no es consecuencia lógica del conjunto de premisas. CONSECUENCIA LÓGICA.Deducción: Conjunto de premisas ∑ Conclusión

Q

∑ => Q

Q es consecuencia logia de ∑

∑ ≠ Q

Q no es consecuencia lógica de ∑

ARGUMENTO VÁLIDO.-

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

29

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Un argumento es valido si Q es consecuencia lógica de ∑. A nivel semántico un argumento es valido cuando no existe ninguna valuación que haga simultáneamente verdadera al conjunto de premisas y falsa a la conclusión. La demostración de la validez de un argumento a nivel semántico supone evaluar todas las formulas del conjunto de premisas y la conclusión, este proceso se lo realiza por medio de tablas de verdad, si en las diferentes valuaciones no existe ninguna fila (valuación) en la que todas las formulas, del conjunto de premisas, son verdaderas y la conclusión es falsa simultáneamente, entonces el argumento o deducción es valida en caso contrario el argumento no es valido. El siguiente ejemplo ilustra esta situación Ej: Demostrar la validez del siguiente argumento: “Un líquido es ácido si y solo si colorea de azul el papel tornasol rojo. Un líquido colorea de azul el papel tornasol rojo si y solo si contiene iones de hidrógeno libres. Por lo tanto, un líquido es ácido si y solo si contiene iones de hidrógeno libres.” 1: letras proposicionales: en este punto se debe identificar el conjunto de letras proposicionales del lenguaje. p: Un líquido es ácido. q: Un líquido colorea de azul el papel tornasol rojo. r: Un líquido contiene iones de hidrógeno libres. El conjunto de letras proposicionales del lenguaje es: P={p, q, r} 2: Fórmulas de lenguaje: A partir de las letras proposicionales identificadas en el paso anterior se debe construir las formulas del lenguaje, mediante las cuales se reproduce todo el argumento a nivel simbólico, se debe construir la base de conocimiento (el conjunto de _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

30

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

premisas que es la información conocida) y la conclusión (que es la información que se desea obtener a partir de de la base de conocimiento): •

Un líquido es ácido si y solo si colorea de azul el papel tornasol rojo. p↔q

•

Un líquido colorea de azul el papel tornasol rojo si y solo si contiene iones de hidrógeno libres. q↔r

La base de conocimiento o el conjunto de premisas a nivel simbólico es: ∑ ={p↔q; q↔r} La conclusión es la siguiente: •

un líquido es ácido si y solo si contiene iones de hidrógeno libres. p↔r Q = {p↔r}

3: Tablas de verdad: Se debe evaluar, tanto las formulas de la base de conocimiento y de la conclusión por medio de tablas de verdad:

P

Q

r

p↔q

q↔r

P↔r

1

1

1

1

1

1

1

1

0

1

0

0

1

0

1

0

0

1

1

0

0

0

1

0

0

1

1

0

1

0

0

1

0

0

0

1

0

0

1

1

0

0

0

0

0

1

1

1

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

31

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

En la tabla se observa que las únicas filas (valuaciones) donde el conjunto de premisas son verdaderas son la fila 1 y fila 8, entonces solo debemos analizar estas filas y observar el valor de verdad de la conclusión para estas filas, como la conclusión para estas filas también es verdadera, entonces el argumento es valido. En el supuesto caso de que existiera un valor de verdad falso, para la conclusión, en una de estas dos filas

entonces el

argumento seria invalido. Ejemplo: Demostrar la validez de la siguiente deducción: “O Juan y José tienen la misma edad o Juan es mayor que José. Si Juan y José tienen la misma edad entonces Pedro y Juan no tienen la misma edad. Si Juan es mayor que José entonces Juan es mayor que Maria . Por lo tanto o Pedro y Juan no tienen la misma edad o Juan es mayor que Maria.” 1: letras proposicionales: p: Juan y José tienen la misma edad. q: Juan es mayor que José. r: Pedro y Juan tienen la misma edad s: Juan es mayor que Maria. 2: fórmulas de lenguaje. ∑ = { p ∨ q ; p→ ¬r ; q→s} Q={¬r ∨ s } 3: Tablas de verdad Como el conjunto de letras proposicionales contiene cuatro letras, entonces se tiene un total de 16 valuaciones diferentes.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

32

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

p

q

r

s

¬r

p∨q

p→ ¬r

q→s

¬r ∨ s

1

1

1

1

0

1

0

1

1

1

1

1

0

0

1

0

0

1

1

1

0

1

1

1

1

1

1

1

1

0

0

1

1

1

0

1

1

0

1

1

0

1

0

1

1

1

0

1

0

0

1

0

1

0

1

0

0

1

1

1

1

1

1

1

0

0

0

1

1

1

1

1

0

1

1

1

0

1

1

1

1

0

1

1

0

0

1

1

0

0

0

1

0

1

1

1

1

1

1

0

1

0

0

1

1

1

0

1

0

0

1

1

0

0

1

1

1

0

0

1

0

0

0

1

1

0

0

0

0

1

1

0

1

1

1

0

0

0

0

1

0

1

1

1

En la tabla de verdad al no existir ninguna valuación que haga simultáneamente verdadera al conjunto de premisas y falsa a la conclusión, entonces el argumento es valido, es decir, la conclusión es consecuencia lógica del conjunto de premisas. Ejemplo: Demostrar la validez del siguiente argumento: “O la lógica es difícil o no le gusta a muchos estudiantes. Si la matemática es fácil, entonces la lógica no es difícil. Por lo tanto, si a muchos estudiantes les gusta la lógica, la matemática no es difícil.” 1: letras proposicionales: p: La lógica es difícil _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

33

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

q: La lógica gusta a muchos estudiantes. r: la matemática es fácil. 2: Fórmulas del lenguaje ∑ = { p ∨ ¬q ; r→ ¬p } Q = {q→ r} 3: tablas de verdad:

P

q

R

¬p

¬q

¬r

p ∨ ¬q

r→ ¬p

q→ r

1

1

1

0

0

0

1

0

0

1

1

0

0

0

1

1

1

1

1

0

1

0

1

0

1

0

1

1

0

0

0

1

1

1

1

1

0

1

1

1

0

0

0

1

0

0

1

0

1

0

1

0

1

1

0

0

1

1

1

0

1

1

1

0

0

0

1

1

1

1

1

1

De la misma forma que en los casos anteriores el argumento es Válido. En alguno casos los argumentos no presentan en forma explicita los dos componentes fundamentales, es decir, la base de conocimientos y la conclusión, en estos casos, la conclusión a validar se la obtiene a base de consultas a la base de conocimientos, el siguiente ejemplo muestra una situación como esta. Ejemplo: Formalizar en el lenguaje proposicional: Manuel, Mauricio y Gabriel son acusados de fraude fiscal en el juicio ellos declaran lo siguiente: _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

34

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Manuel: Mauricio es culpable y Gabriel es inocente. Mauricio: Manuel es culpable solo si Gabriel es también culpable. Gabriel : Yo soy inocente pero al menos uno de los otros es culpable. 1: letras proposicionales: p: Manuel es inocente. q: Mauricio es inocente. r: Gabriel es inocente. 2: Fórmulas de lenguaje: Las formulas del lenguaje se las obtiene a partir de los que dice cada uno de los acusados. Manuel dice:

¬q ∧r

Mauricio dice:

r→p

Gabriel dice:

r ∧(¬p ∨ ¬q) ∑ = { ¬q ∧r , ¬r→ ¬p , r ∧(¬p ∨ ¬q)}

3: Contestar las siguientes preguntas: a) Si todos son inocentes ¿Quien ha mentido? b) Si se supone que todos dicen la verdad , ¿Quién es inocente y quien es culpable? Por medio de tablas de verdad se puede establecer el valor de verdad respecto a lo que dice cada uno de los acusados y en función a los valores obtenidos se podrá respuesta a las interrogantes.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

35

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

P

q

R

¬p ¬q ¬r Manuel Mauricio ¬p ∨ ¬q ¬q ∧r

r→ p

Gabriel r ∧(¬p ∨ ¬q)

1

1

1

0

0

0

0

1

0

0

1

1

0

0

0

1

0

1

0

0

1

0

1

0

1

0

1

1

1

1

1

0

0

0

1

1

0

1

1

0

0

1

1

1

0

0

0

0

1

1

0

1

0

1

0

1

0

1

1

0

0

0

1

1

1

0

1

0

1

1

0

0

0

1

1

1

0

1

1

0

R.- a)

Para dar respuesta a la primera interrogante, se observa que la primera fila es

la valuación en la que todos son inocentes y de acuerdo a los valores obtenidos en la tabla de verdad los que han mentido son Manuel y Gabriel. b) La tercera valuación es la valuación en la que todos dicen la verdad y rn este caso Mauricio es culpable.

3.7.3.5. TEOREMA DE LA CONSECUENCIA LÓGICA.1: Monotonía.Sea

∑

Si

∑ ⊆ ∑*

Entonces :

Є L(P) ;

∑ * Є L(P) y

: Q Є L(P)

∑ => Q

∑* => Q

Si se tiene una deducción valida (∑ => Q) la incorporación de nueva información a ∑ (∑*) no invalida la deducción. Ej:

∑ = { (p ∧q) →¬r ; q→ r ; r ∨ q)} Q = {p}

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

36

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

∑ => Q ∑ * = {(p ∧q) →¬r ; q→ r ; r ∨ q,( ¬r∧¬q ) → p , q} Q = p ∑* => Q ............Se mantiene 2: Sea

∑ Є L(P) y Q Є L(P) ∑ es insatisfascible

Si y Solo Si

∑ => Q

De un conjunto de premisas insatisfascibles se puede coincidir cualquier información. 3: Sea F una contradicción fija de L(P) y ∑ Є (P) ∑ es insatisfascible

Si y Solo Si

∑ => F

De una Base de conocimientos es insatisfascible si a partir de ella se puede concluir una contradicción fija. 4: Sea Q Є L(P) y ∅ un conjunto vacío de fórmulas Q es válida si y solo si

∅

=> Q

Una formula es valida (tautología) si es consecuencia lógica de un conjunto vacío de formulas, es decir, si la negación de la formula es una contradicción. 5: TEOREMA DE DEDUCCIÓN Sea:

∑

Є L(P)

∑ ∪ {Q} => P

y

Q, P Є L(P)

si y solo si ∑ => (Q→ P)

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

37

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Si en la conclusión hay una implicación entonces el antecedente de la implicación puede formar parte del conjunto ∑ {p1 , p2, p3,.....................,pn} => (Q→P) {p,, p2, p3,.....................,pn,Q} => P 6:REDUCCIÓN ENTRE CONSISTENCIA Y CONSECUENCIA LÓGICA Sea:

∑ ∑ => Q

Є L(P)

y

Q Є L(P)

si y solo si ∑ ∪ (¬Q) es insatisfascible.

Para demostrar que una formula es valida, basta con demostrar que la negación de la formula es una contradicción, por extensión, para demostrar que una formula es consecuencia lógica de un conjunto de formulas, basta con demostrar que la negación de la formula (conclusión) unida al conjunto de formulas (base de conocimientos) es una contradicción, es decir, insatisfascible. A este mecanismo de demostración se lo denomina: -Demostración por refutación. -Demostración por reducción al absurdo. 3.7.4. SISTEMA DEDUCTIVO.El establecimiento del sistema deductivo, proporciona el mecanismo por el cual se tiene la posibilidad de generar conclusiones o nueva información, a partir de cierta información existente, a nivel simbólico. Fundamentalmente tiene el propósito de: -

Determinar la validez de un argumento o deducción a nivel simbólico.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

38

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Una demostración a nivel semántica, es decir por medio de tablas de verdad, si bien resulta un método sumamente sencillo, presenta algunas limitaciones, principalmente cuando el numero de letras proposiconales es grande, por ejemplo; si se tiene ‘n’ letras proposicionales, se tendrá 2n interpretaciones o valuaciones diferentes, es en este sentido que la tabla de verdad puede ser muy grande (muchas filas), con 6 letras proposicionales se tiene 64 posibles valuaciones, y se tiene que interpretar todas las formulas del lenguaje para cada una de las valuaciones, este trabajo, si bien es sencillo es muy moroso y fácil de cometer errores. Es por este motivo que se requiere un mecanismo de demostración que permita realizar la demostración a nivel simbólico, el sistema deductivo tiene este propósito. Si bien el sistema deductivo permite demostrar la validez de una deducción o de un argumento a nivel simbólico presenta algunas características: -

Solo indica que un conjunto de fórmulas es insatisfascible (contradicción). Pero con una aplicación adecuada del Teorema de Reducción entre Consistencia y Consecuencia Lógica es posible demostrar la validez de un argumento.

-

No indica en que valuaciones o interpretaciones el argumento es valido o invalido.

FORMULACION DEL SISTEMA DEDUCTIVO. Se parte de un conjunto de cláusulas, es decir, opera sobre cláusulas, por lo tanto, ya que el lenguaje proposicional esta formado por formulas correctamente escritas, es necesario desarrollar un proceso de transformación de dichas formulas a cláusulas. Para la obtención de cláusulas se requiere algunos elementos importantes que a continuación se detallan. 3.7.4.1. CONECTIVOS FUNCIONALMENTE COMPLETOS Los conectivos funcionalmente completos es un sub conjunto de conectivos que permiten representar al resto de conectivos. Se tiene principalmente dos subconjuntos: a) ¬,∧

La negación y la conjunción permiten representar a las otras

conectivas, es decir a la disyunción, implicación y la doble implicación

{∨; Æ ;

ÅÆ} _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

39

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

b) ¬, ∨ conectivas

La negación y la disyunción permiten representar al resto de las {∧; Æ ; ÅÆ}

De estos dos grupos de conectivas funcionalmente completos el mas importante para el proceso transformación de una formula a cláusulas es el segundo grupo, es decir la (¬, ∨) Por ejemplo empleando el conjunto de coactivos funcionalmente completos : (¬, ∨) CONJUNCION. (p∧q) => ¬¬(p∧q) =>¬(¬p∨¬q ) DISYUNCION. (pÆq) => ¬p∨q DOBLE IMPLICACION. (pÅÆq) => (pÆq) ∧ (qÆp) 3.7.4.2. FORMA NORMAL CONJUNTIVA (FNC).Toda fórmula del lenguaje proposicional se puede representar en F.N.C. Una fórmula en F.N.C. esta constituida por una conjunción de disyunciones de literales, donde un literal es una letra proposicional o negación de letra proposicional y se lo representa de la siguiente manera:

n

m

i =1

j =1

IUl

ij

Donde lij es una letra proposicional o negación de letra proposicional.

Es decir, desde el punto de vista matemático se lo puede concebir como un producto de sumas. _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

40

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Ej: (3+2)*(5+3)*(3)*(2+3+6)

en matemáticas: producto de sumas.

Pero desde el punto de vista de la lógica proposicional es un producto de sumas lógicas. (p∨q) ∧(¬q ∨r∨t) ∧(¬r ∨ s) ∧ (p) Una formula es satisfascible si y solo si su equivalencia en F.N.C, también lo es. Es decir, se cambia la representación de la formula, pero las interpretaciones que la hacen verdadera o que la satisfacen, también satisfacen a su equivalente en Forma Normal Conjuntiva. El proceso de transformación de una formula a FNC se lo realiza aplicando algunas equivalencias lógicas y las leyes del algebra booleana. Principios lógicos y leyes lógicas En la lógica proposicional, todas las leyes lógicas son tautológicas, es decir, formas proposicionales, cuyos casos de sustitución son siempre verdaderos. En la lógica de predicados, como veremos en el próximo capítulo, no son tautológicas. Las leyes lógicas son infinitas, a continuación se proporciona la formulación de las más importantes: Distributividad de la conjunción respecto de la disyunción: [ p ∧ ( q v r) ]

[( p ∧ q ) v ( p ∧ r )]

Distributividad de la disyunción respecto de la conjunción: [ p v ( q ∧ r) ]

[( p v q ) ∧ ( p v r )]

Distributividad del condicional respecto de la disyunción: [p

( q v r) ]

[( p

q) v (p

r )]

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

41

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Distributividad del condicional respecto de la conjunción: [p

( q ∧ r) ]

q) ∧ (p

[( p

r )]

De Morgan: - (p ∧ q)

(-p v –q)

-(p v q)

(-p ∧ –q)

Definición del condicional: (p

q)

(-p v q)

(p

q)

-(p ∧ -q)

Definición del bicondicional: q) ∧ (q

(p

q)

(p

p)

(p

q)

(p ∧ q) v (-p ∧ -q)

Transposición: (p

q)

(-q

-p)

Exportación: [(p ∧ q)

r]

[p

(q

r)]

Idempotencia: p

(p ∧ p)

p

(p v p)

Expansión Booleana: p

p ∧ (q v -q)

p

p v (q ∧ -q)

Absorción: _____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

42

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

p

p ∧ (p v q))

p

p v (p ∧ q)

Ej: Obtener el equivalente en F.N.C. de la siguiente fórmula: (pÆq) ∧¬(rƬt) (¬p ∨q) ∧¬(¬r∨¬t) (¬p∨q) ∧(r∧t) (¬p ∨ q) ∧ r ∧ t ...........==Î F.N.C. 3.7.4.3. FORMA NORMAL DISYUNTIVA (F.N.D).Una fórmula en F:ND: esta constituida por una disyunción de conjunciones de literales. n

m

i=1

j=1

U I

l ij

Donde lij es una letra proposicional o negación de letra

proposicional.

Ej:

(p∧¬q∧t) ∨ (r∧¬s)∨ s ……….expresar en F.N.D.

(pÆq) ∧ ¬(rƬt) (¬p∨q) ∧ ¬(¬r ∨¬t) (¬p∨q) ∧(r∧t) (¬p∧r∧t) ∨(q∧r∧t)…………esta en F.N.D. 3.7.4.4. FORMA CLAUSURAL O CLAUSAL.Es una fórmula representada por cláusulas. CLAUSULA: Disyunción de literales, donde un literal es un letra proposicional o negación de letra proposicional.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

43

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Tomando como referencia esta característica una formula en Forma Normal Conjuntiva (F.N.C) es una Conjunción de cláusulas. l1∨ l2∨l3...................ln

CLAUSULA

donde li es una letra proposicional o negación de letras proposicional. F.N.C.:

C1∧ C2 ∧ C3.............Cn

Para simplificar la escritura de una formula en términos de cláusula se puede reemplazar el símbolo de la conjunción (∧) por el símbolo de la coma (,): C1 , C2 , C3 , ............. , Cn Toda formula se puede representar por una o mas cláusulas .Una fórmula es consistente (inconsistente) si y solo si, su equivalente es cláusula también lo es. Por lo tanto, da lo mismo trabajar con la formula original que trabajar con el conjunto de cláusulas resultante de la misma. CLAUSULA ESPECIAL: CLAUSULA VACIA.Una cláusula que no contiene literales es una cláusula vacía y representa un contradicción, es decir, algo insatisfascible. Cláusula vacía : Cláusula sin literales y se lo representa por: Si

o por ∅

n= 0 Î CONTRADICCIÓN

3.7.4.5. PRINCIPIO DE RESOLUCIÓN.-

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

44

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Es un procedimiento de demostración automática por refutación que lleva a cabo en una única operación toda la variedad de procesos involucrados en el razonamiento. Es decir, consiste en una única regla de inferencia. El principio de resolución opera siempre sobre cláusulas, por lo que cuando se utiliza para demostrar la insatisfacibilidad de una formula, esta ha debido convertirse previamente a su forma clausular. La comprobación de la insatisfacibilidad de un conjunto de cláusulas mediante resolución consiste en la aplicación reiterada de su única regla de inferencia hasta encontrar la cláusula vacía. Dos cláusulas Cm y Cp se puede resolver para dar como resultado una cláusula Cr (Conclusión), pero Cm y Cp deben contener al menos el mismo literal en un caso negado y en el otro sin negar y Cr , que es la clausula resolverte, contiene al resto de los literales, excepto al literal que se encuentra en Cm y Cp que estaba negado y sin negar. Por ejemplo si: Cm = p ∨ q ∨ ¬r Cp = t ∨ ¬q Cr = p ∨ ¬r ∨ t

…………Conclusión.

Si una valuación o interpretación satisface a Cm y Cp , entonces también satisface a Cr. REGLA DE RESOLUCIÓN.-(Binaria).2 cláusulas se pueden resolver para obtener una cláusula resolvente. Se selecciona dos cláusulas Cm y Cp , llamadas cláusulas padre, tales que una contenga un literal R y la otra a ¬R , y se resuelven entre si, obteniéndose una nueva cláusula Cr , llamada cláusula resolvente o cláusula hijo.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

45

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

La cláusula resolverte será la disyunción de todos los literales de ambas cláusulas padre con la excepción del par R y ¬R. Si la cláusula resolvente no es la cláusula vacía, se adiciona al conjunto de cláusulas disponibles y se repite el proceso. En caso contrario, si se encuentra la cláusula vacía, significa que el conjunto de cláusulas es insatisfascible, es decir, una contradicción. {C1 ∪ {R} } Cr =

;

{ C2 ∪ {¬R} }

C1 ∪ C2

Tomar en cuenta: Las cláusulas implícitamente están conjuncionadas. Cm : p ∨ ¬q

Cm : p Cp : ¬p Cr :

Cp : q Cr : p

Como las cláusulas están relacionadas por una conjunción, en realidad se tiene la siguiente formula:

p ∧ ¬p

lo que constituye una Contradicción fija, siempre es Falso

MÉTODO GENERAL.La demostración de la valides o invalides de una deducción o de un argumento por medio del principio de resolución, se lleva a cabo por medio del Teorema de Reducción entre Consistencia y Consecuencia Lógica, ya que el principio de resolución solo permite demostrar que un conjunto de cláusulas es insatisfascible o no, para lo cual se establece el siguiente método general: Para demostrar que la deducción ∑ => Q es valida: 1.

Incorporar (¬Q) a ∑

Î

∑ ∪ {¬Q}

2.

Expresar ∑ ∪ {¬Q}

en cláusulas Î

∑*

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

46

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

3.

Aplicar la regla de resolución a ∑ *. Si se logra encontrar la clausula vacia, entonces se habria demostrado que el conjunto de clausulas es una contradicción y por lo tanto el

argumento es valido, es decir Q es

consecuencia logica de ∑ (∑=>Q), en caso contrario el argumento no es válido, es decir, Q no es consecuencia logica de ∑ (∑ ≠> Q). Ej: Demostrar si el siguiente argumento es válido. ∑ = {(r ∨ p) Æ (q ∨ ¬s) , p , s} Q = {q} ∑ => Q a demostrar: Agregar la conclusión negada (¬q) a la base de conocimiento. {(r ∨ p) Æ (q ∨ ¬s), p , s ,¬q} Expresar las formulas como cláusulas. (r ∨ p) Æ (q ∨ ¬s) =

¬(r ∨ p) ∨ (q ∨ ¬s) (¬r ∧ ¬p) ∨ (q ∨¬s) (¬r ∨ q ∨ ¬s) ∧ (¬p ∨ q ∨ ¬s)

De la formula se obtiene dos clausulas:

(¬r ∨ q ∨ ¬s) , (¬p ∨ q ∨ ¬s)

El conjunto de clausulas es: {¬r ∨ q ∨ ¬s , ¬p ∨ q ∨ ¬s , p , s ,¬q} Aplicando el principio de resolución:

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

47

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

Como a partir del conjunto de cláusulas resultante de ∑ ∪ {¬Q} se obtiene la cláusula vacía, por lo tanto el conjunto de cláusulas es una contradicción y por lo tanto Q es consecuencia lógica de ∑ , es decir, el argumento es valido. Esta afirmación se sustenta por el teorema siguiente: ∑ => Q

si y solo si ∑ ∪ (¬Q) es insatisfascible.

ARBOL DE REFUTACIÓN.El árbol de refutación muestra gráficamente al conjunto de cláusulas que intervienen en el proceso de obtención de la cláusula vacía. Para el ejemplo anterior es el siguiente:

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

48

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

En los nodos terminales del árbol de refutación solo se encuentran las cláusulas iniciales con las que se empieza la aplicación del principio de resolución.

Ejemplo: Demostrar la validez del siguiente argumento : “No pongo la calefacción eléctrica solo si tengo gas. No consumo leña a menos que el petróleo sea caro o no ponga calefacción eléctrica. El petróleo no es caro. Consumo leña a menos que tengo frió. Por lo tanto solo si tengo frió tengo gas”. 1: letras proposicionales: p: Yo pongo la calefacción electrica. q: Yo tengo gas. r : Yo consumo leña. s : El petróleo es caro. t : Yo tengo frío. 2: formulas del lenguaje: ∑ = {¬q Æ p , ¬(s ∨ ¬p) Æ ¬r , ¬s , ¬tÆ r} Q = ¬tÆq

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

49

SIS 1205 “A” ANALISIS DISCRETO INGENIERIA DE SISTEMAS _____________________________________________________________________________________

3. ∑ U { ¬Q} {¬q Æ p , ¬(s ∨ ¬p) Æ ¬r , ¬s , ¬tÆ r , ¬(¬tÆq)} 4. clausulas: {q ∨ p , s ∨ ¬p ∨ ¬r , ¬s , t ∨ r , ¬t , ¬q} 5. Resolucion:

Como a partir del conjunto de cláusulas se logra obtener la cláusula vacía, por lo tanto, el conjunto de cláusulas es una contradicción, entonces el conjunto de formulas original también es una contradicción, por lo tanto se establece que el argumento es valido.

_____________________________________________________________________ M.Cs. Ing Julio Cesar Bermudez vargas

50