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[szerkesztés]

Következtetések (konklúzió)[szerkesztés]

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[szerkesztés]

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[szerkesztés]

A negáció[szerkesztés]

¬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ó[szerkesztés]

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ó[szerkesztés]

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"[szerkesztés]

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

Az implikáció[szerkesztés]

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[szerkesztés]

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[szerkesztés]

Definíció

minden ítéletváltozó formula
ha φ formula, akkor (¬φ) is formula
ha φ és ψ formulák, akkor (φ∧ψ), (φ∨ψ), (φ→ψ) és (φ↔ψ) is formulák
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[szerkesztés]

$p\wedge q\equiv q\wedge p\qquad p\vee q\equiv q\vee p$
$p\wedge (q\wedge r)\equiv (p\wedge q)\wedge r\qquad p\vee (q\vee r)\equiv (p\vee q)\vee r$
$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)$
$p\wedge (p\vee q)\equiv p\qquad p\vee (p\wedge q)\equiv p$
$p\wedge p\equiv p\qquad p\vee p\equiv p$
$p\rightarrow q\equiv \lnot p\vee q$
$p\leftrightarrow q\equiv (p\rightarrow q)\wedge (q\rightarrow p)$
$\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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

$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[szerkesztés]

Definíció: Γ:formulahalmaz, ψ:formula; A Γ-beli