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 i (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 zawiera i
      • lub też ogólniej dla każdego koniunkcyjnego operatora binarnego zawiera i
    • dla każdego zawiera lub (lub też oba)
    • dla każdego zawiera
    • dla każdego zawiera wszystkie formuły powstałe przez podstawienie dowolnych formuł pod w
      • dla każdego zawiera wszystkie formuły powstałe przez podstawienie dowolnych formuł pod w
    • dla każdego zawiera przynajmniej jedną formułę powstałą przez podstawienie pewnej formuły pod w
      • dla każdego zawiera przynajmniej jedną formułę powstałą przez podstawienie pewnej formuły pod w
    • 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 nie wiemy czy należy dodać czy też widząc 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.

Dowód twierdzenia Hintikki dla rachunku zdań

Niech głębokość formuły wynosi 0 dla zmiennych zdaniowych, dla innych formuł natomiast:

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 to można go znaleźć również dla formuł o głębokości Rozważmy więc dowolną formułę o głębokości zaś wraz z nią następujące przypadki:

  • jeśli formułą tą jest to należy do zbioru i ma głębokość Ponieważ mają one równe wartości dla każdego wartościowania, więc spełniona jest również
  • jeśli formułą tą jest to zarówno jak i mają głębokość co najwyżej i należą do zbioru Hintikki. Ponieważ zarówno jak i są spełnione, spełniona jest też
  • jeśli formułą tą jest to albo albo o głębokości równej co najwyżej 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

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

Zobacz też


Witaj

Uczę się języka hebrajskiego. Tutaj go sobie utrwalam.

Źródło

Zawartość tej strony pochodzi stąd.

Odsyłacze

Generator Margonem

Podziel się