Základné pojmy z logiky

Základné pojmy z logiky

Výrok – oznamovacia veta, ktorá vyjadruje niečo, čo je buď pravdivé alebo nepravdivé (má jednoznačnú pravdivostnú hodnotu). Výroky označujeme veľkými tlačenými písmenami A, B, ..., Z

Pravdivostná hodnota výroku – P(V) = 1(pravda) alebo 0(nepravda)

Axióma – elementárne tvrdenie o vlastnostiach základných pojmov; očividné tvrdenie; P(V) = 1, nemusíme to dokazovať, platí to vždy

Hypotéza – domnienka; výrok, ktorého pravdivostnú hodnotu sme doteraz neurčili

Zložené výroky – vznikajú z jednoduchých výrokov pomocou logických spojok

Logické spojky – ∧ (a zároveň); ∨ (alebo – v nevylučovacom zmysle, v zmysle aspoň jeden); → (ak, tak); ↔ (práve vtedy, keď – obe rovnaké)

• KONJUKCIA – A ∧ B (logický súčin, pravdivostné hodnoty sa násobia)
• DISJUNKCIA (ALTERNATÍVA) – A ∨ B (logický súčet)
• IMPLIKÁCIA – A → B
• EKVIVALENCIA – A ↔ B = (A → B) ∧ (B → A)

Tabuľka pravdivostných hodnôt

A	B	A ∧ B	A ∨ B	A → B	A ↔ B
1	1	1	1	1	1
1	0	0	1	0	0
0	1	0	1	1	0
0	0	0	0	1	1

^*Konjukcia je pravdivá, len ak sú oba výroky pravdivé

^*Alternatíva neplatí ak sú oba výroky 0

^*Implikácia neplatí, len ak je prvý pravdivý a druhý nepravdivý

^*A a B sú ekvivalentné, ak platia obe implikácie A → B a B → A

Negáciavýroku V: (V’) – ku každému výroku V vieme sformulovať výrok, ktorý popiera pravdivosť tvrdenia obsiahnutého vo výroku V; popiera to, čo tvrdí výrok V (má opačnú pravdivostnú hodnotu); Nie je pravda, že V.

Negáciazložených výrokov

(A ∧ B)‘ = A‘ ∨ B‘ (A ∨ B)‘ = A‘ ∧ B‘

(A → B)‘ = A ∧ B‘ (A ↔ B)‘ = (A ∧ B‘) ∨ (B ∧ A‘)

Kvantifikované výroky – udávajú počet; obsahujú kvantifikátory

• VŠEOBECNÝ KVANTIFIKÁTOR ∀ (všetky, každý)

Každý uvažovaný objekt má vlastnosť, o ktorej hovoríme

• EXISTENČNÝ KVANTIFIKÁTOR ∃ (existuje aspoň jeden), ∃! (existuje práve jeden)

Aspoň jeden uvažovaný objekt má vlastnosť, o ktorej hovoríme

Každý je ... Aspoň jeden nie je

Aspoň dva sú ... Najviac jeden je

Práve päť ... Aspoň šesť / Najviac 4

Obmena implikácie (A → B) – (B‘ → A’), má tú istú pravdivostnú hodnoty ako tá pôvodná

Obrátená implikácia – (B → A)

Typy dôkazov

• PRIAMY DÔKAZ

Dokážeme reťazec implikácií A → T₁ → T₂ → T₃ → ... → T_n → B. Prvý člen je už dokázané tvrdenie (axióma), každé ďalšie je logickým dôsledkom predchádzajúcich, posledný člen je dokazované tvrdenie.

• NEPRIAMY DÔKAZ

Dokážeme platnosť obmenenej vety (priamo). Týmto spôsobom dokazujeme iba vety tvaru implikácie. (A → B) – (B‘ → A’)

• DÔKAZ SPOROM

Znegujeme matematickú vetu a dokazujeme priamym dôkazom. Záver je v spore s podmienkami, alebo s matematickými tvrdeniami. Ukážeme nepravdivosť negovaného výroku a dôjdeme k sporu → pôvodný výrok teda platí.