EDB — 05Z

[05Z]Vogliamo riscrivere le tautologie viste in [00N]↺↻ sotto forma di relazioni insiemistiche.

Sia \(X\) un insieme e siano \(𝛼,𝛽,𝛾⊆ X\) sottoinsiemi. Sia \(x∈ X\). Se definiamo \(A=(x∈ 𝛼)\), \(B=(x∈ 𝛽)\), \(C=(x∈ 𝛾)\) nelle tautologie, potremo poi riscrivere la tautologia come una formula fra insiemi \(𝛼,𝛽,𝛾,X,∅\), che usi i connettivi \(=,∩,∪\) e il complementare.

Sorprendentemente, la riscrittura può essere effettuata algoritmicamente e in maniera puramente sintattica. Scegliete una tautologie vista in [00N]↺↻. Nel seguito \(𝜑,𝜓\) indicano sottoparti della tautologia che sono formule ben formate.

• Sostituite \(((𝜑) ⇒ (𝜓))\) con \(((¬(𝜑)) ∨ (𝜓))\) (otterrete un’altra tautologia).

• Poi sostituite sintatticamente \(¬ (𝜑)\) con \((𝜑)^ c\), \(∨\) con \(∪\) e \(∧\) con \(∩\); sostituite \(A\) con \(𝛼\), \(B\) con \(𝛽\), \(C\) con \(𝛾\), \(V\) con \(X\) e \(F\) con \(∅\).

• Infine, se la formula contiene almeno un “\(\iff \)”, trasformateli tutti in “\(=\)”; altrimenti aggiungete “\(=X\)” alla fine.

Verificate che questo “algoritmo” funziona davvero!