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?
postać normalna
-
- Administrator
- Posty: 34539
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 4 razy
- Pomógł: 5226 razy
Re: postać normalna
Bo tak było cztery linijki wyżej, zanim to rozpisaliśmy?
bazyl01, co jest dla Ciebie postacią normalną? Bo ja znam przynajmniej dwie...
bazyl01, co jest dla Ciebie postacią normalną? Bo ja znam przynajmniej dwie...
- Hir
- Użytkownik
- Posty: 85
- Rejestracja: 7 mar 2024, o 21:07
- Płeć: Kobieta
- wiek: 29
- Podziękował: 25 razy
- Pomógł: 35 razy
Re: postać normalna
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.
\(\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.
-
- Administrator
- Posty: 34539
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 4 razy
- Pomógł: 5226 razy
Re: postać normalna
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
-
- Użytkownik
- Posty: 32
- Rejestracja: 12 cze 2023, o 20:27
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 3 razy
Re: postać normalna
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?
Dodano po 4 dniach 1 godzinie 44 minutach 7 sekundach:
Czy mógłbym prosić o jakąś pomoc?