Introducción Lógica Matemática

  • Upload
    viktor

  • View
    7

  • Download
    0

Embed Size (px)

DESCRIPTION

Lógica Matemática

Citation preview

Lgica Matemtica.Mtro. Vctor Ortega Armenta.Introduccin a la Lgica Matemtica.La Lgica es el estudio del razonamiento, especficamente estudia mtodos que separan los razonamientos vlidos de los no vlidos. La lgica es la herramienta para el anlisis de las demostraciones y se centra en la relacin entre afirmaciones.El filsofo griego Aristteles (384 - 322a.C.) fue el primero en realizar un estudio sistemtico del razonamiento lgico. En sus grandes tratados de lgica, escribi un conjunto de reglas para el razonamiento deductivo destinadas a servir de base para el estudio de todas las ramas del conocimiento. No fue sino hasta el siglo XVII en que el filsofo y matemtico alemn Gottfried Wilhelm Leibniz (1646-1716) concibi la idea de desarrollar un lenguaje simblico que pudiera ser utilizado como un lenguaje cientfico universal para mecanizar el proceso de razonamiento de los nmeros y sus relaciones.El matemtico ingls George Boole (1815-1864) y Augustus DeMorgan (1806-1871) establecieron las bases de la Lgica Simblica. En 1847 DeMorgan public su tratado Formal Logic; or the calculus of Inference, necessary and probable, y en 1854 George Boole public su obra An investigation into the laws of thought. Por otra parte David Hilbert (1862-1943) es considerado como el fundador de la teora moderna de la demostracin, formul la teora de los espacios de Hilbert y unific el campo de la teora de nmeros algebraicos en su tratado Zahlbericht de 1897. Posteriormente, Bertrand Russell (1872-1970) y Alfred North Whitehead (1861 - 1947) utilizaron la lgica simblica en su monumental obra Principia Mathematica (1910-1913) cuyo objetivo general era deducir la totalidad de las matemticas a partir de nociones bsicas de lgica y teora de conjuntos. En 1930 Kurt Gdel (1906-1978) demostr sus dos teoremas de incompletitud cuya consecuencia inmediata del segundo fue la demostracin de la imposibilidad del programa de Hilbert y asimismo se demostr que era imposible el objetivo de Russell y Whitehead de deducir la totalidad de las matemticas a partir de nociones bsicas de lgica y teora de conjuntos. George Peacock (17911858) fue un matemtico ingls cuya mayor contribucin al anlisis matemtico fue el intento de fundamentar el lgebra con bases estrictamente lgicas. Giuseppe Peano (18581932) fue un matemtico, lgico y filsofo italiano, conocido por sus contribuciones a la lgica matemtica y la teora de nmeros. Ernst Schrder (18411902) fue un matemtico alemn, conocido especialmente por sus trabajos sobre lgica algebraica. Friedrich Ludwig Gottlob Frege (1848-1925) fue un matemtico, lgico y filsofo alemn, considerado como el padrede la lgica matemtica moderna y la filosofa analtica. In 1879 Frege public Begriffsschrift (Conceptscript), en el cual, por primera vez, fue presentado un sistema de lgica matemtica en el sentido moderno. Frege decubri las ideas fundamentales que hicieron posible el desarrollo completo de la lgica moderna, y por lo tanto invent una disciplina completa, por ello es reconocido como el mayor lgico desde Aristteles. Alfred Tarski (1902-1983) es considerado uno de los grandes lgicos a travs de los tiempos. En 1941 public Introduction to Logic and Methodology of deductive Sciences fundando una metodologa de las teoras deductivas sobre dos bases: la nocin de teora como conjunto de proposiciones cerrado bajo una nocin de derivacin mediante aplicacin de reglas y el desarrollo de una semntica basada en las nociones de satisfaccin, verdad y consecuencia lgica.El rea de la lgica que trata de proposiciones se llama clculo proposicional o lgica proposicional. Fue desarrollada sistemticamente por el filsofo griego Aristteles hace ms de dos mil trescientos aos.Una proposicin es un enunciado u oracin declarativa (afirmativa o negativa) que puede ser verdadera o falsa, pero no ambas a la vez. Si la proposicin es verdadera se dice que su valor de verdad es verdadero (V), y si la proposicin es falsa su valor de verdad es falso (F).Para denotar proposiciones (en Lgica) usamos letras, al igual que las usamos al denotar variables (en matemticas). Por convenio, las letras que se utilizan al denotar variables son p, q, r, s,Una proposicin compuesta, tambin llamada forma de enunciado forma proposicional es una expresin formada por dos o ms proposiciones o enunciados (tales como p, q y r) que contienen al menos un operador o conector lgico (por ejemplo (, ^ y ) y se convierten en un enunciado cuando los enunciados reales se sustituyen por enunciados compuestos variables. Una proposicin que consta de una nica variable o constante proposicional se denomina proposicin atmica.Se dice que dos proposiciones compuestas (o formas de enunciado) son lgicamente equivalentes si y slo si, tienen los mismos valores de verdad para todos sus enunciados finales. La equivalencia lgica de las formas de enunciado P y Q se denota como P Q.Un argumento es una secuencia de enunciados. Todos los enunciados de un argumento, a excepcin del final, se llaman premisas, suposiciones o hiptesis. El enunciado final se llama conclusin. El smbolo, que se lee por lo tanto, normalmente se coloca justo antes de la conclusin. Un argumento slido, se llama as, si y slo si es vlido y todas sus premisas son verdaderas. Decir que un argumento es vlido significa que su forma es vlida, lo verdadero de su conclusin se deduce necesariamente por la forma lgica de lo verdadero de sus premisas. Un argumento es vlido si p1^ p2 ^^ pn q es una tautologa. Los argumentos vlidos tambin son llamados reglas de inferencia. Un argumento lgico es una secuencia de proposiciones escritas como p1p2 :pnq Las proposiciones p1, p2, , pn son llamadas hiptesis o premisas y la proposicin q es la conclusin. Una falacia es un error en el razonamiento que da lugar a un argumento no vlido. Tres falacias comunes son usar premisas ambiguas y tratarlas como si fueran no ambiguas, razonamiento circular (suponiendo que se ha demostrado sin tener que deducirlo de las premisas) y saltar a una conclusin sin bases adecuadas. Otras dos falacias son el error converso y error contrario, que dan lugar a argumentos que superficialmente se parecen a los que son vlidos por modus ponens y modus tollens, pero en realidad no lo son. Se usa un contraejemplo para demostrar que una afirmacin es falsa, o que una negacin es verdadera.Un predicado es una frase que contiene un nmero finito de variables y se convierte en un enunciado cuando se sustituyen valores especficos en lugar de las variables. El dominio de una variable de predicado es el conjunto de todos los valores que se pueden sustituir en lugar de la variable. Sea P(x) una oracin que incluye la variable x y sea D un conjunto. P se llama funcin proposicional o predicado (respecto a D) si para cada x en D, P(x) es una proposicin. D es el dominio del discurso o dominio de referencia de P.Tautologa. Una proposicin compuesta es una tautologa si siempre es verdadera para todos sus valores de verdad de sus enunciados finales.Contradiccin. Una proposicin compuesta es una contradiccin si siempre es falsa para todos sus valores de verdad de sus enunciados finales.Contingencia. Una proposicin compuesta que no es ni una tautologa ni una contradiccin se denomina contingencia.Las reglas de la lgica le dan significado preciso a los enunciados o sentencias matemticas. Los mtodos lgicos se utilizan en matemticas para demostrar teoremas, en ciencias de la computacin para el diseo de circuitos lgicos digitales, construccin y verificacin de programas, bases de datos relacionales, teora de autmatas e inteligencia artificial; en escritura comn para aclarar las oraciones.

Tablas de Verdad.Las tablas de verdad muestran los valores de verdad de enunciados o proposiciones compuestas. Las tablas de verdad fueron desarrolladas por Friederich Ludwig Gottlob Frege (1848-1925), Charles Sanders Peirce (1839-1914) y Schrder en la dcada de 1880 y desde 1920 fueron usadas ampliamente en la literatura, su uso se consolid a partir de la aplicacin que hizo Ludwig Wittgenstein (1889-1951) de stas en su obra Tractatus Lgico-philosophicus, de 1922.

VerdaderoFalso

TrueFalse

EncendidoApagado

AbiertoCerrado

PositivoNegativo

AltoBajo

OnOff

SNo

+-

10

Negacin (Not).Sea p una proposicin. La negacin de p, se denota mediante p, p o p y se lee no p es la proposicin inversa a la proposicin p. A continuacin se muestra su tabla de verdad:pp

10

01

Conjuncin (And)Tambin llamada multiplicacin lgica. Sean p y q proposiciones. La conjuncin de p y q, que se denota por pq y se lee p y q es la proposicin que es verdadera cuando tanto p como q son verdaderas y falsa en cualquier otro caso. A continuacin se muestra su tabla de verdad:pqp q

111

100

010

000

Disyuncin (Or)Tambin llamada suma lgica. Sean p y q proposiciones. La disyuncin de p y q, que se denota por p q y se lee p o q es la proposicin que es falsa cuando tanto p como q son falsas y verdadera en cualquier otro caso. A continuacin se muestra su tabla de verdad:pqp q

111

101

011

000

Disyuncin exclusiva (exclusive or)Sean p y q proposiciones. La disyuncin exclusiva de p y q, que se denota por p q es la proposicin que verdadera cuando exactamente una de las proposiciones p y q es verdadera y falsa en cualquier otro caso. A continuacin se muestra su tabla de verdad:pqp q

110

101

011

000

Condicional (implicacin)Sean p y q proposiciones. La implicacin de p q, que se denota por p q y se lee si p, entonces q es la proposicin que es falsa cuando p es verdadera y q es falsa y verdadera en cualquier otro caso. A continuacin se muestra su tabla de verdad:pqp q

111

100

011

001

Bicondicional (doble implicacin)Sean p y q proposiciones. La bicondicional o doble implicacin de p q, que se denota por p q y se lee p, si y slo si, q es la proposicin que es verdadera cuando p y q tienen los mismos valores de verdad y falsa en cualquier otro caso. A continuacin se muestra su tabla de verdad:pqp q

111

100

010

001

Jerarqua o precedencia de operadores lgicos. La secuencia que se debe seguir en las expresiones que incluyen alguno o todos los operadores lgicos, es la siguiente: (), , , , y .

La lgica es una ciencia de las leyes necesarias del pensamiento, sin la cual no se comprende ni se razona. Immanuel Kant, 1785

Las bases estructurales de las matemticas son la definicin, el teorema y la demostracin. Las definiciones especifican con precisin los conceptos que nos interesan, se usan para crear nuevos conceptos en trminos de los existentes. Los teoremas dicen exactamente lo que hay de verdadero en esos conceptos. Las demostraciones descubren, en forma irrefutable, la verdad de esas afirmaciones. Un sistema matemtico consiste en axiomas, definiciones y trminos no definidos. Se supone que los axiomas son verdaderos, aunque algunos trminos no estn definidos de forma explcita por los axiomas.Un teorema es una proposicin que se ha probado que es verdadera. Algunos tipos de teoremas reciben el nombre de lemas y corolarios.Un lema es un teorema que no suele ser muy interesante por s mismo, pero que resulta til para probar otro teorema.Un Corolario es un teorema que puede probarse fcilmente o se deriva a partir de otro teorema.La teora de la demostracin es una rama de la lgica matemtica que considera a las demostraciones como objetos matemticos. Desde esta perspectiva las demostraciones suelen presentarse como estructuras de datos inductivamente definidas que se construyen de acuerdo con los axiomas y reglas de inferencia de los sistemas lgicos.Una demostracin o prueba es un argumento que establece la verdad de un teorema. Es una sucesin de afirmaciones que representan una argumentacin de la validez de un enunciado matemtico. Existen varios mtodos de demostracin, los cuales se describen a continuacin:Una demostracin directa de un enunciado de la forma si P entonces Q, comienza suponiendo que P es verdadera y de ah concluye que Q es verdadera.Una demostracin indirecta (por contraposicin) de un enunciado de la forma si P entonces Q comienza suponiendo que la negacin de Q es verdadera y de ah concluye que la negacin de P es verdadera, si no Q entonces no P.Una demostracin por contradiccin (reduccin al absurdo) de la veracidad de un enunciado de la forma si P entonces Q, comienza suponiendo que Q es falsa y de esta suposicin concluye una contradiccin.El razonamiento deductivo es el proceso de obtener conclusiones mediante una secuencia de proposiciones. Una conclusin es la proposicin que se deriva de la hiptesis.

Bibliografa.Epp. S. Susanna. Matemticas Discretas con Aplicaciones. Cengage Learning, Mxico: 2012.Espinosa Armenta, R. Matemticas Discretas. Alfaomega, Mxico: 2010. Grassmann, W. K., Tremblay, J.P. Matemtica Discreta y Lgica. Prentice Hall, Madrid: 1998.H. Rosen, Kenneth. Matemtica Discreta y sus Aplicaciones(5 ed). McGraw Hill, Mxico: 2004.Johnsonbaugh, Richard. Matemticas Discretas(6 ed). Pearson Educacin, Mxico: 2005. Lipschutz, S., Lipson, M. Matemticas Discretas (Serie Schaum). McGrawHill, Mxico: 2009.7