Iskazni račun, Logika

Svođenje na normalnu iskaznu formu

Comments Off on Svođenje na normalnu iskaznu formu 27 September 2014

Svođenje na normalnu iskaznu formu je metoda pojednostavljivanja složenih iskaza i metoda koja može poslužiti kao način da se utvrdi da li je neka formula tautologija.

Normalna iskazna forma je forma koja sadrži iskazne promenljive (npr, p, q, r,…) ili njihove negacije (¬p, ¬q, …) povezane u konjukcije ili u disjunkcije.

Na primer stav: (p v q v r) (p v q)  je stav koji ima normalnu formu. Svaki složeni iskaz može se prevesti u normalnu iskaznu formu.

Mogu se razlikovati dva oblika normalne forme iskaza:

1)      Konjuktivna normalna forma ima obilk α1 ∙ α2 ∙ α3 … gde su α1 itd. iskazne promenljive, njihove negacije ili disjunkcije.

2)      Disjunktivna normalna forma ima obilk α1 v α2 v α3 … gde su α1 itd. iskazne promenljive, njihove negacije ili konjukcije.

Svesti neki iskaz na normalnu iskaznu formu znači transformisati iskaz prema osnovnim tautologijama (ekvivalencijama) koje opisuju kako ekvivalencije, implikacije i negirane konjukcije i disjunkcije zameniti formulama u kojima se javljaju samo elementi koji su dozvoljeni u normalnoj iskaznoj formi.

Primer transformacije:

p (q p)

prema pravilu (a b) = (¬a v b)

p (¬q v p)

prema istom pravilu

¬p v (¬q v p)

prema pravilu o asocijativnosti

p v p) v ¬q                    (normalna iskazna forma)

zakon isključenja trećeg            p v p)

v ¬q

tablica za disjunkciju

 

 

 

 

Dakle, uvek kad u formuli vidimo ekvivalenciju transformišemo je u konjukciju dve implikacije, uvek kada vidimo implikaciju, transformišemo je u disjunkciju, uvek kada vidimo negaciju konjukcije i disjunkcije transformišemo je prema De Morganovim zakonima ¬ (p v q) =¬p ¬q ili isto tako i za konjukciju ¬ (p q) =¬p v ¬q.

Ako metodom svođenja na normalnu formu želimo da dokažemo da je neka formula tautologija, od koristi su sledeće ekvivalencije:

p = p                                        p =

v p =                            ┴ v p = p

Drugim rečima, tačan iskaz (tautologija) se može skratiti iz konjukcije, a netačan (kontradikcija) iz disjunkcije. Opet, ako u disjunkciji imamo tačan iskaz i disjunkcija je tačna, a ako u konjukciji imamo netačan iskaz ta konjukcija je netačna.

Još jedan primer:

(p v q) ¬p q

po pravilu o dsitributivnosti sledi…

(p ¬ p) v (q ¬p) q

skratimo kontradikciju (p ¬p) iz disjunkcije

(q ¬ p) q

po pravilu o implikaciji

¬(q ¬ p) v q

De Morganov zakon

¬ q v ¬ ¬ p v q

pravilo o dvostrukoj negaciji

¬ q v p v q                         (disj. normalna forma)

pravilo o asocijativnosti

¬ q v q v p

zakon isključenja trećeg  q v q)

v p

tablica za disjunkciju

 

formula je tautologija

 

 

primeri za vežbu: Svedi na normalnu formu i dokaži da je formula tautologija:

 

p = q

p ∙ p = p

(p → q) v (q → p)

p → (p v q)

((p → q) →p) →p

((p → q) ∙ p) → q

((p → q) ∙ ¬q) → ¬p

¬p → (p → q)

(u lekciji je znak za konjukciju , za ekvivalenciju =, a za implikaciju )

SHARES
Share on FacebookShareTweet on TwitterTweet

Comments are closed.

© 2017 Kratka istorija filozofije. Powered by WordPress.

Daily Edition Theme by WooThemes - Premium WordPress Themes

%d bloggers like this: