MATA P1: Výroky, množiny a operace s nimi
Matematická logika (z řeckého slova
λογος
- LOGOS – „slovo, smysluplná řeč“)
•
Výrok – primitivní pojem matematické logiky. Tvrzení, pro které má smysl otázka o jeho pravdivosti. Příklady: • Praha je hlavní město České republiky. • • • • • •
2 je racionální číslo. Číslo 2 je menší než číslo 2 . Nezapomeňte napsat domácí cvičení! Druhá mocnina každého reálného čísla je větší nebo rovna nule. x≤3 Na planetě Mars existuje život.
Označování výroků – malá písmena latinské abecedy ( a, b, c, …) Pravdivostní hodnota výroku (dvouhodnotová funkce na množině výroků – dvouhodnotová logika)) a je pravdivý výrok … ph( a ) = 1 a je nepravdivý výrok … ph( a ) = 0
Negace výroku Označení ¬a , čteme „není pravda, že a “, „negace a “ Výrok ¬a má opačnou pravdivostní hodnotu, než výrok
a.
Příklady: (bez předřazení slov „není pravda že“ negujte následující výroky) • a : Hodnota dané funkce v bodě 3 je větší než 5. • b : V utkání padne aspoň 6 gólů. • c : Mezi uvedenými čísly jsou nejvýše tři prvočísla. • d : V testu jsem udělal právě dvě chyby. • e : Každý den je důvod k radosti. • f : Existuje aspoň jedno prvočíslo, které je sudé.
Logické operace a logické spojky Logická operace negace disjunkce konjunkce implikace
Logická spojka
ekvivalence
a⇔b
Čteme Není pravda, že a . a nebo b a a b , a a zároveň b Jestliže a, potom b, a je postačující podmínka pro ,. b je nutná podmínka pro a. a právě tehdy, jestliže b, a je nutná a postačující podmínka pro b.
¬a
a∨b a ∧b a⇒b
Formule výrokové logiky a) Každý výrok je formulí výrokové logiky. b) Jsou-li a a b formule výrokové logiky, potom ¬a, a ∨ b, a ∧ b, a ⇒ b, a ⇔ b jsou rovněž formule výrokové logiky. c) Všechny formule výrokové logiky vznikají konečným počtem aplikací pravidel a) a b). Význam logických spojek a 1 1 0 0
b 1 0 1 0
¬a 0 0 1 1
a∨b 1 1 1 0
a ∧b 1 0 0 0
a⇒b 1 0 1 1
a⇔b 1 0 0 1
Tautologie výrokové logiky Tautologií je každá formule výrokové logiky, která je vždy pravdivá, bez ohledu na pravdivost či nepravdivost vstupujících výroků.
Příklady: 1. Dokažte, že následující formule jsou tautologie: • a ∨ ¬a (zákon vyloučeného třetího) • ¬(¬a ) ⇔ a (zákon negace) • (a ⇒ b ) ⇔ (¬b ⇒ ¬a ) (pravidlo kontrapozice - obměna implikace) • ¬(a ∨ b ) ⇔ (¬a ∧ ¬b ) (1. de Morganovo pravidlo) • ¬(a ∧ b ) ⇔ (¬a ∨ ¬b ) (2. de Morganovo pravidlo) • (a ⇔ b ) ⇔ ((a ⇒ b ) ∧ (b ⇒ a )) • (a ⇔ b ) ⇔ (¬b ⇔ ¬a ) • ((a ∧ b ) ⇒ c ) ⇔ (a ⇒ (b ⇒ c )) • (a ∧ b ) ⇔ (b ∧ a ) , (a ∨ b ) ⇔ (b ∨ a ) , (a ⇔ b ) ⇔ (b ⇔ a ) (a ∨ a ) ⇔ a , a ⇒ (a ∨ b ) , (a ∧ b ) ⇒ a , • (a ∧ a ) ⇔ a ,
a ⇒ a, a ⇔ a
• (a ⇒ b ) ⇔ (¬a ∨ b ) , (a ∨ b ) ⇔ (¬a ⇒ b ) • ¬(a ⇒ b ) ⇔ (a ∧ ¬b ) (negace (a ∧ b ) ⇔ ¬(a ⇒ ¬b ) .
implikace),
Problém: Kolik nejméně logických spojek je potřeba pro zápis logických formulí? 2. Vyslovte obměnu, obrácení a negaci implikace: „Jestliže nebudu připraven, budu vyvolán“. 3. Vyslovte obměnu, obrácení a negaci věty: (∀x ∈ N ) (2 nedělí n dělí n + 1).
⇒2
4. Petr a Pavel čekají před kinem na své dva spolužáky Adama, Břetislava a Cyrila. Petr tvrdí: „Přijde-li Adam a Břetislav, přijde i Cyril.“ Pavel říká: „Já myslím, že když přijde Adam a nepřijde Cyril, nepřijde ani Břetislav.“ Na to povídá Petr: „To přece říkáš totéž co já“. Rozhodněte, zda oba skutečně říkají totéž.
Predikátová logika a( x ) je predikát s volnou proměnnou x na množině M, jestliže platí: dosadíme-li za x v a(x ) libovolný prvek c z M, potom a(c ) je výrok
(ať již pravdivý nebo nepravdivý).
Příklady predikátů: • 2x – 3 = 0 • Přímka p protíná kružnici k se středem v počátku soustavy souřadnic a s poloměrem 2. • Na planetě x ve Sluneční soustavě existuje život. • Obyvatel planety Země je gramotný. Uvažujeme množinu { x ∈ M ; a(x ) } = X. • Pokud platí: X = M, zapíšeme tuto skutečnost zápisem (∀x ∈ M )(a(x )) , čteme „pro všechna x z M platí a(x ) “ ( ∀ nazýváme obecný kvantifikátor). • Pokud platí: X ≠ ∅ , zapíšeme tuto skutečnost zápisem (∃x ∈ M )(a(x )) , čteme „existuje x z množiny M, tak, že a(x)“ ( ∃ nazýváme existenční kvantifikátor).
Tautologie predikátové logiky (Negace formulí s kvantifikátory) • ¬((∃x ∈ M )(a(x ))) ⇔ (∀x ∈ M )(¬a(x )) • ¬((∀x ∈ M )(a(x ))) ⇔ (∃x ∈ M )(¬a(x ))
Negování výroků s kvantifikátory:
a
¬a
Každý prvek množiny M má danou vlastnost Aspoň jeden prvek množiny M má danou vlastnost. Množina M má aspoň k prvků.
Aspoň jeden prvek množiny M nemá danou vlastnost Žádný prvek množiny M nemá danou vlastnost. Množina M má nejvýše k – 1 prvků. Množina M má aspoň k + 1 prvků. Množina M má nejvýše k – 1 nebo aspoň k + 1 prvků.
Množina M má nejvýše k prvků. Množina M má právě k prvků.
Příklady: 5. Vyjádřete pomocí nástrojů predikátové logiky následující tvrzení: ke každému x z množiny A existuje y z množiny B tak, že pro všechna z z množiny A platí: x je prvkem y a zároveň z je různé od y. Zapište negaci vzniklé formule a zjednodušte ji. 6. Utvořte negaci výroků: • Do divadla se mnou půjde nejvýše jeden z mých dvou bratrů. • Budu-li vytrvalý, dosáhnu svého cíle. • Chléb koupím právě tehdy, když nekoupím rohlíky. 7. Činnost generátorů A, B, C v jedné elektrárně je dána podmínkami: Když není v chodu A, je v činnosti B. Jestliže není v provozu B a není v provozu ani C, pak je mimo provoz i A. Je-li vypnut A a zapnut B, pak je zapnut také C. Určete všechny možnosti pro práci této trojice generátorů. Podmínku vyjádřete jedním výrokem.
