Množiny a výroková logika
Lukáš Kokrda
Ekonomicko správní fakulta Masarykova Universita
podzim 2020
Lukáš Kokrda Množiny a výroková logika
Zavedení pojmu množiny
• Jsme zvyklí v našem světě pojmenovávat skupiny objektů.
• Objektů se společnou vlastností nebo absencí vlastnosti.
• Například sudá (parná) čísla:
„Jsou všechna celá čísla dělitelná bezezbytku číslem 2.4
9 Nebo lichá (nepárná) čísla:
„Jsou všechna celá čísla nedělitelná bezezbytku číslem 2
Značení množin a jejich vlastnosti
• velké písmeno
• množina symbolů pro karty K = {V,    X- ♦}
• množina mincí
M =
býti prvkem
• epsilon G
• pětikoruna £ /W
• stokoruna ^ /W
ignorujeme multiplicity
• každý prvek je v množině pouze jednou mohutnost množiny
• počet prvků množiny
• \K\ = 4 nebo M
Lukáš Kokrda
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
o nelze vypsat všechny prvky . e = {l,2,3,4,...}
• C = (2,3)
o prázdna množina
• neobsahuje žádné prvky
• 0,0
• podmnožina
9 množinová inkluze
• všechny prvky jedné množiny jsou obsaženy v druhé množině
• A C B, A C B
Lukáš Kokrda
Množiny a výroková logika
Významné číselné množiny
• Přirozená čísla: N = {1, 2, 3,...}
9 Přirozená čísla s 0: No = {0,1,2,3,...}
• Celá čísla: Z = {..., —2, — 1, 0,1,2,...}
• Racionálni čísla (čísla zapsatelná zlomkem):
Q = {-f,-2,o,l,...}
• Iracionálni čísla (čísla s nekonečným neperiodickým rozvojem)
1= {V2, VŠ, VŠ, e, tí,...}
• Reálná čísla: K. = (—oc, oc)
• Komplexní čísla: C = {a + b/|a, b G M, /2 = —l}
Lukáš Kokrda
Množiny a výroková logika
Operace s množinami
Unární operace - Doplněk/komplement množiny ...A,A'
Příklad
Q = K. Reálná čísla
A — (—00, 2) Čísla menší rovna 2
Ä = ^
XI •     •     • >
Lukáš Kokrda Množiny a výroková logika
Operace s množinami
Binární operace sjednocení množin ..." U "
• A U B je seskupení všeho, co je v obou skupinách
• Co je na obrázku zavádějící?
Příklad
Množina M = {A, /x, a, 7} Množina N — {a, /3,7,8}
MU N = {a, £,7, ä, A,/i}
Lukáš Kokrda
Množiny a výroková logika
Operace s množinami
Binární operace - průnik množin ..." n "
a A n B jsou prvky, které jsou společné oběma množinám
Q	
A^--^	--
Příklad
Množina M = {A, /i, a, 7} Množina N = {ce, /3,7,6} M n N = {a, 7}
ä1
Lukáš Kokrda
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 ---^	<f---~"\B
Příklad
H je množina hodnocení ze zkoušky, tj. H = {A, 6, C, D, E, F} U je množina úspěšného hodnocení zkoušky, tj. U = {A,B, C,D,E}
H \ U = {F}, tj. množina neúspěšného hodnocení zkoušky
Lukáš Kokrda
Množiny a výroková logika
Operace s množinami
Binární operace - kartézský součin ..." x "
• A x B jsou všechny dvojice, kde první prvek je z první množiny a druhý prvek z druhé množiny
Příklad
Kf = Km = {A, B, AB, 0} je množina krevních skupin, pak kartézský součin Kf x Km =
{(A, A); (A, B); (A, AB); (A, 0); (B, A); (B, B); (B, AB); (B, 0); (AB, A); (AB, B); {AB, AB); (AB, 0); (0, A); (0, B); (0, AB); (0,0)}
Nejčastější kartézské součiny
• M x 1 = M2 body v rovině [x,y]
• RxRxl = I3 body v „prostoru" [x,y, z]
Lukáš Kokrda
Množiny a výroková logika
Výrokový počet
Výrok je tvrzení u něhož lze rozhodnout zda je pravdivé, nebo nepravdivé
Příklady výroků? Více než polovina příkladů výroků nejsou výroky.
• Den má 86 400 sekund.
• 1 + 2 = 5
• Strč prst skrz krk.
• S námi se vyplatí počítat.
• Máte rádi ESF?
Značení výroků a jejich pravdivostní hodnoty:
• výroky: p, q
• pravdivý - P, 1, T
• nepravdivý - N, 0, F
Kategorie vět, které nejsou výrokem.
otázky, rozkazy, názvy, subjektivní názory, výroky s proměnou
Lukáš Kokrda
Množiny a výroková logika
Negace
Negace výroku p, značíme -ip někdy také p
Není pravda, že ... Neplatí, že ...
Příklad
Výrok p ...; Matematika 0 je zbytečný předmět.
Výrok -ip ...; Není pravda, že Matematika 0 je zbytečný předmět.
Pravdivostní tabulka
Negace	
P	^P
1	0
0	1
Lukáš Kokrda Množiny a výroková logika
Konjunkce „logické a"
Konjunkce výroku p, q, značíme p A q; Výrok p a zároveň q
Příklad
\/ýro/c p ...; Petr je student prvního ročníku. Výrok p ...; Petr má průkaz ISIC.
Výrok p A q: Petr je student prvního ročníku a zároveň má průkaz ISIC.__
Pravdivostní tabulka
Konjunkce		
P	q	pAq
1	1	1
1	0	0
0	1	0
0	0	0
Lukáš Kokrda
Množiny a výroková logika
Disjunkce „logické nebo"
Disjunkce výroku p, q, značíme p V q; Výrok p nebo výrok q
Příklad
Výrok p ...; Absolvování vstupního testu umožňuje studium Mat. Výrok p ...; Absolvování MatO umožňuje studium Mat. Výrok p V q: Absolvování vstupního testu, nebo absolvování MatO umožňuje studium Mat.
Pravdivostní tabulka
Disjunkce		
P	q	
1	1	1
1	0	1
0	1	1
0	0	0
Lukáš Kokrda
Množiny a výroková logika
Implikace
Implikace výroku p, q, značíme p =4> q;
Když výrok p, pak výrok q
Příklad		
Výrok p.	..; Dojedli jste oběd.	
\/ýro/c q.	..: Dostanete zmrzlinu.	
Výrok p =	=4> q: Když dojíte oběd, pak dostanete zmrzlinu.	
Pravdivostní tabulka
Implikace			
P	q	p ^ q	p^q
1	1	1	1
1	0	0	1
0	1	1	0
0	0	1	1
Lukáš Kokrda
Množiny a výroková logika
Ekvivalence výroku p, q, značíme p ^ q; Výrok p, právě tehdy, když výrok q
Příklad
Výrok p ...; Zaplatili jsme pokutu. Výrok q ...: Udělali jsme přestupek.
Výrok p ^=> q: Zaplatili jsme pokutu, právě tehdy, když jsme udělali přestupek.
Pravdivostní tabulka
Ekvivalence		
P	q	
1	1	1
1	0	0
0	1	0
0	0	1
Vzorový příklad
((a A b) O (b V c))
n.
((äJc)A(n(bVč)))
IV.
///.
V. VI.
w/,
a	b	c										
1	1	1										
1	1	0										
1	0	1										
1	0	0										
0	1	1										
0	1	0										
0	0	1										
0	0	0										
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (b V c))
n.
((äJc)A(n(bVč)))
IV.
///.
V. VI.
w/,
a	b	c	a										
1	1	1	0										
1	1	0											
1	0	1											
1	0	0	0										
0	1	1											
0	1	0											
0	0	1											
0	0	0											
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (b V c))
n.
((äJc)A(n(bVč)))
IV.
///.
V. VI.
w/,
a	b			a	c									
1	1			0	0									
1	1			0										
1	0			0										
1	0			0										
0	1			1										
0	1			1										
0	0			1										
0	0			1										
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (b V c))
n.
((äJc)A(n(bVč)))
IV.
///.
V. VI.
w/,
a	b	c	a	c	1.							
1	1	1	0	0								
1	1	0	0	1								
1	0	1	0	0	0							
1	0	0	0	1	o							
0	1	1	1	0	0							
0	1	0	1	1	0							
0	0	1	1	0	0							
0	0	0	1	1	0							
□ i5P
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (b V c))
n.
((äJc)A(n(bVč)))
IV.
///.
V. VI.
w/,
a					a	c	1.	II.						
1					0	0	1	1						
1					0	1	1	1						
1					0	0	0	1						
1					0	1	0	0						
0					1	0	0	1						
0					1	1	0	1						
0					1	0	0	1						
0					1	1	0	0						
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (b V c))
n.
((äJc)A(n(bVč)))
IV.
///.
v.
W.
VII.
a	b	c	a	c	1.	II.	III.					
1	1	1	0	0		1	1					
1	1	0	0	1		1	1					
1	0	1	0	0	0	1	0					
1	0	0	0	1	o	0	1					
0	1	1	1	0	0	1	0					
0	1	0	1	1	0	1	0					
0	0	1	1	0	0	1	0					
0	0	0	1	1	0	0	1					
□ i5P
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (b V c))
n.
((äJc)A(n(bVč)))
IV.
///.
v.
W.
VII,
a	b			a		c	1.	II.	III.	IV.					
1	1			0		0	1	1	1						
1	1					1	1	1	1						
1	0					0	0	1	0						
1	0			0		1	0	0	1						
0	1					0	0	1	0						
0	1					1	0	1	0						
0	0					0	0	1	0						
0	0					1	0	0	1						
□
S1
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (b V c))
///.
c) A (-.(b V č)))
W/,
v. w.
a			c	a	c		1.	II.	III.	IV.	v.				
1			1	0	0		1	1	1	1					
1			0	0			1	1	1	1	1				
1			1	0			0	1	0	1	0				
1			0	0			0	0	1	1	1				
0			1	1			0	1	0	1					
0			0	1			0	1	0	0	1				
0			1	1			0	1	0	1	0				
0			0	1			0	0	1	0	1				
□ i5P
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (b V c))
///.
c) A (-.(b V č)))
v.
VI.
W/,
a	b	c	a	c	1.	II.	III.	IV.	v.		VI.		
1	1	1	0	0	1	1	1	1			0		
1	1	0	0	1	1	1	1	1	1		0		
1	0	1	0	0	0	1	0	1	0		1		
1	0	0	0	1	0	0	1	1	1		0		
0	1	1	1	0	0	1	0	1			0		
0	1	0	1	1	0	1	0	0	1		0		
0	0	1	1	0	0	1	0	1	0		1		
0	0	0	1	1	0	0	1	0	1		0		
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (by c))
///.
c) A {-.{b V č)))
v.
VI.
W/,
a	b	c	a	c	1.	II.	III.	IV.	v.	VI.	VII.	
1	1	1	0	0	1	1	1		1	0	0	
1	1	0	0	1	1	1	1		1	0	0	
1	0	1	0	0	0	1	0		0	1	1	
1	0	0	0	1	0	0	1		1	0	0	
0	1	1	1	0	0	1	0		1	0	0	
0	1	0	1	1	0	1	0		1	0	0	
0	0	1	1	0	0	1	0		0	1	1	
0	0	0	1	1	0	0	1		1	0	0	
Lukáš Kokrda
Množiny a výroková logika
Vzorový příklad
((a A b) O (by c))
///.
c) A {-.{b V č)))
v.
VI.
W/,
a	b	c	a	c	1.	II.	III.	IV.	v.	VI.	VII.	VIII.
1	1	1	0	0	1	1		1	1	0	0	
1	1	0	0	1	1	1	1	1	1	0	0	0
1	0	1	0	0	0	1	0	1	0	1	1	1
1	0	0	0	1	0	0	1	1	1	0	0	0
0	1	1	1	0	0	1		1	1	0	0	
0	1	0	1	1	0	1	0	0	1	0	0	1
0	0	1	1	0	0	1	0	1	0	1	1	1
0	0	0	1	1	0	0	1	0	1	0	0	u
Lukáš Kokrda
Množiny a výroková logika
Negovaní výrokových operací
Pravidla pro úpravy spojek
• (p V q) ^(pAq)
• (pAq) ^(pVq)
• (p^q) ^(pAq)
• (p^ q)     ((p     q) A (p 4= q)) ^ ((p A q) V (p A q))
Lukáš Kokrda Množiny a výroková logika
Výroková forma
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í, a používání kvantifikátorů V, 3
• obecný kvantifikátor V „Pro všechna"
• existenční kvantifikátor 3 „Existuje alespoň jedno"
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.
Lukáš Kokrda 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.
9 pro Vx G {..., —3, —2, — 1, 0,1, 2, 3,...} platí x2 = 1. Pravidla pro negování výroků s kvantifikátory:
• (Vx e ...) ^ (3x e ...)
• (3x e ...) ^ (Vx e ...)
Příklad
• Existuje student, který na přednášce nebyl pozván na Opening Party Support Centre.
• 3x G {..., —3, -2, -1,0,1, 2,3,...} platíx2 ^ 1.
Lukáš Kokrda
Množiny a výroková logika
Výrokový počet
Příklad
Ukažme, že (P     (?) A ((?     P) = (P ^ (?)
■
]
Lukáš Kokrda
Množiny a výroková logika