Unidad 2.- Lógica y tablas de verdad

Lógica Algebra Booleana Las álgebras booleanas, estudiadas por primera vez en detalle por George Boole, constituyen un área de las matemáticas que ha pasado a ocupar un lugar prominente con el advenimiento de la computadora digital. Son usadas ampliamente en el diseño de circuitos de distribución y computadoras, y sus aplicaciones van en aumento en muchas otras áreas. En el nivel de lógica digital de una computadora, lo que comúnmente se llama hardware, y que está formado por los componentes electrónicos de la máquina, se trabaja con diferencias de tensión, las cuales generan funciones que son calculadas por los circuitos que forman el nivel. Estas funciones, en la etapa de diseño del hardware, son interpretadas como funciones de boole. Haciendo una correlación con las fórmulas proposicionales. Asimismo, se plantean dos formas canónicas de las funciones booleanas, que son útiles para varios propósitos, tales como el de determinar si dos expresiones representan o no la misma función. Pero para otros propósitos son a menudo engorrosas, por tener más operaciones que las necesarias. Particularmente, cuando estamos construyendo los circuitos electrónicos con que implementar funciones booleanas, el problema de determinar una expresión mínima para una función es a menudo crucial. No resultan de la misma eficiencia en dinero y tiempo, principalmente, dos funciones las cuales calculan lo mismo pero donde una tiene menos variables y lo hace en menor tiempo. Como solución a este problema, se plantea un método de simplificación, que hace uso de unos diagramas especiales llamados mapas o diagramas de Karnaugh, y el cual tiene la limitación de poder trabajar adecuadamente sólo con pocas variables. Se realizan estas presentaciones con el fin de demostrar la afinidad existente entre el álgebra de boole y la lógica proposicional, y con el objeto de cimentar el procedimiento de simplificación presentado en la lógica de proposiciones. RESEÑA HISTÓRICA A mediados del siglo XIX, George Boole (1815-1864), en sus libros: "The Mathematical Analysis of Logic" (1847) y "An Investigation of te Laws of Thought" (1854), desarrolló la idea de que las proposiciones lógicas podían ser tratadas mediante herramientas matemáticas. Las proposiciones lógicas (asertos, frases o predicados de la lógica clásica) son aquellas que únicamente pueden tomar valores Verdadero/Falso, o preguntas cuyas únicas respuestas posibles sean Sí/No. Según Boole, estas proposiciones pueden ser representadas mediante símbolos y la teoría que permite trabajar con estos símbolos, sus entradas (variables) y sus salidas (respuestas) es la Lógica Simbólica desarrollada por él. Dicha lógica simbólica cuenta con operaciones lógicas que siguen el comportamiento de reglas algebraicas. Por ello, al conjunto de reglas de la Lógica Simbólica se le denomina ÁLGEBRA DE BOOLE. A mediados del siglo XX el álgebra Booleana resultó de una gran importancia práctica, importancia que se ha ido incrementando hasta nuestros días, en el manejo de información digital (por eso hablamos de Lógica Digital). Gracias a ella, Shannon (1930) pudo formular su teoría de la codificación y John Von Neumann pudo enunciar el modelo de arquitectura que define la estructura interna de los computadoras desde la primera generación. Todas las variables y constantes del Álgebra booleana, admiten sólo uno de dos valores en sus entradas y salidas: Sí/No, 0/1 o Verdadero/Falso. Estos valores bivalentes y opuestos pueden

Ing. Miguel Ángel Durán Jacobo

1

Unidad 2.- Lógica y tablas de verdad

ser representados por números binarios de un dígito (bits), por lo cual el Álgebra booleana se puede entender cómo el Álgebra del Sistema Binario. Al igual que en álgebra tradicional, también se trabaja con letras del alfabeto para denominar variables y formar ecuaciones para obtener el resultado de ciertas operaciones mediante una ecuación o expresión booleana. Evidentemente los resultados de las correspondientes operaciones también serán binarios. Todas las operaciones (representadas por símbolos determinados) pueden ser materializadas mediante elementos físicos de diferentes tipos (mecánicos, eléctricos, neumáticos o electrónicos) que admiten entradas binarias o lógicas y que devuelven una respuesta (salida) también binaria o lógica. Ejemplos de dichos estados son: Abierto/Cerrado (interruptor), Encendida/Apagada (bombilla), Cargado/Descargado (condensador), Nivel Lógico 0/Nivel lógico 1 (salida lógica de un circuito semiconductor), etcétera. Los dispositivos con los cuales se implementan las funciones lógicas son llamados puertas (o compuertas) y, habitualmente, son dispositivos electrónicos basados en transistores. Estos dispositivos, y otros que veremos a lo largo de esta unidad, son los que permiten el diseño, y la ulterior implementación, de los circuitos de cualquier computadora moderna, así como de muchos de los elementos físicos que permiten la existencia de las telecomunicaciones modernas, el control de máquinas, etcétera. De hecho, pensando en las computadoras como una jerarquía de niveles, la base o nivel inferior sería ocupada por la lógica digital (en el nivel más alto de la computadora encontraríamos los actuales lenguajes de programación de alto nivel). En esta unidad se representan las puertas lógicas elementales, algunas puertas complejas y algunos ejemplos de circuitos digitales simples, así como algunas cuestiones de notación. Por otra parte se plantean actividades de trabajo, muchas de las cuales implican una respuesta escrita en su cuaderno de trabajo. Trataremos de que resulte sencillo y ameno adentrarnos en el mundo de la lógica digital y despertar la curiosidad, tanto por ella, como por la matemática que subyace en ella. INTRODUCCIÓN Lógica es la disciplina que trata de los métodos de razonamiento. En un nivel elemental, la lógica proporciona reglas y técnicas para determinar si es o no válido un argumento dado. La lógica es el estudio del razonamiento; en particular, se analiza si un razonamiento es correcto. La lógica se centra en las relaciones entre los enunciados y no en el contenido de un enunciado particular. Por ejemplo, considérese el siguiente argumento: • Todos los matemáticos utilizan sandalias. • Cualquier persona que utilice sandalias es algebrista. • Por tanto, Todos los matemáticos son algebristas. Desde el punto de vista técnico, la lógica no permite determinar si estos enunciados son verdaderos; sin embargo, si los dos primeros enunciados fuesen verdaderos, la lógica garantizará que el enunciado. Todos los matemáticos son algebristas, también es verdadero.

Ing. Miguel Ángel Durán Jacobo

2

Unidad 2.- Lógica y tablas de verdad

Los métodos lógicos se utilizan en matemáticas para demostrar teoremas, y en computación para demostrar que los programas hacen precisamente lo que deberían de hacer. Proposiciones Una proposición es todo enunciado que expresa algo sobre lo que se pueda decir si es verdadero o falso, pero no ambas cosas. ¿Cuál de los siguientes enunciados es verdadero falso (pero no ambos)? a) Los únicos enteros positivos que dividen a 7 son 1 y el propio 7. b) Alfred Hitchcock ganó un Premio de la Academia en 1940 por dirigir Rebecca. c) Para todo entero positivo n, existe un número primo mayor que n. d) La tierra es el único planeta en el universo que tiene vida. e) Compre dos boletos para el concierto de rock de Unicar para el viernes. La afirmación (a) es verdadera. Un entero n es primo si n > 1 y los únicos enteros positivos que dividen a n son 1 y el propio n. La afirmación (a) es otra forma de decir que 7 es un número primo. La afirmación (b) es falsa. Aunque Rebecca ganó el Premio de la Academia como mejor película en 1940, John Ford ganó el premio al mejor director por The Grapes of Wrath. Es sorprendente, pero Alfred Hitchcock nunca ganó un Premio de la Academia como director. La afirmación (c) es verdadera; es otra forma de decir que existe una infinidad de números primos. La afirmación (d) puede ser falsa o verdadera (pero no ambas), pero nadie podría decidir esto en este momento. La afirmación (e) no es verdadera ni falsa (en realidad es una orden). Una afirmación que es verdadera o falsa, pero no ambas, es una proposición. Las afirmaciones (a) – (d) son proposiciones, mientras que la afirmación (e) no lo es. En general una proposición se expresa como una afirmación declarativa (y no como una pregunta, una instrucción, etc.). las proposiciones son los bloques de construcción básicos para cualquier teoría de la lógica. Un computador puede ser programado para tomar decisiones basadas en si ciertos enunciados –por ejemplo, “el número que se ha computado es mayor de 100”– son verdaderos o falsos. A la verdad o falsedad de un enunciado se le llama valor de verdad; un enunciado es verdadero o falso, pero no ambas cosas. Algunos enunciados son proposiciones compuestas, es decir, están integrados por subenunciados y varias conectivas.

Ing. Miguel Ángel Durán Jacobo

3

Unidad 2.- Lógica y tablas de verdad

Ejemplo: (a) “Las rosas son rojas y las violetas azules” es un enunciado compuesto por los subenunciados “las rosas son rojas” y “las violetas son azules”. (b) “Él es inteligente o estudia todas las noches” es, implícitamente, un enunciado compuesto por los subenunciados “Él es inteligente” y “estudia todas las noches”. (c) “¿Para dónde va?” no es un enunciado ya que no es ni verdadero ni falso. La propiedad fundamental de un enunciado compuesto es que su valor de verdad está completamente determinado por los valores de verdad de sus subenunciados junto con la manera como están conectados para formar el enunciado compuesto. Conectivos lógicos y proposiciones compuestas En matemáticas las letras x, y, z, . . . denotan, a menudo, variables que pueden ser remplazadas por números reales, y estas variables pueden combinarse con las operaciones comunes +, X, -, y ÷. En lógica, las letras p, q, r,… denotan variables propositivas, es decir, variables que pueden ser remplazadas por proposiciones. Así se puede escribir p: El sol está brillando hoy. q: Hace frío. Entonces, para denotar enunciados utilizaremos las letras p, q, r (en minúsculas o mayúsculas, con o sin subíndices). Las proposiciones o variables pueden combinarse por medio de conectivos lógicos para obtener proposiciones compuestas. Por ejemplo, se pueden combinar las proposiciones anteriores con el conectivo y para formar la proposición compuesta p y q: El sol está brillando y hace frío. El valor de verdad de una proposición compuesta depende solamente de los valores de verdad de las proposiciones que se estén combinando y de los tipos de conectivos que se utilice. A los estados de verdadero o falso que pueden tener una proposición se les llama valor de verdad o valor lógico de esa proposición. Se pueden considerar dos tipos de proposiciones: • Proposiciones simples. Son aquellas que no pueden reducirse a otras más sencillas. Es decir, no tienen conectivos, por ejemplo: “Pedro es alto”. •

Proposiciones compuestas. Son aquellas que pueden reducirse a otras más sencillas. Se reconocen porque usan conectivos lógicos. Cuando nos refiramos a proposiciones compuestas usaremos las letras mayúsculas: P, Q,… Un ejemplo sería: “Pedro es alto y el 7 es par”.

Ing. Miguel Ángel Durán Jacobo

4

Unidad 2.- Lógica y tablas de verdad

A continuación se verán los conectivos lógicos más importantes. Conectivo

Símbolo

Nombre

no

∼p (no p)

negación

^

y

∨

o o … o …, pero no ambos

∨ →

si …, entonces …

↔

… si y sólo si …

conjunción disyunción inclusiva disyunción exclusiva condicional bicondicional

Los valores de verdad de proposiciones, como las conjunciones y disyunciones, pueden describirse mediante tablas de verdad. Una tabla de verdad de una proposición P formada por las proposiciones p1, …, pn enumera todas las condiciones posibles de los valores de verdad para p1, …, pn, donde V indica verdadero y F falso, de modo que para cada una de estas combinaciones se indica el valor de verdad de P. Negación La negación de una proposición p es otra proposición que afirma lo que se niega en la primera y viceversa. Se representa por ∼p y se lee “no p” Si p es una proposición, la negación de p es la proposición no p, denotada por ∼p. Así ∼p es la proposición “no es el caso de p”. De esta definición se desprende que si p es verdadera, entonces ∼p es falsa, y si p es falsa, ∼p es verdadera. El valor de verdad de ∼p relativo a p se da en la siguiente tabla: p V F

∼p F V

A una tabla como esta, que da valores de verdad de una proposición compuesta en función de sus partes componentes, se le llama tabla de verdad. Estrictamente hablando, no no es un conectivo, en vista de que no une dos proposiciones, y ∼p no es en realidad una proposición compuesta. Sin embargo, no es una operación unitaria para la colección de proposiciones, y ∼p es una proposición si p lo es. Ejemplo: Dé la negación de las siguientes proposiciones. (a) p: 2 + 3 > 1

(b) q: Hace frío.

Ing. Miguel Ángel Durán Jacobo

5

Unidad 2.- Lógica y tablas de verdad

Solución: (a) ∼p: 2 + 3 no es mayor que 1. Es decir, ∼p: 2 + 3 ≤ 1. Como p es verdadera en este caso, ∼p es falsa. (b) ∼q: No es el caso de que haga frío. Más simplemente, ∼q: No hace frío. Conjunción, p ^ q Dos enunciados cualesquiera se pueden combinar con la palabra “y” para formar un enunciado compuesto llamado la conjunción de los enunciados originales. Simbólicamente, p ^ q denota la conjunción de los enunciados p y q, que se lee “p y q”. La tabla de verdad del enunciado compuesto p ^ q está dada por la siguiente tabla: p V V F F

q V F V F

p^q V F F F

Observemos que en la tabla de verdad aparecen las cuatro combinaciones posibles de las asignaciones de verdad para p y q. En este caso, la primera línea es una manera abreviada de decir que si p es verdadero y q es verdadero, entonces p ^ q es verdadero. Las otras líneas tienen significados análogos. Consideramos que esta tabla define precisamente el valor de verdad del enunciado compuesto p ^ q como una función de los valores de verdad de p y q. Observe que p ^ q es verdadero solamente en el caso en que ambos subenunciados sean verdaderos. Ejemplo: Considere los cuatro enunciados siguientes: (i) París está en Francia y 2 + 2 = 4. (iii) París está en Inglaterra y 2 + 2 = 4. (ii) París está en Francia y 2 + 2 = 5. (iv) París está en Inglaterra y 2 + 2 = 5. Solamente el primer enunciado es verdadero. Cada uno de los otros enunciados son falsos ya por lo menos uno de sus subenunciados es falso. La conjunción de dos proposiciones es una proposición compuesta que resulta verdadera cuando lo son las dos proposiciones simples que la constituyen, y falsa en caso contrario, es decir, cuando alguna de las dos es falsa. Disyunción inclusiva, p ∨ q Dos enunciados cualesquiera se pueden combinar con la palabra “o” (en el sentido “y/o”) para formar un nuevo enunciado que se llama la disyunción de los enunciados originales. Simbólicamente, p ˇ q denota la conjunción de los enunciados p o q, que se lee “p o q”.

Ing. Miguel Ángel Durán Jacobo

6

Unidad 2.- Lógica y tablas de verdad

La tabla de verdad del enunciado compuesto p ˇ q está dada por la siguiente tabla: p V V F F

q V F V F

p∨q V V V F

Observemos que en la tabla de verdad aparecen las cuatro combinaciones posibles de las asignaciones de verdad para p o q. La tabla de verdad igualmente nos indica que p ∨ q es falso cuando ambos enunciados son falsos. Ejemplo: Considere los cuatro enunciados siguientes: (i) París está en Francia y 2 + 2 = 4. (ii) París está en Francia y 2 + 2 = 5. (iii) París está en Inglaterra y 2 + 2 = 4. (iv) París está en Inglaterra y 2 + 2 = 5. Solamente el enunciado (iv) es falso. Cada uno de los otros enunciados son verdaderos ya por lo menos uno de sus subenunciados es verdadero. A no ser que se diga otra cosa, la “o” se usará en el sentido de “y/o”. Esta observación hace sobresalir la precisión que ganamos con nuestro lenguaje simbólico: p ∨ q está definido por su tabla de verdad y siempre significa “p y/o q”. La disyunción inclusiva de dos proposiciones es una proposición compuesta que resulta verdadera cuando lo es al menos una de las dos proposiciones que la constituyen, y falsa en caso contrario, es decir, cuando las dos son falsas. Por ejemplo: “estudiamos informática o vamos al cine”. Nótese que aunque nos hemos referido para el caso de dos proposiciones, se puede extender el criterio al caso de más de dos proposiciones. Disyunción exclusiva, p ∨ q La palabra “o” se usa comúnmente de dos maneras. Algunas veces se usa en el sentido de “p o q o ambos”, mejor dicho, por lo menos una de las dos alternativas ocurre, como antes se señaló, y algunas veces se usa en el sentido de “p o q pero no ambos”, mejor dicho, exactamente una de las dos alternativas ocurre. Por ejemplo, la frase “El estudiará en la Universidad Nacional o en el Politécnico” usa el “o” en el segundo sentido llamado disyunción exclusiva.

Ing. Miguel Ángel Durán Jacobo

7

Unidad 2.- Lógica y tablas de verdad

Con frecuencia se habla de “p o q” en el sentido exclusivo, es decir, que sólo se puede cumplir una de las proposiciones integrantes, pero no ambas a la vez. Esta es la característica de la llamada disyunción exclusiva. La disyunción exclusiva de dos proposiciones es una proposición compuesta que resulta verdadera cuando lo es una y sólo una de las dos proposiciones que la constituyen, y es falsa en caso contrario. Se representa por p ∨ q y se lee “p o-exclusiva q”, o bien, “p o q, pero no ambas” La tabla de verdad del enunciado compuesto p ˇ q está dada por la siguiente tabla: p V V F F

q V F V F

p ∨ q F V V F

Por ejemplo: “o vamos en autobús o vamos en taxi”. Obsérvese que el primer “o” únicamente sirve para reforzar el sentido exclusivo, pero no es necesario. También en este caso, aunque lo hemos definido para dos proposiciones, se generalizaría de igual modo para cualquier número de proposiciones. Condicional Se representa por (p → q) y se lee “si p, entonces q”. A la proposición p se le llama antecedente, y a q, consecuente. La definiremos como: p → q = ∼p ∨ q, es decir: La condicional de dos proposiciones es una proposición compuesta que resulta falsa cuando el antecedente es verdadero y el consecuente falso, y en los demás casos es verdadera. Tabla de verdad: p V V F F

q V F V F

p→q V F V V

∼p

∼p ∨ q

F F V V

V F V V

Como se ve, la propia tabla justifica la definición. Por ejemplo: “Si hace buen tiempo, entonces iremos al campo”.

Ing. Miguel Ángel Durán Jacobo

8

Unidad 2.- Lógica y tablas de verdad

Bicondicional Se representa por (p ↔ q) y se lee “p si y sólo si q”. La proposición bicondicional de dos proposiciones p y q es equivalente a la proposición compuesta: (p → q) ^ (q →p) La bicondicional de dos proposiciones es una proposición compuesta que resulta verdadera cuando ambas son verdaderas o ambas son falsas, y en caso contrario es falsa. Tabla de verdad: p V V F F

q V F V F

p↔q V F F V

Por ejemplo: “Un triángulo es equilátero si y sólo si tiene los tres lados iguales”. Ejercicio de aplicación 1 Determine si cada una de las afirmaciones de los ejercicios 1-8 es una proposición. Si la afirmación es una proposición, escriba su negación. (No se le piden los valores de verdad de las afirmaciones que son proposiciones). 1. 2 + 5 = 19 ← 2. Mesero, ¿puede traer las nueces? Es decir, ¿puede servir las nueces a los invitados? 3. Para algún entero positivo n, 19340 = n •17. 4. Autrey Meadow fue la “Alicia” original en “The Honeymooners”. ← 5. Pélame una uva. 6. La frase “Hazlo de nuevo, Sam” aparece en la película Casablanca. 7. Todo entero mayor que 4 es la suma de dos números primos. ← 8. La diferencia de dos primos. Ejercicio de aplicación 2 Construir la tabla de verdad de (p → ∼q) ∨ r. El número de casos o filas que tiene la tabla de verdad de una proposición compuesta es siempre 2n, siendo n el número de proposiciones simples de que consta. Por ejemplo, si intervienen tres proposiciones habrá: 23 = 8 casos.

Ing. Miguel Ángel Durán Jacobo

9

Unidad 2.- Lógica y tablas de verdad

Para colocar ordenadamente todos los casos, la tabla se puede formar de la siguiente manera: • En la primera proposición de la tabla, ponemos la mitad de todos los casos posibles con V y la otra mitad con F. En nuestro ejemplo, 4 V y 4 F. • En la segunda proposición ponemos alternativamente V y F, en grupos mitad de la longitud de los grupos anteriores. En nuestro ejemplo 2V, 2 F, 2 V, 2 F. • Y así sucesivamente, con las restantes columnas de la tabla. Para formar la tabla de verdad de (p → ∼q) ∨ r, la descompondremos en otras más simples, así: p V V V V F F F F

q V V F F V V F F

r V F V F V F V F

∼q F F V V F F V V

p → ∼q F F V V V V V V

(p → ∼q) ∨ r V F V V V V V V

Ejercicio de aplicación 3 Evalúe cada proposición en los ejercicios 1 – 6 con los valores de verdad. p = F, 1. p ∨ q

q = V,

r= F.

Verdadero

2. ∼p ∨ ∼q 3. ∼p ∨ q 4. ∼p ∨ ∼ (q ^ r)

Verdadero

5. ∼(p ∨ q) ^ (∼p ∨ r) 6. (p ∨ ∼r) ^ ∼ ((q ∨ r) ∨ ∼ (r ∨ p))

Ing. Miguel Ángel Durán Jacobo

10

Unidad 2.- Lógica y tablas de verdad

Tautologías y contradicciones Se definen los siguientes tipos de proposiciones según los valores de su tabla de verdad: •

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

•

Una proposición es una contradicción cuando todos los valores de su tabla de verdad son falsos. Por tanto, es falsa, independientemente de los valores de verdad o falsedad de las proposiciones simples que la constituyen.

•

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

Ejemplo: averiguar si la siguiente proposición es tautología, contradicción o indeterminada. q ^ ∼ (q ∨ r) q V V F F

r V F V F

q∨r V V V F

∼ (q ∨ r) F F F V

q ^ ∼ (q ∨ r) F F F F

Dicha proposición resulta ser una contradicción ya que su valor lógico es falso en todos los casos posibles. IMPLICACIÓN Y EQUIVALENCIAS LÓGICAS Implicación lógica Cuando una condicional es una tautología, es decir, cuando nunca es falsa, se dice que es una implicación lógica. O dicho de otra forma: una proposición compuesta P implica a otra Q (P → Q), cuando si P es verdadero, entonces, Q es verdadero. El símbolo → se lee “implica”. También (P → Q) se lee “P es condición suficiente para Q”, o “Q es condición necesaria para P”.

Ing. Miguel Ángel Durán Jacobo

11

Unidad 2.- Lógica y tablas de verdad

Ejemplo: p → (p ∨ q) es una tautología, como lo demuestra su tabla de verdad. q V F V F

p V V F F

p∨q V V V F

p → (p ∨ q) V V V V

Y entonces podemos escribir p → (p ∨ q), puesto que es también una implicación lógica. Obsérvese que p es verdadera en las dos primeras líneas, y para estos casos (p ∨ q) es igualmente verdadera. EQUIVALENCIA LÓGICA Cuando una bicondicional es una tautología, se dice que es una equivalencia lógica. O dicho de otra forma: una proposición P es equivalente a otra Q (P ↔ Q), cuando las tablas de verdad en P y Q son iguales. El símbolo ↔ se lee “equivalencia lógica”. También (P ↔ Q) se lee “P es condición necesaria y suficiente para Q”. La equivalencia significa (P ↔ Q) lo mismo que: P → Q ^ Q → P Ejemplo: (p → ∼ q) ↔ (q → ∼ p) es una tautología, como lo demuestra su tabla de verdad. p V V F F

q V F V F

∼q F V F V

p→∼q F V V V

∼p F F V V

Q→∼p F V V V

(p → ∼ q) ↔ (q → ∼ p) V V V V

Y entonces podemos escribir (p → ∼ q) ↔ (q → ∼ p), puesto que se trata de una equivalencia lógica entre proposiciones. Propiedades de las proposiciones El conjunto de las proposiciones lógicas, con los conectivos definidos entre ellas como operaciones, cumple una serie de propiedades que nos permitirán dotarles de una cierta estructura. Estas propiedades se presentan en la tabla a continuación, donde T simboliza Tautología y C simboliza Contradicción.

Ing. Miguel Ángel Durán Jacobo

12

Unidad 2.- Lógica y tablas de verdad

Leyes del álgebra de proposiciones Disyunción

Conjunción

p∨p≡p

Idempotencia

p^p≡p

p∨q≡q∨p

Conmutativa

p^q≡q^p

p ∨ (q ∨ r) ≡ (p ∨ q ) ∨ r

Asociativa

p ^ (q ^ r) ≡ (p ^ q ) ^ r

p ∨ (p ^ q) ≡ p p ∨ (q ^ r) ≡ (p ∨ q) ^ (p ∨ r) Disyunción respecto a la conjunción

Absorción

p ^ (p ∨ q) ≡ p

Distributiva

p ^ (q ∨ r) ≡ (p ^ q) ∨ (p ^ r) Conjunción respecto a la disyunción

Negación

p^∼p≡t

p∨∼p≡t p∨c≡p c es elemento neutro de la ∨ p∨t≡t

∼c≡t ∼∼p ≡ p ∼ (p ∨ q) ≡∼ p ^ ∼q

Identidad Identidad de t y c

p^t≡p t es elemento neutro de la ^ p^c≡c

Negación de c y t Involución (doble negación) Leyes de DeMorgan

∼t≡c

∼ (p ^ q) ≡∼ p ∨ ∼q

Obsérvese que la disyunción y la conjunción de proposiciones se comportan como operaciones duales. Por cumplir las propiedades anteriores, el conjunto de las proposiciones lógicas con los conectivos negación, disyunción y conjunción, tiene una estructura de Álgebra de Boole. RAZONAMIENTOS Un razonamiento es el proceso consistente en partir de una serie de hipótesis llamadas premisas, que se suponen verdaderas, y obtener finalmente una proposición denominada conclusión. Cuando el razonamiento se compone de tres proposiciones, que pueden llamarse premisa mayor, premisa menor y conclusión, y ésta se deduce de la mayor por medio de la menor, dicho razonamiento se denomina silogismo. Para demostrar la validez o invalidez de un razonamiento, se puede proceder de dos formas: • Aplicando las propiedades dadas anteriormente. • Usando tablas de verdad. Nosotros veremos únicamente este último procedimiento. Ing. Miguel Ángel Durán Jacobo

13

Unidad 2.- Lógica y tablas de verdad

VALIDEZ DE RAZONAMIENTOS: MÉTODO DE LAS TABLAS DE VERDAD Para determinar la validez de un razonamiento, seguiremos los siguientes pasos: 1. Se forma la tabla de verdad de todas las premisas y de la conclusión. Por sencillez, se suele interesar poner las premisas más simples al principio. 2. Se eliminan todas aquellas líneas en las que alguna premisa sea falsa, pues las premisas son por definición verdaderas. En los ejercicios marcaremos con el símbolo “•” la premisa que permita eliminar una línea dada. 3. Observando las líneas resultantes y la columna correspondiente a la conclusión diremos: a. Todos los casos resultaron “Verdadero”: razonamiento Válido. El razonamiento está bien hecho. b. Todos los casos resultaron “Falso”: razonamiento Inválido. El razonamiento está mal hecho, pero en este caso ocurre que la conclusión contraria es verdadera. c. Existen casos “Verdadero” y “Falso”: razonamiento Inválido. El razonamiento no vale, y la conclusión no puede extraerse de las premisas de partida. d. Ninguna fila resultante: razonamiento inconsistente. El razonamiento no vale, pues las premisas se contradicen. Ejemplo: Estudiar la validez del razonamiento: (p → q) ∨ r ∼r ∼q ∼p

Solución: p

q

r

∼r

∼q

V V V V F F F F

V V F F V V F F

V F V F V F V F

F• V F• V F• V F• V

F F• V V F F• V V

Hemos simbolizado con “ premisas de valor falso eliminadas.

p→∼q V V F F V V V V

(p → q) ∨ r V V V F• V V V V

∼p

V

” las premisas, con doble trazo la conclusión y con “•” las

Por tanto, al quedar una línea V, estamos en el caso a), luego entonces, el razonamiento es Válido.

Ing. Miguel Ángel Durán Jacobo

14

Unidad 2.- Lógica y tablas de verdad

En la práctica podemos combinar los puntos 1 y 2 de forma que cada vez que construyamos una premisa aprovecharemos para eliminar los casos falsos, y así, nos ahorraremos hacer el resto de la tabla para esas líneas eliminadas. Aplicando este procedimiento en el ejemplo anterior, quedaría: p

q

r

∼r

V V V V F F F F

V V F F V V F F

V F V F V F V F

F• V F• V F• V F• V

Ing. Miguel Ángel Durán Jacobo

∼q

p→∼q

(p → q) ∨ r

F

F•

V

V

∼p

F• V F• V

V

15