Matryca boolowska

Matryca boolowska


W poprzednim rozdziale zdefiniowaliśmy klasyczny rachunek zdań jako teorię aksjomatyczną. Jeśli pozwolimy sobie na używanie skończonych zbiorów i funkcji, możemy równoważnie zdefiniować klasyczny rachunek zdań za pomocą tzw. matrycy boolowskiej.
Definicja 4.1
Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy \( \mathbb{B}=\{0,1\} \) w którym 1 jest wyróżnioną wartością prawdy, wraz z dwoma funkcjami odpowiadającymi za interpretacje spójników \( \Rightarrow \) oraz \( \neg \) zdefiniowanymi następująco


\( \Rightarrow \) 0 1
0 1 1
1 0 1
    
\( \mathrm {p} \) \( \neg p \)
0 1
1 0

\( \quad \mbox{(4.1)} \)

Definicja 4.2

Wartościowaniem nazywamy funkcję, która przypisuje zmiennym zdaniowym elementy zbioru \( \mathbb{B} \). Wartościowanie zmiennych można rozszerzyć na wartościowanie formuł interpretując spójniki \( \Rightarrow \) oraz \( \neg \) jako funkcje zgodnie z tabelami 4.1.

Przykład 4.3

Niech \( {v} \) będzie wartościowaniem zmiennych takim, że \( v(p)=0,v(q)=1, v(r)=0 \). Wtedy

  • formuła \( q \Rightarrow p \) jest wartościowana na 0 (będziemy to zapisywać jako \( v(q \Rightarrow p)=0 \)),
  • formuła \( r \Rightarrow (q \Rightarrow p) \) jest wartościowana na 1 (czyli \( v(r \Rightarrow (q \Rightarrow p))=1 \)),
  • formuła \( \neg p \Rightarrow r \) jest wartościowana na 0 (czyli \( v(\neg p \Rightarrow r)=0 \)).

Ćwiczenie 4.1

Przy wartościowaniu \( v \) z przykładu 4.3 jakie wartości przyjmują następujące formuły

  1. \( p \Rightarrow (q \Rightarrow r) \),
  2. \( p \Rightarrow (p \Rightarrow q) \),
  3. \( \neg \neg q \Rightarrow p \),
  4. \( (\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q) \).

Ćwiczenie 4.2

     1. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były wartościowane na 0

(a) \( p \Rightarrow (q \Rightarrow r) \)
(b) \( (\neg p \Rightarrow q) \)
(c) \( (p\Rightarrow q) \Rightarrow q \)

     2. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były wartościowane na 1

(a) \( \neg (p \Rightarrow q) \)
(b) \( \neg (\neg p \Rightarrow \neg q) \)
(c) \( (\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q) \)

Twierdzenie o pełności

Zauważmy, że istnieją formuły, które dla każdego wartościowania zmiennych zdaniowych, zawsze przyjmują wartość 1 (np. \( p \Rightarrow p \)). Takie formuły będziemy nazywać tautologiami.

Ćwiczenie 4.3
Sprawdź czy poniższe formuły są tautologiami

  1. \( (\phi \Rightarrow (\psi \Rightarrow \phi)) \),
  2. \( (\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow ((\phi \Rightarrow \nu \Rightarrow (\phi \Rightarrow \nu) ) \),
  3. \( (\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi \),
  4. \( ((\phi \Rightarrow q) \Rightarrow p) \Rightarrow p \).



Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania odpowiadają aksjomatom klasycznego rachunku zdań 3.1. Okazuje się że istnieje ścisły związek pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik Emila Posta

Twierdzenie 4.4

Post 1921 Formuła jest twierdzeniem klasycznego rachunku zdań wtedy i tylko wtedy kiedy jest tautologią.

Dowód powyższego twierdzenia jest przedstawiony na wykładzie Logika dla informatyków Dzięki powyższemu twierdzeniu możemy w miarę łatwo stwierdzać, czy dana formuła jest twierdzeniem klasycznego rachunku zdań, sprawdzając, czy jest tautologią, co wymaga rozważenia jedynie skończonej (chociaż często niemałej) liczby wartościowań. Co więcej, mamy też możliwość dowodzenia, że jakaś formuła nie jest twierdzeniem klasycznego rachunku zdań. Uzasadnienie, że nie da się jakiejś formuły udowonić z aksjomatów poprzez stosowanie reguły MP wydaje się zadaniem trudnym, znacznie łatwiej jest poszukać wartościowania, które wartościuje formułę na 0 (znowu wystarczy sprawdzić jedynie skończenie wiele wartościowań).

Ćwiczenie 4.4
Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.



Inne spójniki

Do tej pory jedynymi rozważanymi spójnikami była implikacja i negacja. W analogiczny sposób do 4.1 możemy wprowadzać kolejne spójniki. Często używane spójniki to koniunkcja (spójnik i) oznaczana przez \( \wedge \) oraz alternatywa (spójnik lub) oznaczana przez \( \vee \), które będziemy interpretować w następujący sposób:


\( \wedge \) 0 1
 0   0   0 
 1   0   1 
    
\( \vee \) 0 1
 0   0   1 
 1   1   1 

\( \quad \mbox{(4.2)} \)



Zgodnie z intuicją koniunkcja \( \phi \wedge\psi \) jest wartościowana na 1 wtedy i tylko wtedy, gdy zarówno \( {\phi} \) jak i \( {\psi} \) są wartościowane na 1. Alternatywa \( \phi \vee \psi \) jest wartościowana na 1, jeśli przynajmniej jedna z formuł \( \phi, \psi \) jest wartościowana na 1.

Definicja 4.5

Formuły \( {\phi} \) oraz \( {\psi} \) są równoważne (oznaczamy ten fakt przez \( \phi \equiv \psi \) wtedy i tylko wtedy, gdy dla każdego wartościowania formuła \( {\phi} \) przyjmuje tą samą wartość co formuła \( {\psi} \).

Ćwiczenie 4.5

Udowodnij, że następujące formuły są równoważne

  1. \( \phi \vee \psi \equiv \neg \phi \Rightarrow \psi \)
  2. \( \phi \wedge \psi \equiv \neg (\phi \Rightarrow \neg \psi) \)

Z powyższego zadania wynika, że każdą formułę w której występują spójniki \( \wedge \) lub \( \vee \) można zastąpić równoważną formułą, w której jedynymi spójnikami są \( \Rightarrow \) oraz \( \neg \). Tak naprawdę więc nowe spójniki nie wprowadzają nic nowego poza użytecznymi skrótami w zapisywaniu formuł. Aby się oswoić z własnościami spójników, prześledzimy szereg ich praw.

Ćwiczenie 4.6

Udowodnij następujące równoważności

  1. \( \neg \neg p \equiv p \),
  2. \( p\Rightarrow q \equiv \neg p \vee q \),
  3. \( p \Rightarrow (q \Rightarrow r) \equiv (p \wedge q) \Rightarrow r \),
  4. \( \neg( p \wedge q) \equiv \neg p \vee \neg q \),
  5. \( \neg( p \vee q) \equiv \neg p \wedge \neg q \),
  6. \( p \wedge (q \vee r) \equiv (p \wedge q) \vee (p\wedge r) \),
  7. \( p \vee (q \wedge r) \equiv (p \vee q) \wedge (p\vee r) \),
  8. \( (p \Rightarrow q) \Rightarrow (\neg p \Rightarrow \neg q) \).

Ćwiczenie 4.7

Sprawdź które z następujących formuł są tautologiami

  1. \( ( (p \vee r)\wedge( q \vee \neg r) )\Rightarrow (p \vee q) \),
  2. \( (p \vee q) \Rightarrow ( (p \vee r)\wedge( q \vee \neg r)) \),
  3. \( ( (p \wedge r)\vee( q \wedge \neg r) )\Rightarrow(p \wedge q) \),
  4. \( (p \wedge q) \Rightarrow ( (p \wedge r)\vee( q \wedge \neg r)) \).

Binarne spójniki logiczne interpretowaliśmy jako funkcje z \( \mathbb{B}\times \mathbb{B} arrow \mathbb{B} \). Nie trudno przekonać się, że takich funkcji jest dokładnie 16. Dla każdej takiej funkcji możemy dodać spójnik, który będzie interpretowany dokładnie jako ta funkcja. W poniższej tabeli zamieszczamy wszystkie takie funkcje wraz ze zwyczajowymi oznaczeniami odpowiadających im spójników.

Definicja 4.6

W poniższej tabeli przedstawiamy wszystkie spójniki binarne.


Numer
funkcji
\( p=0 \)
\( q=0 \)
\( p=0 \)
\( {q=1} \)
\( p=1 \)
\( q=0 \)
\( p=1 \)
\( {q=1} \)
   
0 0 0 0 0   \( F \)
1 0 0 0 1   \( \wedge \)
2 0 0 1 0   \( \neg (p \Rightarrow q) \)
3 0 0 1 1   \( \mathrm{p} \)
4 0 1 0 0   \( \neg (q \Rightarrow p) \)
5 0 1 0 1   \( \mathrm{q} \)
6 0 1 1 0   \( XOR \)
7 0 1 1 1   \( \vee \)
8 1 0 0 0   \( NOR \)
9 1 0 0 1   \( \Leftrightarrow \)
10 1 0 1 0   \( \neg q \)
11 1 0 1 1   \( q \Rightarrow p \)
12 1 1 0 0   \( \neg p \)
13 1 1 0 1   \( p \Rightarrow q \)
14 1 1 1 0   \( NAND \)
15 1 1 1 1   \( T \)

Spójnik binarny \( \circ \) będziemy nazywać przemiennym, jeśli zachodzi następująca równoważność

\( p \circ q \equiv q \circ p \quad \mbox{(4.3)} \)

Ćwiczenie 4.8

Sprawdź następujące równoważności

  1. \( x NAND y \equiv \neg (x \wedge y) \)
  2. \( x NOR y \equiv \neg (x \vee y) \)
  3. \( x XOR y \equiv \neg (x \Leftrightarrow y) \)

Ćwiczenie 4.9
Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.


Ćwiczenie 4.10

Udowodnij, że następujące spójniki są łączne

  1. \( \vee \)
  2. \( \wedge \)
  3. \( \Leftrightarrow \)
  4. \( XOR \)

Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik \( k \)-argumetowy powinien odpowiadać funkcji \( \mathbb{B}^k arrow \mathbb{B} \).

Przykład 4.7

W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego


\( \mathrm {p} \) \( \mathrm {q} \) \( \mathrm {r} \) \( \circ (p, q, r) \)
 0   0   0   0 
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

Uwaga 4.1
Różnych spójników \( k \)-argumentowych jest dokładnie \( 2^{2^k} \).