Chapter 2. Bevezetés

Jelen tananyag olvasójáról feltesszük, hogy az elsőrendű logikai nyelv szintaxisával és klasszikus szemantikájával kapcsolatos alapvető fogalmakat és fontos tételeket ismeri. A könyvben használt fogalom-megnevezések és jelölések tisztázására röviden mégis sort kerítünk. A bevezető fejezet elolvasása egyúttal segíti a korábban tanult és jelen tankönyvben szükséges logikai ismeretek felidézését is. Logikai alapozó kurzusokon gyakran a többfajtájú elsőrendű logikai nyelv kerül bevezetésre. A logikai kalkulusokat ugyanakkor most egyfajtájú nyelv segítségével tárgyaljuk, így a bevezetésben sem esik szó a többfajtájú nyelvekről.

2.1. Az elsőrendű nyelv szintaxisa

Egy (egyfajtájú) elsőrendű logikai nyelv ábécéje először is tartalmaz ún. logikán kívüli betűket: ezeket a

Equation 2.. 


három halmazból álló rendszerrel adjuk meg.

  • a nyelv konstansszimbólumainak halmaza.

  • Az

    halmaz elemei függvényszimbólumok . Minden

    -hez tartozik egy

    természetes szám, az

    függvényszimbólum aritása.

  • A

    halmaz elemei predikátumszimbólumok . Minden

    -hez rendelünk egy

    természetes számot, a

    predikátumszimbólum aritását. A

    aritású predikátumszimbólumot propozicionális szimbólumnak (állítás szimbólumnak) is szoktuk nevezni.

Egy elsőrendű logikai nyelvben megszámlálhatóan végtelen sok (individuum)változó áll rendelkezésünkre:

(ezekre gyakran az

betűkkel hivatkozunk). Az ábécé tartalmaz még logikai jeleket: a

negáció ,

konjunkció ,

diszjunkció ,

implikáció összekötő jeleket és az

univerzális és

egzisztenciális kvantorokat . (A továbbiakban jelölje

mindig a

és a

logikai összekötő jelek valamelyikét,

pedig valamelyik kvantort.) Használhatjuk még a

zárójeleket és a vesszőt.

A

ábécé feletti elsőrendű logikai nyelv termek és formulák ( logikai kifejezések ) halmaza. A nyelv termjeinek halmaza az a legszűkebb

halmaz, melynek

  • minden konstansszimbólum (

    elemei) és változó eleme, és

  • ha

    egy

    aritású függvényszimbólum és

    elemei

    -nek (azaz termek), akkor az

    szó is eleme

    -nek (term).

A nyelv formuláinak halmaza az a legszűkebb

halmaz, melynek

  • minden

    alakú szó eleme (azaz formula, ún. atomi formula ), ha

    egy

    aritású predikátumszimbólum és

    rendre termek (elemei

    -nek), továbbá

  • ha

    és

    elemei

    -nek (formulák) és

    változó, akkor az

    alakú szavak szintén elemei

    -nek (formulák).

Egy elsőrendű logikai nyelvben egyetlen konstansnak és változónak sincs közvetlen résztermje , az

term közvetlen résztermjei pedig a

termek. Egy atomi formulának nincs közvetlen részformulája ,

egyetlen közvetlen részformulája

,

bal oldali közvetlen részformulája

, jobb oldali közvetlen részformulája

,

közvetlen részformulája

. (

-ban a

-re kvantoros előtagként hivatkozunk, és azt mondjuk, hogy ebben az előtagban a kvantor az

változót nevezi meg.)

Egy

term résztermjeinek halmaza a legszűkebb olyan halmaz, melynek

eleme, és ha egy term eleme, akkor eleme a term összes közvetlen résztermje is. Egy

formula részformuláinak halmaza az a legszűkebb halmaz, melynek

eleme, és ha egy formula eleme, akkor eleme a formula összes közvetlen részformulája is.

Konstansszimbólum és változó szerkezeti fája egyetlen, a szimbólumot tartalmazó csúcsból áll. Ez a csúcs a fa gyökere.

szerkezeti fájának gyökere

, a gyökér

darab gyermeke rendre

szerkezeti fáinak gyökerei. Atomi formula szerkezeti fája egyetlen ezt a formulát tartalmazó csúcsból áll, ami a fa gyökere.

szerkezeti fájának gyökere

, a gyökér egyetlen gyermeke az

szerkezeti fájának gyökere.

szerkezeti fájának gyökere

, a gyökér bal oldali gyermeke az

, jobb oldali gyermeke a

szerkezeti fájának gyökere.

szerkezeti fájának gyökere

, a gyökér egyetlen gyermeke az

szerkezeti fájának gyökere.

Legyenek az

és az

függvények a következők:

Equation 2.. 


Equation 2.. 


funkcionális összetettsége ,

logikai összetettsége .

Egy formulában egy logikai jel hatásköre a formulának azon részformulái közül a legkisebb logikai összetettségű, amelyekben az adott logikai jel is előfordul. Egy formula fő logikai jele az a logikai jel, melynek hatásköre maga a formula.

A formulák leírásakor használhatunk rövidítéseket. Például ha néhány formulából újabbat ugyanolyan módon gyakran készítünk, a szerkesztés módjára új (összekötő) jelet vezethetünk be. A külső zárójeleket elhagyhatjuk. A logikai összekötő jelekhez, a kvantorokhoz és a bevezetett jelekhez erősorrendet rendelhetünk. Ennek megfelelően, a jelek értelmezését a formulában az alábbi – az erősebbtől a gyengébb felé haladó – sorrendnek megfelelően végezzük el: 1. kvantorok (

,

), 2. negáció (

), 3. konjunkció (

) és diszjunkció (

), 4. implikáció (

), 5. bevezetett jelek.

Egy formulában egy változónak kétféle előfordulását különböztetjük meg. Az

változó egy adott előfordulása az

formulában kötött , ha egy, az

-et megnevező kvantor hatáskörében van. Az

változó előfordulása szabad , ha nem kötött. Egy kvantor a kvantoros előtagban megnevezett és a hatásköre közvetlen részformulájában ennek a változónak a még szabad előfordulásait tesz kötötté (köti). Egy változó-előfordulás kötöttségének meghatározása:

  • Egy atomi formulában minden változó-előfordulás szabad.

  • Az

    formulában egy változó-előfordulás pontosan akkor kötött, ha ez az előfordulás vagy

    -ban van és már

    -ban kötött, vagy

    -ben van és már

    -ben kötött.

  • A

    formulában egy változó-előfordulás pontosan akkor kötött, ha ez az előfordulás már

    -ban kötött.

  • A

    formulában

    minden előfordulása kötött. Ha

    egy előfordulása

    -ban még szabad volt, akkor ezt az előfordulást a

    formulában a

    kvantor köti. Egy, az

    -től különböző változó valamely előfordulása

    -ban pontosan akkor kötött, ha már

    -ban is kötött volt.

Egy változót a formula paraméterének nevezünk, ha van a formulában szabad előfordulása. Egy

formula paramétereinek a halmazára

-val hivatkozunk.

A

formulában a

kvantor által kötött

változó átnevezéséről beszélünk, amikor a

kvantoros előtagban

helyett egy másik, mondjuk

változót nevezünk meg, majd

-ban az

változó minden szabad előfordulását

-ra cseréljük ki (a kapott formulát jelöljük

-nal), és így a

formulát kapjuk. A

formulából szabályosan végrehajtott kötött változó átnevezéssel kapjuk a

formulát, ha

-ban az

nem paraméter, és az

változó egyetlen

által kötött előfordulása sem tartozik egyetlen

-t kötő kvantor hatáskörébe sem.

Az

formula az

formula variánsa (vagy

és

egymással kongruens formulák ) ha egymástól csak kötött változók szabályosan végrehajtott átnevezésében különböznek. Jelölése:

. Annak eldöntése, hogy két formula egymás variánsa-e:

  • Egy atomi formula csak önmagával kongruens.

  • pontosan akkor, ha

    és

    .

  • pontosan akkor, ha

    .

  • pontosan akkor, ha minden

    -re, mely különbözik

    és

    összes (kötött és szabad) változójától,

    .