Přednáška 11

ALGEBRA A GEOMETRIE MNOŽINY Základní pojmy teorie množin Množinou rozumíme soubor určitých objektů, které se dají navzájem rozlišit. Množina je dána, dovedeme-li o každém objektu (jakémkoliv, který nás napadne ) rozhodnout, jestli do ní patří nebo ne.
Zápis aA znamená, že prvek a patří do množiny A (a je prvkem A), naopak
aA znamená, že a nepatří do A. Základní pojmy teorie množin Množinu, která neobsahuje žádný prvek nazýváme prázdnou množinou a značíme ji symbolem . Tak například množina všech reálných kořenů rovnice
x2 + 4 = 0
Je prázdná.
Množina, která obsahuje alespoň jeden prvek se nazývá neprázdná. Základní pojmy teorie množin Množina, která obsahuje pouze konečný počet prvků se nazývá konečná. Konečnou nazýváme i prázdnou množinu.
Množina, která není konečná se nazývá nekonečná.
Množiny budeme značit velkými písmeny.
N bude znamenat množinu všech přirozených čísel, tj. 1, 2, 3, . . .
Základní pojmy teorie množin Z bude množina všech celých čísel, tj.
. . . , -2, -1, 0, 1, 2, . . .
Q bude množina všech racionálních čísel
tj. čísel tvaru p/q , kde pZ a q  N .
Existují čísla, která nejsou racionální, mezi ně patří čísla √ 2 , π a další, tyto nazýváme je iracionálními.
Základní pojmy teorie množin R značí množinu všech reálných čísel, která zahrnuje racionální a iracionální čísla.
C značí množinu všech komplexních čísel tvaru a ± j.b, kde a,b  R. Základní pojmy teorie množin Nechť A, B jsou dvě množiny a každý prvek množiny A je současně prvkem množiny B. Říkáme, že množina A je částí množiny B, nebo také, že A je podmnožinou B, případně, že B je nadmnožinou A. Zapisujeme
A  B eventuálně B  A .
Jestliže současně A  B a A  B, říkáme, Operace s množinami že A a B jsou sobě rovny, píšeme A = B.
1) Množinu tvořenou všemi prvky množiny A a všemi prvky množiny B nazýváme sjednocením množin A a B a označujeme
A  B eventuálně B  A.
Množinu tvořenou všemi prvky patřícími současně Operace s množinami do množiny A i do množiny B nazýváme průnikem množin A, B a značíme
A  B eventuálně B  A.
Je-li
A  B = Ř,
Říkáme, že množiny A, B jsou disjunktní. Operace s množinami Množinu všech prvků patřících do A a současně nepatřících do B nazýváme rozdílem množiny A a množiny B nebo také doplňkem množiny B do množiny A.
Zapisujeme A - B. Zápis B – A reprezentuje zřejmě jinou množinu. Operace s množinami Sjednocení
( A – B )  ( B – A)
Se nazývá symetrický rozdíl množin A a B.
Množinu tvořenou všemi uspořádanými dvojicemi
( a, b ) Operace s množinami Takovými, že a A a b B nazýváme kartézským součinem
množin A a B a značíme A x B.
Operace s množinami -příklady 1) Nechť A = { a, b, c }
B = { a, 1, 2 }.
Potom
A  B = { a, b, c, 1, 2 }
A  B = { a }
A – B = { b, c }
B – A = { 1, 2 }
Operace s množinami -příklady A x B = {(a, a), (a, 1), (a, 2), (b, a),
(b,1), (b, 2), (c, a), (c, 1), (c,2) }
B x A = { (a, a), (a, b), (a, c), (1, a),
(1, b), (1, c), (2, a), (2, b), (2, c) }
Operace s množinami -příklady 2) Dokažte, že platí vztahy
a) ( A  B )  C = ( A  C )  ( B  C )
b) A – ( B  C ) = ( A – B )  ( A – C )
c) A – ( B  C ) = ( A – B )  ( A – C )
Vztahy b), c) lze slovně vyjádřit takto:
Doplněk sjednocení je roven průniku doplňků, doplněk průniku je roven Operace s množinami -příklady sjednocení doplňků. Jsou to tak zvaná pravidla de Morgana.
OTÁZKY A ÚLOHY
1 Co je prázdná, neprázdná, konečná a
nekonečná množina?
2 Vysvětlete co znamená, že A  B,
A = B, A  B Operace s množinami - cvičení 3 Vysvětlete co je sjednocení, průnik, rozdíl
a kartézský součin dvou množin.
4 Dokažte platnost de Morganových
pravidel pro množiny.
5 Dokažte, že platí
A  ( B  C ) = ( A  B)  (A  C ). 2. MATEMATICKÁ LOGIKA V dalším textu předpokládáme, že všechny naše věty jsou vytvořeny gramaticky správně. Uvedeme několik příkladů vět:
V1 Brno je město.
V2 Brno nepatří mezi města.
V3 4 < 3.
V4 Přesně za tisíc let v tuto dobu zde bude
pršet.
MATEMATICKÁ LOGIKA V5 Přirozené číslo x je dělitelné třemi.
V6 Existuje celé číslo x takové, že x2 = 2.
V7 Každé přirozené číslo x je dělitelné
třemi.
2.1 Výrok a výroková funkce. Výrokem rozumíme větu o které lze rozhodnout zda je pravdivá nebo nepravdivá. V našich MATEMATICKÁ LOGIKA Příkladech je
V1 výrokem (pravdivým)
V2 a V3 jsou výroky (nepravdivé)
V4 a V5 nejsou výroky (nelze rozhodnout
zda jsou pravdivé nebo nepravdivé)
V6 a V7 jsou výroky (nepravdivé)
Všimněme si vět V5 a V7. Obě obsahují symbol x. Ve větě V7 lze symbol x vynechat aniž to změní její smysl nebo MATEMATICKÁ LOGIKA Ji lze přeformulovat takto:
V8 Všechna přirozená čísla jsou dělitelná třemi.
Ve V5 symbol x nelze vynechat. Dosadíme-li za x konkrétní číslo, např. 4, potom dostaneme větu
V9 Přirozené číslo 4 je dělitelné třemi.
Ta je již výrokem (nepravdivým). Věta V5 MATEMATICKÁ LOGIKA Je příkladem tzv. výrokové funkce. Pod tímto pojmem rozumíme větu, která není výrokem a která obsahuje symbol připouštějící dosazení konkrétní hodnoty a která po dosazení se stane výrokem. Výrokové funkce se obvykle značí p(x), q(x), . . . .
Místo věty „výrok p je pravdivý“ říkáme „výrok p má logickou hodnotu true“ nebo zkrátka „ platí p “. MATEMATICKÁ LOGIKA Místo věty „výrok p je nepravdivý“ říkáme „výrok p má logickou hodnotu false“ nebo krátce neplatí p .
Vidíme, že naše definice výroku připouští pouze dvě logické hodnoty. Říkáme, že pracujeme s dvojhodnotovou logikou. Její základy položil již Aristoteles.
2.2 Negace výroku a logické kvantifi-kátory. Vidíme, že výrok V2 je v jistém MATEMATICKÁ LOGIKA smyslu opačný k výroku V1. Říkáme, že je jeho negací. Obecně negací výroku p rozumíme výrok q, který má tuto vlastnost:
je-li p pravdivý je q nepravdivý a naopak je-li p nepravdivý je q pravdivý. Negace
výroku p se označuje a čteme non p .
Nechť A je nějaká množina a p(x) nějaká výroková funkce. Výrok MATEMATICKÁ LOGIKA V10 Pro každý prvek x  A je pravdivý výrok p(x)
se v matematice často zapisuje takto:
V11 p(x)  x  A nebo  x  A : p(x)
a čte se : p(x) platí pro každé x z množiny A.
Opačným výrokem k výroku V10 je výrok V12 V množině A existuje (alespoň jeden) MATEMATICKÁ LOGIKA prvek a takový, že výrok p(a) je nepravdivý – zapisuje se takto:
V13  a A : p(a)
a čte se : v množině A existuje prvek a takový, že neplatí p(a) .
Z uvedených příkladů je význam symbolů
 ,  zřejmý. Říká se jim logické kvantifikátory. MATEMATICKÁ LOGIKA Negací ke každému výroku p je výrok
„ není pravda, že platí p „
2.3 Disjunkce a konjunkce výroků. Vyjdeme z příkladu výroku
V14 Trojúhelník ABC je rovnoramenný nebo pravoúhlý.
Tento výrok je spojením dvou výrokůV15 MATEMATICKÁ LOGIKA V15 Trojúhelník ABC je rovnoramenný
V16 Trojúhelník ABC je pravoúhlý
Spojka nebo zde není vylučovací, ale říká že výrok V14 není pravdivý pouze v případě, kdy ani jeden z výroků V15, V16 není pravdivý. Ve všech ostatních případech je pravdivý. Dostáváme se k pojmu disjunkce dvou výroků: MATEMATICKÁ LOGIKA Jsou-li dány dva výroky p a q, potom nový výrok tvaru „ p nebo q “ nazýváme disjunkcí výroků p, q a zapisujeme ji
p  q (čteme p or q) – je pravdivá, když alespoň jeden z výroků p, q je pravdivý a nepravdivá, když oba výroky p, q jsou nepravdivé.
Uvažme další výrok: MATEMATICKÁ LOGIKA V17 Trojúhelník ABC je rovnoramenný a pravoúhlý.
Tento výrok je spojením dvou výroků V15, V16 spojkou „ a “. Je pravdivý pouze v tom případě, kdy oba dva výroky jsou pravdivé.
Ve všech ostatních případech je nepravdivý.
Dostáváme se k pojmu konjunkce dvou výroků: MATEMATICKÁ LOGIKA Konjunkce je pravdivá pouze v případě, kdy oba výroky p a q jsou pravdivé.
Mějme dva výroky p, q. Nový výrok tvaru „ p a q “ nazýváme konjunkcí výroků p, q a zapisujeme ji p  q – (čti p et q ).
2.4 Implikace a ekvivalence výroků. Vyjdeme opět z příkladu výroku:
V18 Jestliže trojúhelník ABC je rovnostranný potom je rovnoramenný. MATEMATICKÁ LOGIKA Předchozí výrok se opět skládá ze dvou výroků:
V19 Trojúhelník ABC je rovnostranný,
V20 Trojúhelník ABC je rovnoramenný.
Při označení výroků p, q má výrok V18 strukturu
V21 Jestliže platí p, potom platí q.
Tento výrok nic neříká o pravdivosti výroků
p a q. Říká pouze to, že současně není MATEMATICKÁ LOGIKA Možné, aby současně platil výrok p a neplatil výrok q, tj. výrok p  q je nepravdivý. Výrok V21 lze formulovat také takto:
V22 Jestliže neplatí q, potom neplatí p.
Tím se dostáváme k pojmu implikace dvou výroků: Jsou-li dány výroky p, q, potom nový výrok tvaru „jestliže p, potom q“ MATEMATICKÁ LOGIKA nazýváme implikací výroků p, q a píšeme
p  q (čti p implikuje q). Implikace je nepravdivá pouze když výrok p je pravdivý a současně výrok q je nepravdivý. Ve všech ostatních případech je pravdivá.
V matematice často místo výroku
Jestliže platí p, potom platí q
používá některá z následujících konstrukcí: MATEMATICKÁ LOGIKA Nechť platí p. Potom platí q.
Z p plyne q,
p je postačující podmínkou pro q,
q je nutnou podmínkou pro p,
q platí tehdy, když platí p,
p platí jen tehdy, když platí q.
Tato terminologie ztratí hrozivost, když ji aplikujeme na příkladu výroku V18. MATEMATICKÁ LOGIKA Místo něj použijeme některou z následují-cích konstrukcí:
Nechť trojúhelník ABC je rovnostranný potom je rovnoramenný.
Z rovnostrannosti trojúhelníka ABC plyne jeho rovnoramennost.
Rovnostrannost trojúhelníka ABC je postačující podmínkou jeho rovnoramen- nosti.
MATEMATICKÁ LOGIKA Rovnoramennost trojúhelníka ABC je nutnou podmínkou jeho rovnostrannosti.
Trojúhelník ABC je rovnoramenný tehdy, když je rovnostranný.
Trojúhelník ABC je rovnostranný jen tehdy, když je rovnoramenný.
Často místo výroku „ jestliže x A, potom platí p(x) “ se používá výrok „ pro každé x A platí p(x) “ MATEMATICKÁ LOGIKA V matematice se často setkáváme s výroky, kdy kromě implikace p  q je pravdivá i implikace opačná, tj. s výroky tvaru :
V23 (p  q )  (q  p )
Tak například vedle výroku „ Jestliže trojúhelník ABC je pravoúhlý potom | AB | 2 + | BC | 2 = | AC | 2 “ ( Pythagorova věta) platí i výrok opačný „ Jestliže | AB | 2 + | BC | 2 = | AC | 2 , potom trojúhelník ABC je pravoúhlý“ MATEMATICKÁ LOGIKA Výrok tvaru V23 krátce zapisujeme
V24 p  q nebo také p  q
(čti p je ekvivalentní s q) a výroky p, q nazýváme ekvivalentní.
Výrok V24 lze formulovat takto:
V25 p je nutnou a postačující podmínkou pro q nebo také
V26 p platí tehdy a jen tehdy, když platí q MATEMATICKÁ LOGIKA V obou výrocích V25, V26 lze mezi sebou vyměnit písmena p a q.
2.5 Tautologie. Snadno se přesvědčíme, že výrok
V27 p  p je vždy pravdivý ať p platí nebo ne. Takovým, vždy pravdivým, logic-kým výrokům se říká tautologie nebo též logické zákony, tautologii V27 se říká MATEMATICKÁ LOGIKA Aristotelův zákon o vyloučeném třetím.
Dalšími důležitými tautologiemi jsou tzv. pravidla de Morgana:
V28 p  q  p  q
V29 p  q  p  q
2.6 Teorémy a jejich důkazy. Pravdivé výroky matematického charakteru se nazývají matematickými větami – teorémy. MATEMATICKÁ LOGIKA Většina teorémů má tvar implikace p  q.
Inženýři, a zvláště studenti inženýrství a bakalářství, se často dopouštějí chyby v tom, že si z výroku p  q zapamatují pouze výrok q a ten prohlásí za pravdivý v každé situaci (ať výrok p platí nebo neplatí). Mohou tím vzniknout těžké omyly a někdy i zábavné situace. Tak například výrok
Jestliže 2=1, potom pan Novák je papežem MATEMATICKÁ LOGIKA Je jistě pravdivý. Ve skutečnosti pan Novák a papež jsou dvě osoby. Jestliže 2=1, potom pan Novák a papež jsou jedna osoba a tedy pan Novák je papežem. Samotný výrok
Pan Novák je papežem
Sám o sobě pravdivý pochopitelně není.
Platnost každé matematické věty je třeba dokázat. Výjímku tvoří tak zvané axiomy, které předem považujeme za pravdivé. MATEMATICKÁ LOGIKA Důkazy vět dělíme na přímé a nepřímé. Podstatou obou typů důkazu je implikace. Nechť je dán výrok v, jehož platnost máme dokázat.
Podstata přímého důkazu spočívá v následujícím postupu: Hledá se pravdivý výrok p (jehož platnost byla již dříve ověřena, např. axiom), takový aby platila implikace p  v. Platnost výroku p je tím dokázána, neboť, jak víme v pravdivé MATEMATICKÁ LOGIKA implikaci z pravdivého výroku může plynout pouze pravdivý výrok.
Podstata nepřímého důkazu spočívá v násle-dujícím postupu: hledá se nepravdivý výrok n (jehož neplatnost byla již dříve ověřena), takový aby platila implikace v  n. Platnost výroku v je tím dokázána, neboť, jak víme v pravdivé implikaci nemůže z pravdivého výroku plynout nepravdivý MATEMATICKÁ LOGIKA výrok. To však znamená, že výrok v je nepravdivý a tedy výrok v je pravdivý (pokud ovšem pracujeme ve dvojhodnotové logice). Uvedený druh důkazu se nazývá také důkaz sporem.
Častým případem teorémů jsou teorémy tvaru
V30  n  N : p(n),
kde p(n) je nějaká výroková funkce.
MATEMATICKÁ LOGIKA Ze střední školy znáte následující větu o matematické indukci:
* [p(1)  ( kN : (p(k)  p(k+1)))] 
  nN : p(n)
Zápis vypadá hrozivě. Je to výrok:
Jestliže platí výrok p(1) a současně je pravda, že pro každé přirozené číslo k z platnosti výroku p(k) plyne platnost p(k+1), MATEMATICKÁ LOGIKA potom pro každé přirozené číslo n platí výrok p(n).
Pravdivost implikace * je dokázána. Stačí tedy pro platnost výroku V30, což je pravá strana v implikaci *, dokázat platnost výroku na levé straně, tj. výroku
** p(1)  ( kN : (p(k)  p(k+1)))
Výrok ** je konjunkcí a k jeho platnosti stačí tedy dokázat, že současně platí dva MATEMATICKÁ LOGIKA výroky.
*** p(1)  kN : (p(k)  p(k+1))
V postupu *** každý již určitě vidí známou metodu dokazování matematickou indukcí.
Na závěr podotkněme, že zápisem
x  A: w(x)
Rozumíme v matematice množinu všech prvků x z množiny A splňujících w(x).
MATEMATICKÁ LOGIKA OTÁZKY a ÚLOHY Na závěr podotkněme, že zápis xA: w(x) reprezentuje množinu všech prvků x z množiny A takových, že pro ně platí výrok w(x). Tak například {x R: x > 0} znamená množinu všech reálných čísel x , která jsou větší než nula.
OTÁZKY a ÚLOHY
1.Popište vlastními slovy, co je výrok a co je výroková funkce.
MATEMATICKÁ LOGIKA OTÁZKY a ÚLOHY 2.Co je negace výroku a co jsou logické kvantifikátory. Uveďte příklady.
3.Co jsou disjunkce a konjunkce dvou výroků.Uveďte příklady.
4.Co jsou implikace a ekvivalence dvou výroků. Uveďte příklady.
5.Co je v matematické větě podmínka nutná a co postačující. Uveďte příklady. MATEMATICKÁ LOGIKA OTÁZKY, ÚLOHY a CVIČENÍ 7.Vysvětlete princip důkazu matematickou ďndukcí.
8. Co je tautologie.
CVIČENÍ
6.Vysvětlete princip přímého a nepřímého důkazu matematické věty.
1. Negujte bez použití slov „není pravda, že“ výroky
a)Nejméně dvě třetiny studentů je chytrých.. MATEMATICKÁ LOGIKA CVIČENÍ 3. Dokažte, že následující výroky jsou tautologiemi
a) ((p  q)  (p  q))  (p  q)
b) (p  q)  (q  p)
4. Ukažte, že platnost výroku „ jestliže platí p, potom platí q“ je dokázána, když se nám podaří dokázat některý z výroků
a) Neplatí zároveň výrok p a negace výroku q MATEMATICKÁ LOGIKA CVIČENÍ b)Jestliže neplatí q, potom neplatí p
(Stačí dokázat, že výroky
a) (p  q)  p  q
b) (p  q)  (q  p) jsou tautologie )
5. Matematickou indukcí dokažte, že platí
a)  n  N :
1 + 2 + 3 + 4 + . . . + n = MATEMATICKÁ LOGIKA CVIČENÍ b)  n  N :
1 + q + q2 + . . . + q n – 1 = 3 REÁLNÁ a KOMPLEXNÍ ČÍSLA 3.1 DĚLENÍ REÁLNÝCH ČÍSEL
Přirozená 1, 2, 3, . . . N
Celá 0, 1, -1, 2, -2, . . . Z
Racionální – tvaru p/q , kde p je číslo celé a q číslo přirozené . . . Q
Platí N  Z , Z  Q.
S racionálními čísly v matematice nevysta-číme. Délka úhlopříčky jednotkového čtverce je číslo a to není racionální.
REÁLNÁ a KOMPLEXNÍ ČÍSLA Všechna reálná čísla, která nejsou racionální nazýváme iracionální.
3.2 REÁLNÉ MNOŽINY, SUPREMUM A INFIMUM.
Množiny, jejichž prvky jsou pouze reálná čísla nazýváme reálnými množinami. Pro nás zvlášť důležitými reálnými množinami budou intervaly. Nechť a < b jsou libovolná reálná čísla. REÁLNÁ a KOMPLEXNÍ ČÍSLA 1. (- , a) ={x  R: x < a}
2. (- , a] ={x  R: (x < a)  (x = a)}
3. (a,  ) ={x  R: x> a}
4. [a, ) ={x  R: (x> a)  (x = a)}
5. (- , ) = R
6. (a, b) ={x  R: (x > a)  (x < b)}
7. (a, b] = (a, b)  {b}
8. [a, b) = (a, b)  {a}
9. [a, b] = (a, b)  {a,b}
REÁLNÁ a KOMPLEXNÍ ČÍSLA Intervaly 1, 3, 5 a 6 nazýváme otevřené, intervaly 2,4,5 a 9 uzavřené a intervaly 7,8 polouzavřené. Interval 5 je jak otevřený tak uzavřený.
O reálné množině množině M řekneme, že je shora ohraničená, jestliže existuje reálné číslo h takové, že pro všechna xM platí x  h. Každá shora ohraničená množina má nekonečně mnoho horních závor. Mezi nimi REÁLNÁ a KOMPLEXNÍ ČÍSLA existuje vždy nejmenší číslo – supremum množiny M, značíme supM.
supM má tyto dvě vlastnosti: a) Je horní závorou množiny M, tj, pro každé xM platí x  supM. b) je nejmenší z horních závor.
Příklad. Nechť A = (- , 2) , B = (- , 2 ]
Potom supA=2, ale i supB=2. Všimněme si, že supA  A zatímco supB  B. REÁLNÁ a KOMPLEXNÍ ČÍSLA To nás vede k definici: jestliže supM M, potom toto supremum nazveme maximem množiny M.
Analogicky definujeme ohraničenost reálné množiny zdola a