Tartalom
Ebben a fejezetben azzal foglakozunk, hogy hogyan lehet meglevő programokból új programokat készíteni. Természetesen sokféleképpen konstruálhatunk meglevő programjainkból új programokat, de most csak háromféle konstrukciós műveletet fogunk megengedni: a szekvencia-, elágazás- és ciklusképzést. Később megmutatjuk, hogy ez a három konstrukciós művelet elegendő is. Nemcsak definiáljuk ezeket a konsrukciókat, de megvizsgáljuk programfüggvényüket és leggyengébb előfeltételüket is.
Az első definíció arról szól, hogy egy programot közvetlenül egy másik után
végezzünk el. A definícióban használni fogjuk a következő jelölést: legyen
,
,
7.1. Definíció (SZEKVENCIA).
Legyenek
programok. Az
relációt az
és
szekvenciájának nevezzük, és
-vel jelöljük, ha
:
Vegyük észre, hogy ha két olyan program szekvenciáját képezzük, amelyek értékkészlete csak véges sorozatokat tartalmaz, akkor a szekvencia is csak véges sorozatokat rendel az állapottér pontjaihoz.
Hasonlóan egyszerűen ellenőrizhető az is, hogy determinisztikus programok szekvenciája is determinisztikus reláció (függvény).
A programkonstrukciókat szerkezeti ábrákkal, úgynevezett struktogramokkal szoktuk ábrázolni.
Legyenek ,
programok
-n. Ekkor
az
szekvencia struktogramja:
A második konstrukciós lehetőségünk az, hogy más-más meglevő programot hajtsunk végre bizonyos feltételektől függően.
7.2. Definíció (ELáGAZáS).
Legyenek
feltételek,
programok
-n. Ekkor az
relációt az
-kből képzett
-k által meghatározott elágazásnak nevezzük és
-nel jelöljük, ha
:
ahol
:
Az elágazás definíciójában nem kötöttük ki, hogy a feltételek diszjunktak, tehát az állapottér egy pontjában több feltétel is igaz lehet, ebben az esetben az elágazás az összes olyan sorozatot hozzárendeli ehhez a ponthoz, amit legalább egy olyan program, aminek a feltételrésze ebben a pontban igaz. Ezért haa a feltételek nem diszjunktak, akkor a determinisztikus programokból képzett elágazás lehet nem determinisztikus is.
Ha csak olyan programokból képzünk elágazást, amik csak véges sorozatokat rendelnek az állapottér minden pontjához, az elágazás akkor is rendelhet (azonos elemekből álló) végtelen sorozatot, ha a feltételek igazsághalmazai nem fedik le az egész állapotteret.
Megjegyezzük, hogy a definíció szerint, ha egy pontban egyik feltétel sem teljesül, az elágazás "elszáll", ellentétben a legtöbb gyakorlatilag használt programnyelvvel.
Legyenek programok,
feltételek
-n. Ekkor az
elágazás struktogramja:
A harmadik konstrukciós lehetőségünk az, hogy egy meglevő programot egy feltételtől függően valahányszor egymás után végrehajtsunk. A ciklus definálásához szükségünk van további két jelölésre: véges sok, illetve végtelen sok sorozat konkatenációjának redukáltjára.
Legyenek és
,
Legyenek ,
7.3. Definíció (CIKLUS).
Legyen
feltétel és
program
-n. A
relációt az
-ból a
feltétellel képzett ciklusnak nevezzük, és
-lal jelöljük, ha
:
:
Első ránézésre a definíció kissé bonyolult. Nézzük meg alaposabban!
A defifícó alapján nyílvánvaló, hogy a determinisztikus programból képzett ciklus is determinisztikus lesz.
Ezzel ellentétben, ha egy csak véges sorozatokat rendelő programot foglalunk ciklusba, akkor a ciklus értékkészlete még tartalmazhat végtelen sorozatot (ha soha nem jutunk ki a feltétel igazsághalmazából).
Legyen
program,
feltétel
-n.
Ekkor a
ciklus struktogramja:
A fentiekben leírt konstrukciókat programokra lehet alkalmazni. De vajon
programokat hoznak-e létre? Az alábbi tétel kimondja, hogy az előzőkben definiált
három konstrukciós művelet meglevő programokból valóban programokat hoz
létre.
7.1. TéTEL: A SZEKVENCIA, AZ ELáGAZáS éS A CIKLUS PROGRAM.
Legyen tetszőleges
állapottér,
programok, valamint
feltételek
-n. Ekkor
programok -n.
Bizonyítás: Mindhárom konstrukció definíciójában explicit szerepel, hogy reláció
-on,
és
,
azaz teljesül a program definíciójának első pontja. A továbbiakban esetekre bontva
megvizsgáljuk a másik két kritérium teljesülését.
Legyen
tetszőleges, és
. Ekkor két eset lehetséges:
Ha és ebben az esetben
és
triviálisan teljesül, hiszen
program.
Ha úgy, hogy
és
. Ekkor a
definíciója miatt
redukált. Másrészt
, tehát
.
Legyen
tetszőleges, és
. Ekkor
Tegyük fel, hogy . Ekkor
, tehát teljesíti a program definíciójának kritériumait.
Tegyük fel, hogy . Ekkor
, így mivel
program,
teljesíti a definícióban megkívánt tulajdonságokat.
Legyen
tetszőleges, és
.
Tegyük fel, hogy . Ekkor
, így az előírt tulajdonságok triviálisan teljesülnek.
Tegyük fel, hogy . Ekkor három eset lehetséges:
_