Zakład Logiki i Epistemologii
Instytut Filozofii i Socjologii UKW
w Bydgoszczy
ul. Ogińskiego 16
Wykład 6
Klasyczny rachunek zdań (1)
Ujęcie semantyczne
Jest to ujęcie tzw. zero-jedynkowe.
Metoda ta pozwala w skończonej ilości kroków rozstrzygnąć o każdym wyra-
żeniu tego rachunku, czy jest ono prawdziwe. Tzn. pozwala ona rozstrzygnąć czy wszystkie zdania dające się uzyskać z tego wyrażenia przez podstawienie dowolnych zdań za zmienne są prawdziwe.
Nazwa tej metody bierze się stąd, że symbol "1" stosuje się dla oznaczenia zdania prawdziwego, zaś "0" - zdania fałszywego.
Pojecie prawdy jest zdefiniowane w metodologii nauk dedukcyjnych. Ta definicja zostanie przedstawiona później.
Metodę 0-1 nazywa się również metodą matrycową, gdyż posługujemy się w niej tabelkami.
Uwaga
Ogólnie, pojęcie matrycy jest pojęciem syntaktycznym. Matrycowo charaktery-zuje się wiele systemów logiki np. wielowartościowe, intuicjonistyczna). Ma-tryce pozwalają ustalić tylko tezy. Teza jest pojęciem syntaktycznym.
W przypadku logiki klasycznej matryca dla tej logiki jest tożsama z charakterystyką prawdziwościową stałych logicznych.
Próba określenia prawa logiki
Wyrażenia, które nie są zmiennymi nazywamy stałymi.
Mamy stałe:
- logiczne
- pozalogiczne
Stałe logiczne występują w sformułowaniach twierdzeń logicznych. Stałe logiczne mogą być użyte w twierdzeniach różnych nauk, języku potocznym, o ile te zdania dotyczą dowolnych przedmiotów.
1
Stałe klasycznego rachunku zdań:
- funktory prawdziwościowe
- kwantyfikatory
- słowo "jest"
Stałymi logicznymi są wyrażenia dające się zdefiniować za pomocą stałych logicznych i zmiennych.
Precyzowanie sensu stałych logicznych należy do logiki formalnej. Użyciem stałych logicznych rządzą prawa logiki.
Stałe pozalogiczne
Należą do nich nazwy przedmiotów i własności badanych tylko przez nauki szczegółowe, różne od logiki. Również stałe występujące w języku potocznym dotyczącym tylko pewnego określonego rodzaju przedmiotów.
Ex. elektron, komórka, drzewo.
Określenie
Prawo logiki jest to prawdziwe wyrażenie zdaniowe zbudowane wyłącznie ze stałych logicznych i zmiennych oraz nawiasów.
Mówiąc inaczej, prawo logiki jest to
- wyrażenia zdaniowe
- zbudowane ze stałych i zmiennych
- prawdziwe
Ex. Prawami logiki są
Λx (x =x) zdanie
x = x forma zdaniowa
(w języku formalnym jest tylko jeden poprawny sposób zapisu) język = zbiór znaków + reguły używania znaków
składania znaków
reguły
uznawania znaków
Jest to szerokie rozumienie języka. W logice formalnej przez język rozumie się zwykle zbiór znaków i reguły składniowe
2
reguły uznawania
dedukcyjne
empiryczne
Reguły aksjomatyczne mówią, które ciągi znaków można uznać bezwarunko-wo (np. całość jest większa od części).
Reguły dedukcyjne mówią, które ciągi można uznać na podstawie innych cią-
gów już uznanych
w sensie logicznym = znaczenie nazwy
pojęcie
w sensie psychologicznym = przedstawienie nieoglądowe w sensie logicznym = znaczenie zdania
sąd
w sensie psychologicznym = fakt psychiczny zachodzenia jakiejś rzeczywistości
Zatem
- nazwa i pojęcie mają ten sam zakres.
- sąd w sensie logicznym jest prawdziwy
Ujęcie zero-jedynkowe rachunku zdań opiera się na dwóch założeniach: 1) zakłada się zasadę dwuwartościowości
2) zakłada się, że w systemie wszystkie funktory występujące w wyrażeniach tego rachunku są prawdziwościowe.
Przy tym zakłada się znajomość charakterystyki funktorów prawdziwościowych.
Przyjmuje się również – jako oczywiste – że te dwie wartości logiczne wyklu-czają się wzajemnie.
Będziemy charakteryzowali własności następujących związków: 10 związek logicznej sprzeczności dwóch zdań
20 związek współprawdziwości dwóch zdań – koniunkcja 30 związek niewspółfałszywości dwóch zdań – związek alternatywy zwykłej 40 związek warunkowy dwóch zdań – implikacja
50 związek zgodności dwóch zdań pod względem prawdy i fałszu –
rónoważność
60 związek niewspółprawdziwości dwóch zdań – dysjunkcja, kreska Sheffera 3
70 związek współfałszywości dwóch zdań – jednoczesne zaprzeczenie 80 związek niezgodności dwóch zdań pod względem prawdy i fałszu – alterna-tywa rozłączna
Słownik klasycznego rachunku zdań
Słownik ten obejmuje trzy grupy wyrażeń:
1) stałe logiczne: ∧, ∨, ∨!, →, ⇔, ~
2) zmienne zdaniowe: p, q, r, s, t, ...
3) nawiasy: (,)
Stałych logicznych 2-argumentowych jest 16, ale ze względu na to, że nie wszystkie mają swoje odpowiedniki w języku naturalnym oraz ze względu na częste użycie zwykle wymienia się przedstawia się 5 powyższych stałych. Sta-
łych 1-argumentowych jest 4. W języku naturalnym używa się tylko jedną z nich. Dla wygody rachunkowej przyjmuje się, że liczba zmiennych zdaniowych jest nieskończona.
Przykłady formuł "niegramatycznych" zapisanych w języku logiki: ~∧p, pq∧, r
→∨p.
Przykłady formuł poprawnie zbudowanych w języku logiki: p∨q, (p∨q)∨r, p→
p, ~(p∧~p).
Tylko niektóre formuły są prawami logiki. Dlatego jest wymagana procedura, która pozwala rozstrzygnąć, które formuły poprawnie zbudowane są prawami logiki. Praw logiki jest nieskończona ilość, ale w zasadzie tylko 18 ma prak-tyczne zastosowanie.
Słownik rachunku predykatów dodatkowo zawiera jeszcze następujące wyrażenia
1) kwantyfikatory: ∀, ∃
2) zmienne nazwowe jednostkowe: x, y, z, ....
3) zmienne predykatowe: P, Q, R, S, T, ....
Odczytywanie stałych
1) koniunkcja
p∧q czytamy: p i q, np. Kopernik był kobietą ∧ (2+2) = 4
2) Alternatywa
p∨q czytamy: p lub q, np. Einstein był fizykiem ∨ Kopernik był astrono-mem
3) Alternatywa rozłączna
p∨!q czytamy: p albo q, np. (2+2=5) ∨! Clinton kocha Hilary 4
p→q czytamy: jeżeli p, to q, np. (2+2=4) → L. Rywin jest producentem filmo-wym
5) równoważność
p⇔q czytamy: p jest równoważne q; p wtedy u tylko wtedy, gdy q 6) dysjunkcja
p|q czytamy: p albo q (L. Borkowski, Logika formalna, s. 65) nie jest tak, że zarazem p i q
7) łączna negacja (jednoczesne zaprzeczenie)
p↓q czytamy ani p ani q
7) negacja
~p czytamy: nieprawda, że p; nie jest tak, że p
Za zmienne zdaniowe podstawia się zdania w sensie logicznym. Ze względu na to, że spójniki występujące w języku naturalnym są wieloznaczne wprowadza się definicyjnie stałe logiczne.
Definicja stałych logicznych za pomocą tabelki
ϕ ψ ϕ ∧ ψ ϕ ∨ ψ ϕ ∨ ψ ϕ → ψ ϕ ⇔ ψ ϕ | ψ ϕ ↓ ψ
1 1
1
1
0
1
1
0
0
1 0
0
1
1
0
0
1
0
0 1
0
1
1
1
0
1
0
0 0
0
0
0
1
1
1
1
negacja
ϕ ~ϕ
1
0
0
1
Tabelka n-arg. funktora prawdziwościowego składa się z n kolumn argumentów i kolumny funktora. Tyle jest wierszy, ile jest możliwych n-wyrazowych układów, czyli 2n.
Tyle jest funktorów, ile jest funkcji
{1, 0} x {1, 0} {1, 0}
czyli 24.
F1 F2 F3 F4 F5 F6 F7 F8 F9 F10
F11
F12
F13
F14
F15
F16
1 1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0 1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1 0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0 0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
5
2-arg. funktor verum
F16
- 2-arg. funktor falsum
F3
- implikacja odwrotna
F11(p,q)
- p niezależnie od tego, czy q czy nie q
Tabelka dla 3-arg. funktora prawdziwościowego ma 256 funktorów
{1, 0} x {1, 0} x {1, 0} {1, 0}
czyli 28.
Natomiast wierszy jest 8.
Funktory prawdziwościowe wieloargumentowe można zdefiniować za pomocą funktorów prawdziwościowych 2-arg.
Ex.
Alternatywa zwykła 3-arg.
v(p,q,r) =df ((p v q) v r)
Okazuje się, że przy pomcy negacji, koniunkcji i alternatywy można zdefiniować każdy pozostały funktor prawdziwościowy n-argyumentowy p|q =df ~p ∧ ~q
p≡q =df )p ∧ q) ∨ (~p ∧ ~q)
p ∨ q =df ~p → q
vr(p) =df p → p
fl(p) =df ~( p → p)
as(p) =df p
~p =df p|p
p ∧ q =df (p|q) | (p|q)
~p =df p↓p
p ∧ q =df (p↓q) ↓ (p↓q)
Sam funktor dysjunkcji, jak również sam funktor negacji łącznej wystarczą do zdefiniowania wszystkich pozostałych stałych logicznych.
Znaczenie dysjunkcji Sheffera dla ontologii podkreślał Józef Bocheński.
Są to definicje normalne.
W takim przypadku definicja ta musi być zdaniem prawdziwym, tzn., musi zachodzić równoważność pomiędzy definiendum a definiensem.
Poniższe cztery funktory funktorami jedno-argumentowymi jak i dwu-argumentowymi. Funktorów 1-arg. jest tyle, ile jest układów symboli 0, 1.
6
- znak asercji, tworzy zdanie mające tę samą wartość logiczną, co wartość argumentu.
vr
- verum, tworzy zawsze zdanie prawdziwe
fl
- falsum, tworzy zawsze zdanie fałszywe
~
- negacja, tylko ten funktor występuje w języku potocznym p
as(p)
~p
vr(p)
fl(p)
1
1
0
1
0
0
0
1
1
0
Które wyrażenia są tezami rachunku zdań ?
Uwaga
Pojęcie tezy jest pojęciem syntaktycznym.
Pojęcie prawa jest pojęciem semantycznym
Tezami są te wyrażenia, które przy sprawdzaniu 0-1 otrzymują wyróżnioną wartość prawdziwości.
W jaki sposób dokonuje się sprawdzania wyrażeń rachunku zdań ?
1. Sprawdzanie rozwinięte
Należy wypisać 2n wierszy, gdzie n – liczba zmiennych zdaniowych różno-kształtnych.
Jeśli wyrażenie jest zawsze prawdziwe to jest tezą/prawem.
2. Metoda skrócona
Stosuje się najczęściej przy sprawdzaniu implikacji. Zakładamy, że poprzednik jest prawdziwy i badamy, czy następnik może być fałszywy. Można też zało-
żyć, następnik jest fałszywy i sprawdzamy, czy poprzednik może być prawdziwy.
Jeśli jest wykluczone, aby poprzednik był prawdziwy, a następnik fałszywy, to całe wyrażenie jest prawdziwe.
Ex.
~(p ∨ q) → (~p ∧~q)
1 0 0 0 0 10 0 10
1
Polega na założeniu fałszywości implikacji.
Implikacja jest fałszywa, gdy poprzednik jest prawdziwy, a następni fałszywy.
Po tym założeniu następuje wymuszanie wartości logicznych.
7
Jeśli osiągniemy sprzeczność, to wyrażenie jest prawem logiki.
Osiągnęliśmy sprzeczność, gdy z założenia następnik miał być fałszywy, oka-zało się jednak, że musi być prawdziwy.
Ex.
(p → q) → (~p → ~q)
0 1 1 0 10 0 0 1
Zatem wyrażenie nie jest tezą rachunku zdań. Nie osiągnięto sprzeczności.
Ex.
(p → q) → ((q → r) → (p → r))
1 1 1 0 1 1 0 0 1 0 0
0
Tą metodą można badać również schematy reguł rachunku zdań.
Wzajemne związki funktorów praedziwościowych
Każdy n-arg. funktor prawdziwościowy można określić za pomocą funktorów prawdziwościowych F1, ... , Fk. wttw, gdy prawdziwe jest następująca równoważność
F(p1, ... , pn) ≡ ϕ(p1, ... , pn , F1, ... , Fk ) jest wyrażeniem zapisanym wyłącznie za pomocą zmiennych zdaniowych p1, ...
, pn i funktorów prawdziwościowych F1, ... , Fk .
Wzajemne zastępowanie funktorów prawdziwościowych opiera się na jednako-wym przebiegu wartości logicznych form zdaniowych, w których te funktory występują, przy tym samym układzie wartości logicznych odpowiednich argumentów.
Ex. Definicja Fregego
(p ∨ q) ≡ (~p → q)
Jest to funktor F2.
Prawdziwościowo te dwa wyrażenia są takie same.
(p ∧ q) ≡ ~(p → ~q)
~p ≡ p ↓ p (jednoczesne zaprzeczenie)
~p ≡ p | p
(p ∧ q) ≡ ~(p | q) ≡ ((p | q) | (p | q))
Można zauważyć, że w tych definicjach mamy:
8
jednakowe wartości form zdaniowych
funktory występują w formach zdaniowych
układ argumentów
Wybrane tezy rachunku zdań
1.
Prawo wyłączonego środka
p ∨ ~p
a) z dwóch sprzecznych stanów rzeczy jedne zachodzi (interpretacja ontologiczna);
b) metalogiczne prawo wyłączonego środka: z dwóch zdań sprzecznych jedno jest prawdziwe (to sformułowanie dotyczy zdań, a nie form zdaniowych);
2.
Prawo niesprzeczności
~(p ∧ ~p)
a) interpretacja ontologiczna: z dwóch sprzecznych stanów rzeczy jeden nie istnieje;
b) metalogiczne prawo niesprzeczności: z dwóch zdań sprzecznych jedno jest fałszywe;
3.
Prawo Dunsa Szkota
(p ∧ ~p) → q
p → (~p → q) (implikacyjne prawo przepełnienia)
4.
Prawo podwójnego przeczenia
~(~p) ≡ p
5.
Prawo redukcji do absurdu
(~p → p) → p)
(p → ~p) → ~p)
(p → (q ∧ ~q)) → ~p)
6.
Prawo tożsamości (zwrotności)
p → p
p ≡ p
7.
Prawo tautologii (powtórzenia)
(p ∨ p) ≡ p
(p ∧ p) ≡ p
(wyrażenie "tautologia" ma różne znaczenia) 9
Prawo zastępowania równoważności
(p ≡ q) ≡ ((p → q) ∧ (q → p))
9.
Prawo zastępowania implikacji
(p → q) ≡ (~p v q)
(p → q) ≡ ~(p ∧ ~q)
10.
Modus tollens
((p → q) ∧ ~q) → ~p
w notacji Łukasiewicza
CKCpqNqNp
- funktor główny na początku
- funktor 2-arg. przed dwoma arguemntami
11.
Transpozycja
(p → q) ≡ (~q → ~p)
ECpqCNqNp
12.
Transpozycja złożona
((p ∧ q) → r) ≡ ((p ∧ ~r) → ~q)
ECKpqrCKpNrNq
13.
Prawa de Morgana
~(p ∧ q) ≡ (~p ∨ ~q)
~(p ∨ q) ≡ (~p ∧ ~q)
14.
Prawo negowania implikacji
~(p → q) ≡ (p ∧ ~q)
15.
Prawo negowania równoważności
~(p ≡ q) ≡ ((p ∧ ~q) ∨ (q ∧ ~p))
16. Prawo komutacji (przestawiania)
(p → (q → r)) ≡ (q → (p → r))
17.
Prawo eksportacji i importacji
(p ∧ q) → r)) ≡ (p → (q → r))
eksportacji →
importacji ←
10
Sylogizm warunkowy
((p → q) ∧ (q → r)) → (p → r)
(p → q) → ((q → r) → (p → r))
CCpqCCqrCpr
19.
Symetria równoważności
(p ≡ q) ≡ (q ≡ p)
20.
Prawo przechodniości implikacji
((p ≡ q) ∧ (q ≡ r)) → (p ≡ r)
21. Prawa przemienności
(p ∧ q) ≡ (q ∧ p)
(p ∨ q) ≡ (q ∨ p)
22. Prawa łączności
((p ∧ q) ∧ r) ≡ (p ∧ (q ∧ r))
((p ∨ q) ∨ r) ≡ (p ∨ (q ∨ r))
23.
Rozdzielność koniunkcji
((p ∨ q) ∧ r) ≡ ((p ∧ r) ∨ (q ∧ r))
24.
Rozdzielność alternatywy
((p ∧ q) ∨ r) ≡ ((p ∨ r) ∧ (q ∨ r))
25.
Prawo nowego czynnika
(p → q) → ((p ∧ r) → (q ∧ r))
26.
Prawo nowego składnika
(p → q) → ((p ∨ r) → (q ∨ r))
27.
Mnożenie następnika
((p → q) ∧ (p → r)) ≡ (p → (q ∧ r))
28.
Dodawanie poprzednika
((p → r) ∧ (q → r)) ≡ ((p ∨ q) → r)
29.
Mnożenie implikacji stronami
((p → q) ∧ (r → s)) → ((p ∧ r) → (q ∧ s))
30. Dodawanie implikacji stronami
11
((p → q) ∨ (r → s)) → ((p ∨ r) → (q ∨ s)) 31.
Dylemat konstrukcyjny
((p → q) ∧ (r → s)) → ((p ∨ r) → (q ∨ s))
32.
Dylemat konstrukcyjny prosty
((p → r) ∧ (q → r) ∧ (p ∨ q)) → r
((p → r) ∧ (q → r)) → ((p ∨ q) → r)
33.
Dylemat konstrukcyjny prosty
((p → q) ∧ (p → r) ∧ (~q ∨ ~r))→ ~p
((p → r) ∧ (q → r)) → ((~q ∨ ~r) → r)
34.
Dylemat konstrukcyjny złożony
((p → q) ∧ (r → s) ∧ (~q ∨ ~s)) → (~p ∨ ~r))
35.
Prawo odwracania implikacji stronami
((p → q) ∧ (r → s) ∧ (p ∨ r) ∧ ~(q ∧ s)) → ((q → p) ∧ (s → r)) Stąd reguła
p → q
r → s
p ∨ r
~(q ∧ s)
----------
q → p
s → r
Analogicznie można skonstruować regułę dla odwracania kilku n implikacji Reguła ta głosi, że głosi, że z n implikacji oraz alternatywy ich poprzedników oraz gdy następniki każdych dwóch takich implikacji nie są zarazem prawdziwe, wynika implikacja odwrotna.
12
...........
ϕn → ψn
ϕ1 ∨ ... ∨ ϕn
~(ψi ∧ ψj) gdzie 1 ≤ i, j ≤ n
--------------
ψ1 → ϕ1
.................
ψn → ϕn
Prawa ekstensjonalności
36.
(p ≡ q) → (~p ≡ ~q)
37.
((p ≡ q) ∧ (r ≡ s)) → ((p ∧ r) ≡ (q ∧ s))
38.
((p ≡ q) ∧ (r ≡ s)) → ((p ∨ r) ≡ (q ∨ s))
39. ((p ≡ q) ∧ (r ≡ s)) → ((p → r) ≡ (q → s))
40.
((p ≡ q) ∧ (r ≡ s)) → ((p ≡ r) ≡ (q ≡ s))
41.
((p ≡ q) ∧ (r ≡ s)) → ((p f r) ≡ (q f s))
gdzie f jest dowolnym funktorem.
Reguła ekstensjonalności dla założeniowego rachunku zdań
ϕ ≡ ψ
κ
-----------
κ(ϕ \\ ψ)
Symbol "κ(ϕ \\ ψ)" oznacza wyrażenie, które powstaje przez zastąpienie na ja-kimś miejscu (lub miejscach) wyrażenia ϕ przez wyrażenie ψ.
Uwaga
Jest różnica między regułą podstawiania a regułą zastępowania: podstawia się za zmienne, a zastępuje się wyrażenia.
13
Wybrane prawa logiki udowodnione metodą tabelkową.
1) Pierwsze prawo redukcji do absurdu
(p → ~p) → ~p
p
~p
p → ~p
(p → ~p) → ~p
1
0
0
1
0
1
1
1
2) Drugie prawo redukcji do absurdu
(p → q) ∧ (p → ~q) → ~p
p q
p → q
~q p → ~q
~p (p → q) ∧ (p → ~q) (p → q) ∧ (p → ~q) → ~p
1 1
1
0
0
0
0
1
1 0
0
1
1
0
0
1
0 1
1
0
1
1
1
1
0 0
1
1
1
1
1
1
3) Prawo de Morgana dla koniunkcji
~(p ∧ q) ⇔ (~p ∨ ~q)
p q
p ∧ q ~( p ∧ q) ~p
~q ~p ∨ ~q ~(p ∧ q) ⇔ (~p ∨ ~q)
1 1
1
0
0
0
0
1
1 0
0
1
0
1
1
1
0 1
0
1
1
0
1
1
0 0
0
1
1
1
1
1
4) Prawo de Morgana dla alternatywy
~(p ∨ q) ⇔ (~p ∧ ~q)
p q
p ∨ q ~( p ∨ q) ~p ~q ~p ∧ ~q ~(p ∨ q) ⇔ (~p ∧ ~q) 1 1
1
0
0
0
0
1
1 0
1
0
0
1
0
1
0 1
1
0
1
0
0
1
0 0
0
1
1
1
1
1
5) Prawo zaprzeczenia implikacji
~(p → q) ⇔ (p ∧ ~q)
p q
p → q ~( p → q)
~q
p ∧ ~q
~(p → q) ⇔ (p ∧ ~q)
1 1
1
0
0
0
1
1 0
0
1
1
1
1
0 1
1
0
0
0
1
0 0
1
0
1
0
1
6) Prawa zastępowania implikacji
(p → q) ⇔ ~(p ∧ ~q)
p q
p → q ~q p ∧ ~q
~(p ∧ ~q) (p → q) ⇔ ~(p ∧ ~q)
1 1
1
0
0
1
1
1 0
0
1
1
0
1
0 1
1
0
0
1
1
0 0
1
1
0
1
1
14
(p → q) ⇔ (~p ∨ q)
7) Prawa zastępowania koniunkcji
(p ∧ q) ⇔ ~(~p ∨ ~q)
p q
p ∧ q ~p ~q ~p ∨ ~q
~(~p ∨ ~q)
(p ∧ q) ⇔ ~(~p ∨ ~q)
1 1
1
0
0
0
1
1
1 0
0
0
1
1
0
1
0 1
0
1
0
1
0
1
0 0
0
1
1
1
0
1
analogicznie
(p ∧ q) ⇔ ~(p → ~q)
8) Prawa zastępowania alternatywy
(p ∨ q) ⇔ ~(~p ∧ ~q)
p q
p ∨ q ~p ~q ~p ∧ ~q
~(~p ∧ ~q) (p ∨ q) ⇔ ~(~p ∧ ~q)
1 1
1
0
0
0
1
1
1 0
1
0
1
0
1
1
0 1
1
1
0
0
1
1
0 0
0
1
1
1
0
1
analogicznie
(p ∨ q) ⇔ (~p → q)
9) Prawo zastępowania równoważności
(p ⇔ q) ⇔ ((p → q) ∧ (q → p))
p q
p ⇔ q p → q q → p (p → q) ∧ (q → p) (p ⇔ q) ⇔ ((p → q) ∧ (q → p)) 1 1
1
1
1
1
1
1 0
0
0
1
0
1
0 1
0
1
0
0
1
0 0
1
1
1
1
1
10) ((p → q) ∧ (q → r)) → (p→ r)
p q r p → q q → r p→ r (p → q) ∧ (q → r) ((p → q) ∧ (q → r)) → (p→ r) 1 1 1
1
1
1
1
1
1 1 0
1
0
0
0
1
1 0 0
0
1
0
0
1
1 0 1
0
1
1
0
1
0 1 1
1
1
1
1
1
0 0 1
1
1
1
1
1
0 1 0
1
0
1
0
1
0 0 0
1
1
1
1
1
15
p q
p ∨ q
~p (p ∨ q) ∧ ~p
((p ∨ q) ∧ ~p) → q
1 1
1
0
0
1
1 0
1
0
0
1
0 1
1
1
1
1
0 0
0
1
0
1
11) ((p ∧ q) → r) ⇔ ((p ∧~r) → ~q)
12) (p → (q →r )) ⇔ (q → (p → r))
13) (p →(q → r)) → ((p → q) → (p→ r))
16