00 HANDOUT

• Logika je neempirická vědní disciplína na pomezí matematiky, filosofie a informatiky.
• Vymezení logiky: Logika je věda o vyplývání (resp. logickém důsledku).

• Úsudek je soubor vět obsahující premisy (předpoklady) P1, P2, ..., Pn
• a závěr (konkluzi) Z, jenž je od premis oddělen slovem ”Tudíž", čarou apod.:
• premisa P1
• premisa P2
•          ....
• premisa Pn
• --------------------
•      závěr Z

Věta Z vyplývá z vět P1, P2, . . . , Pn, právě když platí, že za všech okolností, kdy jsou pravdivé věty P1, P2, . . . , Pn, je pravdivá rovněž věta Z

• Úsudek U je platný, právě když jeho závěr Z vyplývá z jeho premis P1, P2, . . . , Pn.
• ^{V rámci VL ověřujeme platnost úsudku prověřením jeho logické formy, již získáme formalizací vět úsudku prostředky VL (nejjednodušší výroky nahrazujeme výrokovými proměnnými, gramatické spojky výrokově-logickými spojkami).}

Výrok je věta, která je pravdivá nebo nepravdivá.

každý výrok má právě jednu ze dvou pravdivostních hodnot

pravdivostní hodnota složeného výroku/formule je funkcionálně odvislá od pravdivostních hodnot jeho/jejích složek

• Dílčím členům (A ∧ B), resp. (A ∨ B), říkáme konjunkty, resp.
• disjunkty.
• Prvnímu členu (A → B) říkáme antecedent druhému konsekvent.

• abeceda
• - výrokové proměnné (jakožto symboly): p, q, r, . . . p1, q1, r1, . . .
• - výrokové spojky (jakožto symboly): ¬, ∧, ∨, →, ↔
• - pomocné symboly: (, )

• gramatika
• Výrokové proměnné (p, q, r, . . . ) jsou správně utvořenými formulemi (s.u.f.).
• Jestliže A a B jsou s.u.f., pak ¬A, (A ∧ B), (A ∨ B), (A → B), (A ↔ B) jsou s.u.f.
• Nic jiného není s.u.f

• podformule
• Každá formule A je podformulí A.
• Je-li formule A tvaru ¬B, B ∧ C, nebo B ∨ C, nebo B → C, nebo B ↔ C, tak B a C jsou podformulemi A.
• Nic jiného není podformulí formule A.

Každá jednotlivá valuace v je funkce, jež každé proměnné  přiřazuje pravdivostní hodnotu 1 nebo 0.

• Interpretace τ formule A na základě valuace v je rovna 1, stručně τ(v, A) = 1, právě když platí, že:

O formuli A říkáme, že je pravdivá, právě když τ(v, A) = 1.

Výrokově-logická tautologie je formule, jež je při každé valuaci pravdivá. To, že A je tautologií, značíme  I= A.

Výrokově-logická kontradikce je formule, jež je při každé valuaci nepravdivá

Formule A je ekvivalentní formuli B, právě když při každé valuaci v platí, že 

Nechť A je formule, která obsahuje alespoň na jednom místě podformuli B. Jestliže platí, že B je ekvivalentní s C, a jestliže formule A´ vznikne nahrazením libovolného počtu výskytů formule B formulí C ve formuli A, pak A´ je ekvivalentní s A

p ↔ ¬¬p

¬(p ∧ ¬p)

p ∨ ¬p

¬(p ∧ q) ↔ (¬p ∨ ¬q)

¬ (p → q) ⇔ (p ∧ ¬q)

¬(p ∨ q) ↔ (¬p ∧ ¬q)

(p → q) ↔ (¬p ∨ q)

(p → q) ↔ (¬q → ¬p)

(p ↔ q) ↔ ((p → q) ∧ (q → p))

p → (q → p)

(p ∧ ¬p) → q

Formule Z výrokově-logicky vyplývá z formulí P1, P2, . . . , Pn, právě když Z je pravdivá při všech valuacích, při nichž jsou pravdivé všechny formule P1, P2, . . . , Pn. Značíme P1, P2 . . . Pn I= Z.

• 1) jazykem (jen syntax)
• 2) množinou axiomů
• 3) množinou odvozovacích pravidel

• 1:   A → ( B → A)
• 2: ( A → ( B → C)) → (( A → B) → ( A → C))
• 3: (¬B → ¬A) → ( A → B)

Axiom daného axiomatického systému S je zvolená základní v něm nedokazovatelná formule (typicky se jedná o tautologii).

• Konečná posloupnost formulí A₁, A₂, .... A_n je v daném axiomatickém systému S důkazem, právě když pro každé i takové, že 1 ≤ i ≤ n, formule A_i je
• 1. axiomem S nebo
• 2. je odvozena aplikací některého pravidla odvození systému S na formule A_j, ..., A_k, přičemž j,... k < i.

• Nechť T je systém formulí. Konečná posloupnost formulí A₁, A₂, .... A_n je v daném axiomatickém systému S důkazem, právě když pro každé i takové, že 1 ≤ i ≤ n, formule A_i je
• 1. axiomem S nebo
• 2. prvkem T
• 3. je odvozena aplikací některého pravidla odvození systému S na formule A_j, ..., A_k, přičemž j,... k < i.

Formule A je dokazatelná v axiomatickém systému S, právě když v tomto systému S existuje důkaz, jehož je tato formule posledním členem

Formule A je teorémem axiomatického systému S, právě když je dokazatelná v systému S. Značíme pomocí I-_s A.

Nechť T je teorie (systém formulí), A a B formule. Potom T I- A → B, právě když T ∪ {A} I- B.

• rozhodnutelnost
• konzistentnost
• korektnost
• úplnost

Axiomatický systém S je rozhodnutelný, právě když o každé formuli A (jazyka shodného s jazykem S) je rozhodnutelné (tj. existuje příslušný efektivní algoritmus), zda je či není teorémem S.

Axiomatický systém S je konzistentní, právě když v S nejsou dokazatelné A a ¬A (tj. spor)

• Axiomatický systém S je korektní, právě když platí, že je-li T |-_S A, pak T |=_S A.
• Speciální případ -  je-li |-_S A, pak |=_S A.

• Axiomatický systém S je úplný, právě když platí, že je-li T |=_S A, pak T |-_S A.
• Speciální případ- je-li |=_S A, pak |-_S A.

|- ... dokazatelnost formule napravo od "|-" z množiny formulí nalevo od "|-"

 |= ... vyplývání, tj. formule napravo od "|="je (tauto)logický důsledek množiny formulí nalevo od "|="

• i. hilbertovská dedukce
• ii. přirozená dedukce 
• iii. sekvenční kalkul

• A → B
• A
• -----------
• B

• A → B
• ¬B
• -----------
• ¬A

• A
• B
• -------
• A ∧ B

• A → B
• B → C
• ------------
• A → C

A → B

• A → ¬B
• -------------
• ¬A

• A ∧ B                    A ∧ B
• ------------                 -------------
• A                            B

• A                     B
• ----------            -------------
• A ∨ B            A ∨ B

• A ∨ B          A ∨ B
• ¬A                 ¬B
• -----------        -------------
• B                  A

• p ∨ B
• ¬p ∨ C
• -----------------
•   B ∨ C