1. Strona główna
  2. Wstęp do Matematyki
  3. 03. Rachunek zdań - gramatyka i przykłady

03. Rachunek zdań - gramatyka i przykłady

 

1. Rachunek zdań

Jedną z najprostszych logik jest rachunek zdań. O ile w systemie Euklidesa można mówić o punktach, prostych i okręgach, a w teorii zbiorów o zbiorach, o tyle w rachunku zdań atomowym pojęciem jest zdanie. Zatem w rachunku zdań można

  1. wyrazić pewne ogólne własności zdań,
  2. z prostszych zdań tworzyć bardziej złożone.

W języku rachunku zdań symbole $p,q,\ldots$ oznaczają zdania atomowe, w których wewnętrzną strukturę nie chcemy dalej wnikać. Zdefiniujemy teraz w sposób precyzyjny gramatykę rachunku zdań, czyli zasady tworzenia nowych formuł rachunku zdań z już istniejących.

  1. $p,q,\ldots$ są formułami rachunku zdań,
  2. jeśli $\phi,\psi$ są formułami rachunku zdań, to $(\phi\wedge \psi)$, $(\phi\vee \psi)$,$(\phi\to\psi)$ oraz $(\neg \phi)$ są formułami rachunku zdań.

2. Przykłady użycia rachunku zdań.

Na pierwszy rzut oka może się wydawać, że jest język rachunku zdań jest bardzo ograniczony. Okazuje się jednak, że w rachunku zdań da się wysłowić szereg fundamentalnych właściwości własności otaczającej nas rzeczywistości. W szczególności, można w nim wyrazić wewnątrzną strukturę urządzeń elektronicznych, w tym mikroprocesorów. Na potrzeby tych notatek skoncentrujemy się na prostych przykładach, które jednak dość łatwo się rozszerzają do całkiem nietrywialnych zagadnień.

2.1. Sudoku

W pierwszej kolejności pokażemy, jak w języku rachunku zdań wysłowić istnienie rozwiązań w Sudoku.

sudoku44

Figure 1. Przykładowy problem Sudoku do zakodownia w rachunku zdań.

Rozwiązanie tego problemu kodujemy w następujący sposób. Zmienna $p_{i,j,n}$ oznacza, ze na pozycji $(i,j)$ stoi liczba $n$. Warunek

(1)
\[\bigwedge_{i\in\{1,2,3,4\}}\ \bigwedge_{j\in\{1,2,3,4\}}\ \bigvee_{n\in\{1,2,3,4\}} p_{i,j,n} \]

oznacza zatem, że na każdej pozycji $(i,j)$ stoi jedna z liczb z zakresu od $1$ do $4$.

Następnie chcemy wykluczyć, że dwie różne liczby $n$, $m$ stoją na tym samym polu

(2)
\[\bigwedge_{i\in\{1,2,3,4\}}\ \bigwedge_{j\in\{1,2,3,4\}}\ \bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{m\in\{1,2,3,4\},m\neq n}\ p_{i,j,n}\to \neg p_{i,j,m} \]

Następnie chcemy zapewnić spełnienie warunków zwycięstwa w Sudoku. Po pierwsze, w każdym wierszu muszą stać wszystkie liczby od $1$ do $4$.

(3)
\[\bigwedge_{i\in\{1,2,3,4\}}\ \bigwedge_{n\in\{1,2,3,4\}}\ \bigvee_{j\in\{1,2,3,4\}}\ p_{i,j,n}. \]

To samo odnosi się do kolumn

(4)
\[\bigwedge_{j\in\{1,2,3,4\}}\ \bigwedge_{n\in\{1,2,3,4\}}\ \bigvee_{i\in\{1,2,3,4\}}\ p_{i,j,n}. \]

Kolejne warunki kodują żadanie, żeby w kwadratach pojawiały się także cztery liczby. Zacznijmy od górnego lewego rogu:

(5)
\[\bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{i\in\{1,2\}}\ \bigvee_{j\in\{1,2\}}\ p_{i,j,n}. \]

Następnie analogicznie zajmujemy się prawym górnym, lewym dolnym i prawym dolnym rogiem.

(6)
\[\bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{i\in\{3,4\}}\ \bigvee_{j\in\{1,2\}}\ p_{i,j,n}. \]
(7)
\[\bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{i\in\{1,2\}}\ \bigvee_{j\in\{3,4\}}\ p_{i,j,n}. \]
(8)
\[\bigwedge_{n\in\{1,2,3,4\}}\ \bigwedge_{i\in\{3,4\}}\ \bigvee_{j\in\{3,4\}}\ p_{i,j,n}. \]

Na koniec żadamy, żeby był spełniony warunek początkowy

(9)
\[p_{2,2,2}\wedge p_{1,3,4}\wedge p_{2,4,3}\wedge p_{3,1,2}\wedge p_{4,2,4}\wedge p_{4,4,1} \]

Rachunek zdań ma tą wyróżniające cechę, że zdania w tym języku podlegają automatycznej analizie przez komputer, który umie stwierdzić, czy da się tak dobrać $p_{i,j,n}$, żeby wszystkie powyższe warunki były spełnione. My skorzystamy z solwera on-line SatRennesPa.

sudoku44_sol

Figure 2. Przykładowe rozwiązanie problemu w terminach rachunku zdań.

Po zaimplementowaniu tych wskazówek n.p. w programie Paint dodstajemy

sudoku44_sol_red

Figure 3. Przykładowy problem Sudoku do zakodownia w rachunku zdań.

2.2. Owca, wilk i kapusta

Odnośnie powyższej gry można sobie postawić co najmniej dwa interesujące pytania. Mianowicie, jak bezpiecznie przewieźć cały dobytek na drugą stronę oraz ile ruchów jest niezbędne, żeby operacja przewożenia się udała.

O ile na piewsze pytanie można uzyskać odpowiedź metodą eksperymentów, o tyle na drugie pytanie odpowiedź można otrzymać programując nasze zadanie w terminach rachunku zdań. Przekonamy się, że 7 ruchów wystarcza w tej grze, natomiast 6 jest jeszcze nie wystarczające.

Przez $w_{0},\ldots,w_{7}$ będziemy oznaczać, że wilk jest po prawej stronie w chwili $0$, w chwili $1$ i tak dalej. Podobnie przez $o_{0},\ldots,o_{7}$, $k_{0},\ldots,k_{7}$ i $l_{0},\ldots,l_{7}$ oznaczamy, że owca, kapusta i łodka są po prawej stronie w chwili od $0$ do $7$.

Przyjrzyjmy się liście wymagań. Po pierwsze, jeśli w chwili $i$ owca i wilk znajdują sie po prawej stronie, to także powinna być tam łódka.

(10)
\[\bigwedge_{i\in\{0,\ldots 7\}}\ (w_i \wedge o_i)\to l_i \]

Analgicznie

(11)
\[\bigwedge_{i\in\{0,\ldots 7\}}\ (\neg w_i \wedge \neg o_i)\to \neg l_i \]

Podobne ograniczenia dotyczą kapusty i owcy

(12)
\[\bigwedge_{i\in\{0,\ldots 7\}}\ (o_i \wedge k_i)\to l_i \]

Analgicznie

(13)
\[\bigwedge_{i\in\{0,\ldots 7\}}\ (\neg o_i \wedge \neg k_i)\to \neg l_i \]

Warunek początkowy

(14)
\[o_0\wedge k_0\wedge w_0\wedge l_0 \]

oznacza, że na początku wszyscy znajdują się po prawej stronie, a warunek

(15)
\[o_7\wedge k_7\wedge w_7\wedge l_7 \]

oznacza, że na końcu wszyscy znajdują się po prawej stronie.

Kolejne dwa warunki zapobiegają przedostawaniu się wpław:

(16)
\[\bigwedge_{i\in\{0,\ldots 6\}}\bigwedge_{r\in \{o,w,k\}} (l_i \wedge \neg r_i)\to \neg r_{i+1}. \]
(17)
\[\bigwedge_{i\in\{0,\ldots 6\}}\bigwedge_{r\in \{o,w,k\}} (\neg l_i \wedge r_i)\to r_{i+1}. \]

oznacza, że na początku wszyscy znajdują się po prawej stronie, a warunek

(18)
\[o_7\wedge k_7\wedge w_7\wedge l_7 \]

Chcemy też unikać przepływania w grupach (rozbijamy ten warunek na 4 warianty):

(19)
\[\bigwedge_{i\in\{0,\ldots 6\}} \bigwedge_{r^1\in \{o,w,k\}}\bigwedge_{r^2\in \{o,w,k\}, r^2\neq r^1} (r^1_i \wedge \neg r^1_{i+1}) \to (r^2_i \wedge r^2_{i+1}) \]
(20)
\[\bigwedge_{i\in\{0,\ldots 6\}} \bigwedge_{r^1\in \{o,w,k\}}\bigwedge_{r^2\in \{o,w,k\}, r^2\neq r^1} (\neg r^1_i \wedge r^1_{i+1}) \to (r^2_i \wedge r^2_{i+1}) \]
(21)
\[\bigwedge_{i\in\{0,\ldots 6\}} \bigwedge_{r^1\in \{o,w,k\}}\bigwedge_{r^2\in \{o,w,k\}, r^2\neq r^1} (r^2_i \wedge \neg r^2_{i+1}) \to (r^1_i \wedge r^1_{i+1}) \]
(22)
\[\bigwedge_{i\in\{0,\ldots 6\}} \bigwedge_{r^1\in \{o,w,k\}}\bigwedge_{r^2\in \{o,w,k\}, r^2\neq r^1} (\neg r^2_i \wedge r^2_{i+1}) \to (r^1_i \wedge r^1_{i+1}) \]

Chcemy ponadto, żeby łódka poruszała się w każdej rundzie

(23)
\[\bigwedge_{i\in\{0,\ldots 6\}} (l_i \to \neg l_{i+1}) \wedge (\neg l_i \to l_{i+1}) \]

Przy pomocy solwera znajdujemy rozwiązanie

wilk

Figure 4. Instrukcje, jak tranportować dobytek na drugi brzeg (w 7 rundach).

Ograniczenie się do 6 rund powoduje, że problem nie ma rozwiązania- solwer nas o tym informuje (w gruncie rzeczy w tle jest produkowany dowód, że takie rozwiązanie nie istnieje).

Created with Madoko.net.