Množiny a výroková logika Štěpán Křehlík Ekonomicko správní fakulta Masarykova Universita podzim 2018 Štěpán Křehlík Množiny a výroková logika Množiny Zavedení pojmu množiny • Jsme zvyklí v našem světě pojmenovávat skupiny objektů. • Hráči FC Viktoria Plzeň VE fcŕ» Hn S no Michael Krmenčík Útočník David Limberský Obránce Matúš Kcizáčik Brankář Romati Hubník Obránce Milan Petržela Záložn ík Tomáš Hořava Záložník Daniel Kolář Záložník 9 Herci seriálu Hry o trůny • Podobná asociace do matematiky Štěpán Křehlřk Množiny a výroková logika Značení množin a jejich vlastnosti • velké písmeno • množina symbolů pro karty K = {V, X- ♦} • množina mincí • býti prvkem • epsilon " g" • pětikoruna g /W • stokoruna ^ /W o ignorujeme multiplicity • každý prvek je v množině pouze jednou • mohutnost množiny □ s Štěpán Křehlřk Množiny a výroková logika Množiny Typy m noži n • konečná množina • můžeme prvky vypsat bez ohledu na čas • A = {a, b, c, c/, e} • nekonečná množina • nelze vypsat všechny prvky • e = {l,2,3,4,...} o prázdná množina • neobsahuje žádné prvky • 0,0 • podmnožina o množinová inkluze • všechny prvky jedné množiny jsou obsaženy v druhé množině • A C B, A C B Štěpán Křehlík Množiny a výroková logika Operace s množinami Unární operace - Doplněk/komplement množiny ...A,A' Příklad_ Q ... Studenti prvního ročníku ESF A... Ti studenti, kteří napsali vstupní test A' ? Štěpán Křehlřk Množiny a výroková logika Operace s množinami Binární operace sjednocení množin ..." U " • AU B je seskupení všeho, co je v obou skupinách Příklad Množina M = {A, /i, a, 7} Množina N = {ce, /3,7,6} MU N = {a,/3,7,5, A,/i} Štěpán Křehlřk Množiny a výroková logika Operace s množinami Binární operace - průnik množin ..." n " • A D B jsou prvky, které jsou společné oběma množinám Q A^-^\ --- Příklad Označme A množinu olympijských medailistek v super G. Dále označme B množinu olympijských medailistek v paralelním obřím slalomu. A n B = {Ledecká} Štěpán Křehlřk Množiny a výroková logika Operace s množinami Binární operace - rozdíl množin ..." \ " • A \ B jsou prvky, které patří do množiny A a přitom nepatří do množiny B Q A ---^ q; Jestliže výrok p, pak výrok q Příklad Výrok p ...; Užili jsme projímadlo . Výrok q ...: Pos**li jsme se. Výrok p => q: Jestli, že užijeme projímadlo, pak se pos***me. Pravdivostní tabulka Implikace P P P ^ q 1 1 1 1 0 0 0 1 1 0 0 1 Štěpán Křehlík Množiny a výroková logika Výrokový počet Ekvivalence výroku p, q, značíme p ^ q; Vvýrok p, právě tehdy, když výrok q Příklad Výrok p...: Užili jsme projímadlo. Výrok q ...: Měli jsme zácpu. Výrok p ^=> q: Užili jsme projímadlo, právě tehdy, když jsme měli zacpu. Pravdivostní tabulka Ekvivalence P P 1 1 i 1 0 0 0 1 0 0 0 i Štěpán Křehlík Množiny a výroková logika Výrokový počet Výroková forma je sdělení obsahující proměnou Příklad • Lidé mají hmotnost větší jak 80 kg. 9 x2 = 1, pro x e {..., —3, —2, — 1, 0,1, 2, 3,...}. • zadávání množin pomocí charakteristických vlastností, používání kvantifikátorů V, 3 Příklad • Všichni studenti na přednášce byli pozvaní na Opening Party Support Centre. o pro Vx e {..., —3, —2, — 1, 0,1, 2, 3,...} platíx2 = 1. Štěpán Křehlík Množiny a výroková logika Výrokový počet Příklad Negujte následující výroky: • Všichni studenti na přednášce byli pozvaní na Opening Party Support Centre. • pro Vx e {..., —3, —2, — 1, 0,1, 2, 3,...} platí x2 = 1. Pravidla pro negování logických spojek: • -(pVq) (-pAq) • -n(p Aq) ^ (^p V -iqr) • -(P ^ <7) & ((P A -.q) V (q A -.p)) Štěpán Křehlík Množiny a výroková logika Výrokový počet Příklad Ukažme, že (P (?) A (Q P) = P ^ Q ■ ] □ [S1 ► < -E ► < = Štěpán Křehlík Množiny a výroková logika