lógica computacional dr. eduardo a. rodrÍguez tello · panorama general de la lógica conceptos...

Proceso de admisión 2019 – Curso de matemáticasLógica computacional

Dr. Eduardo A. RODRÍGUEZ TELLO

CINVESTAV-Tamaulipas

20 de mayo de 2019

Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Lógica computacional 20 de mayo de 2019 1 / 69

1 Panorama general de la lógica


Panorama general de la lógica Conceptos básicos

1 Panorama general de la lógicaConceptos básicosBreve panorama histórico¿Qué estudia y qué no estudia la lógica?



Conceptos básicosObservando el mundo desde una perspectiva lógica

La lógica surgió de una necesidad humana innata de darlesentido al mundo y, en la medida de lo posible, obtener ciertocontrol sobre él

Una forma de entender el mundo es analizar la conexión entre lacausa y el efecto




Típicamente, estas conexiones entre causa y efecto se puedenrepresentar mediante una sentencia Si...entonces.

Ejemplos

Si estudio para el examen, entonces obtendré una buena calificación

Si tomo demasiado refresco, entonces la cantidad de glucosa en misangre aumentará considerablemente




Cada sentencia Si...entonces se compone de dos declaracionesmás pequeñas llamadas sub-sentencias:

El antecedente, que se encuentra después de palabra SiEl consecuente, que sigue a la palabra entonces.

Ejemplo

Si son las 5 p.m., entonces es hora de ir a casa

Antecedente: son las 5 p.m.

Consecuente: es hora de ir a casa




A medida que el hombre entendía el mundo, este comenzó ahacer afirmaciones más generales al respecto

Por ejemplo:Todos los caballos son amistososCada vez que llueve, la tierra se humedece




Palabras como todos y cada vez permiten clasificar las cosas enconjuntos (grupos de objetos) y subconjuntos (grupos dentro degrupos).

Por ejemplo, cuando decimos “Todos los caballos son amistosos”,significa que el conjunto de todos los caballos está contenidodentro del conjunto de todas las cosas amistosas




También es posible también conocer el mundo al analizar quéexiste y qué no existe

Ejemplos

Algunos de mis profesores son accesibles

Existe al menos un estudiante en la escuela que se apellida López

Nadie en mi colonia corre más rápido que Luis




Palabras como algunos, y existe se refieren a la superposición deconjuntos (intersección)

Por ejemplo, cuando decimos: “Algunos de mis profesores sonaccesibles”, significa que hay una intersección entre el conjuntode los profesores y el conjunto de las personas accesibles




De manera similar, palabras como ninguno, y no existe se refierena que no hay intersección entre los conjuntos

Por ejemplo, cuando decimos: “Nadie en mi colonia corre másrápido que Luis”, significa que no hay una intersección entre elconjunto de los habitantes de la colonia y el conjunto de todas laspersonas que corren más rápido que Luis



Conceptos básicosConstrucción de argumentos lógicos

Un argumento contiene un conjunto de premisas iniciales y unaconclusión final

Comúnmente las premisas y la conclusión están vinculadas poruna serie de pasos intermedios

Las premisas son los hechos conocidos: las afirmaciones que sesabe (o se cree firmemente) que son ciertas

En muchas situaciones, escribir un conjunto de premisas es unexcelente primer paso para resolver un problema




Ejemplo

Debemos decir si se autoriza la construcción de una nueva escuela que abrirá enseptiembre. Después de realizar algunas llamadas telefónicas tenemos las siguientespremisas (hechos)

Los fondos para el proyecto no estarán disponibles hasta marzo

La empresa constructora no comenzará a trabajar hasta que reciba el pago

Todo el proyecto tardará al menos ocho meses en completarse




En la mayoría de los casos un argumento también incluye pasosintermedios que muestran cómo las premisas conducengradualmente a una conclusión (resultado)

EjemploSegún las premisas, no podremos pagarle a la empresa constructorahasta marzo, por lo que no se terminará de construir la escuela hastaal menos ocho meses después, que es noviembre. Pero, la escueladebe comenzar en septiembre. Por lo tanto ...

La palabra por lo tanto indica una conclusión: “El edificio no estaráterminado antes de que la escuela comience en septiembre”




Después de crear un argumento, se debe poder decidir si esválido, i.e., si es un buen argumento

Para probar la validez de un argumento, se asume que todas laspremisas son verdaderas y luego se observa si la conclusión sederiva automáticamente de ellas

Si la conclusión se obtiene automáticamente, entonces se tieneun argumento válido

En caso contrario, tenemos un argumento inválido




El argumento del ejemplo de la construcción de una escuelapuede parecer válido, pero también puede generar algunasdudas.

Por ejemplo, si otra fuente de financiamiento estuviera disponible,la empresa de construcción podría comenzar antes y quizásterminar en septiembre

Por lo tanto, el argumento tiene una premisa oculta llamadaentimema:

No hay otra fuente de fondos para el proyecto




Los argumentos lógicos sobre situaciones del mundo real (encontraste con los argumentos matemáticos o científicos) casisiempre tienen entimemas

Por lo tanto, cuanto más claro se formule un argumento lógico (sinentimemas), más posibilidades habrá de que éste sea válido



Conceptos básicosCreando conclusiones lógicas empleando las leyes del pensamiento

Como base para comprender la lógica, el filósofo (matemático,lógico y escritor) británico Bertrand A. W. Russell (1872-1970)estableció tres leyes del pensamiento

Estas leyes (llamadas también principios) tienen su base en ideasque se remontan a Aristóteles, quien fundó la lógica clásica hacemás de 2,300 años




Las tres leyes clásicas del pensamiento son realmente básicas yfáciles de entender

Pero, lo importante a tener en cuenta es que estas leyes permitensacar conclusiones lógicas sobre las declaraciones, incluso si nose está familiarizado con las circunstancias del mundo real queestán discutiendo




Principio de identidad: Establece que toda entidad es idéntica a símisma

∀x x = x

EjemplosAlbert Einstein es idéntico a sí mismo (Albert Einstein)El Sol es idéntico a sí mismoEsta pera es idéntica a sí misma




Principio del tercero excluido: Una proposición es verdadera o falsa(i.e., la disyunción de una proposición y de su negación es siempreverdadera)

(A ∨ ¬A) es verdadera

EjemplosAlbert Einstein fue un físico famoso o no fue un físico famosoLa pera está madura o no está maduraEl Sol está ardiendo o no está ardiendo




Principio de no contradicción: Establece que una proposición y sunegación no pueden ser ambas verdaderas al mismo tiempo y en elmismo sentido

¬(A ∧ ¬A) es verdadera

EjemplosMi nombre es Eduardo (E)Mi nombre no es Eduardo (¬E)Por el principio de no contradicción estamos seguros que no esposible que mi nombre sea y no sea Eduardo al mismo tiempo


Panorama general de la lógica Breve panorama histórico




Breve panorama históricoLógica del período clásico

Antes de Aristóteles de Estagira (384-322 a.C.), el argumentológico se aplicaban de manera intuitiva cuando era apropiado enmatemáticas, ciencias y filosofía

Por ejemplo, dado que todos los números son pares o impares, sise puede demostrar que un cierto número no es par, se sabesentonces que debe ser impar

Los griegos se destacaron en este enfoque de divide y vencerás

Regularmente usaban la lógica como una herramienta paraexaminar el mundo

Aristóteles, sin embargo, fue el primero en reconocer que laherramienta en sí podía ser examinada y desarrollada




En seis escritos sobre lógica, más tarde reunidos como una obraúnica llamada Órganon (que significa herramienta), analizó cómofunciona un argumento lógico

Aristóteles esperaba que la lógica, bajo su nueva formulación,sirviera como una herramienta de pensamiento que ayudara a losfilósofos a entender mejor el mundo




La noción central de la lógica aristotélica es el silogismo

Aristóteles considero por primera vez los silogismos en su escritoPrimeros Analíticos (en latín Analytica Priora)




Un silogismo es un tipo de argumento lógico que aplicarazonamiento deductivo para llegar a una conclusión basado endos o más proposiciones que asume son verdaderas

Ejemplo

1 Todos los hombres son mortales

2 Todos los griegos son hombres

3 Por lo tanto, todos los griegos son mortales

En este ejemplo, tras establecer las premisas 1 y 2, la conclusión3 se sigue por necesidad




Gran parte del trabajo de Aristóteles se centró en comprender loque él llamó proposiciones categóricas

Una proposición (declaración) categórica afirma o niega quetodos o algunos de los miembros de una categoría (el términosujeto, S) están incluidos en otra (el término predicado, P)

Aristóteles identificó cuatro tipos distintos primarios deproposición categórica y les dio formas estándar:

Dos universales, A (positiva) y E (negativa)Dos particulares, I (positiva) y O (negativa)




Los dos términos (sujeto y predicado) en una proposicióncategórica pueden ser clasificados como distribuido o nodistribuido

Si todos los miembros de la clase del término se ven afectadospor la proposición, esa clase es distribuida; de lo contrario, es nodistribuida




Ext. Dist.

Tipo Cualidad S P Sentencia S P

A + U P Todo S está en P X 7

Todos los gatos son mamíferos

E − U U Ningún S está en P X X

Ningún escarabajo es mamífero

I + P P Algún S está en P 7 7

Algunos mexicanos son triunfadores

O − P U Algún S no está en P 7 X

Algunos políticos no son corruptosCualidad: +, positiva;−, negativa

Extensión: U , universal; P , particulares

Distribución: X, distribuida; 7, no distribuida




A y E son contrarias porque difieren encualidad siendo universales

I y O son subcontrarias, porque difieren en lacualidad siendo particulares

A con respecto a O, e I con respecto a E soncontradictorias, porque difieren en cantidad ycualidad

A con respecto a I, y E con respecto a O sonsubalternas porque difieren en cantidad

Cuadro de oposición




Euclides de Alejandría (325-265 a.C.) es mejor conocido por sutrabajo en geometría, que todavía se conoce como geometríaeuclidiana en su honor

Su mayor logro aquí fue su organización lógica de los principiosgeométricos en axiomas y teoremas




Euclides comenzó con cinco axiomas (o postulados),afirmaciones verdaderas que él creía eran simples y evidentes

A partir de estos axiomas, usó la lógica para probar teoremas,afirmaciones verdaderas que eran más complejas y no evidentesde inmediato

De esta manera, logró probar el vasto cuerpo de geometríalógicamente a partir solamente de los cinco axiomas

Los matemáticos todavía utilizan esta organización lógica deenunciados en axiomas y teoremas




Euclides también usó un método lógico llamado prueba porcontradicción (reductio ad absurdum, en latín)

En este método, se asume lo contrario de lo que se quiere probary luego se muestra que esta suposición conduce a una conclusiónque es obviamente incorrecta

EjemploPor ejemplo, un detective tratando de resolver un asesinato podría razonar: “Si elmayordomo cometió el asesinato, debe haber estado en la casa entre las 7 y las 8pm. Pero, testigos lo vieron en la ciudad a veinte kilómetros de distancia durante esashoras, así que no pudo haber estado en la casa. Por lo tanto, el mayordomo nocometió el asesinato”




Mientras los sucesores de Aristóteles desarrollaron su trabajosobre la lógica silogística, otra escuela griega de filosofía, losestoicos, adoptaron un enfoque diferente

Ellos se centraron en las declaraciones condicionales de la formasi... entonces...

El más notable de ellos fue Crisipo de Solos (279-206 a.C.)




EjemploPremisas:

Si las nubes se están acumulando en el oeste, entonces lloveráLas nubes se están acumulando en el oeste

Conclusión:Lloverá



Breve panorama históricoLógica en los siglos I al XII

Después del período griego clásico hubo realmente pocosavances en la lógica

Durante el primer milenio de nuestra la mayoría del trabajo enlógica se hizo en el mundo árabe

Los filósofos cristianos y árabes en Bagdad continuarontraduciendo y comentando a Aristóteles




Avicena, Ibn Siná, en persa, (980-1037 d.C.) rompió con estapráctica, estudiando conceptos lógicos que implicaban tiempo(siempre, algunas veces, nunca)

Posteriormente la lógica dejó de estudiarse por mucho tiempo




Es hasta el siglo XII que resurgió el interés por la lógica, enespecial en las falacias lógicas (argumentos que parecen válidos,pero no lo son)

Ejemplo de una falacia (afirmación del consecuente)

Premisas:

Si está nevando, entonces hace fríoHace frío

Conclusión:

Por lo tanto, está nevandoAun cuando ambas premisas sean verdaderas, la conclusión podría ser falsa,porque no siempre que hace frío está nevando




El estudio de las falacias se remonta por lo menos hastaAristóteles, quien en sus Refutaciones sofísticas identificó yclasificó trece clases de falacias

Desde entonces se han agregado a la lista cientos de otrasfalacias y se han propuesto varios sistemas de clasificación

Además, como una de las siete artes liberales (gramática,retórica, aritmética, geometría, astronomía y música), la lógicatambién fue fundamental para el currículo de las universidades endesarrollo durante los siglos XII a XVI



Breve panorama históricoLógica moderna (siglos XVII a XIX)

Gottfried Leibniz (1646–1716) fue un filósofo, matemático, lógico,teólogo, jurista, bibliotecario y político alemán

Fue el mejor lógico del Renacimiento en Europa, y al igual queAristóteles, vio el potencial de la lógica para convertirse en unaherramienta indispensable para comprender el mundo




Fue el primero en llevar el trabajo de Aristóteles un pasosignificativo más adelante al convertir las declaraciones lógicas ensímbolos que luego podrían manipularse como números yecuaciones

El resultado fue el primer intento crudo de lógica simbólica

De esta manera, Leibniz esperaba que la lógica transformara lafilosofía, la política e incluso la religión en cálculos puros,proporcionando un método confiable para responder a todos losmisterios de la vida con objetividad




Desafortunadamente, su sueño de transformar todas las áreas dela vida en cálculo no fue perseguido por la generación que losiguió

Sus escritos sobre lógica como cálculo simbólico acumularonpolvo durante casi 200 años

Cuando fueron redescubiertos, los lógicos ya habían alcanzadoestas ideas y las habían superado

Como resultado, Leibniz no fue tan influyente como podría habersido durante esta fase crucial en el desarrollo de la lógica




Hasta principios del siglo XIX, la lógica se estudió de manerainformal, es decir, sin el uso de símbolos en lugar de palabras

Comenzando con Leibniz, los matemáticos y filósofos hasta estemomento habían improvisado una amplia variedad de notacionespara conceptos lógicos comunes

Sin embargo, estos sistemas generalmente carecían de cualquiermétodo para el cálculo a gran escala




A fines del siglo XIX, sin embargo, los matemáticos habíandesarrollado una lógica formal, también llamada lógica simbólica,en la que los símbolos computables representan palabras ydeclaraciones

Tres personajes fueron clave para la lógica formal: George Boole,Georg Cantor y Gottlob Frege




El álgebra booleana fue inventada por el inglés George Boole(1815-1864)

Es el primer sistema completamente desarrollado que maneja lalógica como un cálculo y se considera la precursora de la lógicaformal

Es similar a la aritmética estándar en el sentido de que utilizavalores numéricos y las operaciones familiares para la suma y lamultiplicación

Sin embargo, a diferencia de la aritmética, sólo se usan dosnúmeros: 0 y 1, que significan falso y verdadero, respectivamente




Por ejemplo:SeaA = Thomas Jefferson escribió la Declaración de Independencia

SeaB = Paris Hilton escribió la Constitución de los Estados Unidos

Como la primera declaración es verdadera y la segunda es falsase puede decir que A = 1 y B = 0




En el álgebra de Boole, la adición se interpreta como o (or), por loque la declaración

Thomas Jefferson escribió la Declaración de Independencia oParis Hilton escribió la Constitución de los Estados Unidos

se traduce como:A+B = 1 + 0 = 1

Debido a que la ecuación booleana se evalúa como 1, ladeclaración es verdadera




De forma similar, la multiplicación se interpreta como y (and), porlo que la declaración

Thomas Jefferson escribió la Declaración de Independencia yParis Hilton escribió la Constitución de los Estados Unidos

se traduce comoA×B = 1× 0 = 0

En este caso, la ecuación booleana se evalúa como 0, por lo quela declaración es falsa




La teoría de conjuntos, iniciada en la década de 1870 por elmatemático y lógico de origen ruso Georg Cantor (1845-1918),fue otro precursor de la lógica formal, pero con una influencia yutilidad mucho más amplias que el álgebra de Boole

Un conjunto es una colección de elementos con característicassimilares considerada en sí misma como un objeto

Algunos ejemplos:{1, 2, 3, 4, 5, 6}

{Batman, Wonder Woman, Spiderman}

Esta construcción simple es muy efectiva para caracterizar ideasimportantes en la lógica




Por ejemplo considere la siguiente sentencia: Todo los nombres deestados en USA que contienen una z comienzan con la letra A

Esta sentencia puede ser verificada al identificar los siguientesdos conjuntos

Conjunto 1: {Arizona}Conjunto 2: {Alabama, Alaska, Arizona, Arkansas}

Como puede observarse cada elemento del primer conjunto estambién elemento del segundo

Por lo tanto el primer conjunto es subconjunto del segundo, por loque la sentencia es verdadera




Gottlob Frege (1848-1925), un matemático, lógico y filósofoalemán, inventó el primer sistema real de lógica formal

El sistema que inventó es realmente un sistema lógico embebidodentro de otro

El sistema más pequeño, la lógica proposicional, usa letras pararepresentar afirmaciones simples, que luego se vinculan mediantesímbolos para cinco conceptos clave: no, y, o, si, y si y sólo si




Por ejemplo:Sea E = Evelyn está en el cine

Sea P = Pedro está en casa

Estas definiciones permiten formar estas dos declaraciones:Evelyn está en el cine y Pedro está en casa

Si Evelyn está en el cine, entonces Pedro no está en casa.

y convertirlos en símbolos de la siguiente manera:

E ∧ P

E → ¬P




El sistema más grande, la lógica de predicados, incluye todas las reglas de lalógica proposicional, pero las expande. Utiliza diferentes letras para representarel sujeto y el predicado de una declaración simple

Por ejemplo:

Sea e = Evelyn

Sea p = Pedro

Sea Mx = x está en el cine

Sea Hx = x está en casa

Estas definiciones permiten representar las siguientes dos sentencias:

Evelyn está en el cine y Pedro está en casa; como Me ∧Hp

Si Evelyn está en el cine, entonces Pedro no está en casa; como Me→ ¬Hp




La lógica de predicados también incluye dos símbolos adicionalestodos y algunos, los cuales permiten representar las siguientessentencias:

Todos están en el cine

Algunos están en casa

De la siguiente forma:∀x [Mx]

∃x [Hx]

La lógica de predicados tiene el poder de representar las cuatroproposiciones categóricas básicas del cuadro de oposición deAristóteles



Breve panorama históricoLógica en el siglo XX

A fines del siglo XIX, siguiendo el ejemplo de Euclides, losmatemáticos intentaron reducir todo el conocimiento a unconjunto de teoremas lógicamente dependientes de un pequeñonúmero de axiomas

Frege, inventor del primer sistema de lógica formal, vio laposibilidad de que las matemáticas en sí mismas pudieranderivarse de la lógica y la teoría de conjuntos

Comenzando con sólo unos pocos axiomas sobre conjuntos,demostró que los números y, en última instancia, todas lasmatemáticas se derivaban lógicamente de estos axiomas




La teoría de Frege pareció funcionar bien hasta que BertrandRussell encontró una inconsistencia que demuestra que susistema es contradictorio

Esta inconsistencia se conoce como la paradoja de Russell




Paradoja de RussellSea M el conjunto de todos los conjuntos que no se contienen a sí mismos comomiembros. Es decir

M = {x : x /∈ x} (1)

Según la teoría de conjuntos de Cantor, la ecuación (1) se puede representar por

∀xx ∈M ↔ x /∈ x (2)

es decir Cada conjunto es elemento de M si y sólo si no es elemento de sí mismo.Ahora, como M es un conjunto, se puede substituir x por M en la ecuación (2), dedonde se obtiene

M ∈M ↔M /∈M (3)

Es decir que M es un elemento de M si y sólo si M no es un elemento de M , lo cuales absurdo




El proyecto de reducir las matemáticas y la lógica a una brevelista de axiomas abre una pregunta interesante: ¿Qué sucede sicomienzas con un conjunto diferente de axiomas?

Una posibilidad, por ejemplo, es permitir que una sentencia seevalúe a algo distinto de verdadero o falso

En otras palabras, permitir que una sentencia viole el principio deltercero excluido de Russell

Para los Griegos esta flagrante violación hubiera sido impensable,pero con la lógica formulada simplemente como un conjunto deaxiomas, se abrió esta posibilidad




Jan Łukasiewicz (1878-1956), un matemático, lógico y filósofopolaco, propuso en 1917 la lógica plurivalente, que incluyó supropio cálculo de tres valores de verdad (verdadero, falso, posible)

Fue la primera lógica de cálculo no clásica

Posteriormente surgieron otras formas de lógica no clásica: lógicadifusa, la lógica cuántica, etc.




Con las matemáticas definidas en términos de un conjunto deaxiomas, surgió la pregunta de si este nuevo sistema era a la vezconsistente y completo

Es decir, ¿era posible usar la lógica para derivar cada sentenciaverdadera sobre matemáticas a partir de estos axiomas, yninguna sentencia falsa?




En 1931, un lógico y matemático, de origen austriaco y naturalizadoestadounidense, llamado Kurt Gödel (1906-1978) demostró que un númeroinfinito de sentencias matemáticas son verdaderas, pero no pueden probarsedados los axiomas publicados en los Principia Mathematica1

1Tres libros que definen las bases de la matemática en términos de un conjunto de axiomas, fueron escritos por Bertrand

Russell y Alfred North Whitehead




Gödel también demostró que cualquier intento de reducir lasmatemáticas a un sistema consistente de axiomas produce elmismo resultado: un número infinito de verdades matemáticas,llamadas declaraciones indecidibles, que no son demostrablesdentro de ese sistema

Este resultado, denominado Teorema de la Incompletitud,estableció a Gödel como uno de los mejores matemáticos delsiglo XX




En cierto sentido, el teorema de la incompletitud de Gödelproporcionó una respuesta a la esperanza de Leibniz de que lalógica algún día proporcionaría un método para calcular lasrespuestas a todos los misterios de la vida

La respuesta, desafortunadamente, fue un No definitivo

La lógica, al menos en su formulación actual, es insuficiente paraprobar cada verdad matemática, y mucho menos cada verdad deeste complejo mundo




Sin embargo, en lugar de centrarse en lo que la lógica no puedehacer, los matemáticos y científicos del siglo XX han encontradoinfinitas formas de usar la lógica

El principal de estos usos es la computadora, que algunosexpertos (especialmente los informáticos) consideran el mayorinvento del siglo XX

Hardware, el diseño físico de los circuitos informáticos, utilizacompuertas lógicas, que imitan las funciones básicas de la lógicaproposicional: reciben información en forma de corriente eléctricade una o dos fuentes y emiten corriente sólo en determinadascondiciones




Por ejemplo, una compuerta NOT emite corriente sólo cuando nofluye corriente desde su entrada

Una compuerta AND emite sólo cuando la corriente fluye desdesus dos entradas

Una compuerta OR emite sólo cuando la corriente fluye desde almenos una de sus dos entradas




Software, los programas que dirigen las acciones del hardware,están todos escritos en lenguajes de computadora, como Java,Visual Basic, C++, Ruby o Python

Aunque todos los lenguajes informáticos tienen sus diferencias,cada uno contiene un núcleo de similitudes, incluido un conjuntode palabras clave de lógica proposicional, como and, or, if... then,etc


Panorama general de la lógica ¿Qué estudia y qué no estudia la lógica?



Panorama general de la lógica ¿Qué estudia y qué no estudia la lógica?

¿Qué estudia y qué no estudia la lógica?

La lógica

no puede sí puede

Crear un argumento valido Evaluar la validez de un argumento dado

Decir que es verdadero o falso en realidad Decir cómo trabajar con sentencias verda-deras y falsas

Decir si una sentencia es sólida (sound) Decir si una sentencia es válida

Justificar conclusiones a las que llegó porinducción

Justificar conclusiones a las que se llegópor deducción





20 de mayo de 2019


1 Lógica proposicional


Lógica proposicional Proposiciones y variables proposicionales

1 Lógica proposicionalProposiciones y variables proposicionalesOperadores básicosProposiciones atómicas y molecularesParéntesis y precedencia de operadoresTablas de verdadCondiciones lógicas en tablas de verdad



Proposiciones y variables proposicionales

Una proposición es una oración declarativa que puede serverdadera o falsa (pero no ambas)

Ejemplos:La Ciudad de México es la capital de MéxicoHay menos políticos en Tampico que en la Ciudad de México1 + 1 = 22 + 2 = 5



Proposiciones y variables proposicionales

Una variable que representa una proposición es llamada variableproposicional

Las variables proposicionales son los bloques de construcciónbásicos de las fórmulas proposicionales

Por ejemplo:P = La Ciudad de México es la capital de MéxicoQ = Hay menos políticos en Tampico que en la Ciudad de México


Lógica proposicional Operadores básicos




Operadores básicos

La lógica proposicional tiene cinco operadores básicos (deenlace)

Estos operadores lógicos son similares a los operadoresaritméticos, ya que dados algunos valores de entrada producenun nuevo valor

Sin embargo, los operadores lógicos realmente sólo tratan condos valores: los valores de verdad, T y F (verdadero y falso)



Operadores básicos

Operador Nombre Significado Ejemplo

¬ Negación No ¬X

∧ Conjunción Y X ∧ Y

∨ Disyunción O X ∨ Y

→ Condicional Si ... entonces X → Y

↔ Bicondicional Si y sólo si X ↔ Y


Lógica proposicional Proposiciones atómicas y moleculares




Proposiciones atómicas y moleculares

En la lógica proposicional las proposiciones atómicas son las deforma más simple (básica)

Una proposición atómica es una proposición completa sin ningúnoperador de enlace

Cuando unimos dos o más proposiciones atómicas conoperadores de enlace se forma entonces una proposiciónmolecular



Proposiciones atómicas y moleculares

Por ejemplo consideremos las siguientes dos proposiciones atómicas:Hoy es sábado

No hay clase

Si empleamos un operador de enlace podríamos unirlas para formaruna proposición molecular

Hoy es sábado y no hay clase

El operador de enlace no forma parte de ninguna de lasproposicionales atómicas empleadas


Lógica proposicional Paréntesis y precedencia de operadores




Paréntesis y precedencia de operadores

En la lógica proposicional los operadores de enlace pueden serusados con proposiciones moleculares de la misma forma quecon las proposiciones atómicas

En estos casos uno de ellos es el operador dominante por queactúa sobre toda la proposición

Por ejemplo en la siguiente proposición molecular los espacios sepueden llenar con proposiciones atómicas o moleculares

( ) ∧ ( )




Si se emplean proposiciones moleculares, éstas a su vezcontienen otros operadores de enlace

Sin embargo, la conjunción ∧ se mantiene como el operadordominante

Por ejemplo, la conjunción de dos negaciones, como “Antonio noestudia en la universidad” y “Ana no estudia en la Universidad”

Si designamos por T la proposición “Antonio estudia en laUniversidad” y por A la proposición “Ana estudia en laUniversidad” tendríamos la siguiente fórmula

(¬T ) ∧ (¬A)




Consideremos ahora una conjunción cuyo primer miembro sea asu vez una disyunción y cuyo segundo miembro sea unaproposición atómica

x = 1 o x = 2, y y = 3

Sea P = “x = 1”, Q = “x = 2”, y R = “y = 3”

(P ∨Q) ∧R (1)

Los paréntesis que encierran la proposición molecular P ∨Q en lafórmula (1) muestra que las partes están ligadas por unaproposición única




Una convención acerca del uso de los paréntesis es que lasconjunciones y las disyunciones tienen “menor precedencia” quelas condicionales y bicondicionales, i.e., dada una fórmula sinparéntesis, las conjunciones y las disyunciones deben agruparseantes

Por ejemplo

Proposición Lectura correcta Lectura incorrecta

P ∧Q → R (P ∧Q) → R P ∧ (Q → R)

¬P ↔ Q ∨R ¬P ↔ (Q ∨R) (¬P ↔ Q) ∨R

P ∧Q ↔ R ∨ S (P ∧Q) ↔ (r ∨ S) (P ∧ (Q ↔ R)) ∨ S




La negación ¬ tiene mayor precedencia que los operadoresbinarios

Por ejemplo, esta fórmula:

((¬P ) ∧ (¬Q) ∧ (¬R) ∧ S) ∨ ((¬P ) ∧Q ∧R ∧ (¬S))

Es equivalente a esta otra (retirando paréntesis innecesarios):

(¬P ∧ ¬Q ∧ ¬R ∧ S) ∨ (¬P ∧Q ∧R ∧ ¬S)




En resumen, la precedencia de los operadores en lógicaproposicional es la siguiente.

Operador Nombre Precedencia

¬ Negación 1

∧ Conjunción 2

∨ Disyunción 3

→ Condicional 4

↔ Bicondicional 5


Lógica proposicional Tablas de verdad




Tablas de verdadTabla de verdad de la negación

X ¬X

T F

F T



Tablas de verdadTabla de verdad de la conjunción

X Y X ∧ Y

T T T

T F F

F T F

F F F

Nota: Una conjunción es verdadera sólo cuando ambas partes de ella son verdaderas. De lo contrario, es falsa.



Tablas de verdadTabla de verdad de la disyunción

X Y X ∨ Y

T T T

T F T

F T T

F F F

Nota: Una disyunción es verdadera cuando al menos una de sus partes es verdadera. De lo contrario, es falsa.



Tablas de verdadTabla de verdad de la condicional

X Y X → Y

T T T

T F F

F T T

F F T

Nota: Una sentencia condicional es falsa sólo cuando la primera parte es verdadera y la segunda parte es falsa. De lo contrario,

es verdadera.



Tablas de verdadTabla de verdad de la bicondicional

X Y X ↔ Y

T T T

T F F

F T F

F F T

Nota: Una sentencia bicondicional es verdadera sólo cuando ambas partes de ella tienen el mismo valor de verdad. De lo

contrario, es falsa.


Lógica proposicional Condiciones lógicas en tablas de verdad




Condiciones lógicas en tablas de verdadTautologías

Una tautología es una proposición que siempre es verdadera,independientemente de los valores de verdad de sus constantes

Se representa con el símbolo >

Un ejemplo de tautología es la proposición X ∨ ¬X

Debido a que ya sea X o ¬X pueden ser verdaderas, al menosuna parte de esta proposición es verdadera, por lo tanto estaproposición molecular siempre es verdadera

X ¬X X ∨ ¬X

T F T

F T T



Condiciones lógicas en tablas de verdadContradicciones

Una contradicción es una proposición que siempre es falsa,independientemente de los valores de verdad de sus constantes

Se representa con el símbolo ⊥

Un ejemplo de contradicción es la proposición X ∧ ¬X

Debido a que ya sea X o ¬X pueden ser falsas, al menos unaparte de esta proposición es falsa, por lo tanto esta proposiciónmolecular siempre es falsa

X ¬X X ∧ ¬X

T F F

F T F



Condiciones lógicas en tablas de verdadImplicación tautológica

Una proposición P se dice que implica tautológicamente unaproposición Q si y sólo si la condicional P → Q es una tautología

La proposición “Pérez apuesta a los Pumas y Lopez apuesta a losTigres” implica tautológicamente “Pérez apuesta a los Pumas”

Ya que cualesquiera que sean las proposiciones P y Q,P ∧Q → P es una tautología

P Q P ∧Q → P

T T TT F TF T TF F T



Condiciones lógicas en tablas de verdadEquivalencia lógica

Dos proposiciones son lógicamente equivalentes (llamadatambién equivalencia semántica) si en cualquier posibleasignación las dos tienen el mismo valor de verdad

Por ejemplo, si consideramos las proposiciones P , ¬¬P y sucorrespondiente tabla de verdad podremos comprobar que ambastienen el mismo valor de verdad en cualquier línea

P ¬P ¬¬P

T F TF T F



Condiciones lógicas en tablas de verdadEquivalencia lógica

Veamos otro ejemplo. Verificaremos si la proposición A ∧ ¬B eslógicamente equivalente a la proposición ¬(¬A ∨B)

A B ¬A ¬B ¬A ∨B ¬(¬A ∨B) A ∧ ¬B

T T F F T F F

T F F T F T T

F T T F T F F

F F T T T F F



Condiciones lógicas en tablas de verdadEquivalencia tautológica

Si dos proposiciones son lógicamente equivalentes, el valor deverdad de una es siempre el mismo que el de la otra, y subicondicional correspondiente será siempre verdadera (unatautología)

Las proposiciones lógicamente equivalentes se llaman tambiénproposiciones tautológicamente equivalentes y la bicondicional deellas (o equivalencia) se denomina equivalencia tautológica

A B ¬A ¬B ¬A ∨B ¬(¬A ∨B) A ∧ ¬B (¬(¬A ∨B)) ↔ (A ∧ ¬B)

T T F F T F F TT F F T F T T TF T T F T F F TF F T T T F F T



Condiciones lógicas en tablas de verdadConsistencia

Dos o más proposiciones son consistentes si al menos una asignación devalores de verdad hace que todas ellas sean verdaderas

Por ejemplo, si consideramos las siguientes cuatro proposiciones P , Q,(Q → ¬P ), y R y su correspondiente tabla de verdad

P Q (Q → ¬P ) R

T T F TT T F FT F T TT F T FF T T TF T T FF F T TF F T F

En ninguna interpretación se da que todas las proposiciones son verdaderas,por lo tanto el conjunto de proposiciones es inconsistente



Condiciones lógicas en tablas de verdadValidez

Un argumento es válido si en cada asignación donde las premisas sonverdaderas, la conclusión también lo es

Por ejemplo, si consideramos las siguientes dos premisas P ∧Q, R → ¬P y laconclusión ¬Q ↔ R y su correspondiente tabla de verdad

P Q R P ∧Q R → ¬P ¬Q ↔ R

T T T T F FT T F T T TT F T F F TT F F F T FF T T F T FF T F F T TF F T F T TF F F F T F

En la asignación donde las premisas son verdaderas la conclusión también loes, por lo tanto el argumento es válido





20 de mayo de 2019


1 Teoría de inferencia y demostración en lógica proposicional


Teoría de inferencia y demostración en lógica proposicional Reglas básicas de inferencia y demostración

1 Teoría de inferencia y demostración en lógica proposicionalReglas básicas de inferencia y demostraciónDeducción proposicionalReglas de inferencia adicionalesÁrboles de verdadConclusiones no válidasDemostración condicionalConsistenciaDemostración indirecta



Reglas básicas de inferencia y demostración

Inferencia y deducción son procesos muy importantes en la lógicaproposicional

Deducción. Inicia con un conjunto de fórmulas lógicas(proposiciones simbolizadas) que se denominan premisas y sebusca entonces usar reglas de inferencia para que estas premisasnos conduzcan a otras fórmulas denominadas conclusiones

La idea principal de la inferencia lógica es que de premisasverdaderas se obtienen sólo conclusiones que son verdaderas



Reglas básicas de inferencia y demostraciónModus ponendo ponens

La regla de inferencia llamada modus ponendo ponens (en latín: el modo que, alafirmar, afirma) permite demostrar Q A partir de P → Q y P

Ejemplo:

Premisa 1: Si él está en partido de fútbol, entonces él está en elestadioPremisa 2: Él está en el partido de fútbolConclusión: Él está en el estadio

Sea

P = “Él está en el partido de fútbol”Q = “Él está en el estadio”

Entonces

Premisa 1: P → Q (antecedente P , consecuente Q)Premisa 2: PConclusión: Q



Reglas básicas de inferencia y demostraciónModus ponendo ponens

Otros ejemplos:

a. R → SR

∴ S

b. PP → ¬Q

∴ ¬Q

c. P ∧Q → RP ∧Q

∴ R

Observe que en el ejemplo b. la condicional (P → ¬Q) está como segundapremisa y P es el antecedente

Cuando el modus ponendo ponens (o cualquier otra regla de inferencia) seaplica el orden de las premisas es indiferente



Reglas básicas de inferencia y demostraciónDemostraciones

Cuando se emplea una regla de inferencia para pasar de unconjunto de proposiciones a otra proposición (conclusión) sedemuestra que la última proposición es consecuencia lógica delas otras

También puede expresarse como que se ha derivado laconclusión de las premisas, o que la conclusión se infiere de (esimplicada por) las premisas



Reglas básicas de inferencia y demostraciónDemostraciones

Un ejemplo de demostración:

R → S P(1)R P(2)S PP(3)

Cada línea de la demostración está numerada

Las premisas están identificadas con P

La línea (3) se deduce a partir de ellas usando el modus ponendo ponens,indicado con PP



Reglas básicas de inferencia y demostraciónDemostraciones de dos pasos

Algunas veces no es posible ir directamente de las premisas a laconclusión en un solo paso

Cada vez que se deduce una proposición por medio de una regla,esta proposición puede utilizarse junto con las premisas paradeducir otra proposición




Ejemplo de demostración de dos pasos:

Se requiere probar la proposición C, para ello se requieren dos pasos, cada unousando el modus ponendo ponens

Estos dos pasos son las líneas (4) y (5) de la siguiente demostración

A → B P(1)B → C P(2)A P(3)B PP 1, 3(4)C PP 2, 4(5)




Un ejemplo más de demostración de dos pasos:

Se requiere probar la proposición R

S → ¬T P(1)S P(2)

¬T → R P(3)¬T PP 1, 2(4)R PP 3, 4(5)



Reglas básicas de inferencia y demostraciónRegla de la doble negación

Es una regla simple que permite pasar de una premisa única a laconclusión

Por ejemplo:No ocurre que Ana no es una estudiante

¿Qué conclusión podemos sacar de esta premisa?Ana es una estudiante

Esta regla también actúa e sentido contrario Por ejemplo, de laproposición:

Juan toma taxi para ir a la escuela

Se puede concluir la negación de su negación:No ocurre que Juan no toma taxi para ir a la escuela




La regla de la doble negación (abreviada DN) tiene dos formassimbólicas:

P∴ ¬¬P

¬¬P∴ P




Ejemplo 1:

R P(1)¬¬R DN 1(2)

Ejemplo 2:

¬¬(P ∧Q) P(1)P ∧Q DN 1(2)



Reglas básicas de inferencia y demostraciónModus tollendo tollens

La regla de inferencia llamada modus tollendo tollens (en latín: elmodo que, al negar, niega) permite pasar de dos premisas (a) unaproposición condicional, y (b) una proposición que niega elconsecuente, a una conclusión que niega el antecedente

Se abrevia TT y simbólicamente se representa así:

P → Q¬Q

∴ ¬P




Ejemplo:

Premisa 1: Si tiene luz propia, entonces el astro es una estrellaPremisa 2: El astro no es una estrellaConclusión: Por lo tanto no tiene luz propia

Sea

P = “Tiene luz propia”Q = “El astro es una estrella”

Entonces

Premisa 1: P → QPremisa 2: ¬QConclusión: ¬P




Ejemplo 1:

Q ∧R → S P(1)¬S P(2)

¬(Q ∧R) TT 1, 2(3)

Ejemplo 2:

P → ¬Q P(1)¬¬Q P(2)¬P TT 1, 2(3)




Veamos un ejemplo donde se empleen las tres reglas vistas hastaahora. Se quiere demostrar ¬¬R:

P → Q P(1)¬Q P(2)¬P → R P(3)¬P TT 1, 2(4)R PP 3, 4(5)

¬¬R DN 5(6)




Otro ejemplo adicional. Se quiere demostrar A:

¬A → ¬B P(1)B P(2)

¬¬B DN 2(3)¬¬A TT 1, 3(4)

A DN 4(5)



Reglas básicas de inferencia y demostraciónAdjunción y simplificación

Se tienen dos proposiciones como premisas:Jorge es adultoMaría es adolescente

Si ambas son verdaderas, entonces se podrían juntar en unaproposición molecular con el operador de enlace y (∧)

Esto daría lugar a la proposición verdadera siguiente:Jorge es adulto y María es adolescente

Si ambas premisas son ciertas, la conclusión será cierta

La regla que permite hacer esto se denomina regla de adjunción(abreviada A)




La regla de adjunción simbólicamente se representa así:

PQ

∴ P ∧Q o también Q ∧ P




Ejemplo 1:

Q ∧ S P(1)¬T P(2)¬T ∧ (Q ∧ S) A 1, 2(3)

Ejemplo 2:

A ∨B P(1)B ∨ C P(2)

(A ∨B) ∧ (B ∨ C) A 1, 2(3)




La regla de simplificación (abreviada S) permite pasar de unaconjunción a cada una de las dos proposiciones que están unidascon el operador de enlace y (∧)

Suponga que se tiene la premisa:El cumpleaños de María es el viernes y el mío es el sábado

De esta premisa se pueden deducir dos proposiciones(conclusiones):

El cumpleaños de María es el viernesEl mío es el sábado

Si la premisa es cierta, ambas conclusiones también lo serán




La regla de simplificación simbólicamente se representa así:

P ∧Q∴ P o también Q




Ejemplo 1:

(P ∨Q) ∧R P(1)R S 1(2)

Ejemplo 2:

Q ∧ S P(1)Q S 1(2)

Ejemplo 3:

(P ∨Q) ∧R P(1)P ∨Q S 1(2)




Ejemplo 4:

(P ∧Q) ∧R P(1)(P ∧Q) S 1(2)

Ejemplo 5:

T ∧ ¬V P(1)¬V S 1(2)



Reglas básicas de inferencia y demostraciónModus tollendo ponens

La regla de inferencia llamada modus tollendo ponens (en latín: elmodo que, al negar, afirma) establece que negando un miembrode una disyunción se afirma el otro miembro

Se abrevia TP y simbólicamente se representa así:

P ∨Q¬P

∴ Q

P ∨Q¬Q

∴ P




Ejemplo:

Premisa 1: Esta sustancia contiene hidrógeno o contiene oxígenoPremisa 2: Esta sustancia no contiene hidrógenoConclusión: Esta sustancia contiene oxígeno

Sea

P = “Esta sustancia contiene hidrógeno”Q = “Esta sustancia contiene oxígeno”

Entonces

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




Ejemplo 1:

(P ∧Q) ∨ S P(1)¬S P(2)P ∧Q TP 1, 2(3)

Ejemplo 2:

¬S ∨ T P(1)¬T P(2)¬S TP 1, 2(3)




Ejemplo 3:

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

Ejemplo 4:

(P ∧Q) ∨ (R ∧ S) P(1)¬(P ∧Q) P(2)

R ∧ S TP 1, 2(3)


Teoría de inferencia y demostración en lógica proposicional Deducción proposicional




Deducción proposicional

Hasta ahora hemos aprendido a efectuar deducciones simples

Consideremos ahora algunas un poco más avanzadas

Si la ballena es un mamífero entonces toma oxígeno del aire. Sitoma oxígeno del aire, entonces no necesita branquias. Laballena es un mamífero y vive en el océano. Por lo tanto, nonecesita branquias.

El primer paso es simbolizar el razonamiento anterior




Sea

W = “La ballena es un mamífero”

O = “Toma oxígeno del aire”

G = “Necesita branquias”

H = “Habita en el océano”

Entonces las premisas y la conclusión quedan de la siguiente forma:

Premisa 1: W → O

Premisa 2: O → ¬G

Premisa 3: W ∧H

Conclusión: ¬G




La deducción proposicional se puede escribir así:

W → O P(1)O → ¬G P(2)W ∧H P(3)W S 3(4)O PP 1, 4(5)

¬G PP 2, 5(6)

Así puesto que ¬G representa la proposición “No necesita branquias” se ha

demostrado que la conclusión del razonamiento es válida. Esto es un ejemplo dededucción formal.




Veamos otro ejemplo más

Si la enmienda no fue aprobada entonces la Constitución quedacomo estaba. Si la Constitución queda como estaba entonces nopodemos añadir nuevos miembros al comité. O podemos añadirnuevos miembros al comité o el informe se retrasará un mes. Peroel informe no se retrasará un mes. Por lo tanto la enmienda fueaprobada.

Simbolicemos este razonamiento



Deducción proposicionalSea

A = “La enmienda fue aprobada”

C = “La Constitución queda como estaba”

M = “Podemos añadir nuevos miembros al comité”

R = “El informe se retrasará un mes”

Entonces la deducción proposicional se puede escribir así:

¬A → C P(1)

C → ¬M P(2)

M ∨R P(3)

¬R P(4)

M TP 3, 4(5)

¬C TT 2, 5(6)

A TT 1, 6(7)


Teoría de inferencia y demostración en lógica proposicional Reglas de inferencia adicionales




Reglas de inferencia adicionales

Hasta ahora hemos visto sólo algunas reglas básicas deinferencia

Esto limita un poco las deducir que podemos realizar

Por esta razón a continuación estudiaremos reglas de inferenciaadicionales



Reglas de inferencia adicionalesLey de la adición

La ley de la adición (abreviada LA) expresa el hecho que si setiene una proposición cierta, entonces la disyunción de esaproposición y otra cualquiera será también cierta

Dado P , entonces la proposición P ∨Q es consecuencia

Ejemplo: suponga que la siguiente premisa es ciertaEste libro es azul

Entonces se sabe que la proposición siguiente ha de ser tambiéncierta

Este libro es azul o es nuevo




Ejemplo 1:

Q P(1)Q ∨ ¬R LA 1(2)

Ejemplo 2:

¬R P(1)S ∨ ¬R LA 1(2)




Ejemplo 3:

T ∧ S P(1)(T ∧ S) ∨R LA 1(2)

Ejemplo 4:

T ∨R P(1)(P ∧ S) ∨ (T ∨R) LA 1(2)



Reglas de inferencia adicionalesLey del silogismo hipotético

La ley del silogismo hipotético es una forma de argumento válidoque consiste en un silogismo con una sentencia condicional parauna o ambas de sus premisas

Se abrevia HS y se representa simbólicamente así:

P → QQ → R

∴ P → R

Recordemos: un silogismo es un tipo de argumento lógico que aplica razonamiento deductivo para llegar a una conclusión

basado en dos o más proposiciones que asume son verdaderas




Ejemplo: de las premisasPremisa 1: Si hace calor, entonces José va nadarPremisa 2: Si José va a nadar, entonces arregla la casa despuésde comer

Se puede obtener la conclusión: Si hace calor, entonces arregla la casadespués de comer

Para simbolizar el razonamiento, seaD = “Hace calor”S = “José va a nadar”H = “Arregla la casa después de comer”

Entonces

D → S P(1)

S → H P(2)

D → H HS 1, 2(3)




Ejemplo 1:

¬P → ¬Q P(1)¬Q → ¬R P(2)¬P → ¬R HS 1, 2(3)

Ejemplo 2:

¬P → ¬Q ∨R P(1)¬Q ∨R → ¬T P(2)

¬P → ¬T HS 1, 2(3)




Ejemplo 3:

S → T P(1)T → R ∨Q P(2)S → R ∨Q HS 1, 2(3)

Ejemplo 4:

(P → Q) → R P(1)R → (Q ∧ T ) P(2)

(P → Q) → (Q ∧ T ) HS 1, 2(3)



Reglas de inferencia adicionalesLey del silogismo disyuntivo

La ley del silogismo disyuntivo empieza con una disyunción y doscondicionales que tienen como antecedente a cada una de laspremisas de la disyunción. La conclusión es otra disyunción delos consecuentes de las condicionales.

Se abrevia DS y se representa simbólicamente así:

P ∨QP → RQ → S

∴ R ∨ S o también S ∨R




Ejemplo: de las premisas

Premisa 1: Llueve o el campo está secoPremisa 2: Si llueve, entonces jugaremos adentroPremisa 3: Si el campo está seco, entonces jugaremos baloncesto

Se puede obtener la conclusión: jugaremos adentro o jugaremos al baloncesto

Para simbolizar el razonamiento, sea

R = “Llueve”

D = “El campo está seco”

P = “Jugaremos adentro”

B = “Jugaremos al baloncesto”

Entonces

R ∨D P(1)

R → P P(2)

D → B P(3)

P ∨B DS 1, 2, 3(4)




Ejemplo 1:

¬P ∨Q P(1)¬P → ¬R P(2)Q → S P(3)

¬R ∨ S DS 1, 2, 3(4)

Ejemplo 2:

P ∨Q P(1)P → ¬R P(2)Q → ¬S P(3)

¬S ∨ ¬R DS 1, 2, 3(4)




Ejemplo 3:

¬P ∨ ¬Q P(1)¬P → R P(2)¬Q → S P(3)R ∨ S DS 1, 2, 3(4)

Ejemplo 4:

P ∨ ¬Q P(1)P → ¬R P(2)

¬Q → S P(3)¬R ∨ S DS 1, 2, 3(4)



Reglas de inferencia adicionalesLey de simplificación disyuntiva

La ley de simplificación disyuntiva (abreviada DP) se representasimbólicamente así:

P ∨ P∴ P

Ejemplo de la proposición:“El equipo de los Pumas ganará o el equipo de los Pumas ganará”

Se puede concluir que “El equipo de los Pumas ganará”

Simbólicamente:

P ∨ P P(1)P DP 1(2)



Reglas de inferencia adicionalesLey de simplificación disyuntiva

Ejemplo 1:

¬Q ∨ ¬Q P(1)¬Q DP 1(2)

Ejemplo 2:

(P ∧Q) ∨ (P ∧Q) P(1)P ∧Q DP 1(2)



Reglas de inferencia adicionalesLeyes conmutativas

Las leyes conmutativas (abreviadas CL) se aplican a conjuncionesy disyunciones. Expresan que el orden de las proposicionesatómicas no afectan el significado de la proposición molecular

Representadas en forma simbólica:

P ∧Q∴ Q ∧ P

P ∨Q∴ Q ∨ P




El razonamiento siguiente es un ejemplo del uso de las leyes conmutativas en laconjunción:

Galileo murió en 1642 y Newton nació en 1642Por lo tanto, Newton nació en 1642 y Galileo murió en 1642

Sea:

G = “Galileo murió en 1642”N = “Newton nació en 1642”

El razonamiento es:

G ∧N P(1)

N ∧G CL 1(2)




El razonamiento siguiente es un ejemplo del uso de las leyes conmutativas en laconjunción:

x es mayor que cinco o x es igual a cincoPor lo tanto, x es igual a cinco o x es mayor que cinco

Sea:

M = “x es mayor que cinco”I = “x es igual a cinco”

El razonamiento es:

M ∨ I P(1)

I ∨M CL 1(2)




Ejemplo 1:

P ∧ ¬Q P(1)¬Q ∧ P CL 1(2)

Ejemplo 2:

¬P ∨ ¬Q P(1)¬Q ∨ ¬P CL 1(2)

Ejemplo 3:

¬P ∧Q P(1)Q ∧ ¬P CL 1(2)



Reglas de inferencia adicionalesLeyes de De Morgan

Las leyes de De Morgan (abreviadas DL) son un par de reglas deinferencia que permiten la expresión de conjunciones ydisyunciones puramente en términos una de otra vía la negación


¬(P ∨Q)∴ ¬P ∧ ¬Q

¬(P ∧Q)∴ ¬P ∨ ¬Q

Se resumen en tres pasos:Cambiar ∧ por ∨ o ∨ por ∧Negar cada miembro de la conjunción o disyunciónNegar la fórmula completa

Augustus De Morgan (1806-1871) matemático y lógico británico




Ejemplo 1:

¬(P ∧ ¬Q) P(1)¬P ∨ ¬¬Q DL 1(2)

Ejemplo 2:

¬(¬P ∧ ¬Q) P(1)¬¬P ∨ ¬¬Q DL 1(2)

Ejemplo 3:

¬¬P ∨ ¬Q P(1)¬(¬P ∧Q) DL 1(2)




Ejemplo 4:

¬(P ∨ ¬Q) P(1)¬P ∧ ¬¬Q DL 1(2)

Ejemplo 5:

¬¬P ∧ ¬Q P(1)¬(¬P ∨Q) DL 1(2)



Reglas de inferencia adicionalesLey de las proposiciones bicondicionales

La ley de las proposiciones bicondicionales (abreviadas LB)permite deducir de una bicondicional dos proposicionescondicionales


P ↔ Q∴ P → Q

P ↔ Q∴ Q → P

P ↔ Q∴ (P → Q) ∧ (Q → P )

P → QQ → P

∴ P ↔ Q

Se adoptará la convención de que la bicondicional tieneprecedencia que cada uno de los otros términos de enlace


Teoría de inferencia y demostración en lógica proposicional Árboles de verdad




Árboles de verdad

Independientemente de la longitud de una proposición molecular,es posible encontrar sus valores de verdad si se conocen losvalores de verdad de sus partes

Una forma de analizar el valor de verdad de una proposiciónmolecular es estableciendo un árbol de verdad (también llamadosdiagramas de certeza)



Árboles de verdad

Veamos un ejemplo con la proposición (P ∨Q) ∧R donde P esuna proposición cierta, Q es falsa y R es una proposición cierta

(P ∨Q) ∧R

T F T

T

T



Árboles de verdad

Consideremos ahora otro ejemplo con la proposición(P ∧Q → P ) ∧ (R ∨ S) donde P es cierta, Q es cierta, R es falsay S es falsa

(P ∧Q → P ) ∧ (R ∨ S)

T T T

T

T

F F

F

F


Teoría de inferencia y demostración en lógica proposicional Conclusiones no válidas




Conclusiones no válidas

Hasta ahora en todo los ejemplos que hemos realizado se pedíadeducir a partir de premisas dadas una conclusión que eraefectivamente válida

En lógica a veces se requiere también probar que una conclusiónno es consecuencia lógica de las premisas dadas

O que un razonamiento particular es no válido

Una conclusión es una consecuencia lógica de las premisas cuando toda interpretación que hace verdaderas a las premisastambién hace verdadera a la conclusión

Un razonamiento es válido sólo si la conclusión es una consecuencia lógica de las premisas




Veamos a través de un ejemplo un método para probar que unrazonamiento particular es no válido

Suponga el siguiente razonamiento:Si usted es un habitante de Cd. Victoria, entonces usted es unhabitante de MéxicoUsted es un habitante de MéxicoPor lo tanto, usted es un habitante de Cd. Victoria

Sea:V = “Usted es un habitante de Cd. Victoria”M = “Usted es un habitante de México”

Simbolizando:

V → MM

∴ V

La forma del razonamiento nos permite deduciruna conclusión falsa de premisas verdaderas (Vfalsa, M verdadera)

Se demuestra entonces que el razonamientoes no válido




El método (denominado de asignación de certeza) para demostrarque una inferencia es no válida se puede resumir en dos pasos:

1 Simbolizar las premisas y conclusiones2 Encontrar una asignación de valores de verdad para las

proposiciones atómicas tales que todas las premisas sean ciertas yla conclusión sea falsa

V → M

F T T

T

Premisas

M

Conclusion

F

V




Un ejemplo un poco más largo

P ∧Q → (P → R) ∨ S

T T

T

Premisas

P ∧ ¬RConclusion

¬P ∨ ¬QT T

F F

F

T F

F

T

T

T

T FF

T

T

El razonamiento es no válido por que la conclusión no es unaconsecuencia lógica de las premisas


Teoría de inferencia y demostración en lógica proposicional Demostración condicional




Demostración condicional

Una demostración condicional (abreviada CP) permite usar partede la conclusión como una premisa que se puede usar paraprobar el resto de la conclusión

Para demostrar la validez de un argumento cuya conclusión tienela forma X → y (i.e., cualquier declaración condicional) se puedenseguir los siguientes pasos:

1 Separe el antecedente X de la condicional2 Agregue ese antecedente X a la lista de premisas (como una

premisa supuesta AP)3 Se prueba el consecuente y como si fuera la conclusión

Veamos un ejemplo a continuación




Dadas las premisas P → Q, R → ¬Q; deseamos probar la conclusión R → ¬P

P → Q P(1)

R → ¬Q P(2)

R AP(3)

¬Q PP 2, 3(4)

¬P TT 1, 4(5)

R → ¬P CP 3, 5(6)

En (3) se introduce el antecedente de la condicional (se recorre a la derecha -no es premisa original)

En (5) se deduce el consecuente de la condicional

La línea (6) se recorre a la izquierda por que es conclusión de las premisasoriginales




Ejemplo 2. Dadas las premisas A → (B → C), ¬D ∨A, B; deseamos probar laconclusión D → C

A → (B → C) P(1)

¬D ∨A P(2)

B P(3)

D AP(4)

A TP 2, 4(5)

B → C PP 1, 5(6)

C PP 3, 6(7)

D → C CP 4, 7(8)

La parte de la demostración que se ha corrido a la derecha se denominademostración subordinada


Teoría de inferencia y demostración en lógica proposicional Consistencia




Consistencia

Como hemos visto ya, una contradicción (representada ⊥) es unaproposición que siempre es falsa, independientemente de losvalores de verdad de sus constantes

Un ejemplo de contradicción es la proposición P ∧ ¬P

Cada dos o más proposiciones que lógicamente no pueden serciertas a la vez se dice que son inconsistentes



Consistencia

En ocasiones no se requiere deducir una conclusión particular,sino deducir si un conjunto de proposiciones es consistente oinconsistente

Para demostrar que un conjunto de premisas son inconsistentesse deduce una contradicción (i.e., las premisas no pueden sertodas ciertas a la vez)

Veamos un ejemplo



Consistencia

Dadas las premisas D → J , D, ¬J ; deseamos probar que soninconsistentes

D → J P(1)D P(2)¬J P(3)J PP 1, 2(4)J ∧ ¬J A 3, 4(5)


Teoría de inferencia y demostración en lógica proposicional Demostración indirecta




Demostración indirecta

Una demostración indirecta1 (abreviada RAA) permite demostrarla negación del antecedente de una condicional cuando se sabeque el consecuente es falso (i.e., es una contradicción)

Representados en forma simbólica:P → (Q ∧ ¬Q)

∴ ¬P

1También puede denominarse demostración por contradicción o demostración por reducción al absurdo.




Para ello se seguen los siguientes pasos:1 Introducir la negación de la conclusión deseada como una nueva

premisa2 Con la premisa nueva y las premisas dadas se deduce una

contradicción3 Se establece la conclusión deseada como una inferencia lógica

deducida de las premisas originales

Veamos un ejemplo a continuación




Dadas las premisas (1)-(3), se desea llegar a la conclusión ¬D

D → W P(1)

A ∨ ¬W P(2)

¬(D ∧A) P(3)

D P(4)

W PP 1, 4(5)

A TP 2, 5(6)

¬D ∨ ¬A DL 3(7)

¬A TP 4, 7(8)

A ∧ ¬A A 6, 8(9)

¬D RAA 4, 9(10)

Introducir la negación de la conclusión deseada como una nueva premisa, línea (4)

Con la premisa nueva y las premisas dadas se deduce una contradicción, líneas (5) a (9)

Se establece la conclusión deseada como una inferencia lógica deducida de las premisas originales, línea (10)





21 de mayo de 2019


1 Lógica de predicados


Lógica de predicados Términos y predicados

1 Lógica de predicadosTérminos y predicadosFórmulas atómicas y variablesCuantificadores universalesDos formas típicas de proposiciones con cuantificadores universalesCuantificadores existenciales



Términos y predicados

En lógica de predicados un término es una expresión con la quese nombra o se designa un único objeto

Ejemplos:María está ausenteJuan va despacioEste libro es azulDos es mejor que tres

Un término no necesariamente es un nombre, puede ser unafrase, por ejemplo “el presidente de México”




Algunos términos son nombres y algunos son descripciones quese refieren a un individuo u objeto

Ejemplos:Brasil es el mayor productor de café del mundoEste libro es demasiado pesado1 + 1 = 2

En estas proposiciones los nombres son: Brasil, 1, y 2

Las descripciones son las frases: “el mayor productor de café delmundo”, “este libro”, y “1 + 1”




En la proposición “Sócrates es un sabio” sabemos que “Socrates”es un término

La frase “es un sabio” es un predicado

En proposiciones atómicas generalmente el sujeto de laproposición es un término y el predicado es el resto de laproposición que dice algo sobre ese sujeto

Ejemplos:Juan es nadadorSusana está tristeJosé corre deprisa




En la lógica de predicados también es posible simbolizar lasproposiciones

Veamos un ejemplo. Sea F el predicado “canta” y m = María

Entonces se puede simbolizar la proposición “María canta” comoF (m)

Otro ejemplo. En la proposición “José corre deprisa”, sea R elpredicado “corre deprisa” y b = José

Entonces la proposición se puede simbolizar como R(b)




Algunas veces debemos tener cuidado en distinguir los términosde los predicados

Considere por ejemplo, la proposición “Sócrates es un hombre”

Es obvio que “Sócrates” es un término, se puede pensar que“hombre” también lo es

Pero al ser un nombre común no identifica una persona o cosaparticular, por lo tanto no es un término




Ejemplos de proposiciones que usan nombres comunes dentro desus predicados:

Chicago es una ciudadEinstein fue un científico brillanteMarte es un planeta




Los nombres comunes también pueden usarse para construirtérminos

Ejemplosel edificio en la esquina de Avenida Juárez y Avenida Paseo de laReformaen aquel tallerel hombre que robó el banco


Lógica de predicados Fórmulas atómicas y variables




Fórmulas atómicas y variables

En lógica de predicados la expresión más corta que tiene sentidopor sí sola es una letra predicativa a la que está unida un término

Por ejemplo, L(j) que representa la proposición atómica “Jaimeestudia lógica”

El término “Jaime” y el predicado “estudia lógica” por sí solos nodicen nada

Tampoco j y L




Consideremos la expresión “x es un número par” que se puedesimbolizar como P (x)

Ni una ni otra dicen nada sobre algo particular y no puedenevaluarse porque x no es ningún objeto particular

Sin embargo, pueden ser consideradas independientemente oformando parte de expresiones más largas

Y se les conoce como fórmulas atómicas




Si en la expresión “x es un número par” se sustituye x por 4 setendrá la proposición atómica cierta “4 es un número par” que sesimboliza como P (4)

Si se sustituye x por 5 se obtiene una proposición falsa

Cuando las letras (como x) se usan como términos, sin querepresenten objetos particulares, se denominan variables

Las variables se consideran también términos a pesar de nonombrar ni referirse a ningún objeto único




Por lo tanto una definición más completa de término es lasiguiente:

Un término es una expresión con la que o se designa un únicoobjeto, o es una variable que puede ser sustituida por unaexpresión que nombre un objeto único




El conocimiento de las variables y fórmulas atómicas permite daruna forma clara de traducción del lenguaje corriente alsimbolismo de la lógica de predicados

Por ejemplo, consideremos la proposición Benito Juárez nombróministro de justicia a Manuel Ruíz

A(x, y)↔ x nombró a yj = Benito Juárezr = Manuel Ruíz

En símbolos A(j, r)




Llamamos proposiciones atómicas a las fórmulas atómicas cuyostérminos no utilizan variables

Las proposiciones atómicas con términos de enlace formaproposiciones moleculares

En lógica de predicados las expresiones que contienen términosde enlace se denominan fórmulas moleculares, tanto si contienenvariables como si no




Ejemplo 1: Si Miguel Ángel fue un artista del Renacimiento,entonces Leonardo da Vinci fue un artista del Renacimiento

R(x)↔ x fue un artista del Renacimientom = Miguel Ángell = Leonardo da Vinci

En símbolos R(m)→ R(l)




Ejemplo 2: Beto ayuda a Juan y es ayudado por PedroH(x, y)↔ x ayuda a yb = Betoj = Juanp = Pedro

En símbolos H(b, j) ∧H(p, b)




Ejemplo 3: Si x es mayor que dos y dos es mayor que z, entoncesx es mayor que z

Esto se puede simbolizar usando símbolos matemáticos y lógicos,por lo que podemos escribir la siguiente fórmula molecular

x > 2 ∧ 2 > z → x > z


Lógica de predicados Cuantificadores universales




Cuantificadores universales

Ya hemos visto que al sustituir las variables por términos en lasfórmulas atómicas, se obtienen proposiciones atómicas quepueden evaluarse (T o F)

Por ejemplo, consideremos la fórmula atómica “x es alto”

Si se sustituye x por “Michael Jordan”, entonces obtenemos laproposición verdadera siguiente

“Michael Jordan es alto“




Otro camino para transformar fórmulas atómicas en proposicionesverdaderas o falsas es usando un cuantificador universal paracada variable

Ejemplo: la fórmula atómica “x > 0” puede transformarse en unaproposición que podamos evaluar al expresarla de la siguienteforma

“Para cada x, x > 0” (“Para todo x, x > 0”)

El cuantificador se denomina universal porque utiliza la variable xpara afirmar que cada cosa en el universo tiene una ciertapropiedad (es mayor que cero)

La última proposición se simboliza por: (∀x)(x > 0)




El cuantificador universal también es expresado comúnmente enlenguaje corriente con las siguientes expresiones

Para cada xCada unoPara todo xCualquiera




Con frecuencia nos interesan no todas las cosas en el universo,sino un conjunto definido de cosas (e.g., el conjunto de números)

El conjunto de cosas que se consideran en una discusión sedenomina dominio de referencia

Así en algunos ejemplos se restringe el dominio a un conjuntoparticular y entonces el cuantificador universal se refiere a cadaelemento de ese conjunto




Ciertas expresiones de cuantificación universal se utilizan paraexpresar simultáneamente una negación

Considere el ejemplo: “Ninguno quiere setas venenosas”,simbolizado por (∀x)(x no quiere setas venenosas)

Observe que “Ninguno” expresa una cuantificación universal en laproposición original y se representa con la frase “Todo x”

El sentido negativo de “Ninguno” se expresa ahora con la palabra“no”

Para simbolizar completamente se define:L(x)↔ x quiere setas venenosas, y obtenemos

(∀x)(¬L(x))




El cuantificador universal negado también es expresadocomúnmente en lenguaje corriente con las siguientes expresiones

Para ningún xNingunoNadieNadaNo




Es necesario diferenciar los casos en que una negación sigue alcuantificador, de los casos en que la negación precede alcuantificador

Consideremos la siguiente proposición: “No todas las cosas sonbonitas”

Ésta es simplemente la negación de: “Todas las cosas sonbonitas”

Definiendo B(x)↔ x son bonitas, segunda proposición sesimboliza: (∀x)(B(x))

Y la primera es la negación de ésta: ¬(∀x)(B(x))


Lógica de predicados Dos formas típicas ...




Dos formas típicas de proposiciones concuantificadores universales

Consideremos la proposición “Para cada x, si x es un hombre, xes un animal”

Definiendo, M(x)↔ x es un hombre, A(x)↔ x es un animal, laproposición anterior se puede simbolizar por:

(∀x)(M(x)→ A(x))

Esta última es un ejemplo típico de proposición de la forma “Cadatal-y-tal es esto-y-esto”




Revisemos ahora el caso donde se tiene a la vez cuantificaciónuniversal y negación

Por ejemplo: “Ningún hombre es inmortal” que también puedeexpresarse como “Para todo x, si x es un hombre, entonces x esno inmortal”

Definiendo, M(x)↔ x es un hombre, I(x)↔ x es inmortal,podemos simbolizar así:

(∀x)(M(x)→ ¬I(x))

Esta última es un ejemplo típico de proposición de la forma“Ningunos tales-y-tales son estos-y-estos”




En algunos casos se niega una proposición completa

Por ejemplo: “No toda mujer tiene el pelo largo”

Definiendo, W (x)↔ x es una mujer, L(x)↔ x tiene el pelo largo,podemos simbolizar la proposición previa así:

¬(∀x)(W (x)→ ¬L(x))




Existen múltiples formas de expresar en castellano una mismaidea

A menudo es necesario cambiar la forma de expresar esa ideapara que se pueda reconocer una estructura lógica clara

Si se llega a una forma condicional “si ... entonces” la estructurageneralmente es más clara




Consideremos la fórmula (∀x)(T (x)→ ¬P (x))

Definiendo: T (x)↔ x es un árbol, P (x)↔ x es una planta

Cada una de las siguientes son formas distintas de expresar laproposición lógica anterior

Todo árbol es una plantaLas cosas que son árboles son también plantasSólo plantas son árbolesNada es un árbol si no es una plantaSi algo es un árbol entonces es una planta


Lógica de predicados Cuantificadores existenciales




Cuantificadores existenciales

En lógica de predicados se emplea el símbolo ∃, llamadocuantificador existencial, antepuesto a una variable para indicarque “existe” al menos un elemento del conjunto, al que hacereferencia la variable, que cumple la proposición escrita acontinuación

Por ejemplo, considere la proposición “Para algún numero naturaln, n ∗ n = 25”

Definiendo: P (a, b, c)↔ a ∗ b = c, y con N representando elconjunto de los números naturales, podemos simbolizar laproposición previa así:

∃n ∈ NP (n, n, 25)

La proposición es verdadera




Un ejemplo más, considere la proposición “Para algún numeronatural n, n es par y n ∗ n = 25”

Definiendo: P (x, y, z)↔ x ∗ y = z, Q(x)↔ x es par, y con Nrepresentando el conjunto de los números naturales, podemossimbolizar la proposición previa así:

∃n ∈ N(Q(n) ∧ P (n, n, 25)

)La proposición es falsa




Las proposiciones que utilizan cuantificadores existencialestambién pueden ser negadas

Por ejemplo, si definimosP (x)↔ x es mayor que cero y menor que uno, y empleamos Npara representar el conjunto de los números naturales

La proposición “Existe al menos un número natural x el cual esmayor que cero y menor que uno” se puede simbolizar como

∃x ∈ NP (x)

Esta proposición es falsa y su negación puede ser simbolizadapor

¬∃x ∈ NP (x)




Si no existe un elemento del conjunto N para el cual la proposiciónsea verdadera, entonces debe ser falsa para todos los elementos

Por lo que la negación de ¬∃x ∈ NP (x) es lógicamenteequivalente a la proposición

“Para todo número natural x, x no es mayor que cero y menor queuno”

(∀x)(¬P (x))

De manera análoga las siguientes proposiciones son lógicamenteequivalentes

(∀x)(P (x)) ≡ ¬∃x ∈ N¬P (x)

Si para todo x se cumple P (x) no existe un x que no cumpla P (x)





21 de mayo de 2019


1 Especificación universal y leyes de identidad


Especificación universal y leyes de identidad Un cuantificador

1 Especificación universal y leyes de identidadUn cuantificadorDos o más cuantificadoresLógica de la identidadCerteza lógica



Un cuantificador

Acabamos de agregar la notación de los cuantificadoresuniversales al conjunto de instrumentos lógicos que hemosestudiado

Veremos ahora una regla de supresión de estos cuantificadoresuniversales

Esta regla nos permite analizar y utilizar la estructura detallada delas proposiciones en el razonamiento



Un cuantificador

Consideremos la siguiente inferencia válida:Cada ciudadano de Tamaulipas es un ciudadano de México.El gobernador Cabeza de Vaca es un ciudadano de Tamaulipas.Por tanto, el gobernador Cabeza de Vaca es un ciudadano deMéxico.

Definiendo: T (x)↔ x es un ciudadano de Tamaulipas,M(x)↔ x es un ciudadano de México, yc = gobernador Cabeza de Vaca

Se puede simbolizar las premisas y la conclusión delrazonamiento por: Demostrar M(c)

(∀x)(T (x)→M(x))(1)

T (c)(2)



Un cuantificador

Esa simbolización es el primer paso en la estrategia de lademostración

El segundo es precisar algún objeto particular para sustituirlo envez de la variable x (especificación)

Después de eliminar el cuantificador, se pueden aplicarsimplemente los métodos de deducción que hemos visto



Un cuantificador

Siguiendo los tres pasos en el ejemplo anterior, se obtiene ladeducción:

(∀x)(T (x)→M(x)) P(1)

T (c) P(2)

T (c)→M(c) Especificar c para x(3)

M(c) PP 2, 3(4)

La regla que permite especificar se denomina especificaciónuniversal



Un cuantificador

Como segundo ejemplo consideremos el siguiente razonamiento:Cada número positivo es mayor que cero.1 es un número positivo.3 es un número positivo.Por tanto, 1 y 3 son mayores que 0.

Definiendo: P (x)↔ x es un número positivo, se puede simbolizarel razonamiento por: Demostrar 1 > 0 ∧ 3 > 0

(∀x)(P (x)→ x > 0)(1)

P (1)(2)

P (3)(3)



Un cuantificador

(∀x)(P (x)→ x > 0) P(1)

P (1) P(2)

P (3) P(3)

P (1)→ 1 > 0 1/x 1(4)

1 > 0 PP 2, 4(5)

P (3)→ 3 > 0 3/x 1(6)

3 > 0 PP 3, 6(7)

1 > 0 ∧ 3 > 0 A 5, 7(8)

Se ha indicado en (4) y (6) la especificación por “1/x” y “3/x”seguidas del número de línea a la que se aplicó la especificaciónuniversal



Un cuantificador

No estamos limitados a usar en una sola premisa de unademostración un cuantificador universal El siguiente ejemploilustra este punto.

Para cada x, si x es un número par, entonces x+ 2 es par.Para cada x, si x es un número par, entonces x no es un númeroimpar.Dos es un número par.Por tanto, 2 + 2 no es un número impar.



Un cuantificador

Definiendo: E(x)↔ x es un número par, yO(x)↔ x es un número impar, se simboliza el razonamiento y seescribe la deducción:

(∀x)(E(x)→ E(x+ 2)) P(1)

(∀x)(O(x)→ ¬O(x)) P(2)

E(2) P(3)

E(2)→ E(2 + 2) 2/x 1(4)

E(2 + 2) PP 3, 4(5)

E(2 + 2)→ ¬O(2 + 2) > 0 2 + 2/x 2(6)

¬O(2 + 2) PP 5, 6(7)



Un cuantificador

En las distintas premisas que utilizan cuantificadores no se estáobligado a usar siempre la misma variable

El siguiente ejemplo ilustra este punto, definiendo:E(x)↔ x es un número par, O(x)↔ x es un número impar, yP (x)↔ x es un número positivo. Demostrar E(4)

(∀x)(x > 0→ E(x) ∨O(x)) P(1)

(∀x)(P (x)→ x > 0) P(2)

P (4) P(3)

¬O(4) P(4)

La segunda premisa también puede escribirse así:(∀y)(P (y)→ y > 0)



Un cuantificador

Simbolizando la segunda premisa con y la deducción es:

(∀x)(x > 0→ E(x) ∨O(x)) P(1)

(∀x)(P (y)→ y > 0) P(2)

P (4) P(3)

¬O(4) P(4)

P (4)→ 4 > 0 4/y 2(5)

4 > 0 PP 3, 5(6)

4 > 0→ E(4) ∨O(4) 4/x 1(7)

E(4) ∨O(4) PP 6, 7(8)

E(4) TP 4, 8(9)


Especificación universal y leyes de identidad Dos o más cuantificadores




Dos o más cuantificadores

Usando sólo un cuantificador universal con cada proposición noes posible expresar razonamientos más elaborados (relacionesentre dos objetos o más)

Afortunadamente, es muy sencillo extender lo que hemos hecho,incluyendo proposiciones que contengan más de un cuantificadoruniversal

Siempre que estos se encuentren al inicio de la proposición




Por ejemplo, consideremos el siguiente razonamiento:Para cada x e y, si x es mayor que y, entonces no ocurre que y seamayor que x.Dos es mayor que uno.Por tanto, no ocurre que uno sea mayor que dos.

Demostrar: ¬(1 > 2)

(∀x)(∀y)(x > y → ¬(y > x)) P(1)

2 > 1 P(2)

2 > 1→ ¬(1 > 2) 2/x, 1/y 1(3)

¬(1 > 2) PP 2, 3(4)




Hay muchas relaciones no matemáticas, por ejemplo laproposición “Isabel II es la madre del príncipe Carlos”

Este tipo de relaciones son predicados dobles

Definiendo: M(x, y)↔ x es la madre de y, e = Isabel II, yc = príncipe Carlos

La proposición se puede simbolizar por

M(e, c)




Veamos un ejemplo con cuantificadores: “Cada hombre es másviejo que cada muchacho”

Definiendo: M(x)↔ x es un hombre, B(x)↔ x es un muchacho,O(x, y)↔ x es más viejo que y,

Entonces la proposición se simboliza

(∀x)(∀y)(M(x) ∧B(y)→ O(x, y))




Debemos aclarar que no estamos limitados a usar sólo doscuantificadores

Es posible introducir tantos como sea necesario para simbolizarde manera adecuada las proposiciones enunciadas en lenguajecorriente

Veamos un ejemplo donde se introducen tres cuantificadores paralas variable x, y, y z para simbolizar la primera premisa




El razonamiento es el siguiente:Para cada x, y, y z, si x es mayor que y e y es mayor que z,entonces x es mayor que z.Dos es mayor que uno.Tres es mayor que dos.Por tanto, tres es mayor que uno.

El razonamiento completo se simboliza: Demostrar 3 > 1

(∀x)(∀y)(∀z)(x > y ∧ y > z → x > z) P(1)

2 > 1 P(2)

3 > 2 P(3)

3 > 2 ∧ 2 > 1→ 3 > 1 3/x, 2/y, 1/z 1(4)

3 > 2 ∧ 2 > 1 A 2, 31(5)

3 > 1 PP 4, 5(6)


Especificación universal y leyes de identidad Lógica de la identidad




Lógica de la identidad

En castellano se usa con frecuencia alguna forma del verbo “ser”(e.g., es, era, son, eran, etc) entre dos términos para indicar quenombran o se refieren a la misma cosa

Por ejemplo: “Isabel II es la reina de Inglaterra”, esto significa“Isabel II” nombra o indica la misma cosa que “la reina deInglaterra”, o“Isabel II” es lo mismo que “la reina de Inglaterra”, o“Isabel II” es idéntica a “la reina de Inglaterra”

Definiendo: e = Isabel II y q = la reina de Inglaterra, se puedesimbolizar como: e = q

El signo = se denomina signo de identidad




Sin embargo, es necesario tener precaución puesto que el verbo“ser” se utiliza también en otro sentido

Por ejemplo, consideremos las siguientes proposiciones“Isabel II es una mujer”“Las mujeres son personas”

Sería incorrecto enunciarlas en la forma:“Isabel II” nombra la misma cosas que “una mujer”“Las mujeres” son idénticas a “personas”

El signo de identidad (=) no se coloca entre dos cosas, sino entredos símbolos de expresiones, cuando esas expresiones serefieren a una misma cosa




Ejemplo 1: “El 4 de julio es el Día de la Independencia”Definiendo: j = El 4 de julio e i = Día de la Independencia

Se puede simbolizar como: j = i

Ejemplo 2: “Sir Francis Drake era un corsario”Definiendo: P (x)↔ x es un corsario

Se puede simbolizar como: P (d)

Ejemplo 3: “Los gatos son felinos”Definiendo: C(x)↔ x es un gato, F (x)↔ x es un felino

Se puede simbolizar como: (∀x)(C(x)→ F (x)




Ejemplo 4: “Un quinto es el veinte por ciento”Se puede simbolizar como: 1

5 = 20%

Ejemplo 5: “Benjamín Franklin fue un impresor”Definiendo: f = Benjamín Franklin, P (x)↔ x es un impresor

Se puede simbolizar como: P (f)




La identidad juega un papel importante en Lógica matemática

Consideremos el siguiente ejemplo:

2 > 1 P(1)

2 = 1 + 1 P(2)

1 + 1 > 1 I 1, 2(3)

La línea (3) se obtiene de la línea (1) sustituyendo “2” por “1 + 1”

Esto por la regla de identidades que indica en línea (2) que “2” y“1 + 1” nombran la misma cosa




Veamos un ejemplo que contiene el uso de variables

Demostrar 2 > 0

(∀x)(∀y)(x > y → x+ 1 > y) P(1)

1 > 0 P(2)

2 = 1 + 1 P(3)

1 > 0→ 1 + 1 > 0 1/x, 0/y, 1(4)

1 + 1 > 0 PP 2, 4(5)

2 > 0 I 3, 5(6)


Especificación universal y leyes de identidad Certeza lógica




Certeza lógica

Una certeza lógica es una fórmula que es verdaderaindependientemente del valor de verdad al que evalúa cadapremisa particular

Las tautologías son ejemplos de certezas lógicas, otros ejemplosson afirmaciones de la forma siguiente:

1 = 1x = xLincoln = Lincoln3 + 4 = 3 + 4

La regla de certezas lógicas (abreviada L) permite hacer uso decertezas lógicas en las demostraciones formales, y puede serintroducida en cualquier momento de una deducción



Certeza lógica

Ejemplo 1, demostrar 2 + 1 = (1 + 1) + 1, dada la premisa2 = 1 + 1

2 + 1 = (1 + 1) + 1 P(1)

2 + 1 = 2 + 1 L(2)

2 + 1 = (1 + 1) + 1 I 2, 1(3)

La línea (2) es una certeza lógica que se ha construidoseleccionando el primer miembro de la conclusión deseada yestableciendo que es igual a sí mismo

Observe también como se ha utilizado la regla de identidades



Certeza lógica

Ejemplo 2, demostrar 3 + 1 = (2 + 1) + 1, dada la premisa3 = 2 + 1

3 = 2 + 1 P(1)

3 + 1 = 3 + 1 L(2)

3 + 1 = (2 + 1) + 1 I 2, 1(3)



Certeza lógica

Ejemplo 3, demostrar (2 ∗ 3) ∗ 5 = 30, dadas las premisas 2 ∗ 3 = 6y 6 ∗ 5 = 30

2 ∗ 3 = 6 P(1)

6 ∗ 5 = 30 P(2)

(2 ∗ 3) ∗ 5 = (2 ∗ 3) ∗ 5 L(3)

(2 ∗ 3) ∗ 5 = 6 ∗ 5 I 3, 1(4)

(2 ∗ 3) ∗ 5 = 30 I 4, 2(5)


lógica computacional dr. eduardo a. rodrÍguez tello · panorama general de la lógica conceptos...

Documents