Medbiol - Logica proposicional

Como dijimos en nuestro artículo sobre “Búsquedas para investigación y las matemáticas” los operadores booleanos son parte fundamental en el funcionamiento de los motores de búsqueda: ahora hablaremos sobre otro elemento importantísimo para que estos gigantes del software funcionen, la lógica proposicional.

¿Qué es la lógica proposicional?

La lógica proposicional es un sistema formal, basado en proposiciones y en las posibilidades que tienen de ser falsas o verdaderas. Esto aplica para las proposiciones iniciales y tambien para sus combinaciones.

¿Qué es una proposición?

Una proposición es una frase de la cual puede decirse que es una sola de dos cosas: verdadera, falsa. Por ejemplo, las siguientes frases:

  • La tierra gira alrededor del sol,
  • E. colli es un procariota,
  • Roma es la capital de Francia y
  • 2 > 4 

Son proposiciones, las dos primeras verdaderas y las últimas falsas. Por otra parte, recuerda que para que una frase sea una proposición debe poder calificarse como verdadera o falsa, así que la frase ¿qué día es hoy? no es una proposición, ya que no podemos decir que es falsa o verdadera.

Símbolos

Se tienen los siguientes símbolos:

  1. «ꓦ» leído «o» o «O» («OR» o «or» en inglés).
  2. «ꓶ» leído «no» o «NO» («NOT» o «not» en inglés).

Axiomas

Dadas las proposiciones p, q se tienen los siguientes axiomas:

  1.  p ꓦ q es falsa si ambas p, q son falsas.
  2. ꓶp es verdadera si p es falsa y viceversa.

Teoremas

Se tienen los siguientes teoremas:

Teorema 1.

ꓶp ꓦ q es falsa si p es verdadera y q falsa y es verdadera en los demás casos.

Demostración. Hay cuatro casos posibles:

i. p verdadera, q falsa: entonces, por axioma 2., ꓶp es falsa y como también q lo es, por ax. 1, ꓶp ꓦ q es falsa.
ii. p, q verdaderas
iii. p falsa, q verdadera y
iv. p, q falsas.

Demuestra que en cualquiera de estos tres últimos casos ꓶp ꓦ q es verdadera.

Denotación. ꓶp ꓦ q se denota, con el “símbolo abreviante” “→”, “p → q”, y se lee “p entonces q”, “si p entonces q” o “p implica q” (p ← q o q → p se lee “q implica p”): recalcando, por el anterior teorema, p → q sólo es falsa si p verdadera y q falsa y es verdadera en todos los demás casos

Nota. En matemática se usan los símbolos abreviantes para evitar largas cadenas de caracteres.

 

Teorema 2.

Si p y p → q son verdaderas, entonces q es verdadera.

Demostración.

p y p → q verdaderas, o lo que es lo mismo, p y (ꓶp ꓦ q) verdaderas; entonces, por ax. 2, una de las dos ꓶp ó q es verdadera, pero ya que, por ax. 1, ꓶp no lo es, ha de serlo q.

Teorema 3.

ꓶ(ꓶp ꓦ ꓶq) es verdadera sólo si p, q verdaderas

Demostración:

i. p, q verdaderas: entonces, por axioma 2., ꓶp, ꓶq falsas; entonces por ax. 1., ꓶp ꓦ ꓶq es falsa; entonces, por ax. 2., ꓶ(ꓶp ꓦ ꓶq) es verdadera.
ii. Demuestra que ꓶ(ꓶp ꓦ ꓶq) es falsa en los demás casos.

Denotación: ꓶ(ꓶp ꓦ ꓶq) se denota, mediante el símbolo abreviante “∧” , “p ∧ q”, y se lee “p y q”: recalcando, por el anterior teorema, p ∧ q es verdadera sólo si p,q verdaderas.

Teorema 4.

La proposición (p → q) ∧ (p ← q) es verdadera si p, q son ambas verdaderas o ambas falsas.

Demostración.

i. Supongamos p, q verdaderas, entonces, por teor. 1., p → q es verdadera; por las misma razón, p ← q también es verdadera; entonces, por teor. 3., (p → q) ∧ (p ← q) es verdadera.
ii. p, q falsas: demuestra que también en este caso p → q ∧ p ← q es verdadera.
iii. Demuestra que (p → q) ∧ (p ← q) es falsa si una de las dos p, q es falsa y la otra verdadera.

Denotación. p → q ∧ p ← q se denota, mediante el símbolo abreviante “↔”, “p ↔ q”, y se lee “p es equivalente q” (o, “p equivale a q”): recalcando, por el anterior teorema, p ↔ q es verdadera sólo si p,q son ambas verdaderas o ambas falsas.

Teorema 5.

p  ↔ ꓶꓶp.

Demostración.

i. Supongamos p verdadera: entonces, por ax. 2., ꓶp es falsa; entonces por ax. 2., ꓶꓶp es verdadera; entonces por teor. 4, p ↔ ꓶꓶp.

ii. Sea p falsa: demuestra que en este caso también p ↔ ꓶꓶp.
De i. e ii. se tiene que p  ↔ ꓶꓶp.

Teorema 6.

((p → q) ∧ (q → r)) → ((p → r)).

Demostración.

i. p, q, r verdaderas: por teor. 1., p → q, q → r y p → r verdaderas; entonces, por teor. 3., (p → q) ∧ (q → r) verdadera y p → r ya lo era; entonces, por teor. 1., ((p → q) ∧ (q → r)) → ((p → r)) es verdadera.
ii. Hay siete casos más, desde p, q verdaderas y r falsa, hasta p, q, r falsas: demuestra que también en todos éstos casos ((p → q) ∧ (q → r)) → ((p → r)) es verdadera.

Teorema 7.

((p ↔ q) ∧ (q ↔ r)) → ((p ↔ r))

Demostración. Se deja al lector

Nota. En vez de “entonces” y “equivalente a” pueden escribirse, respectivamente, “→” y “↔”. Por ejemplo, la parte i. del teor. 5 queda: p verdadera ↔ ꓶp falsa ↔ ꓶꓶp verdadera; entonces, aplicando el  teor. 7., p ↔ ꓶꓶp (nótese que, si se quiere, las   justificaciones se suponen sabidas y se omiten).

Teorema 8.

Sea p ↔ q y r una proposición: entonces, i. ꓶp ↔ ꓶq, ii. (r → p) ↔ (r → q), iii. (p ∧ r) ↔ (q ∧ r), iv. (p ꓦ r) ↔ (q ꓦ r)

Demostración. Se deja al lector.

Teorema 9.

Sean p, q y r proposiciones: entonces, i. (p → q) ↔ (ꓶq → ꓶp), ii. ((p ∧ p) ↔ p, iii. (p ∧ q) ↔ (q ∧ p), iv. (p ∧ (q ∧ r)) ↔ ((p ∧ q) ∧ r), v.ꓶ(p ꓦ q) ↔ ꓶ(ꓶp ∧ ꓶq), vi. (p ∧ p) ↔ p, vii. (p ꓦ q) ↔ (q ꓦ p), viii) (p ꓦ (q ꓦ r)) ↔ ((p ꓦ q) ꓦ r), viiii. (p ∧ (q ∧ r)) ↔ ((p ∧ q) ∧ r), ix. (p ∧ (q ꓦ r)) ↔ ((p ∧ q) ꓦ (p ∧ r)), x. (p ꓦ (q ∧ r)) ↔ ((p ꓦ q) ∧ (p ꓦ r)), xi. (p ∧ ꓶꓶq) ↔ ꓶ( p → q), xii. (p ꓦ q) ↔ (ꓶp → q).

Demostración. Se deja al lector (sólo demuestra algunos pocos ítems, en particular ix. y x.).

Tablas de la verdad

Los anteriores teoremas es común “demostrarlos” (así entre comillas) mediante “tablas de verdad” en las que se consideran todos los casos posibles y donde a un caso (consideración) de p verdad se le asigna el “valor de verdad” “V” y “F” en caso contrario: por ej., la tabla de verdad para ꓶp ꓦ q (o sea, p → q) es,

Ejercicio. Elabora las tablas de verdad para los teoremas 7. y 8.

Notas

  • Ya que hay 3 formas de ser p → q verdadera, una con q verdadera y dos con q falsa, de p → q verdadera no puede deducirse que q lo sea: la herramienta para dirimir esto es el teor. 2.: si p y p → q son verdaderas q también lo es.
  • Obsérvese que acá no se ha definido p → q, como suele hacerse, sino que primero se ha demostrado cuándo ꓶp ꓦ q es verdadera, cuándo falsa y luego se ha abreviado con p → q. Lo mismo se hizo con p ∧ q y p ↔ q: tomar los “atajos” de definiciones superfluas y tablas de verdad (éstas muy tempranamente) en aras de una supuesta rapidez de exposición a la larga complica y retarda ésta y va en contra de la práctica demostrativa basada en teoría previa.
  • En varios buscadores se usan p OR q, p AND q (o, pq) y NOT p en lugar, respectivamente, de p ꓦ q, p ∧ q y ꓶp (OR, AND y NOT comúnmente se los llama «operadores booleanos»).

En Conjuntos

• La proposición “x pertenece a A” (o, “x está en A”) se denota “x ∈ A” y la proposición “x no pertenece a A” se denota “x ∉ A” (o, ꓶx ∈ A)

• La proposición x ∈ A ꓦ x ∈ B se denota “x ∈ (A ∪ B)”, leído “x pertenece a A unión B”, es decir, A ∪ B está constituido por elementos que están en A o en B (otra forma de expresarlo es: A ∪ B = {x | x ∈ A ∨ x ∈ B}). Ejemplo: dados los conjuntos A = {1,2,3,4,5} y B = {4,5,6,7,8,9}, la unión de estos conjuntos es A∪B = {1,2,3,4,5,6,7,8,9}, lo cual se ilustra en el siguiente “diagrama de Venn”:

  • La proposición x ∈ B → x ∈ A se denota “B ⊂ A”,  leído “B es subconjunto de A”.
Cojunto-Logica-propocional
  • Dado un conjunto universal U del cual A es subconjunto, “A complemento” (o, “complemento de A”), denotado  A’ (o, AC) es el conjunto de elementos que están U pero no  en A: A’ = {x ∈ U | x ∉ A}

Teorema. x ∉ A’ ↔ x ∈ A.
Demostración. x ∉ A’ ↔ ꓶ (x ∈ A’) ↔ ꓶ (ꓶ x ∈ A) ↔ ꓶꓶ(x ∈ A) ↔ x ∈ A: aplicando reiteradamente el teor. 7. se tiene x ∉ A’ ↔ x ∈ A (una conclusión como esta, contenida en el enunciado de teorema, por lo regular se omite).

Teorema(A’)’ = A

Demostración. Se deja al lector

Teorema. x ∈ A ∧ x ∈ B ↔ x ∈ (A’ ∪ B’)’.

Demostración. x ∈ A ∧ x ∈ B ↔ x ∉ A’ ∧ x ∉ B’ ↔ ꓶx ∈ A’ ∧ ꓶx ∈ B’ ↔
ꓶ(x ∉ A ∨ x ∉ B) ↔ ꓶ(x ∈ A’ ∨ x ∈ B’) ↔ ꓶ(x ∈ (A’ U B’)) ↔ ꓶx ∈ (A’ U B’) ↔
x ∈ (A’ U B’)’.

Notación. (A’ U B’)’ se denota “A ∩ B”, denominado la “intersección de A y B”, que como se ve en el enunciado del anterior teorema, es el conjunto de los elementos que están tanto en A como en B: A ∩ B = {x |x ∈ A ∧ x ∈ B}.

Notación. La proposición x ∈ A ∧  x  ∉ B se denota “x ∈ (A – B)”: A – B = {x | x ∈ A ∧ x ∉ B} (se denomina «diferencia A menos B»). 

Definición. El “conjunto vació”, denotado “∅” (o, “{ }”) es el conjunto que no tiene elementos.

Nota. Dada la definición de ∅, la proposición x ∈ ∅ siempre es falsa.

Denotación. A ⊂ B ∧ B ⊂ A se denota “A = B”, leído “A igual B”

Teorema. Sean A, B y C conjuntos y U el conjunto universal: i. A ∩ A = A, ii. A U A = A, iii. A ∩ ∅ = ∅, iv. A U ∅ = A, v. A ∩ U = A, vi. A U U = U, vii. A ∩ B = B ∩ A, viii. A U B = B U A, ix. (A’)’ = A, x. (A ∩ B) ∩ C = A ∩ (B ∩ C), xi. (A U B) U C = A U (B U C), xii. A ∩ (B U C) = (A ∩ B) U (A ∩ C), xiii. A U (B ∩ C) = (A U B) ∩ (A U C), xiv. A ⊂ B ↔ A ∩ B = A, xv). A ⊂ B ↔ A U B = B, xvi. A ⊂ B → B’ ⊂ A’, xvii. A ∩ B ⊂ A ⊂ A U B , xviii. C – (A ∩ B) = (C – A) U (C –B), xix. C – (A U B) = (C – A) ∩ (C –B), xx. (B – A) U C = (B U C) – (A – C), xxi. (B – A) ∩ C = (B ∩ C) – A, xxii. A ⊂ B ↔ A – B = ∅, xxiii. A ⊂ B = ∅ ↔ B – A = B, xxiv. A – A = ∅, xxv. ∅ – A = ∅, xxv., xxvi. A – ∅ = A, xxvii. A – B = A ∩ B’, xxviii. (B – A)’ = A U B’, xxix. U – A = A’, xxx. A – U = ∅, xxxi. (A U B)’ = A’ ∩ B’, xxxii. (A ∩ B)’ = A’ U B’.

Demostración.

i. Sea x ∈ A ∩ A  ↔  x ∈ A  ∧ x ∈ A ↔ x ∈ A

xii. Sea x ∈ A ∩ (B U C) ↔ x ∈ A ∧ x ∈ (B U C) ↔ x ∈ A ∧ (x ∈ B ∨ x ∈ C) ↔ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) ↔ x ∈ (A ∩ B) ∨ x ∈ (A ∩ C) ↔ x ∈ ((A ∩ B) U (A ∩ C)).

Se deja al lector demostrar unos pocos del resto de ítems, en particular xiii, xxxi y xxxii.

Búsquedas booleanas para investigación

Nuestro servicio te evitará “complicarte” con los motores de búsqueda y bases de datos académicas pues hará todo el trabajo por ti, incluso en búsquedas más complejas, como por ej. para encontrar resultados sobre

secuencias conservadas de enzimas topoisomerasas o de enzimas helicasas, de modo que en las primeras se excluyan las de bacterias y levaduras y en las segundas de ratones y simios y, en ambas, las humanas

donde habrá que usar los operadores booleanos mezclados sistemáticamente en la exacta “cadena booleana”

((topoisomeras* OR gyrase) NOT (bacteri* OR yeast) OR helicas* NOT (mouse OR ape)) («conserved sequence» OR «conserved motif» OR «conserved domain») NOT human

Accede a nuestro servicio y no tendrás que preocuparte de los efectos sobre la “búsqueda booleana” de modificadores (comillas, asteriscos y paréntesis) y operadores, del orden (de éstos y de palabras) y de la teoría lógica matemática involucrada (¿preocupado ante tantas demostraciones y ejercicios que te hemos dejado?: ¡despreocúpate de ello!).

¡Lo importante es tu investigación!: trasládanos esas preocupaciones y así tus búsquedas serán más rápidas y relevantes; pasarás de “perder” días buscando información a “invertir” unos cuantos minutos.

En nuestro servicio no te reportaremos miles ni millones de resultados, la gran mayoría irrelevantes, sino unos pocos pero relevantes: para la anterior búsqueda, a fecha 24/06/2019, hay 332 resultados en orden de relevancia y 328 en orden de actualidad (a 25/02/2020, 335 y 336, respectivamente).

Otro plus: tendrás más de 50 formas de personalizar tú búsqueda.

Lógica proposicional, conjuntos y búsquedas para investigación

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *