Ciudades
Una red de vuelos entre ciudades. conn(A,B) es un vuelo directo
de A a B; walk(A,B) significa que B es alcanzable desde A
encadenando vuelos. El objetivo es demostrar que existe una ruta.
Reglas
- Los axiomas son los vuelos directos, nombrados por las iniciales de las
ciudades (por ejemplo NR para conn(NuevaYork,Roma)).
- DIR: un vuelo directo es una ruta — de conn(A,B) se
obtiene walk(A,B).
- COMP: las rutas se componen — de walk(A,B) y
walk(B,C) se obtiene walk(A,C).
Convenciones
- Las ciudades (NuevaYork, Roma, Sydney, Tokyo, Odense) son constantes.
- Las mayúsculas sueltas (A, B, C) son metavariables que se unifican al
aplicar una regla. Una metavariable que una regla introduce pero la meta no
determina — como la escala intermedia de COMP — queda en rojo hasta
que otra rama de la demostración la fije, y ese valor se propaga a las metas
hermanas.
Adaptado de Fabrizio Montesi, «Introduction to Choreographies», Capítulo 1.
Modo libre
Un editor de árboles de deducción sin validación lógica: cualquier texto es
una proposición válida y toda regla puede aplicarse sobre cualquier meta. Sirve
para bosquejar libremente la forma de una demostración.
Convenciones
- Las proposiciones y los nombres de regla se escriben en LaTeX y se
muestran como fórmulas (por ejemplo A∧B o →I).
- Los tokens de la forma ?a, ?b, … son metavariables sin asignar y se
muestran en rojo. Tocá un nodo para editar su proposición, o el nombre de una
regla para renombrarla.
- Las reglas se nombran por su cantidad de premisas: Ax (0 premisas),
R1 … R4.
Lógica intuicionista (NJ)
Deducción natural para la lógica proposicional con contextos. Una meta tiene
la forma Γ⊢τ: «a partir de las hipótesis del contexto Γ
se deduce la fórmula τ».
Reglas
- ax: si la fórmula ya está en el contexto (τ∈Γ), la meta
se cierra.
- ⊥e: de Γ⊢⊥ (una contradicción) se deduce cualquier
fórmula.
- ∧i, ∧e1, ∧e2: introducción y eliminación de la
conjunción.
- ∨i1, ∨i2, ∨e: introducción y eliminación de la
disyunción (la eliminación analiza cada caso extendiendo el contexto con su
hipótesis).
- ⇒i, ⇒e: introducción y eliminación de la implicación.
La introducción descarga el antecedente, agregándolo al contexto de la
premisa (Γ,τ⊢σ); la eliminación es modus ponens.
- ¬i, ¬e: introducción y eliminación de la negación. ¬τ se
comporta como τ⇒⊥: la introducción descarga τ
llegando a una contradicción, y la eliminación produce una a partir de
¬τ y τ.
Reglas admisibles
Se derivan de las anteriores: no agregan poder al sistema, sólo acortan la
demostración. Aparecen en el panel después de un separador.
- ¬¬i: de Γ⊢τ se deduce Γ⊢¬¬τ.
(La dirección inversa, ¬¬e, no es válida acá: es clásica, no
intuicionista.)
- MT (modus tollens): de Γ⊢τ⇒σ
y Γ⊢¬σ se deduce Γ⊢¬τ.
Convenciones
- Las metavariables son letras griegas minúsculas — τ, σ, ρ
para fórmulas — y Γ para el contexto.
- Los símbolos proposicionales son letras latinas (A–Z, a–z); ⊥
es la contradicción (falso).
- La implicación se escribe ⇒ (también se acepta
=> al escribirla) y
asocia a derecha: τ⇒σ⇒ρ es
τ⇒(σ⇒ρ). Liga más débil que
∧ y ∨.
- La negación ¬ (también
~) es prefija y liga más fuerte que todos
los conectivos binarios: ¬τ∧σ es
(¬τ)∧σ.
- El contexto puede estar vacío: se escribe dejando el turnstile sin nada a
la izquierda, ⊢τ. Al agregarle hipótesis el vacío desaparece de la
notación: ⇒i sobre ⊢p⇒q deja
p⊢q. Con el contexto vacío ax nunca cierra: no hay
ninguna hipótesis a la que apelar.
- El contexto Γ es un conjunto de fórmulas. La pertenencia
τ∈Γ sólo se decide cuando el contexto es concreto; si todavía
tiene incógnitas, el axioma aún no puede cerrar la meta.
Lógica clásica (NK)
Los mismos juicios, conectivos y convenciones que la lógica intuicionista
(NJ), más una sola regla: la eliminación de la doble negación. Esa regla es toda
la diferencia entre los dos sistemas.
La regla que se agrega
- ¬¬e: de Γ⊢¬¬τ se deduce Γ⊢τ.
NJ tiene la introducción (¬¬i) pero no la vuelta: para un
intuicionista, saber que τ no puede ser falsa no alcanza para exhibir
una prueba de τ.
El resto —ax, ⊥e, las reglas de ∧, ∨, ⇒
y ¬— es exactamente el de NJ.
Reglas admisibles
A las de NJ (¬¬i, MT) se suman dos que se derivan de
¬¬e, y que por eso no existen en NJ:
- PBC (reducción al absurdo): si Γ,¬τ⊢⊥,
entonces Γ⊢τ. Se supone lo contrario de lo que se quiere
probar y se llega a una contradicción.
- LEM (tercero excluido): Γ⊢τ∨¬τ, sin
premisas. Toda fórmula es verdadera o falsa, aunque no sepamos cuál.