Zbiór Hintikki – Wikipedia, wolna encyklopedia

Zbiór Hintikki (ang. Hintikka set) to maksymalnie wysycony (ang. saturated) zbiór generowany przez pewien niesprzeczny zbiór formuł logicznych.

Zbiór taki:

• nie zawiera jednocześnie ${\displaystyle x}$ i ${\displaystyle \neg x}$ (wystarczy postawić ten warunek dla literałów, ponieważ rozszerza się on automatycznie na inne formuły)
• jest wysycony, czyli dla każdej formuły zawiera też:
  • dla każdego ${\displaystyle p\land q}$ zawiera ${\displaystyle p}$ i ${\displaystyle q}$
    • lub też ogólniej dla każdego koniunkcyjnego operatora binarnego ${\displaystyle \alpha }$ zawiera ${\displaystyle \alpha _{1}}$ i ${\displaystyle \alpha _{2}}$
  • dla każdego ${\displaystyle p\lor q}$ zawiera ${\displaystyle p}$ lub ${\displaystyle q}$ (lub też oba)
    • lub też ogólniej dla każdego dysjunkcyjnego operatora binarnego ${\displaystyle \beta }$ zawiera ${\displaystyle \beta _{1}}$ lub ${\displaystyle \beta _{2}}$
  • dla każdego ${\displaystyle \neg \neg x}$ zawiera ${\displaystyle x}$
  • dla każdego ${\displaystyle \forall x.\phi (x)}$ zawiera wszystkie formuły powstałe przez podstawienie dowolnych formuł pod ${\displaystyle x}$ w ${\displaystyle \phi (x)}$
    • dla każdego ${\displaystyle \neg \exists x.\phi (x)}$ zawiera wszystkie formuły powstałe przez podstawienie dowolnych formuł pod ${\displaystyle x}$ w ${\displaystyle \neg \phi (x)}$
  • dla każdego ${\displaystyle \exists x.\phi (x)}$ zawiera przynajmniej jedną formułę powstałą przez podstawienie pewnej formuły pod ${\displaystyle x}$ w ${\displaystyle \phi (x)}$
    • dla każdego ${\displaystyle \neg \forall x.\phi (x)}$ zawiera przynajmniej jedną formułę powstałą przez podstawienie pewnej formuły pod ${\displaystyle x}$ w ${\displaystyle \neg \phi (x)}$
  • podobnie dla wszystkich innych reguł rozpatrywanej logiki.

Jak widać, o ile dla formuł rachunku zdań zbiór Hintikki będzie skończony, to niekoniecznie będzie to miało miejsce dla formuł rachunku predykatów rzędu pierwszego i wyższych, gdyż kwantyfikator ogólny generuje nieskończoną ilość formuł.

Tworzenie zbioru Hintikki jest działaniem niedeterministycznym (widząc ${\displaystyle p\lor q}$ nie wiemy czy należy dodać ${\displaystyle p}$ czy też ${\displaystyle q,}$ widząc ${\displaystyle \exists x.\phi (x)}$ mamy nieskończoną liczbę możliwości), więc jest to twór raczej teoretyczny niż stosowany w informatyce.

Twierdzenie Hintikki (ang. Hintikka’s lemma) mówi, że jeśli istnieje zbiór Hintikki zawierający dane formuły, to istnieje też model, który je spełnia.

Niech głębokość formuły ${\displaystyle d(x)}$ wynosi 0 dla zmiennych zdaniowych, dla innych formuł natomiast:

${\displaystyle d(\neg \neg x)=1+d(x)}$

${\displaystyle d(\alpha )=1+\max(d(\alpha _{1}),d(\alpha _{1}))}$

${\displaystyle d(\beta )=1+\max(d(\beta _{1}),d(\beta _{1})).}$

Przeprowadzimy teraz indukcję strukturalną.
Ponieważ każda zmienna zdaniowa występuje tylko negatywnie lub tylko pozytywnie, możemy ustalić w modelu takie wartościowanie zmiennych zdaniowych, które nie przeczy żadnej formule o głębokości 0.

Jeśli model można znaleźć dla wszystkich formuł o głębokości ${\displaystyle n,}$ to można go znaleźć również dla formuł o głębokości ${\displaystyle n+1.}$ Rozważmy więc dowolną formułę o głębokości ${\displaystyle n+1,}$ zaś wraz z nią następujące przypadki:

• jeśli formułą tą jest ${\displaystyle \neg \neg x,}$ to ${\displaystyle x}$ należy do zbioru i ma głębokość ${\displaystyle n.}$ Ponieważ mają one równe wartości dla każdego wartościowania, więc spełniona jest również ${\displaystyle \neg \neg x.}$
• jeśli formułą tą jest ${\displaystyle \alpha ,}$ to zarówno ${\displaystyle \alpha _{1},}$ jak i ${\displaystyle \alpha _{2}}$ mają głębokość co najwyżej ${\displaystyle n}$ i należą do zbioru Hintikki. Ponieważ zarówno ${\displaystyle \alpha _{1},}$ jak i ${\displaystyle \alpha _{2}}$ są spełnione, spełniona jest też ${\displaystyle \alpha .}$
• jeśli formułą tą jest ${\displaystyle \beta ,}$ to albo ${\displaystyle \beta _{1}}$ albo ${\displaystyle \beta _{2}}$ o głębokości równej co najwyżej ${\displaystyle n}$ należą do zbioru Hintikki. Ponieważ która z nich należy do zbioru i jest spełniona, więc spełniona jest też formuła ${\displaystyle \beta .}$

Tak więc formuła dowolnej głębokości ze zbioru Hintikki jest spełniona przez nasz model, co kończy dowód.

• Jaakko Hintikka