Metoda zero-jedynkowa

 

W poprzednim rozdziale wyjaśniłem czym jest tautologia. W następnych rozdziałach poznasz szereg metod pozwalających na sprawdzenie, czy dana funkcja logiczna jest funkcją tautologiczną.

Pierwszą, najbardziej żmudną i prymitywną metodą jest tzw. metoda zero-jedynkowa. Polega ona na podstawianiu do funkcji każdej możliwej kombinacji zdań prawdziwych i fałszywych (p=1 i q=1, p=1 i q=0, p=0 i q=1, p=0 i q=0). Jeśli dla każdej możliwej kombinacji funkcja będzie prawdziwa (będzie miała wartość 1), będzie funkcją tautologiczną. Powinieneś już pamiętać matryce funktorów prawdziwościowych, gdyż ich znajomość jest niezbędna przy badaniu tautologiczności funkcji. Jeśli jeszcze ich nie znasz, miej je pod ręką:

Metodę 0-1 najprościej wyjaśnić na przykładzie. Weźmy taki oto schemat: (p Λ q) → (p → q) . Aby określić wartość logiczną całej implikacji, musimy najpierw określić wartość jej poprzednika i następnika, czyli (p Λ q) (poprzednik) i (p → q) (następnik).Dla większej przejrzystości stworzyłem tabelkę, gdzie wpisywać będziemy odpowiednie wartości.

Zacznijmy od podstawienia do naszej funkcji dwóch zdań prawdziwych, czyli p=1 i q=1.

1. Pierwszym krokiem jest wpisanie w miejsca tabeli pod p i q wartości jakie odpowiadają tym zmiennym. Pod każdym p i q wpisujemy zatem 1.

2. Następnie musimy rozstrzygnąć jaką wartość będą miały wyrażenia w nawiasach – implikacja i koniunkcja. Po sięgnięciu do matryc koniunkcji i implikacji widzimy, że koniunkcja dwóch zdań prawdziwych jest prawdziwa, podobnie jak implikacja. Wpisujemy zatem pod ich symbolami 1.

3. Wiedząc już jakie wartości przyjmują wyrażenia w nawiasach, możemy stwierdzić jaką wartość przyjmie całe wyrażenie. Wyrażenie (p Λ q) ma wartość 1, wyrażenie (p → q) również ma wartość 1. Zatem, wyrażenie (p Λ q) → (p → q) również ma wartość 1. Pod strzałką symbolizującą implikację wpisujemy zatem 1.

Wiemy już, że wyrażenie jest prawdziwe dla zmiennych p=1 i q=1. Dokonajmy teraz podstawień dla pozostałych wartości zmiennych: p=1 i q=0, p=0 i q=1, p=1 i q=0.

Jak widać, dla wszystkich kombinacji zmiennych funkcja przybiera wartość 1. Jest to zatem funkcja tautologiczna. Funkcja nie byłaby tautologią, gdyby jej wartość przy którymś podstawieniu zmiennych wyniosła 0. Oczywiście, gdyby przybrała wartość 0 już przy podstawieniu pierwszej kombinacji, sprawdzanie pozostałych możliwości byłoby daremne - od razu możnaby orzec, że funkcja tautologią nie jest.

Przykład, z którym się zmierzyliśmy w tym przypadku był bardzo prosty, nie było zbyt wiele do podstawiania. Jednak, wobec przykładów bardziej skomplikowanych, zwłaszcza takich z większą ilością zmiennych, metoda zero-jedynkowa staje się całkowicie niepraktyczna. Sprawdzenie tautologiczności funkcji z czterema zmiennymi wymagałoby przeanalizowania aż 16 możliwości, zajęłoby to masę czasu i niosło ze sobą duże ryzyko pomyłki. Dlatego też wymyślona została metoda skrócona, zwana również metodą dowodu nie wprost. Zapoznasz się z nią w następnym rozdziale.