Szerkesztő:Kizin/próba

Ez csak egy próba oldal, de megpróbálom itt kidolgozni a matematikai logika csonk oldalát.

Tehát ott ez áll bevezetőként:
A matematikai logika a matematika egyik fejezete, a matematikai rendszereket, a matematikai bizonyításokat, matematikai módszerekkel vizsgálja. A matematikai logika célja a helyes következtetési sémák, helyes definíciók vizsgálata, beleértve a matematikai logika által alkalmazott következtetési sémákat, szabályokat, definíciókat is.

A matematikai logika korábban a szimbolikus logika részét képezte, abból fejlődött ki azáltal, hogy a szimbolikus logika formális módszereit kezdte alkalmazni a matematikai következtetések és bizonyítások vizsgálatára.

Bevezetés

Következtetések (konklúzió)

A konklúzió (következtetés) premisszákból (állításokból) vonhatóak le.

	1. példa	2. példa
premissza	Magyarország fővárosa Szeged.	Pelé jó focista.
premissza	Szeged a Tisza partján fekszik.	Minden brazil jó focista.
konklúzió	Magyarország fővárosa a Tisza partján fekszik.	Pelé brazil.
	Ez igaz következtetés a premisszák igazságtartama ellenére	Ez hamis következtetés

Ítélet

Az ítélet alapfogalom és csak igaz vagy hamis lehet.

Így az alábbi példák nem minősülnek ítéletnek: Jaj! Csukd be az ajtót! Ez a mondat hamis!

Egy következtetést induktívnak nevezünk, ha a premisszák igazak, de a nem biztos, hogy a konklúzió is igaz; illetve deduktívnak nevezzük, ha a premisszákból a konklúzió 100%-osan következik.

Induktív következtetés például: Vizes az út, tehát esett az eső. Itt a konklúzió nem biztos, hogy igaz, mert egy locsolóautóból is kifolyhatott az útra a víz.

Ítéletkalkulus

A negáció

¬A jelentése: "Nem A"

A	¬A
i	h
h	i

A negáció egy egyváltozós igazságfüggvény. f_¬:{i,h}→{i,h}

A konjukció

A∧B jelentése: "A és B"

A	B	A∧B
i	i	i
i	h	h
h	i	h
h	h	h

A konjukció egy kétváltozós igazságfüggvény. f_∧:{i,h}²={i,h}×{i,h}→{i,h}

A diszjunkció

A∨B jelentése: "A vagy B"

A	B	A∨B
i	i	i
i	h	i
h	i	i
h	h	h

Ez is egy kétváltozós igazságfüggvény. f_∨:{i,h}²={i,h}×{i,h}→{i,h}

A "kizáró vagy"

A "kizáró vagy" definíciója: (A∨B)∧¬(A∧B)

Az implikáció

A→B jelentése: "Ha A, akkor B"

A	B	A→B
i	i	i
i	h	h
h	i	i vagy h (önkényes)
h	h	i vagy h (önkényes)

Ez is egy kétváltozós igazságfüggvény. f_→:{i,h}²={i,h}×{i,h}→{i,h}

A táblázat utolsó két sora önkényes, vegyünk egy-egy ezekre a sorokra:
Ha 2+2=5, akkor Magyarország fővárosa Budapest.
Ha 2+2=5, akkor Magyarország fővárosa Bécs.

Az ekvivalencia

A↔B jelentése: "A akkor és csak akkor, ha B"

A	B	A↔B
i	i	i
i	h	h
h	i	h
h	h	i

Ítéletkalkulusbeli formula

Definíció

1. minden ítéletváltozó formula
2. ha φ formula, akkor (¬φ) is formula
3. ha φ és ψ formulák, akkor (φ∧ψ), (φ∨ψ), (φ→ψ) és (φ↔ψ) is formulák
4. minden formula előáll a fenti lépések véges sok alkalmazásaival

Definíció (értékelés)

Legyen Form: a formulák halmaza és V⊆Form, v:V→{i,h}, v(P₁)=i

v kiterjeszthető ${\overline {v}}:Form\rightarrow \left\{i,h\right\}$ függvénnyé; a műveletek definíciója alapján

Definíció

Egy formula tautológia, ha bármely értékelésre igaz. Jelölése: $\models \varphi$

Egy formula kontradikció, ha bármely értékelésre hamis.

Megjegyzés: φ tautológia ⇔ ¬φ kontradikció
Ezekre pár példa

Definíció

Két formula ekvivalens, ha ugyanazokra az értékelésekre igazak. Jelölés: $\varphi \equiv \psi$

Így például: $p\rightarrow q\equiv \lnot p\vee q$ Bizonyítást itt találod

Megjegyzés: $\varphi \equiv \psi \Leftrightarrow (\varphi \leftrightarrow \psi )$ tautológia

Ekvivalens formulák

1. $p\wedge q\equiv q\wedge p\qquad p\vee q\equiv q\vee p$
2. $p\wedge (q\wedge r)\equiv (p\wedge q)\wedge r\qquad p\vee (q\vee r)\equiv (p\vee q)\vee r$
3. $p\wedge (q\vee r)\equiv (p\wedge q)\vee (q\wedge r)\qquad p\vee (q\wedge r)\equiv (p\vee q)\wedge (q\vee r)$
4. $p\wedge (p\vee q)\equiv p\qquad p\vee (p\wedge q)\equiv p$
5. $p\wedge p\equiv p\qquad p\vee p\equiv p$
6. $p\rightarrow q\equiv \lnot p\vee q$
7. $p\leftrightarrow q\equiv (p\rightarrow q)\wedge (q\rightarrow p)$
8. $\lnot (p\wedge q)\equiv \lnot p\vee \lnot q\qquad \lnot (p\vee q)\equiv \lnot p\wedge \lnot q$

Továbbá fontosak a következő észrevételek is: $p\wedge \lnot p\equiv h$ kontradikció, így $p\vee \lnot p\equiv i$ tautológia
$p\wedge i\equiv p\qquad p\vee i\equiv i$

$p\wedge h\equiv h\qquad p\vee h\equiv p$

Láthatjuk, hogy a matematikai logika kapcsolatban áll az algebrával, és a műveletek megfeleltethetők egymásnak a következőképpen:

∨→+

∧→·

$\lnot p\rightarrow {\bar {p}}$

i→1

h→0

$\equiv \rightarrow =$

Így is igazak a formulák (például)

$p+q=q+p\qquad p\cdot q=q\cdot p\qquad p+0=p\qquad p\cdot 1=p\qquad p\cdot 0=0$

De nem igaz: $p+1=1\qquad p+(q\cdot r)=(p+q)\cdot (q+r)$

Definíciók és állítások az ítéletkalkulussal kapcsolatban

Definíció (helyettesítés)

egy formula valamely változójának helyére, annak minden előfordulásánál egy másik formulát írunk

Például
$\varphi =(p\wedge q)\leftrightarrow (q\wedge p)$
$\psi =(\lnot r\vee q)$
$\varphi [p/\psi ]=((\lnot r\vee q)\wedge q)\leftrightarrow (q\wedge (\lnot r\vee q))$

Állítás

Tautológiából helyettesítéssel tautológia keletkezik.

Bizonyítás

$\varphi \equiv \psi \Leftrightarrow \varphi \leftrightarrow \psi$ tautológia

$p\wedge q\equiv q\wedge p$

Legyen $p\rightarrow \varphi \qquad q\rightarrow \psi$

Tehát $\varphi \wedge \psi \equiv \psi \wedge \varphi$

Definíció (pótlás)

egy formula valamely részformuláját kicseréljük egy vele ekvivalens formulával

Például
$(p\wedge q)\leftrightarrow (q\wedge p)$
és tudjuk, hogy $p\equiv p\wedge p$
így a pótlás: $((p\wedge p)\wedge q)\leftrightarrow (q\wedge p)$

Állítás

pótlással az eredetivel ekvivalens formulát kapunk

Lemma

ha φ és (φ→ψ) tautológiák, akkor a ψ is tautológia

Bizonyítás

Tegyük fel, hogy ψ nem tautológia,

legyen v olyan értékelés, amelyre v(ψ)=h (hamis)

erre a v értékelésre a φ igaz lesz, hiszen φ tautológia, tehát v(φ)=i (igaz)

ekkor vizsgáljuk meg erre a v értékelésre a (φ→ψ)-t, v(φ→ψ)=h a "→" definíciója szerint, de ez ellentmond annak, hogy (φ→ψ) tautológia.

Normálformák

Definíció (teljes diszjunktív normálforma)

mindegyik φ_i-ben mindegyik p_j szerepel negálva vagy negálatlanul

Tétel

Tetszőleges igazságfüggvényhez megadható olyan formula, amelyben csak a ¬, ∨, ∧ logikai jelek szerepelnek, és amely éppen azt az igazságfüggvényt definiálja.

A bizonyítást itt megtalálod

Teljes konjunktív normálformák

olyan normál formák $\varphi =\varphi _{1}\wedge ...\wedge \varphi _{n}$ ahol $\varphi _{i}=...\vee ...\vee ...$-ben csak $p_{e}$ és $\lnot p_{e}$ változók szerepelnek.

Például:
$\varphi =(p\rightarrow q)\rightarrow r$
Itt is készítsünk egy igaz-hamis táblázatot, de most (a teljes diszjunktív normálformával szemben a hamis-akat kell nézni)

(p	→	q)	→	r
i	i	i	i	i
i	i	i	h	h
i	h	h	i	i
i	h	h	i	h
h	i	i	i	i
h	i	i	h	h
h	i	h	i	i
h	i	h	h	h

Majd megkeressük azokat az értékeket, amelyekre hamis és a p, q, r változókat úgy írjuk le, hogyha abban a sorban hamis, akkor nem változtatjik, de ha igaz, akkor egy ¬-ot írunk elé.

Így: $\varphi \equiv (\lnot p\vee \lnot q\vee r)\wedge (p\vee \lnot q\vee r)\wedge (p\vee q\vee r)$

Így készen is vagyunk, de ha vesszük $\lnot \varphi$-t, akkor megkapjuk a teljes diszjunktív normálformát. Ennek itt láthatod a levezetését a De Morgan azonosságok segítségével: $\lnot (a\wedge b)=\lnot a\vee \lnot b$ és $\lnot (a\vee b)=\lnot a\wedge \lnot b$

Így tehát:

$\varphi \equiv \lnot \lnot \varphi$, ahol ha $\varphi$ a teljes konjunktív normálforma, akkor $\lnot \varphi$ pedig a teljes diszjunktív normálforma.

Teljesség

Definíció

Igazságfüggvénynek egy halmaza TELJES, ha a halmazhoz tartozó függvények kompozíciójaként tetszőleges igazságfüggvény előállítható.

Példa: {¬, ∧, ∨} teljes (lásd teljes diszjunktív és konjunktív normálformák)

Állítás

Az alábbiak teljesek:

(1) {¬, ∧}

(2) {¬, ∨}

(3) {¬ →}

Bizonyítás

itt

Állítás

{∧, ∨, →, ↔} nem teljes

Bizonyítás

itt

Állítás

{¬, ↔} nem teljes

Most bevezetünk két új műveletet, amelyek önmagukban is teljesek

Sheffer-művelet

p|q jelentése: "nem igaz az, hogy p és q"

p	q	q
i	i	h
i	h	i
h	i	i
h	h	i

Állítás

Bizonyítás

$p|p\equiv \lnot p$

$p|q\equiv \lnot (p\wedge q)\Rightarrow p\wedge q\equiv \lnot (p|q)\equiv (p|q)|(p|q)$

és már bizonyítottuk, hogy {∧, ¬} teljes

Peircee-művelet

$p\downarrow q$ jelentése: "sem p, sem q"

p	q	$p\downarrow q$
i	i	h
i	h	h
h	i	h
h	h	i

Állítás

$\left\{\downarrow \right\}$ teljes

Bizonyítás

$p\downarrow p\equiv \lnot p$

$p\downarrow q\equiv \lnot (p\vee q)\Rightarrow p\vee q\equiv \lnot (p\downarrow q)\equiv (p\downarrow q)\downarrow (p\downarrow q)$

és már bizonyítottuk, hogy {∨, ¬} teljes

A logikai következmény

Definíció

Γ:formulahalmaz, ψ:formula

A Γ-beli