„Szerkesztő:Kizin/próba” változatai közötti eltérés
Tartalom törölve Tartalom hozzáadva
282. sor:
: 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.
[[User:kizin/próba/pelda1|A bizonyítást itt megtalálod]]<br>
; Teljes konjunktív normálformák
: olyan normál formák <math>\varphi =\varphi _{1}\wedge ...\wedge\varphi _{n}</math> ahol <math>\varphi _{i}=...\vee ...\vee ...</math>-ben csak <math>p_{e} </math> és <math> \lnot p_{e}</math> változók szerepelnek.
Például:<br>
<math>\varphi =(p\rightarrow q)\rightarrow r</math>
<br> 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)
{|border="1"
|(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: <math>\varphi \equiv (\lnot p \vee\lnot q \vee r)\wedge (p\vee\lnot q \vee r)\wedge (p\vee q\vee r)</math>
Így készen is vagyunk, de ha vesszük <math>\lnot\varphi</math>-t, akkor megkapjuk a teljes diszjunktív normálformát. [[User:kizin/próba/pelda1|Ennek itt láthatod a levezetését]]
a De Morgan azonosságok segítségével:
<math>\lnot (a\wedge b)=\lnot a\vee\lnot b</math> és <math>\lnot (a\vee b)=\lnot a\wedge\lnot b</math>
Így tehát:
<math>\varphi\equiv\lnot\lnot\varphi</math>, ahol ha <math>\varphi</math> a teljes konjunktív normálforma, akkor <math>\lnot\varphi</math> pedig a teljes diszjunktív normálforma.
; 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
:: [[user:kizin/próba/pelda1|itt]]
| |||