Expresion

Esta es mi expresion

L = {x Î {0, 1}* x no contiene ‘00’}
(0 + 1)* 00 (0 + 1)*® Expresión regular del L que contiene ‘00’
(1 + 01)* (0 + l) ® Expresión regular del L que no contiene ‘00’

Los estados 1 y 4 se pueden unir en uno solo.

Se pueden suprimir las transiciones d  (3, 0) = 3 yd  (3, 1) = 3. La idea es que, una vez que M cae en el estado 3, la palabra leída Ï L y, además, cualquier palabra formada por la concatenación la palabra leída, como prefijo, con cualquier x Î S*, como cola, tampoco pertenece a L. Entonces, ¿para qué seguir leyendo?. Una vez suprimidas las dos flechas de salida del estado 3, M queda así:

Qué hace M cuando lee una letra y está en 3?  Nada.

 Queda parado, bloqueado. La función de transición, para la situación de bloqueo, es d(3, 0) = Æ y d(3, 1) =  (subconjunto de estados vacío). Cuando se llega al estado 3 hay situación de bloqueo para " a Î S; S = {0, 1}.

Es un caso parecido al procesador de una computadora. Cuando el Registro de Instrucciones de la Unidad de Control alberga en la parte CO (Código de Orden) una configuración que no forma parte del repertorio de instrucciones, la máquina queda bloqueada al intentar ejecutar esa supuesta instrucción.

En este caso la parte del autómata suprimida no contiene estados. Pero puede darse el caso de supresión de algún estado. Veámoslo.

En este mismo ejemplo, se puede suprimir el estado 3 si convenimos en que d (2, 0) = Æ quiere decir que ir a ningún estado es rechazar la palabra leída, que es el mismo convenio adoptado anteriormente. En este caso se llega a una situación de bloqueo desde un estado de aceptación.

 

Referencias: http://www.prismmodelchecker.org/lectures/pmc/17-omega%20regular.pdf
http://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r26805.PDF
http://www.prismmodelchecker.org/lectures/pmc/17-omega%20regular.pdf
http://www.liafa.jussieu.fr/~colcombe/Talks/talk_msob_seattle_14.8.06.pdf

Modelado

Esta tarea se tenia que elegir un sistema y modelarlo , se dijo que podía modelarse ya sea por un sistema de transiciones o de un grafo.

Yo tome un sistema de plumas de una colonia privada.

Componentes:


Pluma de acceso : Es la que baja y sube  para dar acceso al vehiculo.

Persona : La persona en si es parte de el automovil , osea vendria implicito en el auto pero esta es la que lleva el carro hasta la pluma y se mantiene en espera mientras sube la pluma para avanzar.

 
Existen varios estados en este sistema por ejemplo.


Pluma de acceso: Tiene el estado de espera que es cuando no esta ningun vehiculo esperando.

Cuando llega el vehiculo se levanta la pluma y espera a que pase el vehiculo para bajar.

0 - cuando No ahy vehiculo.
1 - cuando llega el vehiculo y la pluma se levanta.
2 - cuando paso el vehiculo y la pluma baja.

Persona Estados:

0 - ( Depende de el horario y si exista fila para entrar enla colonia) : La persona se encuentra haciendo fila para llegar a el acceso .
1 - Espera: La persona espera a que la pluma se levante.

2 - Avance: cuando ya se levanta y acelera el automovil.


Diagrama de transiciones:


Aqui esta el diagrama de transicion .
 
Estados:


0, 1,2  = Estados del componente Persona (Hace fila para llegar al acceso, llega y espera a que se levante , se levanta y acelera)

0, 1, 2,  = Estados del componente Pluma de acceso(Espera, Cuando se levanta, Cuando el carro pasa y la pluma baja.)

0 - cuando No ahy vehiculo.
1 - cuando llega el vehiculo y la pluma se levanta.
2 - cuando paso el vehiculo y la pluma baja.

Para distinguir a cual se refiere  cada una , se manejara el primer numero para Estados de la persona y el segundo para estados de la pluma. En el sistema puede pasar que solo exista un automovil en la fila entonces el sistema regresara a 0,0 , o que exista automoviles en la fila entonces de el ultimo estado que es 2,2 pasaria a 1,0 , directament con un carro esperando a que se levante la pluma.

Aplicación de la lógica predicativa

Tiene muchos tipos de aplicaciones y un uno de ellos es en la  las bases de datos.

Un uso importante de la lógica de predicados o predicativa se encuentra en las bases de datos 

y mas generalmente una noción de "base de conocimientos", que se define como una base de datos más diversas reglas de cálculo

En esta aplicacion es muy común el uso de predicados que contienen variables como consultas. Los propios predicados representan los datos básicos almacenados , predicados computables o combinaciones de los mismo. 

Una consulta le pide al sistema encontrar todos los individuos correspondientes a las variables en la expresión de tal manera que si la expresión se satisface evaluara un 1. Esta idea puede demostrarse consultando en una base de datos utilizando el lenguaje Prolog que si bien no es el lenguaje de consulta mas utilizado sino el SQL , sino que es uno de los mas naturales para utilizarse.  

Un ejemplo de base de datos en Prolog

Existen muchas maneras de representar los predicados en una bae de datos, como por archivos estructurados representando tablas u hojas de cálculos etc. Aquí en este lenguaje una de las formas ara representar un predicado es solo una enumeración de todas las combinaciones de valores para los que el predicado es verdadero.

Se define el predicado madre y el padre de para poder modelar la familia de el arbol.

 

Es posible que una consulta no contenga variables, en cuyo caso se esperaría una respuesta de 1 o 0.
Por ejemplo
madre (Susan, Hank) ⇒ verdadero
madre (Susan, tom) ⇒ falso


Más interesante aún, cuando ponemos las variables en las consultas, esperamos obtener los valores para
aquellas variables que satisfacen el predicado:
mother(alice, X) ⇒ X = tom;  X = carol (two alternatives for X)
father(tom, X) ⇒ false (no such X exists)
mother(X, Y) ⇒ (several alternative combinations for X, Y)
X = alice, Y = tom;
X = alice, Y = carol;
X = carol, Y = george;
X = carol, Y = heather;
X = susan, Y = hank


Tenga en cuenta que los valores X y Y deben estar en correspondencia. No estaría bien que simplemente
se proporcionara el conjunto de X y el conjunto de Y por separado.

El lenguaje Prolog nos permite presentar consultas y recibir una respuesta automática en un estilo similar a la anterior. Por otra parte, Prolog nos permite definir nuevos predicados que utilizan lógica en lugar de la enumeración.


Tal predicado se define por la expresión lógica siguiente:
abuela (X, Y): - madre  (X, Z), padre (Z, Y).


Esto : - se lee como "si" y la coma que separa la madre y el padre se lee como "y". Esto es, en efecto, "X es la abuela de Y si X es la madre de (algunos) Z y Z es el
padre de Y "Aún tenemos que definir padre, pero vamos a hacer esto ahora.:

A continuación: - se lee como "si" y la coma que separa la madre y el padre se lee como "y". esta
Dice, en efecto, "X es la abuela de Y si X es la madre de (algunos) Z y Z es el padre de Y "Aún tenemos que definir padre, pero vamos a hacer esto ahora.:

padre (X, Y): - La madre de (X, Y).
padre (X, Y): - padre (X, Y).

Aquí tenemos dos afirmaciones distintas lógicas, que dice que "X es el padre de Y si X es la madre de Y ", y el otro diciendo algo similar para el padre. Estas afirmaciones no son contradictorio, por el término de enlace: - es "si" no ", si y sólo si". Sin embargo, la recogida de todas las afirmaciones con un símbolo de predicado dado en la lhs agota las posibilidades para ese predicado.

Así, las dos reglas anteriores juntos podría ser tomado como equivalente a:
padre (X, Y) si y sólo si (la madre (X, Y) o padre (X, Y))

Dadas estas definiciones, además de la base de datos, ahora tenemos una "base de conocimiento"
ya que contamos con las normas, así como enumeraciones. Podemos consultar los predicados se definen en la misma manera que consultan los enumerados.


grandmother(alice, Y) ⇒ Y = george; Y = heather
grandmother(X, Y) ⇒ X = alice, Y = george;
X = alice, Y = heather
X = carol, Y = hank
grandmother(susan, Y) ⇒ false


referencias:

http://www.cse.iitd.ernet.in/~kkb/CSL864-1.pdf http://www.cse.iitd.ernet.in/~kkb/CSL864-1.pdf
http://www.cs.hmc.edu/~keller/cs60book/10%20Predicate%20Logic.pdf

4.3 Patrones de razonamiento con cuantificadores

Para esta semana se tomo un problema en mi caso de el capitulo 4 de el libro The world according to predicate logic y se desarrollo el problema 4.17

El razonamiento valido en la ligica se extiende mas alla de los silogismos .

Un silogismo es una forma de razonamiento deductivo que consta de dos proposiciones como premisas y otra como conclusión, siendo la última una inferencia necesariamente deductiva de las otras dos.

Aqui un ejemplo del siglo 19 de una inferencia válida no silogístico que implica relaciones binarias:

“All horses are animal”, therefore: “All horse tails are animal tails”

Using a binary predicate P for “possess” or “have”.

"Todos los caballos son animales", por lo tanto: "Todas las colas de caballo son las colas de animales"

usando un predicado binario P para "poseer" o "tener", que podemos traducir esto de la siguiente manera.

Otra serie natural de deducciones tiene que ver con cuantificadores iterados. En primer lugar, aquí están algunas inferencias bastante triviales, pero válido, sin embargo:

Ahora se hace mas interesante cuando con otras combinaciones por ejemplo

no implica lo contrario 

 

Osea que por ejemplo todo mundo tiene una madre pero nadie es madre de todos . 

E incluso  ∀x∃yRxy no implica la misma forma con las variables permutadas: ∀x∃yRxy. Todo el mundo tiene un padre , pero no todo el mundo tiene un hijo. Aquí se trata de la única inferencia válida interesante entre las combinaciones de 2 cuantificador:

Ahora dejando del lado el ejemplo el problema que me toco fue el 4.17 que dice asi :

4.17 Determine validity or invalidity of all the remaining possible implications between repeated quantifiers. This ends our list of intuitively valid principles of reasoning with quantifiers. 

Warning: the role of compositionality We do not want to leave you with the wrong impression. From our progressive list, you might think that we have now classified 2- quantifier inferences, then we should go on to 3-quantifier ones, and so on. This was indeed how some medieval logicians saw the task ahead for logic. But this is mistaken.We do not have to go up the hierarchy that seemed in the making. There is a complete proof system for predicate logic whose rules just tell us explicitly what single quantifiers do. All the valid behaviour of complex quantifier combinations then follows automatically by finding the right combinations of proof steps for single quantifiers.

Traduciendolo al español.

Ejercicio 4.17 Determine la validez o invalidez de todas las implicaciones posibles entre los restantes cuantificadores que se repiten. Esto pone fin a nuestra lista de principios intuitivamente válidas de razonamiento con cuantificadores.

Advertencia: el papel de la composicionalidad No queremos dejarlos con una mal impresión. Desde nuestra lista progresista, se podría pensar que ahora tenemos 2 clasificaciones -inferencias de cuantificador, entonces debemos ir a la 3ra, y así sucesivamente. esto fue en efecto cómo algunos lógicos medievales vieron la tarea por delante de la lógica. Pero esto es un error. No tenemos que ir a la jerarquía que parecía en la fabricación. Hay una prueba completa en el sistema para la lógica de predicados cuyas reglas sólo nos dicen explícitamente lo que los cuantificadores individuales hacen. Todo el comportamiento válido de combinaciones de los cuantificadores complejos le siguen automáticamente al encontrar la combinación adecuada de medidas de prueba para cuantificadores simples.

E incluso  ∀x∃yRxy no implica la misma forma con las variables permutadas: ∀x∃yRxy. Todo el mundo tiene un padre , pero no todo el mundo tiene un hijo. Aquí se trata de la única inferencia válida interesante entre las combinaciones de 2 cuantificador:

Ejemplos realizados.

Todo el mundo ve a alguien  ∀x∃ySxy

Alguien ve a todo el mundo  ∃x∀ySxy 

Esto es invalido ya que todo el mundo si puede ver a alguien por ejemplo a un famoso, pero ese famoso no peude ver a todo el mundo.

Todo el mundo es visto por alguien  ∀x∃ySxy
 Alguien es visto por todo el undo    ∃x∀ySxy

Y en este caso utilizando las mismas variables nos damos cuenta que es valido hablandolo logicamente.

Porque? pues porque todo el mundo ( hablando de el planeta tierra) si puede ser visto por alguien (un astronauta) y alguien si puede ser visto por todo el mundo ( Un famoso) entonces aqui se podria validar. Claro la intuicion y la logica es la que nos lleva a validarlo ya que otra persona con otra logica podria invalidarlo por ejemplo.

Todo el mundo es visto por alguien( un astronauta observando al mundo) , alguien es visto por todo el mundo( El mundo o la tierra no tiene vida ni ojos) . entonces Utilizando esta logica daria por invalido estas oraciones , aunque como sabemos el sentido de las palabras no peude ser tomado 100%  textual.

Referencias:
http://www.logicinaction.org/docs/ch4.pdf
http://es.wikipedia.org/wiki/Silogismo

Lógica Predictiva

En esta semana se nos dio a elegir un problema de un libro llamado Symbolic Logic , que havla sobre logica predictiva.

Yo eleji el problema 100 de la pagina 102 y dice asi

All my boys are disobedient;

All my girls are discontented

Todos mis niños son desobedientes

Todas mis niñas están descontentas

Ahora después de esto para encontrar llegar a una conclusión con estas preposiciones se definen algunas equivalencias con notación.

Ño(x) : Niños

Ña(x): Niñas

D(x): Desobedientes

Dc(x): Descontentas

Ahora apartir de aqui podemos hacer varias expresiones utilizando los cuantificadores 

∀ significa para todos

∃ Significa por lo menos uno o alguno.

∀(x)Ño(x) -->D(x)  Que significaria todos mis niños son desobedientes 

∀(x)Ña(x) -->Dc(x)  Que significaria todos mis niñas estan descontentas

De qui podemos sacar conclusiones primero explicada en palabras

Ninguno de mis niños estan descontentos. 

Ninguna de mis niñas son desobedientes.

¬∃Ño(x) -->Dc(x)

¬∃Ña(x) -->D(x)

Que vendria quedando de este modo 

∀(x)Ño(x) -->D(x) 

∀(x)Ña(x) -->Dc(x)  

Por lo tanto

¬∃Ño(x) -->Dc(x)    o   ¬∃Ña(x) -->D(x)

Tarea 4 - BDD y ROBDD

Primero que nada antes de empezar este tema aquí están algunos conceptos , que es BDD o en español diagrama de decisión binario.

En ciencias de la computación, un diagrama de decisión binario (DDB), es una estructura de datos utilizada para representar una función booleana. A un nivel más abstracto, los DDBs pueden ser considerados como una representación comprimida de conjuntos o relaciones. A diferencia de otras representaciones comprimidas, las operaciones se realizan directamente en los DDB, sin necesidad de descomprimirlos.

Y una funcion boolena se puede representarse como un grafo acíclico dirigido con raíz, el cual posee nodos de decisión y dos nodos terminales llamados terminal -0 y terminal-1. Cada nodo de decisión está etiquetado por una variable booleana (0 o 1) y tiene dos nodos hijos, llamados hijo menor e hijo mayor. La arista que une un nodo con un hijo menor (mayor) representa una asignación de la variable con el valor 0 (1).

Un DDB está ordenado si las distintas variables aparecen en el mismo orden para todos los caminos desde la raíz. Un DDB es reducido si se han aplicado las siguientes dos reglas a su grafo:

Unir los isomorfismos de subgrafos.

Eliminar los nodos cuyos dos hijos sean isomorfos.

En el uso popular, el término DDB también se refiere a Diagrama de decisión binario reducido ordenado (DDBRO, mejor conocido en la literatura en inglés como ROBDD: Reduced Ordered Binary Decision Diagram). Una ventaja de un DDBRO es que es canónico (único) para una función particular y un orden de variables.Esta propiedad es útil por ejemplo en la verificación de funciones de equivalencia.

Un camino desde el nodo raíz al terminal-1 representa una asignación de variables (posiblemente parcial) para la cual la función booleana es verdadera. Si el camino desciende desde un nodo hasta un hijo menor (mayor), la variable del nodo adquiere el valor 0 (1).

Para la tarea 4 se pidio lo siguiente:

Inventar una función booleana, usando por mínimo 3 variables y 4 conectivos básicos.
* Construyan y dibujen su BDD. Diagrama binario de Decisión creo asi se llama
* Reduzcan el BDD resultante a un ROBDD.
* Dibujen el ROBDD resultante

Esta es mi expresión booleana :

                                                        (X v Y)  ^  ( Y v  X)  v  ¬ Z 

Ahora genero mi arbol binario.

Ahora para terminar tendremos que hacer su ROBDD que significa  reduced ordered binary decision diagram. y es donde se mostrara la reduccion de el arbol binario obtenido para obtener una expresion minima.

Reducir a ROBDD

Para reducir un árbol binario de decisión a un Diagrama Binario de Decisión se tienen que considerar dos reglas:

 

1. Unir los isomorfismos (de igual forma) de subgrafos
2. Eliminar los nodos que sus dos hijos sean isomorfos.
   

 

 

REFERENCIAS :

http://es.wikipedia.org/wiki/Diagrama_de_decisi%C3%B3n_binario

Aplicación de la lógica proposicional

Primero que nada para hablar de este tema se tiene que tener un concepto de que es la lógica proposicional.

La lógica proposicional es la parte de la lógica que estudia la formación de proposiciones complejas a partir de proposiciones simples, y la inferencia de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples.

Una lógica proposicional es un sistema formal cuyos elementos más simples representan proposiciones, y cuyas constantes lógicas, llamadas conectivas, representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.

La proposición es el significado de una idea, enunciado,conjunto de palabras o letras a las que se les puede asignar uno y sólo uno de los valores de verdad, que pueden ser:

VERDADERO (V) o FALSO(F)

Por lo general, a las proposiciones se las representa por las letras del alfabeto desde la letra p, es decir, p, q, r, s, t, ... etc. Así, por ejemplo, podemos citar las siguientes proposiciones y su valor de verdad:

p : 15 + 5 = 21 (F)

q: Santa Fe es una provincia Argentina. (V) 

r: El número 15 es divisible por 3. (V)

s: El perro es un ave. (F)

Existe una notacion para trabajar con ellas y es esta:

Notación y Conectivos Lógicos

A partir de proposiciones simples es posible generar otras, simples o compuestas. Es decir que se puede operar con proposiciones, y para ello se utilizan ciertos símbolos llamados conectivos lógicos. A continuación vemos una concreta definición de cada uno: Conectiva Expresión en el lenguaje natural Ejemplo Símbolo en este artículo Símbolos alternativos Negación no No está lloviendo. Conjunción y Está lloviendo y está nublado.   Disyunción o Está lloviendo o está soleado. Condicional material si... entonces Si está soleado, entonces es de día. Bicondicional si y sólo si Está nublado si y sólo si hay nubes visibles. Negación conjunta ni... ni Ni está soleado ni está nublado. Disyunción excluyente o bien... o bien O bien está soleado, o bien está nublado.

APLICACIÓN DE LA LÓGICA PROPOSICIONAL

La lógica proposicional dio origen a la algebra booleana que esta a su vez fue la base para la informatica y para la forma en que funcinarion los primeros ordenadores. Ya que el algebra de boole es el area de las matematicas que se aplica en el diseño de circuitos logicos .


Debido a que los computadores trabajan con información binaria, la herramienta matemática adecuada para el análisis y diseño de su funcionamiento es el Álgebra de Boole. El Álgebra de Boole fue desarrollada inicialmente para el estudio de la lógica. Ha sido a partir de 1938, fecha en que Claude Shannon publicó un libro llamado "Análisis simbólico de circuitos con relés", estableciendo los primeros conceptos de la actual teoría de la conmutación, cuando se ha producido un aumento considerable en el número de trabajos de aplicación del Álgebra de Boole a los computadores digitales. Hoy en día, esta herramienta resulta fundamental para el desarrollo de los computadores ya que, con su ayuda, el análisis y síntesis de combinaciones complejas de circuitos lógicospuede realizarse con rapidez.


Ya que se puede aplicar de este modo.



La verdad de una proposición puede asociarse al pasaje de corriente en un circuito eléctrico con un interruptor.

Así, para representar a p, si es F, se tiene


y para p, si es V, se tiene:


Es decir, el interruptor se cierra si p es V y se abre si p es F.

Podemos, así, representar las operaciones proposicionales mediante circuitos con tantos interruptores como proposiciones componentes, combinados en serie o paralelamente.


Veremos, a continuación, como representar en forma booleana las operaciones que surgen de operar con dos proposiciones mediante los conectivos lógicos que conocemos

Conjuncion



Este circuito admite el pasaje de corriente, es decir la verdad de p^q , solo si ambas son V .

Disyuncion
Está representada por un circuito en paralelo.



Como vemos, admite el pasaje de corriente cuando al menos una de las dos es V (comprobar en la correspondiente tabla de verdad).

Cuando se trabaja con circuitos digitales es muy común que al final de un diseño se tenga un circuito con un número de partes (circuitos integrados y otros) mayor al necesario.

Para lograr que el circuito tenga la cantidad de partes correcta (la menor posible) hay que optimizarlo (reducirlo).

Un diseño óptimo causará que:
- El circuito electrónico sea más simple
- El número de componentes sea el menor
- El precio de proyecto sea el más bajo
- La demanda de potencia del circuito sea menor
- El mantenimiento del circuito sea más fácil.
- Es espacio necesario (en el circuito impreso) para la implementación del circuito será menor.

En consecuencia que el diseño sea el más económico posible.

Una herramienta para reducir las expresiones lógicas de circuitos digitales es la matemáticas de expresiones lógicas, que fue presentada por George Boole en 1854,herramienta que desde entonces se conoce como álgebra de Boole.
Las reglas del álgebra Booleana son:

Notas: (punto): significa producto lógico. + (signo de suma): significa suma lógica
Operaciones básicas en el algebra booleana

Ley Distributiva, ley Asociativa, ley Conmutativa

Precedencia y Teorema de Morgan

Para asegurarse de que la reducción del circuito electrónico fue exitosa, se puede utilizar la tabla de verdad que debe dar el mismo resultado para el circuito simplificado y el original.


 


Y esa es una aplicación que tiene la lógica proposicional , que se utiliza en el diseño de circuitos.



Referencias:
http://www.unicrom.com/dig_algebra_booleana.asp 

http://es.wikipedia.org/wiki/L%C3%B3gica_proposicional

http://soko.com.ar/matem/Logica_proposicional.htm

TAUTOLOGIA

En lógica, una tautología es una fórmula bien formada de un sistema de lógica proposicional que resulta verdadera para cualquier interpretación; es decir, para cualquier asignación de valores de verdad que se haga a sus fórmulas atómicas. La construcción de una tabla de verdad es un método efectivo para determinar si una fórmula cualquiera es una tautología o no.

Primero que nada antes de continuar se tiene que tener claro que es una tabla de verdad.

Tablas de verdad
En un sistema de lógica proposicional, una interpretación no es más que una función que asigna un único valor de verdad a todas las fórmulas atómicas bajo consideración. Diferentes interpretaciones, por lo tanto, difieren sólo en las asignaciones de valores de verdad que hacen.

Una tautología es una fórmula bien formada que bajo cualquier interpretación de sus componentes atómicos, tiene valor de verdad 1 (verdadero).

Esto se logra mediante una tabla de verdad. Por ejemplo, considérese la fórmula p ∧ q. Como a cada fórmula atómica puede asignársele uno de dos posibles valores de verdad, hay en total 2² = 4 posibles combinaciones de valores de verdad. Es decir, cuatro interpretaciones posibles: o ambas son verdaderas; o p es verdadera y q falsa; op es falsa y q verdadera; o ambas son falsas. Esto puede presentarse mediante una simple tabla:

Para cada una de estas interpretaciones, puede calcularse el valor de verdad de la fórmula p ∧ q. Los resultados pueden presentarse nuevamente mediante una tabla:


Esta es la tabla de verdad de la fórmula p ∧ q. Como se ve, esta fórmula sólo es verdadera bajo una interpretación: aquella en la que ambas fórmulas atómicas son verdaderas. Una tautología es una fórmula cuyo valor de verdad es 1 para todas las interpretaciones posibles de las fórmulas atómicas. Por lo tanto, p ∧ q no es una tautología. En cambio, la siguiente tabla de verdad muestra una fórmula que sí lo es:

Si una fórmula tiene n fórmulas atómicas, entonces tiene 2ⁿ interpretaciones posibles. En muchos casos, por lo tanto, las tablas de verdad pueden ser muy grandes. Lo importante, sin embargo, es que dado que la lógica proposicional no admite fórmulas infinitas, el número de interpretaciones posibles siempre será un número finito, y por lo tanto siempre será posible decidir si una fórmula cualquiera es una tautología o no.

TAUTOLOGIA A ELABORAR

tiene que contener : 3 variables

• 4 conectivos lógicos
• Por lo menos 1 disyunción, 1 conjunción y 1 negación
• Un pequeño árbol con sus respectivas subdivisiones de la expresión que formule.