1 Logika a dôkazy Flashcards
výrok
oznamovacie vety, ktorými sa vyjadruje niečo, čo je buď pravdivé alebo nepravdivé
axiómia
- elementárne tvrdenie o vlastnostiach základných pojmov
- tvrdenia, ktoré považujeme za očividné
- P(V) = 1, nemusíme ich dokazovať, platí to vždy
hypotéza
- výrok, ktorého pravdivostnú hodnotu sme doteraz neurčili
- = domnienka
Pravdivostná hodnota
- za pravdivostnú hodnotu výroku považujeme pravdivosť a nepravdivosť výroku.
- Pravdivý výrok: „1“ P(V) = 1
- Nepravdivý výrok: „0“ P(V) = 0
- pravdivostná hodnota výroku V: P(V)
logické spojky
a (∧ ); alebo (∨ ); ak, tak (⇒); práve vtedy, keď (⇔ )
Negácia výroku
negácia výroku V: (V)
* ku každému výroku V môžeme sformulovať výrok, ktorý popiera pravdivosť tvrdenia
obsiahnutého vo výroku V
napr. V: „Dnes ráno pršalo.“
V: „ Nie je pravda, že dnes ráno pršalo.“
alebo: V`: „Dnes ráno nepršalo.“
Konjukcia
- zložený výrok: A a B
- označujeme ho: A ∧ B
Disjunkcia = alternatíva
- zložený výrok: A alebo B
- označujeme: A ∨ B
Implikácia
- zložený výrok: ak A tak B
- označujeme: A ⇒ B
obmena implikácie
A ⇒ B
(A ⇒ B) ⇔ (B⇒ A)
obrátená implikácia
A ⇒ B
(B ⇒ A)
ekvivalencia
zložený výrok: A práve vtedy keď B
* označujeme A ⇔ B
Tautológia
výrok, ktorého pravdivostná hodnota je vždy 1 (je vždy pravdivý)
Kontradikcia
výrok, ktorý je vždy nepravdivý
Kvantifikovaný výrok
- každý výrok, ktorý obsahuje kvantifikátory
- existenčný kvantifikátor - ∃ : „existuje“
napr. V: ∃ x∈N; x>1
V`: ∀ x∈N; x ≤ 1 - všeobecný kvantifikátor - ∀ : „pre všetky, pre každý“
napr. V: ∀ x∈R; x2
+1>0
V`: ∃ x ∈R; x2
+1 ≤ 0
Druhy dôkazov
Priamy dôkaz
dokazované tvrdenie je odvodené priamou aplikáciou definícií, predpokladov a predtým dokázaných tvrdení
tvrdenie je odvodené metódou „ak … potom … teda …“.
Nepriamy dôkaz
„ak A, potom B“, pri ktorej sa preukáže „ak nie B, potom nie A“. Má úzky vzťah k dôkazu sporom – každý nepriamy dôkaz môže byť ľahko prevedený na dôkaz sporom.
Dôkaz sporom
sa zakladá na použití chybného predpokladu, ktorý je potom dovedený k sporu . Ak sa tak stane, je preukázaná neplatnosť daného predpokladu a teda platnosť jeho opaku.
