Zadanie domowe z Logiki dla informatyków
Materiały do zajęć, nr 402
Paweł Laskoś-Grabowski
8 listopada 2004
1 Treść
Rozstrzygnąć, czy
("x(Ć Ò! È)) Ò! ("xĆ) Ò! ("xÈ) (1)
jest prawem rachunku kwantyfikatorów.
2 RozwiÄ…zanie
Twierdzenie 1. Formuła (1) nie jest prawem rachunku kwantyfikatorów.
Dowód. Niech Ć a" x = 1, È a" x = x. Przepiszmy naszÄ… formuÅ‚Ä™ w postaci jawnej:

("x(x = 1 Ò! x = x)) Ò! ("x(x = 1)) Ò! ("x(x = x)). (2)

Poprzednik implikacji jest prawdą, ponieważ dla x = 1 skwantyfikowana formuła warto-
Å›ciuje siÄ™ do F Ò! F. Poprzednik nastÄ™pnika jest prawdÄ…, ponieważ dla x = 0 skwantyfi-
kowana formuła wartościuje się do prawdy. Następnik następnika jest fałszem, ponieważ
x = x jest zawsze fałszem. Ostatecznie cała formuła równoważna jest

T Ò! T Ò! F, (3)
co równoważne jest faÅ‚szowi. Skoro dla pewnych Ć, È formuÅ‚a (1) jest faÅ‚szywa, to nie jest
prawem rachunku kwantyfikatorów.
1