Kwantyfikatory Machine: Formuły z kwantyfikatorami. Mam za zadanie sprawdzić czy formuły są równoważne, zadanie z moim rozwiązaniem w linku: http://www.freeimagehosting.net/j44xu Czy tak wygląda rozwiązanie tego zadania?

Basia: Twoje rozwiązanie jest poprawne a to inne rozwiązanie (z wykorzystaniem zaprzeczeń ~[ ∃_x(α⇒β)] ⇔ ∀_x ~(α⇒β) ⇔ ∀_x (α∧~β) ⇔ (∀_x α)∧~β) ~[ (∀_xα) ⇒ β ] ⇔ (∀_xα) ∧ ~β a skoro zaprzeczenia są równoważne to i badane formuły też

Machine: Dziękuję bardzo za potwierdzenie

marcin: W 1 kroku skorzystałeś z p ⇒ q ⇔ ¬p v q ? Natomiast w kroku drugim na końcu nie powinno być nawiasu jeszcze?

Machine: Nie bo w β nie występuje x więc można je spokojnie z nawiasu wyłączyć

marcin: a jak negujemy ∀ to otrzymujemy ∃ ? Jest gdzieś takie prawo napisane?

Basia: tak, jest takie prawo

marcin: a czy twój zapis jest równoważny z : ∃x(ω ⇒ φ) i (∀x ω) ⇒ φ ?

marcin: ale gdyby za α i β podstawić te formuły co je napisałem? To wtedy wyjdzie na to samo?

marcin:

Basia: źle przeczytałam; [ α(x) ⇔β(x) ] nie jest równoważne z α(x) ∧ β(x) dla α(x) = β(x) = 0 mamy [ α(x) ⇔β(x) ] = 1 a [α(x) ∧ β(x)]=0

marcin: czyli dowod jest niepoprawny?

Basia: dowód jest poprawny; Machine miał udowodnić równoważność tych formuł (i udowodnił) a nie badać ich koniunkcję

marcin: Tak ale za α mogę podstawić φ i za β ω i też będzie dla tego dobrze? o to mi głównie chodzi

Basia: oczywiście przecież litery nie mają znaczenia