' $'
&
$
%Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": Úvod do Logiky
7 Jemný úvod do Logiky7 Jemný úvod do Logiky
Základem přesného matematického vyjadřování je správné používání (matematické)
logiky a logických úsudků. Logika jako filozofická disciplína se intenzivně vyvíjí už od
dob antiky, avšak ke skutečnému rozmachu logiky coby součásti matematiky došlo až
začátkem 20. století.
' $'
&
$
%Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": Úvod do Logiky
7 Jemný úvod do Logiky7 Jemný úvod do Logiky
Základem přesného matematického vyjadřování je správné používání (matematické)
logiky a logických úsudků. Logika jako filozofická disciplína se intenzivně vyvíjí už od
dob antiky, avšak ke skutečnému rozmachu logiky coby součásti matematiky došlo až
začátkem 20. století.
Dnes se samozřejmě základní logický kalkulus používá nejen v matematice, ale ,,stojí
na něm veškeré logické obvody a počítače.
Stručný přehled lekce
* Výroky v přirozené mluvě a formální výroková logika.
* Mechanický postup negace výrokových formulí.
* Neformální zmínka o predikátové logice (a kvantifikátorech).
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Úvod do Logiky
7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém
má smysl prohlásit, že je buď pravdivé nebo nepravdivé.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Úvod do Logiky
7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém
má smysl prohlásit, že je buď pravdivé nebo nepravdivé.
Několik příkladů, které z nich jsou výroky?
ˇ Dnes už v Brně pršelo.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Úvod do Logiky
7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém
má smysl prohlásit, že je buď pravdivé nebo nepravdivé.
Několik příkladů, které z nich jsou výroky?
ˇ Dnes už v Brně pršelo.
ˇ Předmět IB000 se vyučuje v prvním ročníku.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Úvod do Logiky
7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém
má smysl prohlásit, že je buď pravdivé nebo nepravdivé.
Několik příkladů, které z nich jsou výroky?
ˇ Dnes už v Brně pršelo.
ˇ Předmět IB000 se vyučuje v prvním ročníku.
ˇ Platí 2 + 3 = 6.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Úvod do Logiky
7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém
má smysl prohlásit, že je buď pravdivé nebo nepravdivé.
Několik příkladů, které z nich jsou výroky?
ˇ Dnes už v Brně pršelo.
ˇ Předmět IB000 se vyučuje v prvním ročníku.
ˇ Platí 2 + 3 = 6.
ˇ To je bez problémů. (Co?)
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Úvod do Logiky
7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém
má smysl prohlásit, že je buď pravdivé nebo nepravdivé.
Několik příkladů, které z nich jsou výroky?
ˇ Dnes už v Brně pršelo.
ˇ Předmět IB000 se vyučuje v prvním ročníku.
ˇ Platí 2 + 3 = 6.
ˇ To je bez problémů. (Co?)
ˇ Platí x > 3.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Úvod do Logiky
7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém
má smysl prohlásit, že je buď pravdivé nebo nepravdivé.
Několik příkladů, které z nich jsou výroky?
ˇ Dnes už v Brně pršelo.
ˇ Předmět IB000 se vyučuje v prvním ročníku.
ˇ Platí 2 + 3 = 6.
ˇ To je bez problémů. (Co?)
ˇ Platí x > 3.
ˇ Pro každé celé číslo x platí, že x > 3.
' $'
&
$
%Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Úvod do Logiky
7.1 Výroky v ,,přirozené podobě7.1 Výroky v ,,přirozené podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém
má smysl prohlásit, že je buď pravdivé nebo nepravdivé.
Několik příkladů, které z nich jsou výroky?
ˇ Dnes už v Brně pršelo.
ˇ Předmět IB000 se vyučuje v prvním ročníku.
ˇ Platí 2 + 3 = 6.
ˇ To je bez problémů. (Co?)
ˇ Platí x > 3.
ˇ Pro každé celé číslo x platí, že x > 3.
Všimněte si, že pravdivost výroku by mělo být možné rozhodnout bez skrytých souvis-
lostí (kontextu), a proto čtvrtý a pátý příklad za výroky nepovažujeme.
Fakt: Z jednoduchých výroků můžeme vytvářet výroky složitější pomocí tzv.
logických spojek.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Úvod do Logiky
Několik dalších příkladů.
ˇ Kateřina přijede ve 12:00 a půjdeme spolu do kina.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Úvod do Logiky
Několik dalších příkladů.
ˇ Kateřina přijede ve 12:00 a půjdeme spolu do kina.
ˇ Množina {a, b} má více než jeden prvek a není nekonečná.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Úvod do Logiky
Několik dalších příkladů.
ˇ Kateřina přijede ve 12:00 a půjdeme spolu do kina.
ˇ Množina {a, b} má více než jeden prvek a není nekonečná.
ˇ Jestliže má Karel přes 90 kilo váhy, nepojedu s ním výtahem.
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Úvod do Logiky
Několik dalších příkladů.
ˇ Kateřina přijede ve 12:00 a půjdeme spolu do kina.
ˇ Množina {a, b} má více než jeden prvek a není nekonečná.
ˇ Jestliže má Karel přes 90 kilo váhy, nepojedu s ním výtahem.
ˇ Jestliže má kráva 10 nohou, mají všechny domy modrou střechu.
Schopnost porozumět takovýmto větám je součást lidského způsobu uvažování
a z tohoto hlediska nemá přímou souvislost s matematikou (je to ,,přirozená
logika ).
' $'
&
$
%Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Úvod do Logiky
Několik dalších příkladů.
ˇ Kateřina přijede ve 12:00 a půjdeme spolu do kina.
ˇ Množina {a, b} má více než jeden prvek a není nekonečná.
ˇ Jestliže má Karel přes 90 kilo váhy, nepojedu s ním výtahem.
ˇ Jestliže má kráva 10 nohou, mají všechny domy modrou střechu.
Schopnost porozumět takovýmto větám je součást lidského způsobu uvažování
a z tohoto hlediska nemá přímou souvislost s matematikou (je to ,,přirozená
logika ).
Formální (matematická) logika pak definuje jazyk matematiky a odstraňuje
nejednoznačnosti přirozeného jazyka.
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Úvod do Logiky
7.2 (Formální) výroková logika7.2 (Formální) výroková logika
Definice 7.1. Syntaxe výrokové logiky.
Buď AT = {A, B, C, . . .} spočetně nekonečná množina výrokových proměnných
(tzv. atomů).
Množina výrokových formulí  je definována induktivně následujícími pravidly:
(1) AT  .
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Úvod do Logiky
7.2 (Formální) výroková logika7.2 (Formální) výroková logika
Definice 7.1. Syntaxe výrokové logiky.
Buď AT = {A, B, C, . . .} spočetně nekonečná množina výrokových proměnných
(tzv. atomů).
Množina výrokových formulí  je definována induktivně následujícími pravidly:
(1) AT  .
(2) Jestliže ,   , pak také ()   a ()  ()  .
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Úvod do Logiky
7.2 (Formální) výroková logika7.2 (Formální) výroková logika
Definice 7.1. Syntaxe výrokové logiky.
Buď AT = {A, B, C, . . .} spočetně nekonečná množina výrokových proměnných
(tzv. atomů).
Množina výrokových formulí  je definována induktivně následujícími pravidly:
(1) AT  .
(2) Jestliže ,   , pak také ()   a ()  ()  .
(3) Každý prvek  vznikne konečně mnoha aplikacemi pravidel (1) a (2).
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Úvod do Logiky
7.2 (Formální) výroková logika7.2 (Formální) výroková logika
Definice 7.1. Syntaxe výrokové logiky.
Buď AT = {A, B, C, . . .} spočetně nekonečná množina výrokových proměnných
(tzv. atomů).
Množina výrokových formulí  je definována induktivně následujícími pravidly:
(1) AT  .
(2) Jestliže ,   , pak také ()   a ()  ()  .
(3) Každý prvek  vznikne konečně mnoha aplikacemi pravidel (1) a (2).
Značení: Symbol  je zván negací a  je nazýván implikací.
Příklady několika správně utvořených formulí:
A, (A)  (B), ((A)  ((B)))  (((B))  (C))
' $'
&
$
%Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Úvod do Logiky
7.2 (Formální) výroková logika7.2 (Formální) výroková logika
Definice 7.1. Syntaxe výrokové logiky.
Buď AT = {A, B, C, . . .} spočetně nekonečná množina výrokových proměnných
(tzv. atomů).
Množina výrokových formulí  je definována induktivně následujícími pravidly:
(1) AT  .
(2) Jestliže ,   , pak také ()   a ()  ()  .
(3) Každý prvek  vznikne konečně mnoha aplikacemi pravidel (1) a (2).
Značení: Symbol  je zván negací a  je nazýván implikací.
Příklady několika správně utvořených formulí:
A, (A)  (B), ((A)  ((B)))  (((B))  (C))
A také příklady několika ne zcela správně utvořených formulí:
A  B, A  B  C, A  B
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Úvod do Logiky
Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to
nepovede k nejednoznačnostem za předpokladu, že negace  má ,,vyšší prioritu
než . (Touto úmluvou se nemění množina ; mění se jen způsob reprezentace
jejích prvků.
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Úvod do Logiky
Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to
nepovede k nejednoznačnostem za předpokladu, že negace  má ,,vyšší prioritu
než . (Touto úmluvou se nemění množina ; mění se jen způsob reprezentace
jejích prvků.
Dále si zavedeme, že
    (disjunkce) je jiný zápis formule   ,
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Úvod do Logiky
Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to
nepovede k nejednoznačnostem za předpokladu, že negace  má ,,vyšší prioritu
než . (Touto úmluvou se nemění množina ; mění se jen způsob reprezentace
jejích prvků.
Dále si zavedeme, že
    (disjunkce) je jiný zápis formule   ,
    (konjunkce) je jiný zápis formule (  ),
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Úvod do Logiky
Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to
nepovede k nejednoznačnostem za předpokladu, že negace  má ,,vyšší prioritu
než . (Touto úmluvou se nemění množina ; mění se jen způsob reprezentace
jejích prvků.
Dále si zavedeme, že
    (disjunkce) je jiný zápis formule   ,
    (konjunkce) je jiný zápis formule (  ),
    (ekvivalence) je jiný zápis formule (  )  (  ).
' $'
&
$
%Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Úvod do Logiky
Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to
nepovede k nejednoznačnostem za předpokladu, že negace  má ,,vyšší prioritu
než . (Touto úmluvou se nemění množina ; mění se jen způsob reprezentace
jejích prvků.
Dále si zavedeme, že
    (disjunkce) je jiný zápis formule   ,
    (konjunkce) je jiný zápis formule (  ),
    (ekvivalence) je jiný zápis formule (  )  (  ).
Například formule (((A)  (B)))  (((B))  (C)) se dá s naší konvencí
zapsat jako
(A  B)  B  C .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce  : AT  {true, false}.
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce  : AT  {true, false}.Pro každou valuaci 
definujeme funkci S :   {true, false} (vyhodnocení) induktivně takto:
ˇ S(A) = (A) pro každé A  AT .
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce  : AT  {true, false}.Pro každou valuaci 
definujeme funkci S :   {true, false} (vyhodnocení) induktivně takto:
ˇ S(A) = (A) pro každé A  AT .
ˇ S() =
true jestliže S() = false;
false jinak.
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce  : AT  {true, false}.Pro každou valuaci 
definujeme funkci S :   {true, false} (vyhodnocení) induktivně takto:
ˇ S(A) = (A) pro každé A  AT .
ˇ S() =
true jestliže S() = false;
false jinak.
ˇ S(  ) =
false jestliže S() = true a S() = false;
true jinak.
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce  : AT  {true, false}.Pro každou valuaci 
definujeme funkci S :   {true, false} (vyhodnocení) induktivně takto:
ˇ S(A) = (A) pro každé A  AT .
ˇ S() =
true jestliže S() = false;
false jinak.
ˇ S(  ) =
false jestliže S() = true a S() = false;
true jinak.
Tvrzení 7.4. Důsledkem této definice je následovné:
ˇ S(  ) = true právě když S() = true nebo S() = true.
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce  : AT  {true, false}.Pro každou valuaci 
definujeme funkci S :   {true, false} (vyhodnocení) induktivně takto:
ˇ S(A) = (A) pro každé A  AT .
ˇ S() =
true jestliže S() = false;
false jinak.
ˇ S(  ) =
false jestliže S() = true a S() = false;
true jinak.
Tvrzení 7.4. Důsledkem této definice je následovné:
ˇ S(  ) = true právě když S() = true nebo S() = true.
ˇ S() = true právě když S() = true a současně S() = true.
' $'
&
$
%Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce  : AT  {true, false}.Pro každou valuaci 
definujeme funkci S :   {true, false} (vyhodnocení) induktivně takto:
ˇ S(A) = (A) pro každé A  AT .
ˇ S() =
true jestliže S() = false;
false jinak.
ˇ S(  ) =
false jestliže S() = true a S() = false;
true jinak.
Tvrzení 7.4. Důsledkem této definice je následovné:
ˇ S(  ) = true právě když S() = true nebo S() = true.
ˇ S() = true právě když S() = true a současně S() = true.
ˇ S(  ) = true právě když platí jedna z následujících podmínek
 S() = true a současně S() = true,
 S() = false a současně S() = false.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Úvod do Logiky
Poznámka: Tento předpis podává nejen definici funkce S, ale také návod na to, jak
ji pro daný argument vypočítat.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Úvod do Logiky
Poznámka: Tento předpis podává nejen definici funkce S, ale také návod na to, jak
ji pro daný argument vypočítat.
Pravdivostní hodnoty
V praxi vyhodnocení logické (výrokové) formule zapisujeme často tzv. pravdi-
vostní tabulkou. Tabulka typicky má sloupce pro jednotlivé proměnné, případné
,,meziformule a výslednou formuli. Řádků je pak 2p, kde p je počet použitých
proměnných. Místo true, false píšeme 1, 0.
' $'
&
$
%Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Úvod do Logiky
Poznámka: Tento předpis podává nejen definici funkce S, ale také návod na to, jak
ji pro daný argument vypočítat.
Pravdivostní hodnoty
V praxi vyhodnocení logické (výrokové) formule zapisujeme často tzv. pravdi-
vostní tabulkou. Tabulka typicky má sloupce pro jednotlivé proměnné, případné
,,meziformule a výslednou formuli. Řádků je pak 2p, kde p je počet použitých
proměnných. Místo true, false píšeme 1, 0.
Příklad 7.5. Jaká je pravdivostní tabulka pro formuli (A  B)  B  C?
A B C A  B (A  B)  B  C
0 0 0 1 1
0 1 0 1 1
1 0 0 0 0
1 1 0 1 1
0 0 1 1 1
0 1 1 1 1
1 0 1 0 1
1 1 1 1 1 2
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Úvod do Logiky
Definice: Formule    je splnitelná, pokud pro některou valuaci  platí, že
S() = true.
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Úvod do Logiky
Definice: Formule    je splnitelná, pokud pro některou valuaci  platí, že
S() = true.
Formule    je vždy pravdivá (také výroková tautologie), psáno |= , pokud
pro každou valuaci  platí, že S() = true.
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Úvod do Logiky
Definice: Formule    je splnitelná, pokud pro některou valuaci  platí, že
S() = true.
Formule    je vždy pravdivá (také výroková tautologie), psáno |= , pokud
pro každou valuaci  platí, že S() = true.
Řekneme, že dvě formule ,    jsou ekvivalentní, právě když |=   .
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Úvod do Logiky
Definice: Formule    je splnitelná, pokud pro některou valuaci  platí, že
S() = true.
Formule    je vždy pravdivá (také výroková tautologie), psáno |= , pokud
pro každou valuaci  platí, že S() = true.
Řekneme, že dvě formule ,    jsou ekvivalentní, právě když |=   .
Tvrzení 7.6. Několik užitečných tautologií:
ˇ |= A  A
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Úvod do Logiky
Definice: Formule    je splnitelná, pokud pro některou valuaci  platí, že
S() = true.
Formule    je vždy pravdivá (také výroková tautologie), psáno |= , pokud
pro každou valuaci  platí, že S() = true.
Řekneme, že dvě formule ,    jsou ekvivalentní, právě když |=   .
Tvrzení 7.6. Několik užitečných tautologií:
ˇ |= A  A
ˇ |=  A  A
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Úvod do Logiky
Definice: Formule    je splnitelná, pokud pro některou valuaci  platí, že
S() = true.
Formule    je vždy pravdivá (také výroková tautologie), psáno |= , pokud
pro každou valuaci  platí, že S() = true.
Řekneme, že dvě formule ,    jsou ekvivalentní, právě když |=   .
Tvrzení 7.6. Několik užitečných tautologií:
ˇ |= A  A
ˇ |=  A  A
ˇ |= (A  (A  B))  B
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Úvod do Logiky
Definice: Formule    je splnitelná, pokud pro některou valuaci  platí, že
S() = true.
Formule    je vždy pravdivá (také výroková tautologie), psáno |= , pokud
pro každou valuaci  platí, že S() = true.
Řekneme, že dvě formule ,    jsou ekvivalentní, právě když |=   .
Tvrzení 7.6. Několik užitečných tautologií:
ˇ |= A  A
ˇ |=  A  A
ˇ |= (A  (A  B))  B
ˇ |= (B  A)  (A  B)
' $'
&
$
%Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Úvod do Logiky
Definice: Formule    je splnitelná, pokud pro některou valuaci  platí, že
S() = true.
Formule    je vždy pravdivá (také výroková tautologie), psáno |= , pokud
pro každou valuaci  platí, že S() = true.
Řekneme, že dvě formule ,    jsou ekvivalentní, právě když |=   .
Tvrzení 7.6. Několik užitečných tautologií:
ˇ |= A  A
ˇ |=  A  A
ˇ |= (A  (A  B))  B
ˇ |= (B  A)  (A  B)
ˇ |= (A  (B  B))  A
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Úvod do Logiky
7.3 Jak správně ,,znegovat formuli ?7.3 Jak správně ,,znegovat formuli ?
Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (po-
dobně jako v běžné řeči).
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Úvod do Logiky
7.3 Jak správně ,,znegovat formuli ?7.3 Jak správně ,,znegovat formuli ?
Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (po-
dobně jako v běžné řeči).
,,Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad.
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Úvod do Logiky
7.3 Jak správně ,,znegovat formuli ?7.3 Jak správně ,,znegovat formuli ?
Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (po-
dobně jako v běžné řeči).
,,Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad.
Výrokové formule se proto obvykle prezentují v normálním tvaru, kde se negace
vyskytují pouze u výrokových proměnných.
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Úvod do Logiky
7.3 Jak správně ,,znegovat formuli ?7.3 Jak správně ,,znegovat formuli ?
Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (po-
dobně jako v běžné řeči).
,,Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad.
Výrokové formule se proto obvykle prezentují v normálním tvaru, kde se negace
vyskytují pouze u výrokových proměnných.
Například, pokud přijmeme pravidlo ,,dvojí negace ( A  A), tak výše napsanou
větu si převedeme na lépe srozumitelný tvar:
,,Nemusím říct, že tě mám nerad.
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Úvod do Logiky
7.3 Jak správně ,,znegovat formuli ?7.3 Jak správně ,,znegovat formuli ?
Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (po-
dobně jako v běžné řeči).
,,Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad.
Výrokové formule se proto obvykle prezentují v normálním tvaru, kde se negace
vyskytují pouze u výrokových proměnných.
Například, pokud přijmeme pravidlo ,,dvojí negace ( A  A), tak výše napsanou
větu si převedeme na lépe srozumitelný tvar:
,,Nemusím říct, že tě mám nerad.
Tvrzení 7.7. Každou výrokou formuli lze převést do normálního tvaru, pokud
povolíme užívání odvozených spojek  a .
,,Znegováním formule  se obvykle myslí převod  do normálního tvaru.
' $'
&
$
%Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Úvod do Logiky
7.3 Jak správně ,,znegovat formuli ?7.3 Jak správně ,,znegovat formuli ?
Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (po-
dobně jako v běžné řeči).
,,Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad.
Výrokové formule se proto obvykle prezentují v normálním tvaru, kde se negace
vyskytují pouze u výrokových proměnných.
Například, pokud přijmeme pravidlo ,,dvojí negace ( A  A), tak výše napsanou
větu si převedeme na lépe srozumitelný tvar:
,,Nemusím říct, že tě mám nerad.
Tvrzení 7.7. Každou výrokou formuli lze převést do normálního tvaru, pokud
povolíme užívání odvozených spojek  a .
,,Znegováním formule  se obvykle myslí převod  do normálního tvaru.
ˇ Pro ilustraci (A  B) je ekvivalentní A  B,
ˇ  C  (A  B) je ekvivalentní C  (A  B).
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Úvod do Logiky
Formální postup negace
Metoda 7.8. Převod formule  do normálního tvaru F().
Definujeme funkce F a G pro náš převod induktivními předpisy
F(A) = A G(A) = A
F() = G() G() = F()
F(  ) = F()  F() G(  ) = F()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = (F()  G())  (G()  F())
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Úvod do Logiky
Formální postup negace
Metoda 7.8. Převod formule  do normálního tvaru F().
Definujeme funkce F a G pro náš převod induktivními předpisy
F(A) = A G(A) = A
F() = G() G() = F()
F(  ) = F()  F() G(  ) = F()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = (F()  G())  (G()  F())
Uvažme formuli (A  (B  (C  A))). Užitím postupu 7.8 získáme:
F((A  (B  (C  A)))) = G(A  (B  (C  A))) =
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Úvod do Logiky
Formální postup negace
Metoda 7.8. Převod formule  do normálního tvaru F().
Definujeme funkce F a G pro náš převod induktivními předpisy
F(A) = A G(A) = A
F() = G() G() = F()
F(  ) = F()  F() G(  ) = F()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = (F()  G())  (G()  F())
Uvažme formuli (A  (B  (C  A))). Užitím postupu 7.8 získáme:
F((A  (B  (C  A)))) = G(A  (B  (C  A))) =
F(A)  G((B  (C  A))) = A  F(B  (C  A)) =
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Úvod do Logiky
Formální postup negace
Metoda 7.8. Převod formule  do normálního tvaru F().
Definujeme funkce F a G pro náš převod induktivními předpisy
F(A) = A G(A) = A
F() = G() G() = F()
F(  ) = F()  F() G(  ) = F()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = (F()  G())  (G()  F())
Uvažme formuli (A  (B  (C  A))). Užitím postupu 7.8 získáme:
F((A  (B  (C  A)))) = G(A  (B  (C  A))) =
F(A)  G((B  (C  A))) = A  F(B  (C  A)) =
A  (F(B)  F((C  A))) = A  (B  G(C  A)) =
A  (B  (F(C)  G(A))) = A  (B  (C  F(A))) =
A  (B  (C  A))
' $'
&
$
%Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Úvod do Logiky
Formální postup negace
Metoda 7.8. Převod formule  do normálního tvaru F().
Definujeme funkce F a G pro náš převod induktivními předpisy
F(A) = A G(A) = A
F() = G() G() = F()
F(  ) = F()  F() G(  ) = F()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = G()  G()
F(  ) = F()  F() G(  ) = (F()  G())  (G()  F())
Uvažme formuli (A  (B  (C  A))). Užitím postupu 7.8 získáme:
F((A  (B  (C  A)))) = G(A  (B  (C  A))) =
F(A)  G((B  (C  A))) = A  F(B  (C  A)) =
A  (F(B)  F((C  A))) = A  (B  G(C  A)) =
A  (B  (F(C)  G(A))) = A  (B  (C  F(A))) =
A  (B  (C  A))
Formuli A  (B  (C  A)) lze dále zjednodušit na (ekvivalentní) formuli A  (B  C).
To ale je již z našeho pohledu matematicky neformální (heuristický) postup.
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Úvod do Logiky
Uvedené formální předpisy takto vyjadřují ,,intuitivní postup negace v mate-
maticky přesném tvaru.
Věta 7.9. Pro libovolnou výrokovou formuli  platí, že
a) F() je jí ekvivalentní formule v normálním tvaru
b) a G() je formule v normálním tvaru ekvivalentní negaci .
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Úvod do Logiky
Uvedené formální předpisy takto vyjadřují ,,intuitivní postup negace v mate-
maticky přesném tvaru.
Věta 7.9. Pro libovolnou výrokovou formuli  platí, že
a) F() je jí ekvivalentní formule v normálním tvaru
b) a G() je formule v normálním tvaru ekvivalentní negaci .
Důkaz povedeme tzv. ,,indukcí ke struktuře formule , tedy indukci povedeme
podle ,,délky ­ počtu aplikací induktivních pravidel (Definice 7.1) při sesta-
vování formule .
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Úvod do Logiky
Uvedené formální předpisy takto vyjadřují ,,intuitivní postup negace v mate-
maticky přesném tvaru.
Věta 7.9. Pro libovolnou výrokovou formuli  platí, že
a) F() je jí ekvivalentní formule v normálním tvaru
b) a G() je formule v normálním tvaru ekvivalentní negaci .
Důkaz povedeme tzv. ,,indukcí ke struktuře formule , tedy indukci povedeme
podle ,,délky ­ počtu aplikací induktivních pravidel (Definice 7.1) při sesta-
vování formule .
ˇ Báze indukce ( = 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě
platí, že F(A) = A je ekvivalentní A a G(A) = A je ekvivalentní A.
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Úvod do Logiky
Uvedené formální předpisy takto vyjadřují ,,intuitivní postup negace v mate-
maticky přesném tvaru.
Věta 7.9. Pro libovolnou výrokovou formuli  platí, že
a) F() je jí ekvivalentní formule v normálním tvaru
b) a G() je formule v normálním tvaru ekvivalentní negaci .
Důkaz povedeme tzv. ,,indukcí ke struktuře formule , tedy indukci povedeme
podle ,,délky ­ počtu aplikací induktivních pravidel (Definice 7.1) při sesta-
vování formule .
ˇ Báze indukce ( = 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě
platí, že F(A) = A je ekvivalentní A a G(A) = A je ekvivalentní A.
ˇ V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule 
délky nejvýše . Vezmeme si formuli  délky +1, která je utvořená jedním
z následujících způsobů:
' $'
&
$
%Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Úvod do Logiky
Uvedené formální předpisy takto vyjadřují ,,intuitivní postup negace v mate-
maticky přesném tvaru.
Věta 7.9. Pro libovolnou výrokovou formuli  platí, že
a) F() je jí ekvivalentní formule v normálním tvaru
b) a G() je formule v normálním tvaru ekvivalentní negaci .
Důkaz povedeme tzv. ,,indukcí ke struktuře formule , tedy indukci povedeme
podle ,,délky ­ počtu aplikací induktivních pravidel (Definice 7.1) při sesta-
vování formule .
ˇ Báze indukce ( = 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě
platí, že F(A) = A je ekvivalentní A a G(A) = A je ekvivalentní A.
ˇ V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule 
délky nejvýše . Vezmeme si formuli  délky +1, která je utvořená jedním
z následujících způsobů:
    (  je ,,definiční rovnítko pro formule).
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Úvod do Logiky
Podle výše uvedeného induktivního předpisu je F() = F() = G().
Podle indukčního předpokladu pak je G() formule v normálním tvaru
ekvivalentní  = .
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Úvod do Logiky
Podle výše uvedeného induktivního předpisu je F() = F() = G().
Podle indukčního předpokladu pak je G() formule v normálním tvaru
ekvivalentní  = .
Obdobně pro funktor G vyjádříme G() = G() = F(). Podle in-
dukčního předpokladu pak je F() formule v normálním tvaru ekviva-
lentní  a to je dále ekvivalentní  =  podle Tvrzení 7.6.
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Úvod do Logiky
Podle výše uvedeného induktivního předpisu je F() = F() = G().
Podle indukčního předpokladu pak je G() formule v normálním tvaru
ekvivalentní  = .
Obdobně pro funktor G vyjádříme G() = G() = F(). Podle in-
dukčního předpokladu pak je F() formule v normálním tvaru ekviva-
lentní  a to je dále ekvivalentní  =  podle Tvrzení 7.6.
   (1  2).
Podle výše uvedeného induktivního předpisu je F() = F(1  2) =
F(1)  F(2). Podle indukčního předpokladu jsou F(1) i F(2)
formule v normálním tvaru ekvivalentní 1 a 2. Potom i F(1) 
F(2) je v normálním tvaru dle definice a podle sémantiky  je ta
ekvivalentní formuli (1  2) = .
' $'
&
$
%Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Úvod do Logiky
Podle výše uvedeného induktivního předpisu je F() = F() = G().
Podle indukčního předpokladu pak je G() formule v normálním tvaru
ekvivalentní  = .
Obdobně pro funktor G vyjádříme G() = G() = F(). Podle in-
dukčního předpokladu pak je F() formule v normálním tvaru ekviva-
lentní  a to je dále ekvivalentní  =  podle Tvrzení 7.6.
   (1  2).
Podle výše uvedeného induktivního předpisu je F() = F(1  2) =
F(1)  F(2). Podle indukčního předpokladu jsou F(1) i F(2)
formule v normálním tvaru ekvivalentní 1 a 2. Potom i F(1) 
F(2) je v normálním tvaru dle definice a podle sémantiky  je ta
ekvivalentní formuli (1  2) = .
Obdobně rozepíšeme G() = G(1  2) = F(1)  G(2). Jelikož
 je pro nás jen zkratka, výraz dále rozepíšeme G() = (F(1) 
G(2)). Podle indukčního předpokladu (a dvojí negace) jsou F(1) a
G(2) po řadě ekvivalentní formulím 1 a 2. Tudíž nakonec odvo-
díme, že G() je ekvivalentní negaci formule 1  2, což jsme zde
měli dokázat.
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Úvod do Logiky
   (1  2).
Zde si musíme opět uvědomit, že spojka  je pro nás jen zkratka, a
přepsat   (1  2). Potom podle předchozích dokázaných pří-
padů víme, že F() = F(1  2) = F(1)  F(2) je ekvi-
valentní formuli (1  2) = , což bylo třeba dokázat. Stejně tak
G() = G(1  2) = F(1)  G(2) je podle předchozích případů
důkazu ekvivalentní (1  2) = .
' $'
&
$
%Petr Hliněný, FI MU Brno 13 IB000 "Úv. Inf.": Úvod do Logiky
   (1  2).
Zde si musíme opět uvědomit, že spojka  je pro nás jen zkratka, a
přepsat   (1  2). Potom podle předchozích dokázaných pří-
padů víme, že F() = F(1  2) = F(1)  F(2) je ekvi-
valentní formuli (1  2) = , což bylo třeba dokázat. Stejně tak
G() = G(1  2) = F(1)  G(2) je podle předchozích případů
důkazu ekvivalentní (1  2) = .
   (1  2) a   (1  2) už dokončíme analogicky.
2
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Úvod do Logiky
7.4 Predikátová logika, kvantifikace7.4 Predikátová logika, kvantifikace
ˇ Predikátová logika je obecnější než logika výroková; každá formule výrokové
logiky je i formulí predikátové logiky, ale ne obráceně.
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Úvod do Logiky
7.4 Predikátová logika, kvantifikace7.4 Predikátová logika, kvantifikace
ˇ Predikátová logika je obecnější než logika výroková; každá formule výrokové
logiky je i formulí predikátové logiky, ale ne obráceně.
ˇ Predikátová logika pracuje s predikáty. Predikáty jsou ,,parametrizované vý-
roky , které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu
parametrů.
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Úvod do Logiky
7.4 Predikátová logika, kvantifikace7.4 Predikátová logika, kvantifikace
ˇ Predikátová logika je obecnější než logika výroková; každá formule výrokové
logiky je i formulí predikátové logiky, ale ne obráceně.
ˇ Predikátová logika pracuje s predikáty. Predikáty jsou ,,parametrizované vý-
roky , které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu
parametrů. Výrokové proměnné lze chápat jako predikáty bez parametrů.
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Úvod do Logiky
7.4 Predikátová logika, kvantifikace7.4 Predikátová logika, kvantifikace
ˇ Predikátová logika je obecnější než logika výroková; každá formule výrokové
logiky je i formulí predikátové logiky, ale ne obráceně.
ˇ Predikátová logika pracuje s predikáty. Predikáty jsou ,,parametrizované vý-
roky , které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu
parametrů. Výrokové proměnné lze chápat jako predikáty bez parametrů.
Pro neformální přiblížení si uvedeme několik ukázek predikátů:
 x > 3 (parameterem je zde x),
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Úvod do Logiky
7.4 Predikátová logika, kvantifikace7.4 Predikátová logika, kvantifikace
ˇ Predikátová logika je obecnější než logika výroková; každá formule výrokové
logiky je i formulí predikátové logiky, ale ne obráceně.
ˇ Predikátová logika pracuje s predikáty. Predikáty jsou ,,parametrizované vý-
roky , které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu
parametrů. Výrokové proměnné lze chápat jako predikáty bez parametrů.
Pro neformální přiblížení si uvedeme několik ukázek predikátů:
 x > 3 (parameterem je zde x),
 R je ekvivalence na M (parametr R),
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Úvod do Logiky
7.4 Predikátová logika, kvantifikace7.4 Predikátová logika, kvantifikace
ˇ Predikátová logika je obecnější než logika výroková; každá formule výrokové
logiky je i formulí predikátové logiky, ale ne obráceně.
ˇ Predikátová logika pracuje s predikáty. Predikáty jsou ,,parametrizované vý-
roky , které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu
parametrů. Výrokové proměnné lze chápat jako predikáty bez parametrů.
Pro neformální přiblížení si uvedeme několik ukázek predikátů:
 x > 3 (parameterem je zde x),
 R je ekvivalence na M (parametr R),
 čísla x a y jsou nesoudělná (parametry x, y),
 obecně psáno P(x, y).
' $'
&
$
%Petr Hliněný, FI MU Brno 14 IB000 "Úv. Inf.": Úvod do Logiky
7.4 Predikátová logika, kvantifikace7.4 Predikátová logika, kvantifikace
ˇ Predikátová logika je obecnější než logika výroková; každá formule výrokové
logiky je i formulí predikátové logiky, ale ne obráceně.
ˇ Predikátová logika pracuje s predikáty. Predikáty jsou ,,parametrizované vý-
roky , které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu
parametrů. Výrokové proměnné lze chápat jako predikáty bez parametrů.
Pro neformální přiblížení si uvedeme několik ukázek predikátů:
 x > 3 (parameterem je zde x),
 R je ekvivalence na M (parametr R),
 čísla x a y jsou nesoudělná (parametry x, y),
 obecně psáno P(x, y).
Definice 7.10. Syntaxe i sémantika predikátové logiky.
Z predikátů lze vytvářet predikátové formule pomocí už známých (viz Defi-
nice 7.1) výrokových spojek a následujících tzv. kvantifikátorů:
ˇ x .  ,,pro každou volbu parametru x platí formule  ,
ˇ x .  ,,existuje alespoň jedna volba parametru x, pro kterou platí  .
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Úvod do Logiky
Fakt: Je-li každá proměnná v dané formuli kvantifikovaná (tj. formule je uza-
vřená), pak je celá formule buď pravdivá nebo nepravdivá.
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Úvod do Logiky
Fakt: Je-li každá proměnná v dané formuli kvantifikovaná (tj. formule je uza-
vřená), pak je celá formule buď pravdivá nebo nepravdivá.
Konvence 7.11. Pro lepší srozumitelnost zápisu formulí predikátové logiky se
domluvíme na následujícím.
 Parametry vyskytující se v predikátech ve formuli  někdy pro referenci
vypisujeme jako ,,parametry samotné formule (x, y, . . .).
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Úvod do Logiky
Fakt: Je-li každá proměnná v dané formuli kvantifikovaná (tj. formule je uza-
vřená), pak je celá formule buď pravdivá nebo nepravdivá.
Konvence 7.11. Pro lepší srozumitelnost zápisu formulí predikátové logiky se
domluvíme na následujícím.
 Parametry vyskytující se v predikátech ve formuli  někdy pro referenci
vypisujeme jako ,,parametry samotné formule (x, y, . . .).
 Poukud není z kontextu jasné, co lze za daný parametr dosazovat, užívá
se notace x  M .  a x  M . . (Platí, jen pokud je kvantifikovaný
parametr prvkem nějaké fixní množiny!).
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Úvod do Logiky
Fakt: Je-li každá proměnná v dané formuli kvantifikovaná (tj. formule je uza-
vřená), pak je celá formule buď pravdivá nebo nepravdivá.
Konvence 7.11. Pro lepší srozumitelnost zápisu formulí predikátové logiky se
domluvíme na následujícím.
 Parametry vyskytující se v predikátech ve formuli  někdy pro referenci
vypisujeme jako ,,parametry samotné formule (x, y, . . .).
 Poukud není z kontextu jasné, co lze za daný parametr dosazovat, užívá
se notace x  M .  a x  M . . (Platí, jen pokud je kvantifikovaný
parametr prvkem nějaké fixní množiny!).
 Tečka za symbolem kvantifikátoru se někdy vynechává (při vhodném uzá-
vorkování formule), nebo se používá symbol ,, : .
' $'
&
$
%Petr Hliněný, FI MU Brno 15 IB000 "Úv. Inf.": Úvod do Logiky
Fakt: Je-li každá proměnná v dané formuli kvantifikovaná (tj. formule je uza-
vřená), pak je celá formule buď pravdivá nebo nepravdivá.
Konvence 7.11. Pro lepší srozumitelnost zápisu formulí predikátové logiky se
domluvíme na následujícím.
 Parametry vyskytující se v predikátech ve formuli  někdy pro referenci
vypisujeme jako ,,parametry samotné formule (x, y, . . .).
 Poukud není z kontextu jasné, co lze za daný parametr dosazovat, užívá
se notace x  M .  a x  M . . (Platí, jen pokud je kvantifikovaný
parametr prvkem nějaké fixní množiny!).
 Tečka za symbolem kvantifikátoru se někdy vynechává (při vhodném uzá-
vorkování formule), nebo se používá symbol ,, : .
 Místo x1 . x2 .    xn .  se někdy krátce píše x1, x2,    , xn . .
Podobně u existenčního kvantifikátoru x1, x2,    , xn . .
' $'
&
$
%Petr Hliněný, FI MU Brno 16 IB000 "Úv. Inf.": Úvod do Logiky
Příklad 7.12. Ukažme si vyjádření následujících slovních výroků v predikátové logice:
ˇ Každé prvočíslo větší než 2 je liché,
n  N. (Pr(n)  n>2)  Li(n).
' $'
&
$
%Petr Hliněný, FI MU Brno 16 IB000 "Úv. Inf.": Úvod do Logiky
Příklad 7.12. Ukažme si vyjádření následujících slovních výroků v predikátové logice:
ˇ Každé prvočíslo větší než 2 je liché,
n  N. (Pr(n)  n>2)  Li(n).
ˇ Každé číslo n, které není prvočíslem, je dělitelné nějakým číslem y kde n = y a
y > 1,
n  N. (Pr(n)  y . (y|n  n=y  y>1)).
' $'
&
$
%Petr Hliněný, FI MU Brno 16 IB000 "Úv. Inf.": Úvod do Logiky
Příklad 7.12. Ukažme si vyjádření následujících slovních výroků v predikátové logice:
ˇ Každé prvočíslo větší než 2 je liché,
n  N. (Pr(n)  n>2)  Li(n).
ˇ Každé číslo n, které není prvočíslem, je dělitelné nějakým číslem y kde n = y a
y > 1,
n  N. (Pr(n)  y . (y|n  n=y  y>1)).
ˇ Jsou-li R a S ekvivalence na M, je také R  S ekvivalence na M.
Zde například můžeme mít dva pohledy na toto tvrzení ­ v jednom bereme množinu
M za pevnou
R, S : (EqM (R)  EqM (S))  EqM (RS),
kdežto ve druhém je i množina M parametrem
M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS).
2
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Úvod do Logiky
Jak ,,negovat formule predikátové logiky?
Metoda 7.13. Převod predikátové formule  do normálního tvaru F().
Dřívější Metodu 7.8 rozšíříme o následující indukční pravidla:
F(P(x1, . . . , xn)) = P(x1, . . . , xn) G(P(x1, . . . , xn)) = P(x1, . . . , xn)
F(x . ) = x . F() G(x . ) = x . G()
F(x . ) = x . F() G(x . ) = x . G()
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Úvod do Logiky
Jak ,,negovat formule predikátové logiky?
Metoda 7.13. Převod predikátové formule  do normálního tvaru F().
Dřívější Metodu 7.8 rozšíříme o následující indukční pravidla:
F(P(x1, . . . , xn)) = P(x1, . . . , xn) G(P(x1, . . . , xn)) = P(x1, . . . , xn)
F(x . ) = x . F() G(x . ) = x . G()
F(x . ) = x . F() G(x . ) = x . G()
Uvažme například formuli
(M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS)) .
Pak
F((M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS))) =
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Úvod do Logiky
Jak ,,negovat formule predikátové logiky?
Metoda 7.13. Převod predikátové formule  do normálního tvaru F().
Dřívější Metodu 7.8 rozšíříme o následující indukční pravidla:
F(P(x1, . . . , xn)) = P(x1, . . . , xn) G(P(x1, . . . , xn)) = P(x1, . . . , xn)
F(x . ) = x . F() G(x . ) = x . G()
F(x . ) = x . F() G(x . ) = x . G()
Uvažme například formuli
(M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS)) .
Pak
F((M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS))) =
G(M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS)) =
' $'
&
$
%Petr Hliněný, FI MU Brno 17 IB000 "Úv. Inf.": Úvod do Logiky
Jak ,,negovat formule predikátové logiky?
Metoda 7.13. Převod predikátové formule  do normálního tvaru F().
Dřívější Metodu 7.8 rozšíříme o následující indukční pravidla:
F(P(x1, . . . , xn)) = P(x1, . . . , xn) G(P(x1, . . . , xn)) = P(x1, . . . , xn)
F(x . ) = x . F() G(x . ) = x . G()
F(x . ) = x . F() G(x . ) = x . G()
Uvažme například formuli
(M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS)) .
Pak
F((M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS))) =
G(M R, S : (Eq(M, R)  Eq(M, S))  Eq(M, RS)) =
M R, S : G((Eq(M, R)  Eq(M, S))  Eq(M, RS)) =
M R, S : (Eq(M, R)  Eq(M, S)  Eq(M, RS)) .