Függvények
Teljes indukció
2. Logika gyakorlat Függvények és a teljes indukció Folláth János Debreceni Egyetem - Informatika Kar
2012/13. I. félév
Függvények
Teljes indukció
Áttekintés
1
Függvények Relációk Halmazok
2
Teljes indukció Természetes számok Formulák
Függvények
Definíció 1. Definíció Az f ⊆ A × B relációt függvénynek nevezzük, ha bármely x ∈ A, y ∈ B esetén, ha (x , y ) ∈ f és (x , z) ∈ f , akkor y = z. Ekkor a függvényt a következőképp jelöljük: f : A → B.
Teljes indukció
Függvények
Teljes indukció
Definíció 1. Definíció Az f ⊆ A × B relációt függvénynek nevezzük, ha bármely x ∈ A, y ∈ B esetén, ha (x , y ) ∈ f és (x , z) ∈ f , akkor y = z. Ekkor a függvényt a következőképp jelöljük: f : A → B. Lazábban fogalmazva az f ⊆ A × B relációt függvénynek nevezzük, ha bármely x ∈ A esetén egyértelműen létezik olyan y ∈ B, hogy (x , y ) ∈ f .
Függvények
Teljes indukció
Definíció 1. Definíció Az f ⊆ A × B relációt függvénynek nevezzük, ha bármely x ∈ A, y ∈ B esetén, ha (x , y ) ∈ f és (x , z) ∈ f , akkor y = z. Ekkor a függvényt a következőképp jelöljük: f : A → B. Lazábban fogalmazva az f ⊆ A × B relációt függvénynek nevezzük, ha bármely x ∈ A esetén egyértelműen létezik olyan y ∈ B, hogy (x , y ) ∈ f . Függvények esetén azt, hogy (x , y ) ∈ f úgy szokás jelölni, hogy f (x ) = y .
Függvények
Teljes indukció
Definíció 1. Definíció Az f ⊆ A × B relációt függvénynek nevezzük, ha bármely x ∈ A, y ∈ B esetén, ha (x , y ) ∈ f és (x , z) ∈ f , akkor y = z. Ekkor a függvényt a következőképp jelöljük: f : A → B. Lazábban fogalmazva az f ⊆ A × B relációt függvénynek nevezzük, ha bármely x ∈ A esetén egyértelműen létezik olyan y ∈ B, hogy (x , y ) ∈ f . Függvények esetén azt, hogy (x , y ) ∈ f úgy szokás jelölni, hogy f (x ) = y . FONTOS! Amíg kérdéses, hogy az adott reláció függvény-e avagy sem, szigorúan a (x , y ) ∈ f vagy az x f y jelölés használandó
Függvények
Teljes indukció
Példafeladat
1. Példa Függvény-e az alábbi reláció? Miért? f ⊆ N × N,
x f y ⇐⇒
x
Függvények
Teljes indukció
Példafeladat
1. Példa Függvény-e az alábbi reláció? Miért? f ⊆ N × N, Nem függvény.
x f y ⇐⇒
x
Függvények
Teljes indukció
Példafeladat
1. Példa Függvény-e az alábbi reláció? Miért? f ⊆ N × N,
x f y ⇐⇒
x
Nem függvény. Mert bármely rögzített x ∈ N esetén végtelen sok y ∈ N van, amelyre x < y és ezáltal x f y
Függvények
Teljes indukció
Példafeladat
1. Példa Függvény-e az alábbi reláció? Miért? f ⊆ N × N,
x f y ⇐⇒
x
Nem függvény. Mert bármely rögzített x ∈ N esetén végtelen sok y ∈ N van, amelyre x < y és ezáltal x f y Már az is elég a cáfolathoz, ha egyetlen rögzített x ∈ N elemmel több y ∈ N áll relációban: Nem függvény, mert 3 f 4 és 3 f 5 is teljesül.
Függvények
Teljes indukció
Önálló feladat
1. Feladat Függvény-e az alábbi reláció? Miért? f ⊆ N × N,
x f y ⇐⇒
x =y
Függvények
Teljes indukció
Önálló feladat
1. Feladat Függvény-e az alábbi reláció? Miért? f ⊆ N × N,
x f y ⇐⇒
x =y
Igen, az. Mert a reláció megadása alapján ha x , y ∈ N és (x , y ) ∈ f illetve (x , z) ∈ f , akkor y = x = z. Ezzel f teljesíti a függvény definíciójában megadott feltételeket.
Függvények
Teljes indukció
Házi feladatok
Feladatok Függvény-e az alábbi reláció? Miért? A = {1, 2, 4}, B = {3, 6, 12}, f ⊆ A × B, x f y ⇐⇒ xy = 12 f ⊆ N × N,
x f y ⇐⇒
x |y
Legyen P a prímszámok halmaza és f ∈ P × P, x f y ⇐⇒ x |y
Függvények
Teljes indukció
Definíció
2. Definíció Legyen X ⊆ A és f : A → B, ekkor f (X ) = {b ∈ B| van olyan a ∈ X , hogy f (a) = b}
Függvények
Teljes indukció
Példafeladat 2. Példa Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X ∩ Y ) ⊆ f (X ) ∩ f (Y )
Függvények
Teljes indukció
Példafeladat 2. Példa Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X ∩ Y ) ⊆ f (X ) ∩ f (Y ) Tegyük fel, hogy b ∈ f (X ∩ Y ). Az a feladatunk, hogy belássuk, hogy ekkor b ∈ (f (X ) ∩ f (Y )).
Függvények
Teljes indukció
Példafeladat 2. Példa Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X ∩ Y ) ⊆ f (X ) ∩ f (Y ) Tegyük fel, hogy b ∈ f (X ∩ Y ). Az a feladatunk, hogy belássuk, hogy ekkor b ∈ (f (X ) ∩ f (Y )). Mivel b ∈ f (X ∩ Y ), van legalább egy a ∈ (X ∩ Y ), amelyre f (a) = b.
Függvények
Teljes indukció
Példafeladat 2. Példa Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X ∩ Y ) ⊆ f (X ) ∩ f (Y ) Tegyük fel, hogy b ∈ f (X ∩ Y ). Az a feladatunk, hogy belássuk, hogy ekkor b ∈ (f (X ) ∩ f (Y )). Mivel b ∈ f (X ∩ Y ), van legalább egy a ∈ (X ∩ Y ), amelyre f (a) = b. Nyílván a ∈ X és a ∈ Y és ezért f (a) = b ∈ f (X ) illetve f (a) = b ∈ f (Y ).
Függvények
Teljes indukció
Példafeladat 2. Példa Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X ∩ Y ) ⊆ f (X ) ∩ f (Y ) Tegyük fel, hogy b ∈ f (X ∩ Y ). Az a feladatunk, hogy belássuk, hogy ekkor b ∈ (f (X ) ∩ f (Y )). Mivel b ∈ f (X ∩ Y ), van legalább egy a ∈ (X ∩ Y ), amelyre f (a) = b. Nyílván a ∈ X és a ∈ Y és ezért f (a) = b ∈ f (X ) illetve f (a) = b ∈ f (Y ). Tehát b ∈ (f (X ) ∩ f (Y )) és éppen ezt akartuk bebizonyítani.
Függvények
Teljes indukció
Önálló feladat 2. Feladat Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X )\f (Y ) ⊆ f (X \Y )
Függvények
Teljes indukció
Önálló feladat 2. Feladat Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X )\f (Y ) ⊆ f (X \Y ) Tegyük fel, hogy b ∈ (f (X )\f (Y )). Az a feladatunk, hogy belássuk, hogy ekkor b ∈ f (X \Y ).
Függvények
Teljes indukció
Önálló feladat 2. Feladat Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X )\f (Y ) ⊆ f (X \Y ) Tegyük fel, hogy b ∈ (f (X )\f (Y )). Az a feladatunk, hogy belássuk, hogy ekkor b ∈ f (X \Y ). Mivel b ∈ (f (X )\f (Y )), b ∈ f (X ), de b 6∈ f (y ).
Függvények
Teljes indukció
Önálló feladat 2. Feladat Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X )\f (Y ) ⊆ f (X \Y ) Tegyük fel, hogy b ∈ (f (X )\f (Y )). Az a feladatunk, hogy belássuk, hogy ekkor b ∈ f (X \Y ). Mivel b ∈ (f (X )\f (Y )), b ∈ f (X ), de b 6∈ f (y ). Ezért van legalább egy a ∈ X , amelyre f (a) = b, de nincs olyan c ∈ Y , amelyre f (c) = b (tehát a 6∈ Y ).
Függvények
Teljes indukció
Önálló feladat 2. Feladat Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (X )\f (Y ) ⊆ f (X \Y ) Tegyük fel, hogy b ∈ (f (X )\f (Y )). Az a feladatunk, hogy belássuk, hogy ekkor b ∈ f (X \Y ). Mivel b ∈ (f (X )\f (Y )), b ∈ f (X ), de b 6∈ f (y ). Ezért van legalább egy a ∈ X , amelyre f (a) = b, de nincs olyan c ∈ Y , amelyre f (c) = b (tehát a 6∈ Y ). Ezek alapján nyílván a ∈ (X \Y ). Tehát b ∈ f (X \Y ) és éppen ezt akartuk bebizonyítani.
Függvények
Teljes indukció
Házi feladatok
Feladatok Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (A ∪ B) ⊆ f (A) ∪ f (B) f (A) ∪ f (B) ⊆ f (A ∪ B) f (A ∪ B) = f (A) ∪ f (B)
Függvények
Teljes indukció
Házi feladatok
Feladatok Adott egy f : A → B függvény. X , Y ⊆ A, bizonyítsa be, hogy f (A ∪ B) ⊆ f (A) ∪ f (B) f (A) ∪ f (B) ⊆ f (A ∪ B) f (A ∪ B) = f (A) ∪ f (B) Tipp Az első két feladatból következik a harmadik. (A halmazok egyenlőségét a kölcsönös tartalmazással is definiálhatjuk)
Függvények
Teljes indukció
A teljes indukció elve
1. Tétel Ha M ⊆ N olyan, hogy 1 ∈ M továbbá m + 1 ∈ M minden m ∈ M esetén, akkor M = N.
Függvények
Teljes indukció
Példafeladat 3. Példa Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + ... + n =
n(n + 1) 2
Függvények
Teljes indukció
Példafeladat 3. Példa Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + ... + n =
n(n + 1) 2
Legyen M azon egészek halmaza, amelyre az állítás teljesül.
Függvények
Teljes indukció
Példafeladat 3. Példa Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + ... + n =
n(n + 1) 2
Legyen M azon egészek halmaza, amelyre az állítás teljesül. = 1, tehát 1 ∈ M. Ha n = 1, akkor n(n+1) 2
Függvények
Teljes indukció
Példafeladat 3. Példa Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + ... + n =
n(n + 1) 2
Legyen M azon egészek halmaza, amelyre az állítás teljesül. = 1, tehát 1 ∈ M. Ha n = 1, akkor n(n+1) 2 Tegyük fel, hogy m ∈ M, ekkor 1 + 2 + . . . + m =
m(m+1) . 2
Függvények
Teljes indukció
Példafeladat 3. Példa Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + ... + n =
n(n + 1) 2
Legyen M azon egészek halmaza, amelyre az állítás teljesül. = 1, tehát 1 ∈ M. Ha n = 1, akkor n(n+1) 2 Tegyük fel, hogy m ∈ M, ekkor 1 + 2 + . . . + m = m(m+1) . 2 Nyílván +(m +1) = 2(m+1)+m(m+1) . 1+2+. . .+m +(m +1) = m(m+1) 2 2
Függvények
Teljes indukció
Példafeladat 3. Példa Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + ... + n =
n(n + 1) 2
Legyen M azon egészek halmaza, amelyre az állítás teljesül. = 1, tehát 1 ∈ M. Ha n = 1, akkor n(n+1) 2 Tegyük fel, hogy m ∈ M, ekkor 1 + 2 + . . . + m = m(m+1) . 2 Nyílván +(m +1) = 2(m+1)+m(m+1) . 1+2+. . .+m +(m +1) = m(m+1) 2 2 Ha kiemelünk (m + 1)-et, akkor azt kapjuk, hogy , tehát m + 1 ∈ M 1 + 2 + . . . + m + (m + 1) = (m+2)(m+1) 2 következik.
Függvények
Teljes indukció
Példafeladat 3. Példa Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + ... + n =
n(n + 1) 2
Legyen M azon egészek halmaza, amelyre az állítás teljesül. = 1, tehát 1 ∈ M. Ha n = 1, akkor n(n+1) 2 Tegyük fel, hogy m ∈ M, ekkor 1 + 2 + . . . + m = m(m+1) . 2 Nyílván +(m +1) = 2(m+1)+m(m+1) . 1+2+. . .+m +(m +1) = m(m+1) 2 2 Ha kiemelünk (m + 1)-et, akkor azt kapjuk, hogy , tehát m + 1 ∈ M 1 + 2 + . . . + m + (m + 1) = (m+2)(m+1) 2 következik. Az 1. tétel alapján M = N és ezzel az állítást bebizonyítottuk.
Függvények
Teljes indukció
Önálló feladat 3. Feladat Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + 22 + . . . + 2n−1 = 2n − 1
Függvények
Teljes indukció
Önálló feladat 3. Feladat Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + 22 + . . . + 2n−1 = 2n − 1 Legyen M azon egészek halmaza, amelyre az állítás teljesül.
Függvények
Teljes indukció
Önálló feladat 3. Feladat Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + 22 + . . . + 2n−1 = 2n − 1 Legyen M azon egészek halmaza, amelyre az állítás teljesül. Ha n = 1, akkor 2n − 1 = 1, tehát 1 ∈ M.
Függvények
Teljes indukció
Önálló feladat 3. Feladat Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + 22 + . . . + 2n−1 = 2n − 1 Legyen M azon egészek halmaza, amelyre az állítás teljesül. Ha n = 1, akkor 2n − 1 = 1, tehát 1 ∈ M. Tegyük fel, hogy m ∈ M, ekkor 1 + 2 + 22 . . . + 2m−1 = 2m − 1.
Függvények
Teljes indukció
Önálló feladat 3. Feladat Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + 22 + . . . + 2n−1 = 2n − 1 Legyen M azon egészek halmaza, amelyre az állítás teljesül. Ha n = 1, akkor 2n − 1 = 1, tehát 1 ∈ M. Tegyük fel, hogy m ∈ M, ekkor 1 + 2 + 22 . . . + 2m−1 = 2m − 1. Nyílván 1 + 2 + 22 . . . + 2n−1 + 2m = 2m − 1 + 2m = 2m+1 − 1, tehát m + 1 ∈ M következik.
Függvények
Teljes indukció
Önálló feladat 3. Feladat Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 2 + 22 + . . . + 2n−1 = 2n − 1 Legyen M azon egészek halmaza, amelyre az állítás teljesül. Ha n = 1, akkor 2n − 1 = 1, tehát 1 ∈ M. Tegyük fel, hogy m ∈ M, ekkor 1 + 2 + 22 . . . + 2m−1 = 2m − 1. Nyílván 1 + 2 + 22 . . . + 2n−1 + 2m = 2m − 1 + 2m = 2m+1 − 1, tehát m + 1 ∈ M következik. Az 1. tétel alapján M = N és ezzel az állítást bebizonyítottuk.
Függvények
Teljes indukció
Házi feladatok
Feladatok Bizonyítsa be teljes indukcióval, hogy minden n ∈ N-re: 1 + 3 + 5 + . . . + (2n − 1) = n2 1 1·2
+
1 2·3
... +
1 n(n+1)
13 + 23 + . . . + n3 =
=
n n+1
n(n+1) 2 2
Függvények
Teljes indukció
A klasszikus nulladrendű nyelv 3. Definíció Klasszikus nulladrendű nyelv en az L(0) = hLC , Con, Formi rendezett hármast értjük, ahol
Függvények
Teljes indukció
A klasszikus nulladrendű nyelv 3. Definíció Klasszikus nulladrendű nyelv en az L(0) = hLC , Con, Formi rendezett hármast értjük, ahol LC = {¬, ⊃, ∨, ∧, ≡, (, )} a nyelv logikai konstansainak a halmaza
Függvények
Teljes indukció
A klasszikus nulladrendű nyelv 3. Definíció Klasszikus nulladrendű nyelv en az L(0) = hLC , Con, Formi rendezett hármast értjük, ahol LC = {¬, ⊃, ∨, ∧, ≡, (, )} a nyelv logikai konstansainak a halmaza Con 6= ∅ a nyelv nemlogikai konstansainak a legfeljebb megszámlálhatóan végtelen halmaza
Függvények
Teljes indukció
A klasszikus nulladrendű nyelv 3. Definíció Klasszikus nulladrendű nyelv en az L(0) = hLC , Con, Formi rendezett hármast értjük, ahol LC = {¬, ⊃, ∨, ∧, ≡, (, )} a nyelv logikai konstansainak a halmaza Con 6= ∅ a nyelv nemlogikai konstansainak a legfeljebb megszámlálhatóan végtelen halmaza LC ∩ Con = ∅
Függvények
Teljes indukció
A klasszikus nulladrendű nyelv 3. Definíció Klasszikus nulladrendű nyelv en az L(0) = hLC , Con, Formi rendezett hármast értjük, ahol LC = {¬, ⊃, ∨, ∧, ≡, (, )} a nyelv logikai konstansainak a halmaza Con 6= ∅ a nyelv nemlogikai konstansainak a legfeljebb megszámlálhatóan végtelen halmaza LC ∩ Con = ∅ Form a nyelv formuláinak a halmaza.
Függvények
Teljes indukció
A formula definíciója
3. Definíció (folytatás) A nyelv formuláinak a halmazát a következő induktív definíció adja meg:
Függvények
Teljes indukció
A formula definíciója
3. Definíció (folytatás) A nyelv formuláinak a halmazát a következő induktív definíció adja meg: Con ⊆ Form (atomi formulák)
Függvények
Teljes indukció
A formula definíciója
3. Definíció (folytatás) A nyelv formuláinak a halmazát a következő induktív definíció adja meg: Con ⊆ Form (atomi formulák) Ha A ∈ Form, akkor ¬A ∈ Form
Függvények
Teljes indukció
A formula definíciója
3. Definíció (folytatás) A nyelv formuláinak a halmazát a következő induktív definíció adja meg: Con ⊆ Form (atomi formulák) Ha A ∈ Form, akkor ¬A ∈ Form Ha A, B ∈ Form, akkor
Függvények
Teljes indukció
A formula definíciója
3. Definíció (folytatás) A nyelv formuláinak a halmazát a következő induktív definíció adja meg: Con ⊆ Form (atomi formulák) Ha A ∈ Form, akkor ¬A ∈ Form Ha A, B ∈ Form, akkor (A ⊃ B) ∈ Form
Függvények
Teljes indukció
A formula definíciója
3. Definíció (folytatás) A nyelv formuláinak a halmazát a következő induktív definíció adja meg: Con ⊆ Form (atomi formulák) Ha A ∈ Form, akkor ¬A ∈ Form Ha A, B ∈ Form, akkor (A ⊃ B) ∈ Form (A ∨ B) ∈ Form
Függvények
Teljes indukció
A formula definíciója
3. Definíció (folytatás) A nyelv formuláinak a halmazát a következő induktív definíció adja meg: Con ⊆ Form (atomi formulák) Ha A ∈ Form, akkor ¬A ∈ Form Ha A, B ∈ Form, akkor (A ⊃ B) ∈ Form (A ∨ B) ∈ Form (A ∧ B) ∈ Form
Függvények
Teljes indukció
A formula definíciója
3. Definíció (folytatás) A nyelv formuláinak a halmazát a következő induktív definíció adja meg: Con ⊆ Form (atomi formulák) Ha A ∈ Form, akkor ¬A ∈ Form Ha A, B ∈ Form, akkor (A ⊃ B) ∈ Form (A ∨ B) ∈ Form (A ∧ B) ∈ Form (A ≡ B) ∈ Form
Függvények
Teljes indukció
Példafeladat
4. Példa Adja meg annak a f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nemlogikai konstansok (Con) számát!
Függvények
Teljes indukció
Példafeladat
4. Példa Adja meg annak a f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nemlogikai konstansok (Con) számát! f (A) = 1, ha A ∈ Con
Függvények
Teljes indukció
Példafeladat
4. Példa Adja meg annak a f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nemlogikai konstansok (Con) számát! f (A) = 1, ha A ∈ Con f (¬A) = f (A), ha A ∈ Form
Függvények
Teljes indukció
Példafeladat
4. Példa Adja meg annak a f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nemlogikai konstansok (Con) számát! f (A) = 1, ha A ∈ Con f (¬A) = f (A), ha A ∈ Form Ha A, B ∈ Form, akkor
Függvények
Teljes indukció
Példafeladat
4. Példa Adja meg annak a f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nemlogikai konstansok (Con) számát! f (A) = 1, ha A ∈ Con f (¬A) = f (A), ha A ∈ Form Ha A, B ∈ Form, akkor f ((A ⊃ B)) = f (A) + f (B)
Függvények
Teljes indukció
Példafeladat
4. Példa Adja meg annak a f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nemlogikai konstansok (Con) számát! f (A) = 1, ha A ∈ Con f (¬A) = f (A), ha A ∈ Form Ha A, B ∈ Form, akkor f ((A ⊃ B)) = f (A) + f (B) f ((A ∨ B)) = f (A) + f (B)
Függvények
Teljes indukció
Példafeladat
4. Példa Adja meg annak a f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nemlogikai konstansok (Con) számát! f (A) = 1, ha A ∈ Con f (¬A) = f (A), ha A ∈ Form Ha A, B ∈ Form, akkor f ((A ⊃ B)) = f (A) + f (B) f ((A ∨ B)) = f (A) + f (B) f ((A ∧ B)) = f (A) + f (B)
Függvények
Teljes indukció
Példafeladat
4. Példa Adja meg annak a f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nemlogikai konstansok (Con) számát! f (A) = 1, ha A ∈ Con f (¬A) = f (A), ha A ∈ Form Ha A, B ∈ Form, akkor f ((A ⊃ B)) = f (A) + f (B) f ((A ∨ B)) = f (A) + f (B) f ((A ∧ B)) = f (A) + f (B) f ((A ≡ B)) = f (A) + f (B)
Függvények
Teljes indukció
Önálló feladat
4. Feladat Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő valódi logikai konstansok (LC r = LC \(, )) számát!
Függvények
Teljes indukció
Önálló feladat
4. Feladat Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő valódi logikai konstansok (LC r = LC \(, )) számát! f (A) = 0, ha A ∈ Con
Függvények
Teljes indukció
Önálló feladat
4. Feladat Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő valódi logikai konstansok (LC r = LC \(, )) számát! f (A) = 0, ha A ∈ Con f (¬A) = f (A) + 1, ha ¬A ∈ Form
Függvények
Teljes indukció
Önálló feladat
4. Feladat Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő valódi logikai konstansok (LC r = LC \(, )) számát! f (A) = 0, ha A ∈ Con f (¬A) = f (A) + 1, ha ¬A ∈ Form Ha A, B ∈ Form, akkor
Függvények
Teljes indukció
Önálló feladat
4. Feladat Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő valódi logikai konstansok (LC r = LC \(, )) számát! f (A) = 0, ha A ∈ Con f (¬A) = f (A) + 1, ha ¬A ∈ Form Ha A, B ∈ Form, akkor f ((A ⊃ B)) = f (A) + f (B) + 1
Függvények
Teljes indukció
Önálló feladat
4. Feladat Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő valódi logikai konstansok (LC r = LC \(, )) számát! f (A) = 0, ha A ∈ Con f (¬A) = f (A) + 1, ha ¬A ∈ Form Ha A, B ∈ Form, akkor f ((A ⊃ B)) = f (A) + f (B) + 1 f ((A ∨ B)) = f (A) + f (B) + 1
Függvények
Teljes indukció
Önálló feladat
4. Feladat Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő valódi logikai konstansok (LC r = LC \(, )) számát! f (A) = 0, ha A ∈ Con f (¬A) = f (A) + 1, ha ¬A ∈ Form Ha A, B ∈ Form, akkor f ((A ⊃ B)) = f (A) + f (B) + 1 f ((A ∨ B)) = f (A) + f (B) + 1 f ((A ∧ B)) = f (A) + f (B) + 1
Függvények
Teljes indukció
Önálló feladat
4. Feladat Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő valódi logikai konstansok (LC r = LC \(, )) számát! f (A) = 0, ha A ∈ Con f (¬A) = f (A) + 1, ha ¬A ∈ Form Ha A, B ∈ Form, akkor f ((A ⊃ B)) = f (A) + f (B) + 1 f ((A ∨ B)) = f (A) + f (B) + 1 f ((A ∧ B)) = f (A) + f (B) + 1 f ((A ≡ B)) = f (A) + f (B) + 1
Függvények
Teljes indukció
Házi feladatok Feladatok Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő nyitó zárójelek számát! Adja meg annak az f : Form → N függvénynek az induktív definícióját, mely minden formula esetén megadja a formulában szereplő záró zárójelek számát! Bizonyítsa be, hogy a nulladrendű nyelv minden egyes formulájában a nyitó és a záró zárójelek száma megegyezik Tipp Az első két feladatból következik a harmadik.
