Metoda dowodu nie wprost

 

Badanie tautologiczności funkcji metodą dowodu nie wprost jest dużo praktyczniejsze niż badanie za pomocą zaprezentowanej w poprzednim rozdziale metody zero-jedynkowej. Polega na przyjęciu założenia, że badana przez nas funkcja jest fałszywa i na takim podstawianiu wartości do zmiennych aby tej fałszywości odpowiadały. Jeśli badana przez nas funkcja będzie tautologią, w trakcie podstawiania napotkamy sprzeczność.

Osobiście preferuję badanie funkcji od lewej strony do prawej i sukcesywne podstawianie odpowiednich wartości tam gdzie tylko to możliwe.

Weźmy przykładową funkcję logiczną: (p → q) → (¬q → ¬p)

1. Zakładamy, że badana przez nas funkcja jest fałszywa. Stawiamy zatem pod znakiem implikacji łączącym całe wyrażenie liczbę 0.

2. Aby implikacja miała wartość 0, jej poprzednik musi być prawdziwy, a następnik fałszywy. Pod implikacją będącą poprzednikiem stawiamy zatem 1, a pod implikacją będącą następnikiem 0.

3. Spójrzmy na pierwszy człon naszej funkcji. Co by się musiało stać, żeby implikacja była prawdziwa? Są na to aż 3 możliwości. Wobec tego, przejdźmy do członu drugiego, może w jego przypadku wybór będzie mniejszy i łatwiejszy. Drugi człon również jest implikacją, z tym, że  musi on być fałszywy. Co musi się stać, aby implikacja miała wartość 0? Jej poprzednik musi mieć wartość 1, a następnik wartość 0. Wpisujemy zatem te liczby pod poprzednik i następnik. Ale UWAGA, nie możemy wpisać tych wartości pod p i q, gdyż poprzednikiem i następnikiem w tej implikacji są NEGACJE p i q. Wpisujemy zatem 1 i 0 pod symbolami negacji.

4. Skoro ¬q=1 i ¬p=0, to w takim razie q=0 i p=1, gdyż negacja zmienia wartość wyrażenia z 1 na 0 i z 0 na 1. Pod q wpisujemy zatem 0, a pod p 1.

5. Skoro znamy już wartości p i q, możemy przepisać je tam, gdzie wartości p i q występują, czyli pod pierwszym członem naszej funkcji.

6. Uzupełniliśmy już wszystkie miejsca. Czy wszystko się zgadza? Nie wszystko. Pierwszy człon funkcji, żeby spełnić założenie o jej fałszywości musiał być prawdziwy. Czy może taki być dla wartości p=1 i q=0? Oczywiście, że nie, gdyż dla takich wartości funkcja przyjmuje wartość 0. 

Napotkaliśmy zatem na sprzeczność. Nie jest możliwe takie podstawienie zmiennych, aby funkcja była fałszywa. Będzie zawsze prawdziwa z racji swojej budowy – dowiedliśmy zatem jej tautologiczności.

Jak widać, metoda nie wprost nie jest taka straszna jakby się mogło wydawać. Po rozwiązaniu kilku zadań, całkowicie się z nią oswoisz i opanujesz do perfekcji.