Példák a Matematikai logika cikkhez

Ebben a cikkben példákat láthatsz a Matematikai logika cikkben leírt definíciókkal, műveletekkel.

Ítéletkalkulushoz tartozó példák

Tautológia, kontradikció

I. Példa

p∨¬p tautológia
p∧¬p kontradikció
p↔¬¬p tautológia
((¬p)→q)→((¬p→¬q)→p) tautológia

Bizonyítás: Bizonyítani az igaz-hamis táblázat segítségével lehet

p	¬p	p∨¬p	p∧¬p
i	h	i	h
h	i	i	h

Amint látható:

p∨¬p tautológia, hiszen mindenhol igaz
p∧¬p kontradikció, hiszen mindenhol hamis

Ugyanígy bebizonyítható a 3. és 4. állítás Tehát:

p	↔	¬	¬	p
i	i	i	h	i
h	i	h	i	h

((¬	p)	→	q)	→	((¬	p	→	¬	q)	→	p)
h	i	i	i	i	h	i	i	h	i	i	i
h	i	i	h	i	h	i	i	i	h	i	i
i	h	i	i	i	i	h	h	h	i	i	h
i	h	h	h	i	i	h	i	i	h	h	h

A középső oszlopokból (az utolsó műveletnél) kiderül, hogy mind a két példa tautológia.

II. Példa

$p\rightarrow q\equiv \lnot p\vee q$

Bizonyítás: Itt is az igaz-hamis táblázatot hívjuk segítségül; Tehát azt kell belátnunk (a definíció alapján), hogy mind a két formula ugyanazokra az értékelésekre igazak, ezt külön-külön látjuk be.

p	→	q	$\equiv$	¬	p	∨	q
i	i	i		h	i	i	i
i	h	h		h	i	h	h
h	i	i		i	h	i	i
h	i	h		i	h	i	h

Tehát a középső sorok (utolsó elvégzendő műveletek sorai) megegyeznek.

III. Példa

$\lnot (p\wedge q)\equiv \lnot p\vee \lnot q$
$\lnot (p\vee q)\equiv \lnot p\wedge \lnot q$

Bizonyítás: Mint az előzőekben

¬	(p	∧	q)	$\equiv$	¬	p	∨	¬	q
h	i	i	i		h	i	h	h	i
i	i	h	h		h	i	i	i	h
i	h	h	i		i	h	i	h	i
i	h	h	h		i	h	i	i	h

¬	(p	∨	q)	$\equiv$	¬	p	∧	¬	q
h	i	i	i		h	i	h	h	i
h	i	i	h		h	i	h	i	h
h	h	i	i		i	h	h	h	i
i	h	h	h		i	h	i	i	h

Normálformákhoz tartozó példák

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.

Bizonyítás

Legyen $f(p_{1},...,p_{n})\equiv h$
azaz $p_{1}\wedge (\lnot p_{1})\wedge p_{2}\wedge ...\wedge p_{n}\equiv h$

Írjuk be p, q és r-t az igaz-hamis táblázatba:

p	q	r	f(p, q, r)
i	i	i	i
i	i	h	i
i	h	i	h
i	h	h	i
h	i	i	h
h	i	h	h
h	h	i	h
h	h	h	i

Az f(p, q, r) 4 helyen igaz, így vegyünk négy darab φ formulát,ugyanis, ha igaz, akkor a négy φ közül az egyiknek teljesülnie kell, azaz
φ₁∨φ₂∨φ₃∨φ₄-et kell venni.

Tehát legyen:

φ₁=p∧q∧r mivel az első sor igaz

φ₂=p∧q∧(¬r) mivel a második sor igaz (az r hamis)

φ₃=p∧(¬q)∧(¬r) mivel a negyedik sor igaz (a q és az r hamis)

φ₄=(¬p)∧(¬q)∧(¬r) mivel az utolsó sor igaz (a p, a q és az r hamis)

tehát: (p∧q∧r)∨(p∧q∧¬r)∨(p∧¬q∧¬r)∨(¬p∧¬q∧¬r)

majdnem minden formula ilyen alakra hozható

Felhasználandó: $a\rightarrow b\equiv \lnot a\vee b\qquad q+{\bar {q}}=1\qquad \varphi \vee \varphi \equiv \varphi$
Így:
$p\rightarrow (q\rightarrow r)={\bar {p}}+({\bar {q}}+r)={\bar {p}}+{\bar {q}}+r={\bar {p}}\cdot 1+{\bar {q}}+r={\bar {p}}\cdot (q+{\bar {q}})+{\bar {q}}+r={\bar {p}}\cdot q+{\bar {p}}\cdot {\bar {q}}+{\bar {q}}+r=$ $={\bar {p}}\cdot q\cdot r+{\bar {p}}\cdot q\cdot {\bar {r}}+{\bar {p}}\cdot {\bar {q}}\cdot r+{\bar {p}}\cdot {\bar {q}}\cdot {\bar {r}}+(p+{\bar {p}})\cdot {\bar {q}}\cdot (r+{\bar {r}})+(p+{\bar {p}})\cdot (q+{\bar {q}})\cdot r=$ $={\bar {p}}\cdot q\cdot r+{\bar {p}}\cdot {\bar {q}}\cdot r+{\bar {p}}\cdot q\cdot {\bar {r}}+{\bar {p}}\cdot {\bar {q}}\cdot {\bar {r}}+p\cdot {\bar {q}}\cdot r+p\cdot {\bar {q}}\cdot {\bar {r}}+{\bar {p}}\cdot {\bar {q}}\cdot r+{\bar {p}}\cdot {\bar {q}}\cdot {\bar {r}}+p\cdot q\cdot r+p\cdot {\bar {q}}\cdot r+{\bar {p}}\cdot q\cdot r+{\bar {p}}\cdot {\bar {q}}\cdot r$

Ez pedig ekvivalens a következővel:
${\bar {p}}\cdot q\cdot r+{\bar {p}}\cdot {\bar {q}}\cdot r+{\bar {p}}\cdot q\cdot {\bar {r}}+{\bar {p}}\cdot {\bar {q}}\cdot {\bar {r}}+p\cdot {\bar {q}}\cdot r+p\cdot {\bar {q}}\cdot {\bar {r}}+p\cdot q\cdot r$

Ezekre lesz igaz, de ez csak hét darab, pedig nyolcnak kellene lenni, tehát a nyolcadik lesz az, amire hamis, azaz: p→(q→r)=h, ha $p\cdot q\cdot {\bar {r}}$ , azaz p hamis; q igaz; r hamis.

Állítás: Az alábbiak teljesek:; (1) {¬, ∧}; (2) {¬, ∨}; (3) {¬ →}

Bizonyítás

(1)
elég kifejezni a ∨-t a ¬ és ∧-vel
$\lnot (a\vee b)\equiv \lnot a\wedge \lnot b$
$a\vee b\equiv \lnot \lnot (a\vee b)\equiv \lnot (\lnot a\wedge \lnot b)$

(2)
elég kifejezni a ∧-t a ¬-val és ∨-val
$\lnot (a\wedge b)\equiv \lnot a\vee \lnot b$
$(a\wedge b)\equiv \lnot \lnot (a\wedge b)\equiv \lnot (\lnot a\vee \lnot b)$

(3)
$a\rightarrow b\equiv \lnot a\vee b$
$\lnot a\rightarrow b\equiv \lnot \lnot a\vee b\equiv a\vee b$
tehát a ¬ és →-val a ∨ kifejezhető, így minden kifejezhető

Állítás: {∧, ∨, →, ↔} nem teljes

Bizonyítás

vizsgáljuk meg az igaz állításokat: i∧i=i∨i=i→i=i↔i=i
szóval, ha egy φ formulában csak ∧, ∨, →, ↔ szerepel, akkor φ=(i, i, ..., i)=i
tehát olyan f igazságfüggvények nem fejezhetőek ki ∧, ∨, →, ↔-val, amelyekre f(i, ..., i)=h