z) z (z>x)
Formula honetan x-ren lehenengo agerpena atxekia da eta hirugarrena librea,
eta z-ren lehenengoa librea eta bigarrena atxekia; hortaz, bai x, bai z aldagai
libreak dira.
b) z (z>0 z
Kasu honetan z-ren bi agerpenak atxekiak dira eta x-rena, berriz, librea.
Beraz, z aldagai atxekia da eta x librea.
3.2. LENGOAIAREN SEMANTIKA
Lengoaiaren semantikak gaien eta formulen esanahia definitzen du. Gaiek eta
formulek esanahirik eduki dezaten, ezinbestekoa da aldagaiek balio zehatzak hartzea. Balio
hauek, landuko dugun alorrean, programaren exekuzioko instant konkretu batean aldagaiek
dituztenak dira, konputazio-egoerari dagozkionak, alegia. Horregatik semantikaren
formalizazioari ekin aurretik konputazio-egoera modu zehatzago batez definituko dugu.
S konputazio-egoera funtzio bat da, non:
. Eremua aldagai-identifikadoreen multzoa den,
. Heina aldagai guztien moten heinen bildura den eta
. Aldagai bakoitzari bere motako balio bat egokitzen zaion.
Lehen mailako logikaren lengoaia ___________________________________________ 29
Egoera funtzioa bikote-multzo batez adieraziko dugu aurrerantzean, bikote
bakoitzak aldagai-identifikadore bat eta honi egokitutako balioa dituela.
3.2. adibidea: Ondorengo programak a eta b zenbaki oso ez-negatiboen batura
kalkulatzen du, baten gehiketa eta baten kenketaz aparteko eragiketarik erabili gabe:
begin
x: = a; y : = b;
while y > 0 do
begin (*)
x:=x+1;
y:=y-1
end
end
Programa honen bukaeran gerta litezkeen egoera batzuk hauek lirateke:
{(a,7), (b,3), (x,10), (y,0)}
{(a,0), (b,5), (x,5), (y,0)}
(*) seinaleaz markatutako kontrol-puntuko egoera posible batzuk:
{(a,7), (b,3), (x,8), (y,2)}
{(a,7), (b,3), (x,9), (y,1)}
Ondorengoak, aitzitik, (*) puntuan gerta ezinezkoak dira:
{(a,7), (b,3), (x,6), (y,4)}
{(a,7), (b,3), (x,8), (y,4)}
{(a,7), (b,3), (x,9), (y,1)}
Egoera aldatu ere egin daiteke, bai (aldagaia, balioa) bikote berri bat erantsiz, bai
aldagai bati balio zaharraren ordez beste berri bat egokituz. Edozein modutan ere, S egoeran
x aldagaiari b balioa egokituz sortzen den egoera berria S[b/x] notazioaz adieraziko dugu.
Lehen mailako formula bat, , S egoeran ondo definituta dagoela esaten da, baldin
eta -ko aldagai libreen identifikadore bakoitzari Sn bere motako balioren bat badagokio.
Gaien eta formulen balioztapena soilik ondo definituta dauden egoeretan burutu daiteke.
Ikus dezagun, bada, gaiak eta formulak nola balioztatzen diren.
30 _____________________________________________________________________
Gaien balioztapena S egoeran
a) S (konstantea) = konstantea.
b) S (aldagaia) = S egoeran aldagaiari dagokion balioa.
c) S (f (t1, ..., tn)) = f (S (t1), ...,S (tn))
Formulen balioztapena S egoeran
d) S P t1,t2,L,tn( )( )=
true baldin P S t1( ),L,S tn( )( )= true
false bestela
Egin kontu konstanteak, funtzioak eta predikatuak ez direla interpretatzen, ikur
interpretagarriak izan ordez, aldez aurretiko interpretazio standard ezaguna bait dute.
e)
S ¬( )=
true baldin S ( )= false
false baldin S ( )= true
S ( )=
true baldin S ( )=S ( )= true
false bestela
S ( )=
true baldin S ( )= true edo S ( )= true
false bestela
S ( )=
true baldin S ( )= false edo S ( )= true
false bestela
S ( )=
true baldin S ( )=S ( )
false bestela
f)
S x( )=
true baldin x - ren motako a balioren bat existitzen bada, non
S a / x( ) ( )= true
false bestela
S x( )=
true baldin x - ren motako edozein a baliorentzat
S a / x( ) ( )= true betetzen bada
false bestela
Lehen mailako logikaren lengoaia ___________________________________________ 31
3.3. adibidea: Adibide honetako edozein aldagairen eremua zenbaki osoen multzoa dela
suposatuko dugu.
- Izan bedi S1 = {(x,4)} egoera, S1(y z (y*z = x y = z)) = true izango da, zeren
eta
S1(yz = x y = z)y,z
2,2
= S1(2*2 = x 2 = 2) =
(2*2 = 4 2 = 2) = true bait da.
- Izan bedi S2 = {(y,1), (z,2)} egoera, S2(x (x > 0 z*x > y)) = true izango da,
S2 (x > o 2x > 1)x
a
= true bait da edozein a zenbakirentzat (betiere osoen
eremuan).
- Azkenik, izan bedi S3 = {(y,2), (z,1)}, S3( x(x > 0 z*x > y)) = false da,
S3(x>0 2x>2)= (1 > 0 2 > 2) = false bait da.
Gure helburua programen kontrol-puntuetan gertatzen diren egoera-multzoak
formulen bidez adieraztea da, nolabait konputazio-egoeren ezaugarri komunak dira agerian
uzten direnak. Testuinguru honetan erabilitako formulei asertzio deitzen zaie.
Asertzio batek egiazkoa deneko egoera-multzoa errepresentatzen du (egoera-multzo
hau infinitua izan daiteke). Hortaz, T-k egoera-multzo osoa errepresentatzen du eta F-k
egoera-multzo hutsa. Esate baterako, programaren puntu batean x aldagaiak zenbaki lehen
bat duela esan nahi bagenu, asertzioa honako hau litzateke:
lehena_da (x) = x 2 yz(x = y*z (y=1 v y =x))
3.4. adibidea: 3.2 adibidean azaldutako programak asertzio hauek edukiko lituzke:
begin {x,y0}
x: = a; y : = b; { x=a y=b x,y0}
while y > 0 do
begin {x+y=a+b xa0 0
x:=x+1; y:=y-1
end
end; {x=a+b y=0 x,a,b0}
formula baino gogorragoa dela esaten da -k errepresentatzen duen egoera-
multzoa -k errepresentatzen duenaren partea bada. Kasu honetan baino ahulagoa dela
esaten da. Formula gogorragoek murriztapen gehiago ezartzen diete beren aldagai libreei.
Honen arabera erraz konpreni daiteke "true" beste edozein formula baino ahulagoa dela eta
"false" dela formularik gogorrena. formula baino gogorragoa baldin bada, orduan
S()=true izango da edozein S egoeratan.
32 _____________________________________________________________________
3.5. adibidea: Formula gogorrago eta ahulagoak:
(a) (x=5 z=25) z=x2
(b) (x=A[i] 1in) k(x=A[k] 1kn)
(c) k(xkz A[k]p) A[(x+z) div 2]p
(d) false , edozein -rentzat
(e) true , edozein -rentzat
Eta, azkenik, programen egiaztapenerako berebizikoa den eragiketa batez arituko
gara, aldibereko ordezpenaz.
Izan bitez formula, x aldagaia eta t gaia, formulan x-ren agerpen libre guztiak t
gaiaz ordeztu ondoren lortutako formula honela denotatuko dugu: x
t
Batzuetan, -n lehendik ere bazegoen aldagairen bat t gaian ageri denean, ordezpena
egitean aldagai-talka gertatzen da. Aldagai-talkarik gertatzen ez denean -k x-ri buruz eta
x
t
k t-ri buruz gauza bera diote. Hau ezin daiteke baieztatu, ordea, talkarik gertatzen bada.
3.6. adibidea: Izan bedi =(z (1
gainean egindako ordezpenak:
a) x
5
= z (1
b) x
A[i]
= z (1
c) d
d+1
= z (1
d) d
x
= z (1
e) x
x·z
= z (1
a), b) eta c) adibideetan ez da formulen esanahia aldatzen (gaiak bai, baina gaiei
buruzkoa ez). Aldiz, d) eta e) adibideetan formulen semantika erabat aldatzen da, talken
kariaz.
Era berean, x1, ..., xn aldagaiak eta t1, ..., tn gaiak emanez gero, xi (1in) aldagai
guztiak ti (1in) gaiez aldi berean ordeztuta lortzen den formula x1 ,x2 ,...,xn
t1 ,t2 ,...,tn
formaz
idazten da.
Aldagai-talkari buruzkoak kasu honetan ere badu zentzurik.
Lehen mailako logikaren lengoaia ___________________________________________ 33
3.7. adibidea: Izan bedi = 1in A[i]=x z (1z
a) i,x
3,'a'
= 13n A[3]='a' z (1z<3 A[z]'a')
b) i,x
i+1,A[i]
= 1i+1n A[i+1]=A[i] z (1z
a) adibidean ez dago aldagai-talkarik, baina b)-n bai.
eta x
t
formulak parekoak izango dira, baldin eta formulan x-ren agerpen
libreak eta x
t
formulan t-ren agerpen libreak leku berdinetan gertatzen badira (gai baten
agerpena librea da bere aldagai guztiak libreak badira).
Bi formula baliokideak dira egoera-multzo bera errepresentatzen badute, hau da, biek
gauza bera baieztatzen badute.
eta x
z
parekoak badira, orduan x eta zx
z
eta, era berean, x eta zx
z
formulak elkarren baliokideak dira. t gaia f(z) erako funtzioa denean ere gauza bera
gertatzen da. Hortaz, ordezpenak talkarik sortzen ez duenean, formulen kuantifikazioak
baliokideak dira.
3.8. adibidea:
a) Izan bedi = x > 0 s (s z),
x eta z(x
z
)= z (z > 0 s (s z)) ez dira baliokideak baina
x eta p (x
p
) = p (p > 0 s (s z)) baliokideak dira.
b) Izan bedi formula, x1, ..., xi sekuentziaren batura S dela baieztatzen duena:
i S= xj
j=1
i
eta i S= xj
j=1
i+1
baliokideak dira
i eta i i
i+1
erakoak dira, hurrenez hurren.
c) i (1in x=A[i]) eta i (1i+1n x=A[i+1]) formulak ere baliokideak
dira.
34 _____________________________________________________________________
Ariketak
3.1. Idatzi ondoko baieztapenak lehen mailako formulez:
- Osozko A[1..n] array-aren i-garren elementuaren ondoren dauden guztiak zeroak
dira.
- A[1..n] array-an x badago, i..j sekzioan egongo da.
- A[1..n]-k bi zero dauzka.
- i posizioak A[1..n] array-a erdibitu egiten du, x baino txikiagoak batetik eta x
baino handiagoak bestetik.
- f karaktere-fitxategian ez daude bi txurigune jarraian.
- A[1..n] array-ak badauka zehazki k zerotako sekzio bat.
- S[1..n] eta A[1..m] array-ek amankomunean dituzten elProgramen egiaztapena eta eratorpena