Matematyka.pl

Sprawa się rozwiązała - chodziło o algorytm, który dla formuły F wskazuje formułę F' o tej odpowiedniej długości. Sam algorytm, dla zainteresowanych, to

Hej,
trafił mi się taki dowód do zrobienia:
Pokaż, że dla danej formuły zdaniowej F o długości N istnieje formuła zdaniowa F' w CNF o długości O(N) , spełnialna wtedy i tylko wtedy, gdy F jest spełnialna

I chyba nie rozumiem co my mamy tutaj dowieść. Jeśli F jest sprzeczna, to wystarczy za F ...

Rzeczywiście, teraz to wszystko się trzyma kupy, dziękuję bardzo

I rzeczywiście wynik się zgadza, rachunki są znacznie prostsze.
Ale pytanie: dlaczego? Może zadam pytanie nowicjusza, ale czemu przy współrzędnych biegunowych nie odejmujemy jednego równania od drugiego?
Bo zaczynam się domyślać, że ja przypadkowo obliczałem objętość pod jakąś tam funkcją dwóch ...

Mam problem z zadaniami następującego typu:
Oblicz pole obszaru ograniczonego następującymi krzywymi:
y^2 - 2y + x^2 = 0 , y^2 - 4y + x^2 = 0 , y = \sqrt{3}x , \sqrt{3}y = x
Ogólnie myślałem że następujące rozumowanie jest poprawne: przechodzę na współrzędne biegunowe (wtedy kąt jest z przedziału ...

Hej, dostałem następujące zadanie:
Niech \phi oraz \psi będą formułami rachunku zdań zbudowane wyłącznie ze zmiennych zdaniowych oraz spójników \vee oraz \wedge i nawiasów. Pokaż, że formuła \phi \Leftrightarrow \psi jest spełniona przez co najmniej dwa wartościowania.

Intuicyjnie zadanie jest ...

A to jest sprzeczne z dowodem w pierwszym poście, że \(\displaystyle{ \psi}\) musi być spełnialne, czyli dowód musi mieć gdzieś błąd

I chciałbym wrócić do zadania na samym początku - okazuje się (na co mój znajomy zwrócił mi uwagę), że podstawiając za formułę \phi wyrażenie p \vee q a za wyrażenie \psi formułę sprzeczną p \wedge \neg p dostajemy wnioski następujące:
1. Formuły p \vee q \Rightarrow p \wedge \neg p oraz \neg p ...

Oczywiście, że chodziło o bycie spełnialną - moje niedopatrzenie - istnieje wartościowanie, dla którego formuła jest prawdziwa. A rozpatrzenie 'tabelki', formalnie patrząc, jest prawidłowe?

Próbowałem nie wprost, ale nie jestem przekonany do tego. Nie wprost musimy wykazać, że jeśli \psi jest ...

Czy definicja rekurencyjna w tym wypadku polega na takich zapisach jak poniżej?
\hat{\sigma}(\phi) = \sigma(\phi)
\hat{\sigma}(\neg\phi) = \begin{cases} T \Leftrightarrow \hat{\sigma}(\phi) = F \\ F \Leftrightarrow \hat{\sigma}(\phi) = T \end{cases}
\hat{\sigma}(\phi_1 \Rightarrow \phi_2 ...

Sprawa wygląda tak, że raczej muszę być bardzo formalny, więc spróbuję 'naprawić' dowód rozważając dwa przypadki:
Z faktu, że \hat{\sigma} przypisuje wartości logiczne formułom zdaniowym, czyli przekształca je na zbiór dwuelementowy \left\{ T, F\right\} to są dwa przypadki
1.
Jeśli \hat{\sigma ...

Dziękuję za odpowiedzi. Co prawda nikt mnie nie upewnił w sprawie poprawności dowodu w pierwszym poście, ale strzelam, że skoro moje przemyślenia teoretyczne były prawidłowe, to przemyślenia w dowodzie również

Chciałbym spytać o poprawność mojego dowodu - Zadanie brzmi tak: Które z poniższych zdań są prawdziwe dla dowolnych formuł zdaniowych \phi i \psi :
Zdanie takie:
Jeśli \phi \Rightarrow \psi oraz \neg \phi \Rightarrow \psi są spełnialne, to \psi jest spełnialna.

Dowód:
Załóżmy nie wprost, że teza ...

To jeszcze mam dwie sprawy:
Pierwsza sprawa jest następująca - spotkałem się z trzema definicjami domknięcia tranzytywnego relacji R - tj. jedną słowną - Jest to najmniejszy zbiór przechodni zawierający relację R .
Drugą w takiej postaci: R^{+} = \bigcup_{i = 0}^{} R^{i}
a trzecią w takiej: R ...

Dostałem następujące zadanie:
Niech \Sigma będzie skończonym zbiorem symboli (alfabetem) oraz niech L \subseteq \Sigma^{*} . Relacja \sim_L \subseteq \Sigma^{*} \times \Sigma^{*} jest zdefiniowana w następujący sposób v \sim_L v' wtedy i tylko wtedy, gdy dla każdego x \in \Sigma^{*} ( vx \in L ...