Az informatika logikai alapjai

6 A bináris és hexadecimális számok közötti kapcsolat (4 bit!):
A B C D E F

Az informatika alapjai

Az előadások a következő témára: “Az informatika alapjai”— Előadás másolata:

1 Az informatika alapjai

2 A számítógép mint adatfeldolgozó eszköz
Adat: az objektumok mérhető és nem mérhető tulajdonságai. Ismeret: az összefüggéseiben látott adathalmaz, tény. Információ: azok az új adatok, amelyek összefüggéseikkel együtt beépülnek ismereteinkbe.

3 Számrendszerek A számrendszerek kialakulása.
A tízes (decimális) számrendszer: 0 … 9. 123.45 1*102+2*101+3*100+4*10-1+5*10-2 anan-1…a1a0a-1a-2…a-m ni=-mai*10i

4 Tetszőleges p>1alapszám esetén:
ni=-mai*pi Jelkészlet: 0 … p-1. Adott számú pozíción egy számrendszerben leírható legnagyobb és legkisebb szám?

5 A számítástechnikában használatos számrendszerek
Kettes (bináris) számrendszer: 0 1 (A számítógépes információtárolás alapegysége a bit, ami ezt a két értéket veheti fel.) Tizenhatos (hexadecimális) számrendszer: 0 … 9 A …F

6 A bináris és hexadecimális számok közötti kapcsolat (4 bit!):
A B C D E F

7 Feladatok: Számoljuk át tízes számrendszerbe az alábbi számokat: ; ; 1A9.DB16. Írjuk át kettes számrendszerbe a tizenhatos számrendszerbeli, illetve tizenhatos számrendszerbe a kettes számrendszerbeli számokat: BABA16 ; ABBA16 ; DADA16 ; ECCE16 ; ;

8 Írjuk fel bináris számrendszerben az alábbi decimális számokat: 3492
Írjuk fel hexadecimális számrendszerben az alábbi decimális számokat: ; ; ; 9977.

9 Aritmetikai műveletek különböző számrendszerekben
Végezzük el az alábbi műveleteket a bináris számok körében:

10 Végezzük el az alábbi műveleteket a hexadecimális számok körében:
ABCD.EF CCC.CC A + DDD.DD A 1AB2C AAA.AA – AB3C AA.AB

11 Adatábrázolás a számítógépen
Az adat gépi formája bitsorozat, tárolásának alapegysége a 8 bitből álló byte. Az adattárolás két módja: – gépi számábrázolás (műveletvégzés); – kódolt ábrázolás.

12 Számábrázolás Fixpontos. (Egyes, kettes komplemens.)
Lebegőpontos. (szám=M*pk, ahol 1/p < M < 1 és M:mantissza; p:alap; k:karakterisztika.)

13 Kódolt ábrázolás Binárisan kódolt decimális számábrázolás: Pakolt:
9613 —> (2 byte) Pakolatlan (1 karakter=1 byte): 9613 —> (4 byte)

14 Nem-numerikus karakterek:
A gyakorlatban legelterjedtebb a kiterjesztett ASCII (American Standard Code for Information Interchange) kód használata. 1 byte=1 karakter 28=256 128 (standard)+128 (speciális, kódlap)

15 ASCII stands for American Standard Code for Information Interchange
ASCII stands for American Standard Code for Information Interchange. Computers can only understand numbers, so an ASCII code is the numerical representation of a character such as ‘a’ or or an action of some sort. ASCII was developed a long time ago and now the non-printing characters are rarely used for their original purpose. Below is the ASCII character table and this includes descriptions of the first 32 non-printing characters. ASCII was actually designed for use with teletypes and so the descriptions are somewhat obscure. If someone says they want your CV however in ASCII format, all this means is they want ‘plain’ text with no formatting such as tabs, bold or underscoring – the raw format that any computer can understand. This is usually so they can easily import the file into their own applications without issues. Notepad.exe creates ASCII text, or in MS Word you can save a file as ‘text only’

16 Extended ASCII Codes As people gradually required computers to understand additional characters and non-printing characters the ASCII set became restrictive. As with most technology, it took a while to get a single standard for these extra characters and hence there are few varying ‘extended’ sets. The most popular is presented below.

17 Műveletek a számítógépen
Aritmetikai műveletek: összeadás. Relációs műveletek: összehasonlítás. Logikai műveletek. Az igazságtáblák: NOT AND OR XOR 1

Az informatika logikai alapjai

1 Az informatika logikai alapjai Várterész Magda DE, Informatikai Kar PTI BSc és informatikatanár hallgatók számára 2017.

2 Példák Az alábbi világokban állításokat akarunk megfogalmazni: A táblára színes karikákat rajzoltak körbe egymás mellé gyerekek. Alma karikája zöld. Botond karikája Alma karikája mellett van. Van a táblán zöld karika. Nem minden karika zöld. Van olyan zöld karika, amelyik mellett nincs zöld karika. A természetes számokkal számlálunk, összeadunk, szorzunk, és eldöntjük, egyenlőek-e. Kétszer egy az egyenlő egy meg egy. Egy szám kétszerese egyenlő a szám önmagával való összegével. Van olyan szám, amelyiknek önmagával való szorzata egyenlő az önmagával való összegével. A 0 a legkisebb természetes szám.

3 Példák Az elemi geomtria térbeli világában pontok, egyenesek és síkok vannak. Két pont egybeeshet, egy pont rajta lehet egy egyenesen, vagy egy síkon. Bármely két különbözõ pontra pontosan egy egyenes illeszthető. Az egyetem Neptun rendszerében beszélhetünk hallgatókról, oktatókról, kurzusokról, stb. A hallgató egy-egy félévben kurzusokat vehet fel, és teljesítheti ezek követelményeit. A kurzusoknak előfeltételei vannak. Egy hallgató csak akkor veheti fel a mesterséges intelligencia kurzust, ha már teljesítette a logika kurzust.

4 Az ábécé 1 Egy elsőrendű logikai nyelv ábécéjének logikán kívüli szimbólumai megadhatók Srt, Pr, Fn, Cnst alakban. Srt nemüres halmaz, elemei fajtákat szimbolizálnak. Pr nemüres halmaz, elemei predikátumszimbólumok. Minden predikátumszimbólumhoz tartozik egy (π 1, π 2. π k ) fajtasorozat, a predikátumszimbólum alakja. Az Fn halmaz elemei függvényszimbólumok. Minden függvényszimbólumhoz tartozik egy (π 1, π 2. π k, π) fajtasorozat, a függvényszimbólum alakja. Cnst pedig a konstansszimbólumok halmaza. Minden konstansszimbólumhoz tartozik egy (π) fajta, a konstansszimbólum fajtája.

5 Az ábécé 2 Az elsőrendű logikai nyelv ábécéjének logikai jelei a logikai összekötőjelek. a kvantorok:, és a különböző fajtájú (individuum)változók. Minden π Srt fajtához szimbólumoknak megszámlálhatóan végtelen v π 1, v π 2. rendszere tartozik, ezeket a szimbólumokat nevezzük π fajtájú változóknak. Használunk még elválasztójeleket: ( ), (zárójelek, vessző).

6 A termek 1 Minden π Srt fajtájú változó és konstans π fajtájú term. 2 Ha az f Fn függvényszimbólum (π 1, π 2. π k, π) alakú és t 1, t 2. t k rendre π 1, π 2. π k fajtájú termek, akkor az f (t 1, t 2. t k ) szó egy π fajtájú term. 3 Minden term az 1 2. szabályok véges sokszori alkalmazásával áll elő.

7 Az elsőrendű formulák 1 Ha a P Pr predikátumszimbólum (π 1, π 2. π k ) alakú és t 1, t 2. t k rendre π 1, π 2. π k fajtájú termek, akkor a P(t 1, t 2. t k ) szó egy elsőrendű formula. Az így nyert formulákat atomi formuláknak nevezzük. 2 Ha A elsőrendű formula, akkor A is az. 3 Ha A és B elsőrendű formulák és , akkor (A B) is elsőrendű formula. 4 Ha A elsőrendű formula, Θ kvantor és x tetszőleges változó, akkor ΘxA is elsőrendű formula. Az így nyert formulákat kvantált formuláknak nevezzük. 5 Minden elsőrendű formula az 1 4. szabályok véges sokszori alkalmazásával áll elő.

8 A szerkezeti indukció elve termekre Ahhoz, hogy igazoltnak tekintsük, hogy egy rögzített ábécé feletti ítéletlogikai nyelv minden termje T tulajdonságú, elég belátni a következőket: (alaplépés:) Minden változó és konstansszimbólum T tulajdonságú. (indukciós lépés:) Ha a t 1, t 2. t k termek T tulajdonságúak, akkor az f függvényszimbólum felhasználásával előállított f (t 1, t 2. t k ) term is T tulajdonságú.

9 A szerkezeti indukció elve formulákra Ahhoz, hogy igazoltnak tekintsük, hogy egy elsőrendű logikai nyelv minden formulája T tulajdonságú, elég belátni a következőket: (alaplépés:) Minden atomi formula T tulajdonságú. (indukciós lépések:) (i 1 ) Ha az A formula T tulajdonságú, akkor A is T tulajdonságú. (i 2 ) Ha az A és a B formulák T tulajdonságúak és , akkor (A B) is T tulajdonságú. (i 3 ) Ha az A formula T tulajdonságú, Θ kvantor és x individuumváltozó, akkor ΘxA is T tulajdonságú.

10 Az egyértelmű elemzés Az elsőrendű logikai nyelv ábécéje feletti minden szóra a következő állítások közül pontosan egy igaz. 1 A szó egy individuumváltozó (term). 2 A szó egy konstansszimbólum (term). 3 A szó az egyértelműen meghatározható t 1, t 2. t k termekből és az f függvényszimbólumból előállított f (t 1, t 2. t k ) alakú term. 4 A szó az egyértelműen meghatározható t 1, t 2. t k termekől és a P predikátumszimbólumból előállított P(t 1, t 2. t k ) alakú atomi formula. 5 A szó egy egyértelműen meghatározható formula negáltja. 6 A szó az egyértelműen meghatározható A és B formulákból és logikai összekötő jelből előállított (A B) alakú formula. 7 A szó az egyértelműen meghatározható A formulából, Θ kvantorból és x változóból előállított ΘxA alakú formula.

11 Logikai kifejezés közvetlen részkifejezései Egyetlen konstansszimbólum termnek és változó termnek sincs közvetlen résztermje. Az f (t 1, t 2. t k ) alakú term közvetlen résztermjei a t 1, t 2. t k termek. Az atomi formuláknak nincs közvetlen részformulája. A A alakú formula egyetlen közvetlen részformulája az A formula. Az (A B) alakú formula közvetlen részformulái az A és a B formulák. A ΘxA alakú formula közvetlen részformulája az A formula.

12 Logikai kifejezés részkifejezéseinek a halmaza Egy term résztermjeinek halmaza a legszűkebb olyan halmaz, melynek maga a term eleme és ha egy term eleme, akkor eleme a term összes közvetlen résztermje is. Egy formula részformuláinak halmaza a legszűkebb olyan halmaz, melynek maga a formula eleme és ha egy formula eleme, akkor eleme a formula összes közvetlen részformulája is.

13 A szerkezeti rekurzió elve termekre Pontosan egy olyan, az elsőrendű logikai nyelv termjein értelmezett F függvény van, melynek (alaplépés:) értékeit rögzítjük a nyelv változóin és konstansain, majd megmondjuk, hogy F értéke (indukciós lépések:) az f (t 1, t 2. t k ) termre a t 1, t 2. t k termeken felvett értékeiből hogyan származtatható.

14 A szerkezeti rekurzió elve formulákra Pontosan egy olyan, az elsőrendű logikai nyelv formuláin értelmezett F függvény van, melynek (alaplépés:) értékeit rögzítjük a nyelv atomi formuláin és megmondjuk, hogy F értéke (indukciós lépések:) (r 1 ) a A formulára az A-n felvett értékéből, (r 2 ) az (A B) formulára az A-n és a B-n felvett értékeiből, illetve (r 3 ) a ΘxA formulára az A-n felvett értékéből hogyan származtatható.

15 Term összetettsége Határozzuk meg a l: L t N 0 függvényt a következőképpen: ha t változó vagy konstansszimbólum, l(t) legyen 0, l(f (t 1, t 2. t k )) legyen l(t 1 ) + l(t 2 ) l(t k ) + 1. Ekkor a t L t termhez rendelt l(t) függvényértéket a t term (funkcionális) összetettségének nevezzük.

16 Formula összetettsége Határozzuk meg a l: L f N 0 függvényt a következőképpen: ha A atomi formula, l(a) legyen 0, l( A) legyen l(a) + 1, l(a B) legyen l(a) + l(b) + 1, l(θxa) pedig legyen l(a) + 1. Ekkor az A L f formulához rendelt l(a) függvényértéket az A formula (logikai) összetettségének nevezzük.

17 Hatáskör, zárójelhasználat Az ítéletlogikában definiáltuk a logikai összekötőjel hatáskörének és a fő logikai összekötőjelnek a fogalmát. A fogalmak változtatás nélkül kiterjeszthetők a kvantorokra is. Egészítsük ki a logikai összekötőjelek közötti erősorrendet azzal, hogy a kvantorokat is besoroljuk. A prioritás csökkenő sorrendben: , ,, . Azokat a zárójeleket, melyek ezt a sorrendet jelölnék ki, elhagyhatjuk.

18 Példa ábécére Most megadunk ábécét egy elsőrendű logikai nyelvhez. , , , , ahol a szimbólumok az alábbi alakúak: P (π 1 ) f (π 1, π 2, π 2 ) c (π 1 ) Q (π 1, π 2 ) R (π 2, π 2 ) Legyenek továbbá x, y, z. π 1 fajtájú változók, x, ỹ, z. pedig π 2 fajtájú változók.

19 Példa termekre és formulákra Az előbb megadott ábécé feletti elsőrendű nyelvben elkészítünk néhány termet és formulát. π 1 fajtájú termek: c, x, y. π 2 fajtájú termek: x, f (c, x), f (x, f (c, x)). atomi formulák: P(x), Q(y, x), R(f (c, x), f (x, f (c, x))). formulák: x xq(y, x), ( xq(y, x) xr(f (c, x), f (c, x))).

20 Példa részkifejezésekre Az f (x, f (c, x)) term közvetlen résztermjei: x és f (c, x), résztermjeinek halmaza: . A x xq(y, x) formula egyetlen közvetlen részformulája: xq(y, x), részformuláinak halmaza: < x xq(y, x), xq(y, x), xq(y, x), Q(y, x)>.