Igazhalmaz

A Wikipédiából, a szabad enciklopédiából

Az igazhalmaz a matematikai logikában, konkrétan az elsőrendű logikában definiálható fogalom, formulák egy adott szemantikai osztályát jelenti. Ha adott valamely elsőrendű nyelv, ennek valamely I interpretációban adott k(I) kiértékelése, eme kiértékelés igazhalmaza a nyelv azon formuláinak halmaza, melyek az illető kiértékelésre nézve igazak.

Megjegyzés: ne keverjük össze e fogalmat egy formula igazsághalmazának fogalmával, mely nem formulák, hanem kiértékelések vagy individuumrendszerek halmaza.

Könnyű belátni, hogy az elsőrendű logikában az igaz halmaz és a telített halmaz fogalma egybeesik. Telített (ang. saturated) egy F formulahalmaz, ha

  1.  \lnot (A) \in \ F akkor és csak akkor teljesül, ha  A \not\in \ F
  2.  A \vee B \ \in \ F pontosan akkor teljesül, ha  A \in F vagy ha  B \in F ;
  3.  A \wedge B \ \in \ F pontosan akkor teljesül, ha  A \in F és  B \in F ;
  4.  A \rightarrow B \ \in \ F pontosan akkor teljesül, ha  \lnot (A) \in \ F vagy  B \in \ F (azaz, az első szabályt is figyelembe véve, ha  A \not\in \ F vagy  B \in \ F ).

A formulák szemantikus tulajdonságai az igazhalmazok segítségével is jellemezhetőek. Nem nehéz ugyanis belátni a következőket:

  • Egy formula logikai törvény, ha minden igazhalmaznak eleme;
  • Egy formula kielégíthető, ha valamelyik igazhalmaznak eleme;
  • Egy formula kielégíthetetlen (logikai ellentmondás), ha egy igazhalmaznak sem eleme;

Hiszen hogy logikai törvény, az pontosan azt jelenti, hogy minden interpretációban minden megengedett változókiértékelésre igaz, tehát hogy mindegyik kiértékelés igazhalmazának eleme, ha kielégíthető, az pontosan azt jelenti, hogy van olyan interpretációban olyan változókiértékelés, melyre a formula igaz, tehát hogy a formula eleme eme kiértékelés igazhalmazának; hogy kielégíthetetlen, az azt jelenti, hogy nincs olyan interpretáció, mely igazzá tenné, tehát olyan igazhalmaz sincs, melynek eleleme lenne.