Formuły równoważne, równania i nierówności

Definicja 2..1   Mówimy, że formuły $\alpha$ i $\beta$ są równoważne, gdy formuła $\alpha\Leftrightarrow\beta$ jest tautologią.

Uwaga 2..2   Formuły $\alpha$ i $\beta$ są równoważne wtedy i tylko wtedy, gdy mają te same tabelki wartości logicznych.

Następujące tautologie opisują własności spójników $\land$ i $\lor$. Zwróćmy uwagę, że tautologie te mówią o równoważności pewnych formuł zdaniowych.

1. $p\land q\Leftrightarrow q\land p$ i $p\lor q\Leftrightarrow q\lor p$ (przemienność $\land$ i $\lor$)
2. $(p\land q)\land r\Leftrightarrow p\land(q\land r)$ i $(p\lor q)\lor r\Leftrightarrow p\lor(q\lor r)$ (łączność $\land$ i $\lor$)
3. $p\land(q\lor r)\Leftrightarrow(p\land q)\lor(p\land r)$ (rozdzielność $\land$ względem $\lor$)
4. $p\lor(q\land r)\Leftrightarrow(p\lor q)\land(p\lor r)$ (rozdzielność $\lor$ względem $\land$)
5. $p\land p\Leftrightarrow p$ i $p\lor p\Leftrightarrow p$
6. $p\land 0\Leftrightarrow 0$ i $p\lor 0\Leftrightarrow p$
7. $p\land 1\Leftrightarrow p$ i $p\lor 1\Leftrightarrow 1$

Zauważmy, że gdy w wyliczonych wyżej tautologiach zastąpimy zmienne zdaniowe przez zmienne liczbowe, symbol $\Leftrightarrow$ przez znak równości, zaś spójniki $\land$ i $\lor$ przez symbole mnożenia $\cdot$ i dodawania $+$, to wówczas otrzymamy wyrażenia algebraiczne, które w wielu przypadkach będą tożsamościami. Na przykład tautologie z punktu 2. odpowiadają w ten sposób prawom łączności mnożenia i dodawania:

$$(x\cdot y)\cdot z=x\cdot(y\cdot z),\ \ \ \ (x+y)+z=x+(y+z).$$

Dzięki łączności w wyrażeniach tego typu w algebrze możemy opuszczać nawiasy. Podobnie w rachunku zdań możemy opuszczać nawiasy w wielokrotnych koniunkcjach i alternatywach.

Dotychczas rozważaliśmy spójniki logiczne odpowiadające spójnikom występującym w mowie potocznej. Możemy również definiować abstrakcyjne spójniki logiczne poprzez zadanie tabelki wartości logicznych. Na przykład, by zdefiniować abstrakcyjny dwuargumentowy spójnik logiczny $*$, wystarczy wypełnić tabelkę

$$\begin{array}{c\vert c\vert c}p&q&p*q\\ \hline 1&1&?\\ 1&0&?\\ 0&1&?\\ 0&0&?\end{array}$$

zastępując znaki $?$ przez $0$ lub $1$. Można to uczynić na $2\times 2\times 2\times 2=16$ sposobów. Dlatego jest $16$ nierównoważnych dwuargumentowych spójników logicznych.

Podobnie określamy $k$-argumentowe spójniki logiczne dla $k=1,2,3,\dots$ Przy pomocy $k$-argumentowego spójnika $*$ ze zdań $p_1,\dots,p_k$ tworzymy nowe zdanie $*(p_1,\dots,p_k)$. Oczywiście jest $2^{2^k}$ nierównoważnych $k$-argumentowych spójników logicznych. Zazwyczaj rozważamy jednak spójniki jedno i dwuargumentowe.

Definicja 2..3   Mówimy, że spójnik dwuargumentowy $*$ jest definiowalny przez formułę $\alpha(p,q)$, gdy formuła $p*q$ jest równoważna formule $\alpha(p,q)$.

W przypadku, gdy spójnik $*$ jest definiowalny przez formułę $\alpha$, w każdej formule $\gamma$ możemy zastąpić wystąpienia spójnika $*$ przez odpowiednie podstawienie formuły $\alpha$, otrzymując równoważną formułę $\gamma'$.

Przykłady. Z prawa de Morgana dla koniunkcji dostajemy, że $\neg(p\land q)$ jest równoważne $\neg p\lor \neg q$. Dlatego $\neg(\neg(p\land q))$ jest równoważne $\neg(\neg p\lor \neg q)$. Na mocy prawa podwójnej negacji $\neg(\neg(p\land q))$ jest równoważne formule $p\land q$. Widzimy więc, że

$p\land q$ jest równoważne $\neg(\neg p\lor \neg q)$,

tzn. formuła

$$p\land q\Leftrightarrow \neg(\neg p\lor \neg q)$$

jest tautologią. Możemy więc powiedzieć, że spójnik koniunkcji $\land$ jest definiowalny przy pomocy spójników negacji i alternatywy. Używając spójników $\neg$ i $\lor$ możemy w dowolnej formule wyeliminować wystąpienia spójnika $\land$, dostając formułę równoważną.

Podobnie dostajemy, że $p\lor q$ jest równoważne $\neg(\neg p\land\neg q)$, czyli spójnik alternatywy jest definiowalny przy pomocy $\neg$ i $\land$.

Korzystając z równoważności $\neg(p\Rightarrow q)$ i $p\land\neg q$ dostajemy, że formuła $p\Rightarrow q$ jest równoważna każdej z formuł $\neg(p\land\neg q)$ i $\neg p\lor q$.

Uwaga 2..4   Każdy spójnik dwuargumentowy (ogólniej: k-argumentowy) można zdefiniować przy pomocy negacji i dowolnego spójnika spośród $\land,\lor,\Rightarrow$.

Wniosek 2..5   Każda formuła jest równoważna formule zbudowanej przy pomocy $\neg$ i dowolnego spójnika spośród $\land,\lor,\Rightarrow$.

Przykład. Znajdziemy formułę równoważną formule $(p\Rightarrow q)\Rightarrow r$, zbudowaną przy pomocy $\neg$ i $\lor$. W ciągu napisów poniżej znak $\Updownarrow$ oznacza skrót: ``jest równoważne''. Korzystając z tego, że $\alpha\Rightarrow\beta$ jest równoważne $\neg\alpha\lor\beta$, mamy więc:

$$(p\Rightarrow q)\Rightarrow r$$

$$\Updownarrow$$

$$\neg(p\Rightarrow q)\lor r$$

$$\Updownarrow$$

$$\neg(\neg p\lor q)\lor r$$

Dlatego formuła $(p\Rightarrow q)\Rightarrow r$ jest równoważna formule $\neg(\neg p\lor q)\lor r$.

Definicja 2..6 (1)   Formuła $\alpha$ jest w postaci alternatywno-koniunkcyjnej, gdy jest postaci

$$\alpha_1\lor\alpha_2\lor\dots\lor \alpha_k,$$

gdzie $k\geq 1$ oraz dla $i=1,\dots,k$

$$\alpha_i=\beta_{i1}\land\beta_{i2}\land\dots\land\beta_{il_i}$$

dla pewnego $l_i\geq 1$, gdzie każde $\beta_{ij}$ jest zmienną zdaniową lub negacją zmiennej zdaniowej.

(2) Formuła $\alpha$ jest w postaci koniunkcyjno-alternatywnej, gdy jest postaci

$$\alpha_1\land\alpha_2\land\dots\land\alpha_k,$$

gdzie $k\geq 1$ oraz dla $i=1,\dots,k$

$$\alpha_i=\beta_{i1}\lor\beta_{i2}\lor\dots\lor\beta_{il_i}$$

dla pewnego $l_i\geq 1$, gdzie każde $\beta_{ij}$ jest zmienną zdaniową lub negacją zmiennej zdaniowej.

Na przykład formuła

$$(p_1\land\neg p_2\land p_3)\lor(p_1\land p_3)\lor(\neg p_1)$$

jest postaci alternatywno-koniunkcyjnej, zaś formuła

$$(p_1\lor\neg p_2\lor p_3)\land(p_1\lor p_3)\land(\neg p_1)$$

jest postaci koniuncyjno-alternatywnej.

Uwaga 2..7 (1)   Każda formuła zdaniowa jest równoważna formule w postaci alternatywno-koniunkcyjnej.
(2) Każda formuła zdaniowa jest równoważna formule w postaci koniunkcyjno-alternatywnej.

Dowód. Dowód przeprowadzimy na przykładzie.
(1) Załóżmy, że tabelka wartości logicznych formuły $\alpha=\alpha(p,q,r)$ wygląda następująco:

$$\begin{array}{c\vert c\vert c\vert c}p&q&r&\alpha(p,q,r)\\ \h... ...\\ 0&1&1&0\\ 1&0&0&0\\ 1&0&1&1\\ 1&1&0&0\\ 1&1&1&0\end{array}$$

Z tabelki tej odczytujemy, że formuła $\alpha(p,q,r)$ jest prawdziwa wtedy i tylko wtedy, gdy

$$[p=0\land q=0\land r=1]\lor[p=0\land q=1\land r=0]\lor[p=1\land q=0\land r=1].$$

Zatem formuła $\alpha(p,q,r)$ jest równoważna formule

$$(\neg p\land \neg q\land r)\lor(\neg p\land q\land \neg r)\lor(p\land\neg q\land r),$$

która jest w postaci alternatywno-koniunkcyjnej.

(2) Rozważmy formułę $\alpha(p,q,r)$. Stosujemy punkt (1) do formuły $\neg\alpha(p,q,r)$, znajdując równoważną jej formułę w postaci alternatywno-koniunkcyjnej. Przypuśćmy dla przykładu, że formuła $\neg\alpha(p,q,r)$ jest równoważna formule

$$(\neg p\land \neg q\land r)\lor(\neg p\land q\land \neg r)\lor(p\land\neg q\land r).$$

Wówczas wyjściowa formuła $\alpha(p,q,r)$ jest równoważna formule

$$\neg\left[(\neg p\land \neg q\land r)\lor(\neg p\land q\land \neg r)\lor(p\land\neg q\land r)\right].$$

Stosując prawa de Morgana dla koniunkcji i alternatywy oraz zastępując wyrażenia $\neg\neg p,\neg\neg q, \neg\neg r$ równoważnymi im wyrażeniami $p,q,r$ (prawo podwójnego przeczenia) dostajemy:

$$\alpha(p,q,r)$$

$$\Updownarrow$$

$$\neg\left[(\neg p\land \neg q\land r)\lor(\neg p\land q\land \neg r)\lor(p\land\neg q\land r)\right]$$

$$\Updownarrow$$

$$\neg(\neg p\land \neg q\land r)\land\neg(\neg p\land q\land \neg r)\land\neg(p\land\neg q\land r)$$

$$\Updownarrow$$

$$(\neg\neg p\lor \neg\neg q\lor \neg r)\land(\neg\neg p\lor \neg q\lor \neg\neg r)\land(\neg p\lor\neg\neg q\lor \neg r)$$

$$\Updownarrow$$

$$( p\lor q\lor \neg r)\land( p\lor \neg q\lor r)\land(\neg p\lor q\lor \neg r).$$

Ostatnia formuła jest już w postaci koniunkcyjno-alternatywnej. $\Box$

Rachunek zdań możemy stosować przy rozwiązywaniu równań i nierówności.

Przykład 1. Rozwiązać równanie

$${x+1\over x-1}=1$$

w dziedzinie liczb rzeczywistych.

Niech $x$ oznacza dowolną liczbę rzeczywistą. Wówczas równość ${x+1\over x-1}=1$ staje się zdaniem (prawdziwym lub nie) i dostajemy następujący ciąg zdań równoważnych:

$${x+1\over x-1}=1$$

$$\Updownarrow$$

$$x+1=x-1\land x-1\neq 0$$

$$\Updownarrow$$

$$1=-1\land x-1\neq 0$$

Ostatnie zdanie jest fałszywe dla każdej liczby $x$, zatem również wyjściowe zdanie jest fałszywe dla każdej liczby $x$. Znaczy to, ze równanie nie ma rozwiązań w liczbach rzeczywistych.

Przykład 2. Rozwiązać nierówność $(x+1)(x+2)>0$ w dziedzinie liczb rzeczywistych.

Niech $x$ oznacza dowolną liczbę rzeczywistą. Wtedy korzystając z własności działań na liczbach rzeczywistych dostajemy następujący ciąg zdań równoważnych:

$$(x+1)(x+2)>0$$

$$\Updownarrow$$

$$(x+1>0\land x+2>0)\lor(x+1<0\land x+2<0)$$

$$\Updownarrow$$

$$(x>-1\land x>-2)\lor(x<-1\land x<-2)$$

$$\Updownarrow$$

$$x>-1\lor x<-2$$

Skorzystaliśmy tu z faktu, że iloczyn dwóch liczb rzeczywistych jest dodatni wtedy i tylko wtedy, gdy bądź obie są ujemne, bądź obie są dodatnie. Widzimy więc, że wyjściowa nierówność jest prawdziwa dokładnie dla tych liczb rzeczywistych $x$, które są większe od $-1$ lub mniejsze od $-2$.

Przykład 3. Rozwiązać nierówność $(x+1)(x-2)<0$ w dziedzinie liczb rzeczywistych.

Niech $x$ będzie dowolną liczbą rzeczywistą. Korzystając z faktu, że iloczyn dwóch liczb rzeczywistych jest ujemny wtedy i tylko wtedy, gdy jedna z nich jest dodatnia, a druga ujemna, mamy:

$$(x+1)(x-2)<0$$

$$\Updownarrow$$

$$(x+1<0\land x-2>0)\lor(x+1>0\land x-2<0)$$

$$\Updownarrow$$

$$(x<-1\land x>2)\lor(x>-1\land x<2)$$

Jednak $x<-1\land x>2$ jest zdaniem fałszywym, więc korzystając z tautologii $0\lor p\Leftrightarrow p$ dostajemy, że powyższe zdanie jest równoważne zdaniu $x>-1\land x<2$, co skrótowo zapisujemy jako warunek $-1<x<2$. Zatem liczby spełniające wyjściowe równanie to dokładnie te liczby $x$, dla których $-1<x<2$.

Przykład 4. Rozwiązać w dziedzinie liczb rzeczywistych równanie

$$\vert x+1\vert-1=\vert x-1\vert.$$

Sposób 1 (metoda przekształceń równoważnych). Niech $x$ będzie dowolną liczbą rzeczywistą. Korzystając z tego, że $\vert x\vert=x$, gdy $x\geq 0$, oraz $\vert x\vert=-x$, gdy $x<0$, wnioskujemy, że nasze równanie jest równoważne następującej alternatywie:

$$(x<-1\land -(x+1)-1=-(x-1))\lor(-1\leq x<1\land x+1-1=-(x-1))\lor(x\geq 1\land x+1-1=x-1)$$

Pierwszy i trzeci człon tej alternatywy jest fałszywy dla dowolnego $x$, dostajemy więc następujący ciąg zdań równoważnych:

$$\vert x+1\vert-1=\vert x-1\vert$$

$$\Updownarrow$$

$$-1\leq x<1\land x+1-1=-(x-1)$$

$$\Updownarrow$$

$$-1\leq x<1\land x={1\over 2}$$

$$\Updownarrow$$

$$x={1\over 2}$$

Metoda przekształceń równoważnych bywa kłopotliwa. Zamiast niej można zastosować metodę implikacji, opisaną niżej.

Sposób 2 (metoda implikacji). W tej metodzie w ciągu przekształcanych zdań niekiedy zdanie $B$ następujące po zdaniu $A$ nie jest równoważne zdaniu $A$, lecz jedynie z niego wynika, tzn. implikacja $A\Rightarrow B$ jest prawdziwa. Fakt ten zapisujemy stosując skrót $\Downarrow$.

Niech więc $x$ będzie dowolną liczbą rzeczywistą. Będziemy korzystali z tego, że $a=b\Rightarrow a^2=b^2$ oraz że $\vert a\vert^2=a^2$. Mamy następujący ciąg zdań.

$$\vert x+1\vert-1=\vert x-1\vert$$

$$\Downarrow$$

$$(x+1)^2+1-2\vert x+1\vert=x^2+1-2x$$

$$\Updownarrow$$

$$4x+1=2\vert x+1\vert$$

$$\Downarrow$$

$$16x^2+8x+1=4x^2+8x+4$$

$$\Updownarrow$$

$$4x^2=1$$

$$\Updownarrow$$

$$x={1\over 2}\lor x=-{1\over 2}$$

W tym ciągu przekształceń nie możemy zastąpić $\Downarrow$ przez $\Updownarrow$, gdyż implikacja odwrotna do $a=b\Rightarrow a^2=b^2$ nie zawsze zachodzi. Powyższy ciąg przekształceń informuje nas jednak, że jeśli $x$ jest rozwiązaniem wyjściowego równania, to $x=\frac{1}{2}$ lub $x=-\frac{1}{2}$ (na mocy przechodniości implikacji). Inaczej mówiąc, dla wszystkich liczb rzeczywistych $x$ prawdziwa jest implikacja

$$(*)\ \ \vert x+1\vert-1=\vert x-1\vert\Rightarrow x=\frac{1}{2}\lor x=-\frac{1}{2}.$$

Znaczy to, że każde rozwiązanie $x$ równania $\vert x+1\vert-1=\vert x-1\vert$ musi spełniać następnik tej implikacji, tzn. $x=\frac{1}{2}\lor x=-\frac{1}{2}$. Nie wynika stąd jeszcze, że obie liczby $\frac{1}{2},-\frac{1}{2}$ spełniają wyjściowe równanie. Wymaga to sprawdzenia. W naszym przypadku liczba $\frac{1}{2}$ jest rozwiązaniem wyjściowego równania, zaś liczba $-\frac{1}{2}$ nie. Nie przeczy to jednak prawdziwości implikacji $(*)$ dla $x=-\frac{1}{2}$, gdyż wtedy jej poprzednik jest fałszywy.