Równoważnośc formuł

[tukanik]

Równoważność formuł jest definiowana jako:
Dwie formuły są równoważne wtedy gdy dla każdego wartościowania ich wartości są takie same.

I teraz pytanie:
\(\displaystyle{ \phi = p \vee \neg p}\)
\(\displaystyle{ \psi = (0 \rightarrow s) \vee q}\)
Obie formuły to tautologie i obie formuły są spełnianie dokładnie przez te same wartościowania, bo przez wszystkie dowolne.
W tym wypadku jest to oczywiste ze względu na tautologie.

Co w przypadku kiedy nie są tautologiami a mają wzajemnie różne zbiory zmiennych?
Np. formułę \(\displaystyle{ \psi}\) spełnia następujące wartościowanie: \(\displaystyle{ f(s) = 0, f(q) = 1}\)
Formuła spełniona. Jeżeli formuła \(\displaystyle{ \phi}\) jest równoważna to musi zostać spełniona przez wartościowanie \(\displaystyle{ f}\) również. Ale czy jest spełniona? Ciężko o tym myśleć, bowiem formuła \(\displaystyle{ \phi}\) ma zupełnie inne zmienne ( i mniej ) niż formuła \(\displaystyle{ \psi}\).

Jak to w końcu jest?

[Jan Kraszewski]

Jest tak, że formalnie masz przeliczalnie wiele zmiennych zdaniowych, z których w danej formule wykorzystujesz tylko skończenie wiele. Natomiast wartościowanie jest funkcją, która wartościuje wszystkie zmienne zdaniowe, zarówno te, które w formule występują, jak i te, których tam nie ma. Wobec tego

Np. formułę \(\displaystyle{ \psi}\) spełnia następujące wartościowanie: \(\displaystyle{ f(s) = 0, f(q) = 1}\)

nie definiuje jeszcze wartościowania.

JK

[tukanik]

Ok, to w takim razie jest już jasne