KAPITOLA 1
Základní pojmy matematické logiky Matematická logika se zabývá studiem výroků, jejich vytváření a jejich pravdivostí. Základním kamenem výrokové logiky jsou výroky. 1. Výroková logika Co je výrok nedefinujejme, pouze si řekneme, co si pod pojmem výrok představujeme. Za výrok budeme považovat každé tvrzení (každou větu) o kterém se dá rozhodnout, zda je pravdivé či nikoliv. Za výroky tedy považujeme pouze oznamovací věty, o kterých umíme rozhodnout zda jsou pravdivé či ne. Výrokem jsou tedy například tvrzení ”jedna a jedna jsou dvě”, ”jedna a jedna jsou tři”, ”dnes je pátek” atd. Výrokem naopak nejsou věty typu ”kolik je jedna a jedna?” či ”je dnes pátek?”. Výroková logika pracuje pouze se základními výroky (o jejichž pravdivosti umíme rozhodnout a o jejichž strukturu se nazajímáme)a zjišťuje pravdivost složených výroků vytvářených ze základních výroků na základě pravdivosti výroků základních. Pro vytváření složitějších výroků se používají tzv. logické spojky negace, konjunkce, disjunkce, implikace a ekvivalence. Tyto spojky mají následující význam: • negace znamená není pravda, že – budeme ji označovat symbolem ¬, • konjunkce znamená a zároveň – budeme ji označovat symbolem ∧, • disjunkce znamená nebo – budeme ji označovat symbolem ∨, • implikace znamená jestliže . . . , potom . . . – budeme ji označovat symbolem ⇒, • ekvivalence znamená . . . právě tehdy, když . . . – budeme ji označovat symbolem ⇔. Dále budeme základní výroky nazývat elementárními výroky a z nich vytvářené výroky budeme nazývat výrokové formule, a to ve smyslu následující definice, která zavádí tzv. formální jazyk výrokového počtu. Definice. Nechť A je množina elementárních výroků. Výrokové formule (nad množinou A) definujeme takto: (1) každý elementární výrok je formule, (2) jsou–li α a β výrokové formule, potom ¬α, α ∧ β, α ∨ β, α ⇒ β a α ⇔ β jsou opět výrokové formule, (3) každá výroková formule vzniká konečným počtem kroků podle uvedených pravidel 1. a 2. Množinu všech výrokových formulí nad množinou A (tj. které vznikly z elementárních výroků z množiny A) budeme značit V (A) a její prvky, tj. výrokové formule, budeme obvykle značit malými řeckými písmeny α, β, γ, . . . . Místo pojmu výroková formule budeme používat zkráceně jen formule. Při jejich zápisu budeme obvykle používat zjednodušení spočívající v tom, že například místo (¬α) ⇒ β budeme psát ¬α ⇒ β a budeme vynechávat vnější závorky, tj. například místo zápisu (α ⇒ (α ∨ β)) budeme psát α ⇒ (α ∨ β). Vynechávat budeme pouze nejvíce vnější závorky. Ostatní závorky uvádět budeme, abychom poznali která 1
2
1. ZÁKLADNÍ POJMY MATEMATICKÉ LOGIKY
spojka patří ke kterým formulím. Uvědomte si, že formule α ∨ (β ∧ γ) je jiná než formule (α ∨ β) ∧ γ. 1.1. Pravdivostní ohodnocení formulí. Uvědomme si, že při zkoumání pravdivostí výrokových formulí není důležité jak logické spojky čteme, nebo jak je značíme, ale důležité je jaký jim dáme význam, a to musíme definovat. Je samozřejmé, že definice budou kopírovat jazykový význam spojek. Budeme tedy říkat, že • formule ¬α je pravdivá, právě tehdy, když je α nepravdivá, • formule α ∧ β je pravdivá, právě tehdy, když jsou obě formule α i β pravdivé, • formule α ∨ β je pravdivá, právě tehdy, je–li alespoň jedna z formulí α nebo β pravdivá, • formule α ⇒ β je pravdivá, právě tehdy, je–li pravdivá α, pak je nutně pravdivá i β, • formule α ⇔ β je pravdivá, právě tehdy, když jsou obě formule α a β pravdivé nebo jsou obě formule α a β nepravdivé. Pravdivostní ohodnocení výrokových formulí je tedy ve skutečnosti zobrazení množiny V (A) → {0, 1}, které splňuje výše uvedená pravidla. Tato pravidla (vlastně i definice významu logických spojek) si můžeme i zobrazit v tzv. pravdivostní tabulce. α
β
¬α
α∧β
α∨β
α⇒β
α⇔β
1
1
0
1
1
1
1
1
0
0
0
1
0
0
0
1
1
0
1
1
0
0
0
1
0
0
1
1
Definice. Formuli budeme nazývat tautologií, je-li vždy pravdivá (tj. její pravdivost nezávisí na pravdivosti či nepravdivosti elemntárních výroků, které v sobě obsahuje) a formuli, která je vždy nepravdivá budeme nazývat kontradikcí. Formule, které nejsou kontradikce, nazýváme splnitelné formule. Pravdivostní hodnoty formulí můžeme získávat tak, že si vytváříme pravdivostní tabulku pro danou formuli. Tabulka obsahuje sloupec pro každou proměnnou (tj. formuli, značenou α, β, γ, . . . ), která se ve formuli vyskytuje, a sloupec pro zkoumanou formuli. Je vhodné též si do tabulky zavést i sloupce pro některé podformule dané formule. Pokud formule obsahuje n proměnných, které mohou nabývat pravdivostní ohodnocení 0 i 1, pak její pravdivostní tabulka musí mít 2n řádků. Příklad. Ověřme, že (pro každou formuli α) formule α ∨ ¬α je tautologie a že formule α ∧ ¬α je kontradikace. Utvořme si pravdivostní tabulky pro obě formule. Dostaneme α
¬α
α ∨ ¬α
α ∧ ¬α
1
0
1
0
0
1
1
0
a ihned vidíme, že formule α ∨ ¬α je tautologie a že formule α ∧ ¬α je kontradikace.
2. PREDIKÁTOVÁ LOGIKA
3
Příklad. Rozhodněme, zda formule ϕ : (α ⇒ β) ⇒ ((¬α ∨ β) ∧ (β ⇒ ¬α)) je kontradikce, splnitelná formule nebo tautologie. Utvořme si pravdivostní tabulku pro formuli ϕ. Dostaneme α
β
α⇒β
¬α ∨ β
β ⇒ ¬α
(¬α ∨ β) ∧ (β ⇒ ¬α)
ϕ
1
1
1
1
0
0
0
1
0
0
0
1
0
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
Protože v posledním sloupci nejsou samé 0, nejdná se o kontradikci. Jelikož v posledním sloupci tabulky nejsou samé 1, nejedná se o tautologii. Formule ϕ je tedy splnitelná fomule, která není tautologií. Příklad. Ověřme, že formule α ∧ (β ∨ γ) a (α ∧ β) ∨ (α ∧ γ) jsou ekvivalentní. Utvořme si pravdivostní tabulky pro obě formule. α
β
γ
β∨γ
α ∧ (β ∨ γ)
α∧β
α∧γ
(α ∧ β) ∨ (α ∧ γ)
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
Protože pravdivostní ohodnocení obou formulí je naprosto stejné (pátý a osmý sloupec), jsou obě formule ekvivalentní, tj. je α ∧ (β ∨ γ) ⇔ (α ∧ β) ∨ (α ∧ γ). 2. Predikátová logika Aparát výrokové logiky neumožňuje zkoumat pravdivost složitějších úsudků. Proto je nutno aparát výrokové logiky rozšířit a zobecnit procesy známé z výrokové logiky. Místo pojmu elementární výrok si zavedem pojem predikát. Tento pojem si přiblížíme spíše intuitivně než formálně zcela přesně. Predikát se může obecně týkat několika objektů a proto každý predikát má svou aritu (tj. přirozené číslo udávající počet objektů kterých se týká). Predikáty budeme značit velkými písmeny, např. P (x) nebo Q(x,y,z). Z označení je i zřejmá arita predikátu. Symboly x, y, z, . . . se nazývají volné proměnné predikátu a jsou omezeny na příslušnost k nějaké dané množině, např. se bude jednat o přirozená čísla, o reálná čísla apod. Predikáty v sobě mohou obsahovat i funkční či relační symboly. Predikátem může být třeba Q(x, y) = x2 < y. Pro predikáty platí požavadek, aby se po dosazení konkrétních hodnot za volné proměnné jednalo o výrok, pravdivý či nepravdivý. predikátový
4
1. ZÁKLADNÍ POJMY MATEMATICKÉ LOGIKY
počet je ještě obohacen o dva logické symboly, a to o existenční kvantifikátor ∃ a obecný kvantifikátor ∀. Nyní si uvedeme definici formule predikátového počtu. Definice. Nechť A je množina predikátů. Množina všech formulí predikátového počtu (nad množinou A) je definována takto: (1) každý predikát je formule, (2) jsou–li α a β predikátové formule, potom ¬α, α ∧ β, α ∨ β,α ⇒ β a α ⇔ β jsou opět formule, (3) je-li α formule a x volná proměnná, pak ∀x α a ∃x α jsou opět formule; (4) každá výroková formule vzniká konečným počtem kroků podle pravidel 1., 2. a 3. Množinu všech výrokových formulí nad množinou A (tj. které vznikly z elementárních výroků z množiny A) budeme značit P (A) a její prvky, tj. výrokové formule, budeme obvykle značit malými řeckými písmeny α, β, γ, . . . , případně s uvedením volných proměnných, tj. např. α(x), β(x, y) apod. Při zápisu formulí budeme opět používat zjednodušení jako v případě formulí výrokového počtu, např. budeme vynéchávat nejvíce vnější závorky. Pokud budou důležité i množiny ze kterých lze dosazovat volné proměnné, můžeme používat zápisy typu ∀(x ∈ M ), ∃(y ∈ B). Poznamenejme, že název či označení proměnné není důležité, důležitý je obsah. Dvě formule, které se liší pouze pojmenováním proměnných u symbolů ∀ a ∃ považujeme za totožné. Tedy formule ∀x α(x) je totožná s formulí ∀y α(y). Pro přehlednost budeme v jedné formuli raději používat různé symboly i pro proměnné svázané s existenčním nebo obecným kvantifikátorem. Ukažme si jeden příklad. Tvrzení ”ke každému reálnému číslu existuje reálné číslo větší” lze popsat predikátovou formulí ϕ(x, y) = ∀x(∃y(x < y)) a tvrzení ”ke každému reálnému číslu existuje reálné číslo menší” lze popsat predikátovou formulí δ(x, y) = ∀x(∃y(y < x)). Tvrzení ”ke každému reálnému číslu existuje reálné číslo menší a existuje reálné číslo menší” je popsatelné konjunkcí ϕ(x, y) ∧ δ(x, y) = (∀x(∃y(x < y))) ∧ (∀x(∃y(y < x))). Ekvivalentně a přehledněji je tvrzení popsáno formulí ϕ(x, y) ∧ δ(x, z) = (∀x(∃y(x < y))) ∧ (∀x(∃z(z < x))). Analogicky jako v případě výrokového počtu nazveme formuli tautologií, pokud je pravdivá při každém dosazení volných proměnných. Tautologií tak bude např. formule ∀x α(x) ∨ ¬(∀x α(x)). Věta. Nechť α(x) a β(x) jsou formule predikátového počtu s volnou proměnnou x. Následující formule jsou tautologie predikátového počtu: (1) ¬(∃x α(x)) ⇔ ∀x (¬α(x)); (2) ¬(∀x α(x)) ⇔ ∃x (¬α(x)); (3) ∃x α(x) ⇔ ¬(∀x (¬α(x))); (4) ∀x α(x) ⇔ ¬(∃x (¬α(x))); (5) ∀x α(x) ∨ (∃x ¬α(x)); (6) ∃x α(x) ∨ (∀x ¬α(x)); (7) (∃x α(x)) ∨ ((∃x β(x)) ⇔ ∃x (α(x) ∨ β(x)). (8) (∀x α(x)) ∧ ((∀x β(x)) ⇔ ∀x (α(x) ∧ β(x)). Ukažme si na příkladě jak pomocí formulí predikátového počtu popsat některá tvrzení. Příklad. Zapište pomocí predikátové formule tvrzení: je–li přirozené číslo dělitelné patnácti, pak je dělitelné pěti i třemi. Symbolem N označíme množinu všech přirozených čísel. Přirozené číslo n je dělin je přirozené. Symbol ∈ označuje příslušnost do telné patnácti, právě tehdy, když 15 množiny. Naše tvrzení je možno popsat formulí
2. PREDIKÁTOVÁ LOGIKA
5
x ∀(x ∈ N)( 15 ∈ N ⇒ ( x5 ∈ N ∧ x3 ∈ N)). Samozřejmě jsou i jiné ekvivalentní formule popisující dané tvrzení. Například, budeme–li tvrzení, že přirozené číslo x je dělitelné patnácti popisovat ekvivalentním způsobem ∃y ∈ N(15 = x · y) bude naše formule mít tvar ∀(x ∈ N)(∃y ∈ N(x = 15 · y)) ⇒ ((∃z ∈ N(x = 5 · z)) ∧ (∃t ∈ N(x = 3 · t))).
Příklad. Zapište pomocí predikátové formule tvrzení: ke každému reálnému číslu existuje nejmenší přirozené číslo, které je větší než dané reálné číslo. Označme symbolem R množinu všech reálných čísel a symbolem N množinu všech přirozených čísel, symbolem a < b označujme, že reálné číslo a je menší než reálné číslo b. Naše tvrzení je možno popsat formulí ∀(x ∈ R)(∃(y ∈ N)(∀(z ∈ N)((x < z) ⇒ ((y < z) ∨ (y = z)))).
