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.
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
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:
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,
.
