ZÁKLADNÍ POJMY VÝROKOVÉ LOGIKY Výrok je každé sdělení, o němž má smysl říci, že je buď pravdivé nebo nepravdivé. Pozn. Není důležité, zda o pravdivosti či nepravdivosti výroku umíme rozhodnout. Podstatné je, zda má smysl o pravdivosti uvažovat, zda má smysl položit si otázku: „Je pravda, že...?“ Úkol 1: Rozhodněte, které z následujících vět jsou výroky: 1. Právě začalo pršet. 2. Na Marsu existují živé organismy. 3. Karel IV. byl v Praze r. 1348. 4. Rozvoj matematických představ. 5. Pojď k tabuli. 6. Číslo 4 je dělitelem čísla 134. 7. 100 : 5 = 20 8. 4 + x = 9 Výroky budeme dále označovat velkými tiskacími písmeny (A, B, C, P, Q, ...) nebo malými tiskacími písmeny (p, q, r, …). Tomuto označení říkáme výrokové proměnné. Ve výrokové logice nás nezajímá konkrétní obsah výroků, ale jejich pravdivost (pravdivostní hodnota). Každému výroku je možné přiřadit pravdivostní hodnotu: Je-li výrok A pravdivý, je jeho pravdivostní hodnota 1, píšeme Ph(A) = 1. Je-li výrok A nepravdivý, jeho pravdivostní hodnota je 0, píšeme Ph(A)=0. Negace výroku A je výrok ù A, který je pravdivý v případě, že výrok A je nepravdivý, a který je nepravdivý v případě, že výrok A je pravdivý. Př. A: Dnes je úterý. ù A: Dnes není úterý. (Není pravda, že je dnes úterý.) Složené výroky Z jednoduchých výroků můžeme tvořit složené výroky pomocí tzv. výrokotvorných (logických) spojek: - „a“, „a současně“, „a zároveň“ ( ) - „nebo“ ( ) - „buď, nebo“ ( ) - „jestliže, pak“; „A implikuje B“ ( ) - „právě tehdy, když“ ( ) Konjunkce výroků a, b je výrok a b, který je pravdivý v případě, že jsou oba výroky pravdivé. Disjunkce (alternativa) výroků a, b je výrok a b, který je pravdivý v případě, že je alespoň jeden z výroků a, b pravdivý. Ostrá disjunkce výroků a, b je výrok a b, který je pravdivý v případě, že je právě jeden z výroků a, b pravdivý. Implikace výroků a, b je výrok a b, který je nepravdivý jen v případě, že první výrok je pravdivý a druhý výrok je nepravdivý. Ve všech ostatních případech je implikace pravdivá. Ekvivalence výroků a, b je výrok a b, který je pravdivý v případě, že oba výroky mají stejnou pravdivostní hodnotu. Někdy se v běžném jazyce nevyjadřujeme přesně - je potřeba logické spojky odhalit: Úkol 2: Zapište symbolicky, nebo vyslovte pomocí logických spojek: a) Petr přijde s Evou. b) Pokud přijde Petr, přijde i Eva. c) Přijde Petr, ale Eva ne. d) Ze dvojice Petr a Eva přijde nejvýš jeden. e) Buď přijde Eva, nebo Petr. f) Eva přijde jen tehdy, když nepřijde Petr. Znaky výrokové logiky: - Výrokové proměnné A, B, P, Q, p, q, r, … - Logické spojky , , , , - Symbol pro negaci výroku ù - Závorky (), {}, [] Znaky výrokové logiky tvoří abecedu výrokové logiky. Pomocí znaků výrokové logiky lze tvořit složené útvary, tzv. výrokové formule. Jsou to zápisy, ve kterých se objevují výrokové proměnné a,b, p, q, .. log. spojky, závorky a to tak, že když dosadíme za výrokové proměnné konkrétní výroky, dostaneme výrok: Např. ù(a b) (ù a ù b). Pak nás zajímá, jaké pravdivostní hodnoty nabývá výsledný výrok v závislosti na pravdivosti výroků A, B. Tautologie je výroková formule, ze které vznikne pro všechny pravdivostní hodnoty výrokových proměnných, z nichž je složena, pravdivý výrok. Kontradikce je výroková formule, ze které vznikne pro všechny pravdivostní hodnoty výrokových proměnných, z nichž je složena, nepravdivý výrok. Splnitelná formule je výroková formule, ze které vznikne pro některé pravdivostní hodnoty výrokových proměnných, z nichž je složena, pravdivý výrok, pro jiné nepravdivý výrok. Výroková formule A je logicky ekvivalentní s výrokovou formulí B, jestliže výroková formule a b je tautologií. V logice nejpoužívanější logicky ekvivalentní výrokové formule ve skriptech (Panáčová, Beránek, 2020) najdete na str. 15. PRAVIDLA ODVOZOVÁNÍ Úsudek – spojení několika výroků, kdy poslední z nich (závěr) se odvozuje z předcházejících pravdivých (tzv. předpokladů). Z výrokové formule p vyplývá (plyne) výroková formule q právě tehdy, když výroková formule p q je tautologie. Zapisujeme . Případům, kdy z pravdivosti výroku p vyplývá pravdivost výroku q, říkáme správný úsudek nebo také pravidlo odvozování. Pravidla odvozování používáme při odvozování důsledků z daných předpokladů. Za výrokové proměnné dosazujeme výroky (jednotlivé, složené nebo kvantifikované). O správnosti těchto úsudků se můžeme přesvědčit pomocí tabulek pravdivostních hodnot příslušných formulí (musí jít o tautologie). ZÁKLADNÍ MNOŽINOVÉ POJMY Množina je takový souhrn objektů, že o každém objektu můžeme rozhodnout, zda do uvažovaného souhrnu objektů patří nebo nepatří. Pro každou množinu A a pro každý objekt a nastane právě jedna ze dvou možností: buď a A, nebo a A . Množina může být určena výčtem prvků nebo pomocí charakteristické vlastnosti, tj. jako obor pravdivosti výrokové formy. Příklad množiny: A = {2, 3, 5, 7} = {x ℕ; x je prvočíslo x < 10} Výroková forma v(x) je sdělení (výraz) obsahující proměnnou x; dosadíme-li za proměnnou x z vhodně zvolené množiny, získáme z výrokové formy výrok. Definičním oborem výrokové formy v(x) jedné proměnné x rozumíme množinu D, pro jejíž libovolný prvek po dosazení za proměnnou x dostaneme výrok. Oborem pravdivosti výrokové formy v(x) jedné proměnné x rozumíme množinu P, pro jejíž libovolný prvek po dosazení za proměnnou x dostaneme pravdivý výrok. Příklady výrokových forem: · x > 7, kde x ℕ · „x je prvočíslo“, x ℕ · 4x + 7 = 11, x ℕ Úkol 3: Přečtěte zápisy a určete množiny výčtem prvků: A = {x ℕ; x 10} B = {x ℕ; x je sudé číslo menší 10} C = {x ℕ; x je dělitelem čísla 10 } D = {x ℕ; x^2 = x} E = {x ℕ; x^3 < 30 x je liché číslo} F = {x ℕ; x je jednociferné číslo x = 10} Množina A je rovna množině B právě tehdy, když každý prvek množiny A je též prvkem množiny B a zároveň každý prvek množiny B je též prvkem množiny A. Zapisujeme A = B. Tento vztah nazýváme rovnost množin. Množina A je podmnožinou (částí) množiny B, právě tehdy, když každý prvek množiny A je též prvkem množiny B. Zapisujeme A B . Tento vztah nazýváme množinová inkluze. Úkol 3: Zapište všechny podmnožiny množiny X = {p, q, r, s}. Potenční systém množiny A je množina všech podmnožin množiny A (značíme P(A)). Množina A se rovná množině B (značíme A = B) právě tehdy, když každý prvek množiny A je prvkem množiny B a současně každý prvek množiny B je prvkem množiny A. (Platí tedy: A = B, právě když A B a B A.) Doplněk množiny A vzhledem k základní množině Z je množina všech prvků množiny Z, které nepatří do množiny A. A´ = {x Z; x A} Sjednocení množin A, B je množina prvků, které patří alespoň do jedné z množin A, B. A B = {x Z; x A x B} Průnik množin A, B je množina prvků, které patří do množiny A a současně do množiny B. A B = {x Z; x A x B} Rozdíl množin A, B je množina, která obsahuje právě ty prvky množiny A, které nepatří do množiny B. A – B = {x Z; x A x B} Symetrický rozdíl množin A, B je množina, která obsahuje ty prvky, které patří právě do jedné z množin. A B = {x Z; (x A x B }