postać normalna

[bazyl01]

Metodą przekształceń równoważnościowych sprowadzić formułę \(\displaystyle{ (p\to q)\wedge(q\to r)\to(p\vee q\to r)}\) do postaci normalnej i sprawdzić czy jest ona tautologią KRZ. Odpowiedź uzasadnić.

Korzystam z prawa eliminacji implikacji najpierw w najbardziej wewnętrznych formułach

\(\displaystyle{ ( \neg p \vee q) \wedge ( \neg q \vee r) \rightarrow [ \neg (p \vee q) \vee r]}\)

Teraz eliminuję główną implikację

\(\displaystyle{ \neg [( \neg p \vee q) \wedge ( \neg q \vee r)] \vee [( \neg p \wedge \neg q) \vee r]}\)

Korzystam z prawa de Morgana dla pierwszego członu koniunkcji, a dla drugiego z prawa roździelności alternatywy względem koniunkcji

\(\displaystyle{ [\neg ( \neg p \vee q) \vee \neg ( \neg q \vee r)] \vee [( \neg p \vee r) \wedge ( \neg q \vee r)] }\)

W pierwszym członie alternatywy stosuję ponownie prawa de Morgana

\(\displaystyle{ [(p \wedge \neg q) \vee (q \wedge \neg r)] \vee [( \neg p \vee r) \wedge ( \neg q \vee r)] }\)

No i tu pojawia się kłopot co robić dalej? Jakieś podpowiedzi?

[Hir]

\(\displaystyle{ [( \neg p \vee r) \wedge ( \neg q \vee r)] }\) jest tym samym, co \(\displaystyle{ [( \neg p \wedge \neg q) \vee r] }\) (dlaczego?).

[Jan Kraszewski]

Bo tak było cztery linijki wyżej, zanim to rozpisaliśmy?

bazyl01, co jest dla Ciebie postacią normalną? Bo ja znam przynajmniej dwie...

[Hir]

Faktycznie, ma Pan rację. Przeczytałam tylko ostatnią linijkę i uznałam, że dążymy do koniunkcyjnej postaci normalnej. Jeśli tak, to dalej rozwiązałabym to następująco:

\(\displaystyle{ [(p \wedge \neg q) \vee (q \wedge \neg r)] \vee [( \neg p \wedge \neg q) \vee r] }\)

Pierwszy i trzeci nawias można zapisać krócej jako \(\displaystyle{ \neg q}\). I teraz już widać, że to będzie tautologia.

[Jan Kraszewski]

Pierwszy i trzeci nawias można zapisać krócej jako \(\displaystyle{ \neg q}\). I teraz już widać, że to będzie tautologia.

Sprawdzenie tautologiczności jest w tym zadaniu raczej wnioskiem z postaci normalnej, więc najpierw musimy ustalić, którą postać normalną mamy osiągnąć... Jeżeli dysjunkcyjną, to mamy, a jak koniunkcyjną, to gorzej...

JK

[bazyl01]

Dzień dobry, chciałbym rzecz jasna skorzystać z twierdzenia mówiącego, że jeśli w każdej alternatywie elementarnej koniunkcyjnej postaci normalnej występuję przynajmniej jedna para przeciwnych literałów, to formuła jest tautologią, ale nie mogę się dobrać do postaci CNF, ugrzązłem.

Dodano po 4 dniach 1 godzinie 44 minutach 7 sekundach:
Czy mógłbym prosić o jakąś pomoc?