Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

7. Metalógica elemental

Capítulo 7 de Logic & Proofs
by

Moris Polanco

on 5 March 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 7. Metalógica elemental

7. Metalógica elemental Objetivos:

Mostrar que dos fórmulas son equivalentes si su bicondicional es una tautología.
Encontrar el equivalente en forma normal disyuntiva de una fórmula.
Explicar la relación entre tablas de verdad y circuitos booleanos. Si un argumento con premisas A1,...,An y conclusión B es válido, entonces B es consecuencia lógica de A1,...,An.

Es decir: B es una consecuencia lógica de A si y solo si (A->B) es una tautología.

Si sucede que B es consecuencia lógica de A y que A es consecuencia lógica de B, se dice que A y B son lógicamente equivalentes.

Entonces, dos fórmulas son lógicamente equivalente si y solo tienen los mismos valores de verdad en cada asignación de verdad.
Ejemplo: (P->Q) y (¬P v Q). (¿Recuerda la definición del condicional?) Consecuencia y Equivalencia La equivalencia lógica se expresa mediante el bicondicional <->

¿Cómo será la tabla de verdad del bicondicional? El bicondicional 1. Sabemos que P y Q son lógicamente equivalentes si y solo si tienen los mismos valores de verdad en cada asignación de verdad.
2. Por la definición del bicondicional, sabemos que P y Q son lógicamente equivalentes si (P<->Q) es una tautología.
3. Entonces, (P<->Q) es verdadero cuando P y Q tienen el mismo valor de verdad, y falso cuando tienen distinto valor de verdad. Tabla de verdad del bicondicional Ejemplo Puesto que un bicondicional es verdadero cuando sus dos fórmulas inmediatas tienen el mismo valor de verdad, y falso si tienen distinto valor de verdad, los árboles de verdad respectivos quedan así: Árbol de verdad del bicondicional (Es decir, el bicondicional es verdadero si phi y psi son ambos verdaderos o si son ambos falsos. Y falso si phi es verdadero y psi falso, o al revés.) Eliminación del bicondicional Introducción del bicondicional Did I get this?, p. 101 Si tengo un bicondicional en una línea de una derivación (p1), y una fórmula que incluye el primero de los equivalentes de ese bicondiconal en otra línea (p2), puedo inferir la fórmula que resulta de reemplazar el equivalente del lado izquierdo por el equivalente del lado derecho, o al revés. Conmutatividad y Reemplazo Reemplazo de equivalentes: Conmutatividad Ejemplo Did I get this? y Learn by Doing, p. 101 Considere la siguiente tabla de todas las posibles funciones de verdad binarias: (16 posibilidades) (¿Y si fueran ternarias?: 256 columnas) Completud funcional Función de verdad 'o' inclusiva Completud: podemos expresar toda posible función de verdad con los conectivos que ya conocemos;
de hecho, bastan la disyunción y la negación.
Esto significa que la combinación de disyunción y negación es un conjunto funcionalmente completo de conectivos. El conectivo de Sheffer (NAND) El conectivo de Sheffer (o NAND) es, en sí mismo, un conjunto funcionalmente completo. Dado que basta con la disyunción y la negación para expresar cualquier función de verdad, podemos probar que el conectivo de Sheffer es funcionalmente completo mostrando que tanto la disyunción como la negación pueden expresarse en términos de este. Negación: El conectivo de Peirce también es funcionalmente completo. El conectivo de Peirce (NOR) (A B) es equivalente a ¬(A v B) Definiciones previas Formas normales Literal: una literal es una letra proposicional (e.g., P, Q, T...) o una letra proposicional negada (e.g.,¬P, ¬Q, etc.) Forma normal disyuntiva: una fórmula de lógica proposicional está en forma normal disyuntiva si y solo si es:
-Una literal
-Una conjuncion de literales
-Una disyunción de conjunción de literales.

Observe que toda fórmula en FND es una disyunción de conjunción de literales, con el entendido de que una disyunción puede consistir en un solo disyunto, y una conjuncion en un solo conyunto. Ejemplos Algoritmo Procedimiento para convertir cualquier fórmula a FND Una fórmula de lógica proposicional está en forma normal conjuntiva si y solo si es:

1. Una literal
2. Una disyunción de literales
3. Una conjunción de disyunciones de literales.

Como en la FND, una disyunción puede contener un solo disyunto, y una conjunción un solo conyunto.
Cualquier fórmula de lógica proposicional es equivalente a una fórmula en FNC. Forma normal conjuntiva Se dice que un sistema lógico es semánticamente completo cuando todas las fórmulas lógicamente válidas (todas las verdades lógicas) del sistema son además teoremas del sistema (es decir, se pueden probar).

La lógica proposicional es un sistema semánticamente completo. Completud Circuitos Fuente: http://www.allaboutcircuits.com/vol_4/chpt_7/9.html http://logic.ly/demo Circuitos y tablas de verdad ¬A = !A

(A&B) = AB

(AvB) = A+B Circuitos y expresiones booleanas !AB+A!B Disyunción exclusiva (XOR): uno u otro, pero no ambos. Representación de la tabla XOR: uno y otro, pero no ambos (disyunción exclusiva) En términos de Sheffer: si

¬A es (A|A)
(A&B) es ((A|B)|(A|B))
(AvB) es ((A|A)|(B|B))

(¬A&B) v (A&¬B) sería

(((A|A)|B)|((A|A)|B))|((A|A)|B)|((A|A)|B)|((A|(B|B))|(A|(B|B))|(A|(B|B))|(A|(B|B)))) En términos de Sheffer (|) Disyunción: (AvB) es ((A|A)|(B|B))
Full transcript