Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 24

Logika Boole’a jest systemem matematycznym zbudowanym wokół dwóch wartości TRUE i FALSE. Choć oryginalnie wynaleziony jako koncepcja czysto matematyczna, system ten jest obecnie postrzegany jako fundament projektowania elektroniki cyfrowej i komputerów. Wartości TRUE i FALSE nazywane są wartościami boolowskimi (logicznymi) i często są reprezentowane jako numeryczne wartości 1 i 0. Wartości boolowskich używamy w sytuacjach, gdy dostępne są tylko dwie możliwości, takich jak wysoki lub niski poziom napięcia, stwierdzenie, które może być prawdziwe lub fałszywe lub pytanie, na które odpowiedź musi brzmieć tak lub nie.

Przekształcanie wartości boolowskich odbywa się przez operacje boolowskie (logiczne). Najprostszą operacją boolowską jest negacja, czyli operacja NOT (nie), oznaczana symbolem ¬. Negacją wartości boolowskiej jest przeciwna wartość. Tym samym ¬0 = 1 oraz ¬1 = 0. Koniunkcję, czyli operację AND oznaczamy symbolem ∧. Koniunkcja dwóch wartości boolowskich jest równa 1 (prawda), jeśli obie te wartości mają wartość 1. Alternatywę lub operację OR oznaczamy symbolem ∨. Alternatywa dwóch wartości boolowskich ma wartość 1, jeśli którakolwiek z tych wartości jest równa 1. Informacje te można podsumować w następujący sposób:

0 ∧ 0 = 0	0 ∨ 0 = 0	¬0 = 1
0 ∧ 1 = 0	0 ∨ 1 = 1	¬1 = 0
1 ∧ 0 = 0	1 ∨ 0 = 1
1 ∧ 1 = 1	1 ∨ 1 = 1

Operacje boolowskie wykorzystywane są do łączenia prostych stwierdzeń w bardziej złożone wyrażenia boolowskie, podobnie jak używamy operacji arytmetycznych + i × do konstruowania złożonych wyrażeń arytmetycznych. Przykładowo, jeśli P jest wartością boolowską reprezentującą prawdziwość stwierdzenia „Słońce świeci”, a Q reprezentuje prawdziwość stwierdzenia „dziś jest poniedziałek”, to możemy napisać P ∧ Q, aby przedstawić prawdziwość stwierdzenia „Słońce świeci i dziś jest poniedziałek”; analogiczna zależność zachodzi dla P ∨ Q, przy czym „i” zastępujemy przez „lub”. Wartości P i Q nazywamy operandami operacji.

Od czasu do czasu będzie pojawiać się kilka innych operacji boolowskich. Alternatywa wykluczająca (rozłączna, exclusive or), inaczej XOR, oznaczana jest symbolem ⊕ i ma wartość 1, jeśli albo jeden, albo drugi operand ma wartość 1, ale nie obydwa jednocześnie. Operacja równoważności, zapisywana za pomocą symbolu ↔, ma wartość 1, gdy obydwa operandy mają tę samą wartość. Na koniec operacja implikacji, opisywana symbolem →, ma wartość 0, jeśli jej pierwszy (lewy) operand ma wartość 1, a drugi 0; w pozostałych przypadkach → ma wartość 1. Podsumowujemy te informacje w następujący sposób.

0 ⊕ 0 = 0	0 ↔ 0 = 1	0 → 0 = 1
0 ⊕ 1 = 1	0 ↔ 1 = 0	0 → 1 = 1
1 ⊕ 0 = 1	1 ↔ 0 = 0	1 → 0 = 0
1 ⊕ 1 = 0	1 ↔ 1 = 1	1 → 1 = 1

Między tymi operacjami zachodzą różne zależności. W istocie możemy wyrazić wszystkie operacje boolowskie jedynie przez operacje AND oraz NOT, co pokazują poniższe tożsamości. Dwa wyrażenia w każdym wierszu są równoważne. Każdy wiersz prezentuje w lewej kolumnie zapis operacji przy użyciu pojęć omówionych wyżej, zaś w prawej równoważne operacje wykorzystujące AND oraz NOT.

P ∨ Q	¬(¬P ∧ ¬Q)
P → Q	¬P ∨ Q
P ↔ Q	(P → Q) ∧ (Q → P)
P ⊕ Q	¬(P ↔ Q)

Prawo rozdzielności koniunkcji i alternatywy przydaje się przy przekształcaniu wyrażeń boolowskich. Jest ono podobne do prawa rozdzielności mnożenia względem dodawania, które głosi, że a × (b+c) = (a × b)+(a × c). Wersja boolowska występuje w dwóch postaciach:

 P ∧ (Q ∨ R) jest równe (P ∧ Q) ∨ (P ∧ R), oraz

 P ∨ (Q ∧ R) jest równe (P ∨ Q) ∧ (P ∨ R).