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
- wyrazić pewne ogólne własności zdań,
- z prostszych zdań tworzyć bardziej złożone.
W języku rachunku zdań symbole 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.
są formułami rachunku zdań,
- jeśli
są formułami rachunku zdań, to
,
,
oraz
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.
Rozwiązanie tego problemu kodujemy w następujący sposób. Zmienna oznacza, ze na pozycji
stoi liczba
. Warunek
oznacza zatem, że na każdej pozycji stoi jedna z liczb z zakresu od
do
.
Następnie chcemy wykluczyć, że dwie różne liczby ,
stoją na tym samym polu
Następnie chcemy zapewnić spełnienie warunków zwycięstwa w Sudoku. Po pierwsze, w każdym wierszu muszą stać wszystkie liczby od do
.
To samo odnosi się do kolumn
Kolejne warunki kodują żadanie, żeby w kwadratach pojawiały się także cztery liczby. Zacznijmy od górnego lewego rogu:
Następnie analogicznie zajmujemy się prawym górnym, lewym dolnym i prawym dolnym rogiem.
Na koniec żadamy, żeby był spełniony warunek początkowy
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ć , żeby wszystkie powyższe warunki były spełnione. My skorzystamy z solwera on-line SatRennesPa.
Po zaimplementowaniu tych wskazówek n.p. w programie Paint dodstajemy
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 będziemy oznaczać, że wilk jest po prawej stronie w chwili
, w chwili
i tak dalej. Podobnie przez
,
i
oznaczamy, że owca, kapusta i łodka są po prawej stronie w chwili od
do
.
Przyjrzyjmy się liście wymagań. Po pierwsze, jeśli w chwili owca i wilk znajdują sie po prawej stronie, to także powinna być tam łódka.
Analgicznie
Podobne ograniczenia dotyczą kapusty i owcy
Analgicznie
Warunek początkowy
oznacza, że na początku wszyscy znajdują się po prawej stronie, a warunek
oznacza, że na końcu wszyscy znajdują się po prawej stronie.
Kolejne dwa warunki zapobiegają przedostawaniu się wpław:
oznacza, że na początku wszyscy znajdują się po prawej stronie, a warunek
Chcemy też unikać przepływania w grupach (rozbijamy ten warunek na 4 warianty):
Chcemy ponadto, żeby łódka poruszała się w każdej rundzie
Przy pomocy solwera znajdujemy rozwiązanie
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).