Vsaka izjava ima resničnostno vrednost. Resničnostni vrednosti sta ⊥
(resnica) in ⊤ (neresnica).
Primer: ⊥ ∨ (⊤ ⇒ ⊤) je resnična, njena resničnostna vrednost je ⊤.
Primer: 2 + 2 = 5 je neresnična, njena resničnostna vrednost je ⊥.
Kadar izjava vsebuje spremenljivke (pravimo jim tudi parametri), je njena resničnostna vrednost odvisna od parametrov.
Primer: Naj bosta x, y ∈ N. Resničnstna vrednost izjave x + y < 3 je odvisna
od x in y, kar lahko prikažemo z resničnostno tabelo:
x | y | x + 2 * y < 3
---------------------
0 | 0 | ⊤
0 | 1 | ⊤
1 | 0 | ⊤
2 | 0 | ⊤
1 | 1 | ⊥
0 | 2 | ⊥
...
Kot vidimo, je lahko takšna tabela neskončna, kar ni praktično.
V izjavi lahko nastopajo tudi izjavne spremenljivke ali zijavni simboli,
to se spremenljivke, ki zavzamejo vrednosti ⊥ in ⊤.
Primer: Naj bosta p, q ∈ 2. Tedaj je ¬ p ∨ q izjava, katere resničnostna tabela je
p | q | ¬ p ∨ q
---------------
⊥ | ⊥ | ⊤
⊥ | ⊤ | ⊤
⊤ | ⊥ | ⊥
⊤ | ⊤ | ⊤
Izjava φ(p_1, …, p_n), v kateri nastopajo izjavne spremenljivke p_1, ...,
p_n (in nobeni drugi parametri) določa preslikavo
2 × ⋯ × 2 → 2
s predpisom
(p_1, …, p_n) ↦ φ(p_1, …, p_n)
Preslikavi, ki slika iz produkta 2 × ⋯ × 2 v 2 pravimo Boolova
preslikava. Prikažemo jo lahko z resničnostno tabelo. Če ima preslikava n
argumentov, ima tabela 2^n vrstic.
Izjava je tavtologija, če je njena resničnostna vrednost ⊤ ne glede na
vrednosti parametrov. Premisli: kako iz resničnostne tabele razberemo, ali je
izjava tavtologija?
Izrek: Naj bo
φizjava, v kateri nastopajo le izjavni simbolip_1,…,p_n. Tedaj velja:
- Če je
φtavtologija, potem ima dokaz.- Če ima
φdokaz, je tavtologija.
Dokaz. Dokaz najdete v N. Prijatelj: Osnove matematične logike (1. del).
Izrek je pomemben, ker nam pove, da lahko dokazovanje izjav v nekaterih primerih nadomestimo s preverjanjem resničnostnih tabel.
Opomba:* Izrek velja samo za izjave, ki jih sestavimo iz izjavnih simbolov,
⊥, ⊤ in logičnih veznikov ¬, ∧, ∨, ⇒, ⇔. Za splošne izjave, ki
vsebujejo tudi ∀ in ∃ izrek ne velja.
Vsaka formula v izjavnem računu ima resničnostno tabelo. Ali lahko vsako tabelo dobimo kot resničnostno tabelo neke formule? Na primer, ali obstaja formula, katere resničnostna tabela se glasi
p | q | ?
----------
⊥ | ⊥ | ⊥
⊥ | ⊤ | ⊤
⊤ | ⊥ | ⊤
⊥ | ⊥ | ⊥
Odgovor je pritrdilen. Na kratko povejmo, kako dobimo tako izjavo. Imamo dve množnosti.
Disjunktivna oblika: za vsako vrstico v tabeli, ki ima vrednost ⊤ zapišemo
konjunkcijo simbolov in njihovih negacij, pri čemer negiramo tiste simbole, ki
imajo v dani vrstici vrednost ⊥. Na primer, v zgornji tabeli imata druga in
tretja vrstica vrednost ⊤, zanju zapišemo konjukciji:
¬ p ∧ qp ∧ ¬ qNato tvorimo disjunkcijo tako dobljenih konjukcij:
(¬ p ∧ q) ∧ (p ∧ ¬ q)
Dobljena formula ima želeno resničnostno tabelo.
Konjunktivna oblika: za vsako vrstico v tabeli, ki ima vrednost ⊥ zapišemo
disjunkcijo simbolov in njihovih negacij, pri čemer negiramo tiste simbole, ki
imajo v dani vrstici vrednost ⊤. Na primer, v zgornji tabeli imata prva in
čertrta vrstica vednost ⊥, zanju zapišemo disjukciji:
p ∨ q¬ p ∨ ¬ qNato tvorimo konjunkcijo tako dobljenih disjunkcij:
(p ∨ q) ∧ (¬p ∨ ¬q)
Zgornjo tabelo bi lahko dobili tudi kot resničnostno tabelo formule
p ⇔ q
Vidimo, da lahko vsako resničnostno tabelo dobimo z uporabo veznikov ¬, ∨ in
∧. Polni nabor je tak izbor veznikov, k katerim lahko dobimo vsako
resničnostno tabelo.
Torej je ¬, ∨, ∧ poln nabor. Lahko bi ga še zmanjšali na ¬, ∧, saj lahko
p ∨ q
izrazimo kot
¬p ∧ ¬q.
Ekvivalentni izjavi imata enake resničnostne vrednosti, torej lahko ekvivalenco
⇔ obravnavamo kar kot enakost, saj to tudi je, kar se tiče resničnostnih
vrednosti. Zato lahko namesto p ⇔ q pišemo tudi p = q, če imamo v mislih le
resničnostne vrednosti.
(Opomba: izjavi sta lahko ekvivalentni, a nimata enakega pomena. Na primer,
izjavi ∀ x, y ∈ R . x + y = y + x in ∀ α ∈ R . sin(2 α) = 2 · cos α · sin α
sta ekvivalentni, saj sta obe resnični, a ne moremo reči, da je njun pomen enak.)
Za logične veznike veljajo algebrajska pravila. Ta pravila lahko uporabljamo kot računska pravila, s katerimi lahko izjavo poenostavmi v ekvivalentno obliko. Pogosto je tako računanje bolj prikladno kot dokazovanje. Spodaj našteta pravila lahko preverimo tako, da zapišemo resničnostne tabele izjav in jih primerjamo.
Pravilom, ki veljajo za logične veznike, pravimo Boolova algebra.
⊤ in ⊥⊤ ∨ p = ⊤ (⊤ absorbira ∨)⊤ ∧ p = p (⊤ je nevtralni element za ∧)¬ ⊤ = ⊥
⊥ ∧ p = ⊥ (⊥ absorbira ∧)
⊥ ∨ p = p (⊥ je nevtralni element za ∧)¬⊥ = ⊤¬¬¬p = p (negacija je involucija)¬(p ∧ q) = ¬p ∨ ¬q¬(p ∨ q) = ¬p ∧ ¬qp ∧ q = q ∧ p (konjunkcija je komutativna)p ∧ p = p (konjunkcija je idempotentna)(p ∧ q) ∧ r = p ∧ (q ∧ r) (konjunkcija je asociativna)
p ∨ q = q ∨ p (disjunkcija je komutativna)
p ∨ p = p (disjunkcija je idempotentna)(p ∨ q) ∨ r = p ∨ (q ∨ r) (disjunkcija je asociativna)Absorbcijski pravili:
p ∧ (p ∨ q) = pp ∨ (p ∧ q) = pDistributivnostni pravili:
p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r)p ∨ ¬ p = ⊤ (izključena tretja možnost)p ∧ ¬ p = ⊥(p ⇒ q) = (¬q ⇒ ¬p)(p ⇒ q) = ¬q ∨ pZapišimo še uporabna logična pravila za kvantifikatorje. Tokrat uporabimo ⇔
namesto =, ker je to bolj običajno.
(∀ x ∈ ∅ . φ(x)) ⇔ ⊤(∃ x ∈ ∅ . φ(x)) ⇔ ⊥(∀ x ∈ {a} . φ(x)) ⇔ φ(a)(∃ x ∈ {a} . φ(x)) ⇔ φ(a)(¬ ∀ x ∈ A . φ(x)) ⇔ ∃ x ∈ A . ¬ φ(x)(¬ ∃ x ∈ A . φ(x)) ⇔ ∀ x ∈ A . ¬ φ(x)(ψ ⇒ ∀ x ∈ A . φ(x)) ⇔ ∀ x ∈ A . ψ ⇒ φ(x)(ψ ∨ ∀ x ∈ A . φ(x)) ⇔ ∀ x ∈ A . ψ ∨ φ(x)(ψ ∧ ∃ x ∈ A . φ(x)) ⇔ ∃ x ∈ A . ψ ∧ φ(x)(∀ u ∈ A × B . φ(u)) ⇔ ∀ x ∈ A . ∀ y ∈ B . φ(x, y)(∃ u ∈ A × B . φ(u)) ⇔ ∃ x ∈ A . ∃ y ∈ B . φ(x, y)(∀ u ∈ A + B . φ(u)) ⇔ (∀ x ∈ A . φ(ι₁(x))) ∧ (∀ y ∈ B . φ(ι₂(y)))(∀ u ∈ A ∪ B . φ(u)) ⇔ (∀ x ∈ A . φ(x)) ∧ (∀ y ∈ B . φ(y))(∃ u ∈ A + B . φ(u)) ⇔ (∃ x ∈ A . φ(ι₁(x))) ∨ (∃ y ∈ B . φ(ι₂(y)))(∃ u ∈ A ∪ B . φ(u)) ⇔ (∃ x ∈ A . φ(x)) ∨ (∃ y ∈ B . φ(y))(∀ u ∈ {x ∈ A | ψ(x)} . φ(u)) ⇔ ∀ x ∈ A . ψ(x) ⇒ φ(x)(∃ u ∈ {x ∈ A | ψ(x)} . φ(u)) ⇔ ∃ x ∈ A . ψ(x) ∧ φ(x)Te ekvivalence je treba preveriti tako, da jih dokažemo.