Funkcja prawdy - Truth function
W logice , wykorzystując funkcję prawda jest funkcja , która przyjmuje wartości prawdy jako wejście i tworzy unikalną wartość Prawda jako wyjście. Innymi słowy: wszystkie dane wejściowe i wyjściowe funkcji prawdy są wartościami prawdy; funkcja prawdy zawsze zwraca dokładnie jedną wartość prawdy; a wprowadzenie tych samych wartości prawdy zawsze da tę samą wartość prawdziwości. Typowym przykładem jest logika zdań , w której instrukcja złożona jest konstruowana przy użyciu pojedynczych instrukcji połączonych łącznikami logicznymi ; jeśli wartość prawdziwości instrukcji złożonej jest całkowicie określona przez wartość (wartości) prawdziwości instrukcji składowych, instrukcja złożona nazywana jest funkcją prawdy , a wszelkie użyte łączniki logiczne są określane jako funkcjonalne prawdy .
Klasyczna logika zdań jest logiką funkcji prawdy, w której każde zdanie ma dokładnie jedną wartość prawdziwości, która jest albo prawdziwa, albo fałszywa, a każda łącznik logiczny jest funkcjonariuszem prawdy (z odpowiednią tabelą prawdy ), a zatem każda instrukcja złożona jest funkcją prawdy. Z drugiej strony, logika modalna nie działa zgodnie z prawdą.
Przegląd
Łącznik logiczny jest funkcją prawdy, jeśli wartość prawdziwości zdania złożonego jest funkcją wartości prawdziwości jego zdań podrzędnych. Klasa łączników jest zgodna z prawdą, jeśli każdy z jej członków jest. Na przykład łącznik „ i ” jest zgodny z prawdą, ponieważ zdanie takie jak „ Jabłka to owoce, a marchewki to warzywa ” jest prawdziwe wtedy i tylko wtedy, gdy każde z jego podzdań „ jabłka to owoce ” i „ marchewki to warzywa ” jest prawda, aw przeciwnym razie jest fałszywa. Niektóre łączniki języka naturalnego, takie jak angielski, nie są zgodne z prawdą.
Połączenia postaci „x wierzy, że …” są typowymi przykładami połączeń, które nie są zgodne z prawdą. Jeśli np. Mary błędnie uważa, że Al Gore był prezydentem USA 20 kwietnia 2000 r., Ale nie wierzy, że księżyc jest zrobiony z zielonego sera, to wyrok
- „ Mary uważa, że Al Gore był prezydentem USA 20 kwietnia 2000 r. ”
jest prawdą, podczas gdy
- „ Mary wierzy, że księżyc jest zrobiony z zielonego sera ”
to fałsz. W obu przypadkach każde zdanie składowe (tj. „ Al Gore był prezydentem USA 20 kwietnia 2000 r. ” I „ księżyc jest zrobiony z zielonego sera ”) jest fałszywe, ale każde zdanie złożone utworzone przez dodanie przedrostka „ Mary uważa, że „różni się wartością prawdy. Oznacza to, że wartość prawdziwości zdania w postaci „ Maria uważa, że… ” nie jest określona wyłącznie przez wartość prawdziwości zdania składowego, a zatem (jednoargumentowy) łącznik (lub po prostu operator, ponieważ jest jednoargumentowy) ) nie działa zgodnie z prawdą.
Klasa łączników klasycznej logiki (np. & , → ) użyta do konstrukcji formuł jest prawdziwie funkcjonalna. Ich wartości dla różnych wartości prawdy jako argumentów są zwykle podawane w tabelach prawdy . Rachunek zdań funkcji prawdy jest systemem formalnym, którego wzory mogą być interpretowane jako prawdziwe lub fałszywe.
Tabela binarnych funkcji prawdy
W logice dwuwartościowej, istnieje szesnaście możliwych funkcji prawdę, zwane również funkcje logiczne , z dwoma wejściami P i Q . Każda z tych funkcji odpowiada tabeli prawdy pewnego logicznego łącznika w logice klasycznej, w tym kilku zdegenerowanych przypadków, takich jak funkcja niezależna od jednego lub obu swoich argumentów. Prawda i fałsz są oznaczone odpowiednio jako 1 i 0 w poniższych tabelach prawdy ze względu na zwięzłość.
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
Kompletność funkcjonalna
Ponieważ funkcja może być wyrażona jako kompozycja , rachunek logiczny prawdziwie funkcjonalny nie musi mieć dedykowanych symboli dla wszystkich wyżej wymienionych funkcji, aby był funkcjonalnie kompletny . Wyraża się to w rachunku zdań jako logiczna równoważność pewnych zdań złożonych. Na przykład, układ logiczny zawiera klasyczne Ź P ∨ Q równoważną P → Q . Operator warunkowy „→” nie jest zatem konieczny dla klasycznego systemu logicznego, jeśli „¬” (nie) i „∨” (lub) są już używane.
Minimalny zestaw operatorów, którzy mogą wyrazić każdą wyrażalne oświadczenie w rachunku zdań nazywany jest minimalny funkcjonalnie komplet . Minimalnie kompletny zestaw operatorów jest osiągany przez samą NAND {↑} i sam NOR {↓}.
Poniżej przedstawiono minimalne funkcjonalnie kompletne zbiory operatorów, których liczba nie przekracza 2:
- Jeden element
- {↑}, {↓}.
- Dwa elementy
- , , , , , , , , , , , , , , , , , .
- Trzy elementy
- , , , , , .
Własności algebraiczne
Niektóre funkcje prawdy mają własności, które można wyrazić w twierdzeniach zawierających odpowiadający im łącznik. Niektóre z tych właściwości, które może mieć binarna funkcja prawdy (lub odpowiadająca jej łącznik logiczny), to:
- Zespolenie : W wyrażeniu zawierające dwa lub więcej takich samych asocjacyjnych zdaniotwórczych w rzędzie, kolejność operacji nie ma znaczenia, pod warunkiem, że sekwencja argumentów nie jest zmieniany.
- przemienność : operandy łącznika można zamienić bez wpływu na wartość prawdziwości wyrażenia.
- dystrybucja : łącznik oznaczony przez · rozprowadza się po innym łączniku oznaczonym przez +, jeśli a · ( b + c ) = ( a · b ) + ( a · c ) dla wszystkich operandów a , b , c .
- idempotencja : za każdym razem, gdy operandy operacji są takie same, łącznik daje wynik jako operand. Innymi słowy, operacja zachowuje zarówno prawdę, jak i fałsz (patrz poniżej).
- absorpcja : para łączników spełnia prawo absorpcji, jeśli dla wszystkich operandów a , b .
Zbiór funkcji prawdy jest funkcjonalnie kompletny wtedy i tylko wtedy, gdy dla każdej z poniższych pięciu właściwości zawiera co najmniej jeden element, który jej nie zawiera:
- monotoniczny : Jeśli f ( a 1 , ..., a n ) ≤ f ( b 1 , ..., b n ) dla wszystkich a 1 , ..., a n , b 1 , ..., b n ∈ {0,1} takie, że a 1 ≤ b 1 , a 2 ≤ b 2 , ..., a n ≤ b n . Np .
- afiniczna : dla każdej zmiennej zmiana jej wartości albo zawsze, albo nigdy, zmienia wartość prawdziwości operacji, dla wszystkich stałych wartości wszystkich innych zmiennych. Np . , .
- self dual : czytanie przypisań wartości prawdy dla operacji od góry do dołu w jej tabeli prawdy jest tym samym, co przyjmowanie uzupełnienia czytania od dołu do góry; innymi słowy, f (¬ a 1 , ..., ¬ a n ) = ¬ f ( a 1 , ..., a n ). Np .
- Zachowanie prawdy : interpretacja, zgodnie z którą wszystkim zmiennym przypisuje się wartość prawdziwości „prawda”, daje w wyniku tych operacji wartość prawdziwości „prawda”. Np . (patrz ważność )
- zachowanie fałszu : interpretacja, zgodnie z którą wszystkim zmiennym przypisuje się wartość prawdziwości „fałsz”, daje w wyniku tych operacji wartość prawdziwości „fałsz”. Np . (patrz ważność )
Arity
Konkretna funkcja może być również nazywana operatorem . W dwóch wartościach logicznych są 2 operatorów sygnalnych (stałe), 4 podmioty unarne , 16 Operatory , 256 podmioty trójskładnikowe i n operatorzy -ary. W trójwartościowym logiki są 3 operatorów sygnalnych (stałe), 27 operatorzy unarne , 19683 Operatory , 7625597484987 operatorzy trójskładnikowe i n operatorzy -ary. W logice k- wartościowej istnieje k operatorów zerowych, operatory jednoargumentowe, operatory binarne, operatory trójskładnikowe i operatory n -arne. N -ary operator k -valued logiczny jest funkcją z . Dlatego liczba takich operatorów jest taka , jak wyprowadzono powyższe liczby.
Jednak niektórzy operatorzy określonej liczby są w rzeczywistości zdegenerowanymi formami, które wykonują operację o niższej wartości na niektórych wejściach i ignorują pozostałe dane wejściowe. Spośród 256 trójskładnikowych operatorów logicznych cytowanych powyżej, wśród nich są takie zdegenerowane formy operatorów binarnych lub operatorów o mniejszej liczbie arów, wykorzystujące zasadę włączania-wykluczania . Operator trójskładnikowy jest jednym z takich operatorów, który w rzeczywistości jest operatorem jednoargumentowym stosowanym do jednego wejścia i ignorującym pozostałe dwa dane wejściowe.
„Nie” jest operatorem jednoargumentowym , zajmuje pojedynczy wyraz (¬ P ). Reszta to operatory binarne , które wykorzystują dwa wyrażenia, aby utworzyć instrukcję złożoną ( P ∧ Q , P ∨ Q , P → Q , P ↔ Q ).
Zbiór operatorów logicznych Ω można podzielić na rozłączne podzbiory w następujący sposób:
W tej partycji jest zbiorem symboli operatora o arności j .
W bardziej znanych rachunkach zdań jest zwykle podzielony w następujący sposób:
- operatory zerowe:
- jednoargumentowe operatory:
- operatory binarne:
Zasada kompozycyjności
Zamiast korzystać z tablic prawdy , logiczne symbole łączące można interpretować za pomocą funkcji interpretacji i funkcjonalnie kompletnego zestawu funkcji prawdy (Gamut 1991), zgodnie z zasadą kompozycyjności znaczenia. Niech ja będę funkcją interpretacji, niech Φ , Ψ będą dowolnymi dwoma zdaniami i niech funkcja prawdy f ni będzie zdefiniowana jako:
- f nand (T, T) = F; f nand (T, F) = f nand (F, T) = f nand (F, F) = T
Następnie, dla wygody, F nie , C lub C i i tak dalej są określone za pomocą f NAND :
- f not ( x ) = f nand ( x , x )
- f lub ( x , y ) = f nand ( f nie ( x ), f nie ( y ))
- f i ( x , y ) = f nie ( f nand ( x , y ))
lub alternatywnie f nie , C lub C i i tak dalej są zdefiniowane bezpośrednio:
- f nie (T) = F; f nie (F) = T;
- f lub (T, T) = f lub (T, F) = f lub (F, T) = T; f lub (F, F) = F
- f i (T, T) = T; f i (T, F) = f i (F, T) = f i (F, F) = F
Następnie
- I (~) = I ( ) = f nie
- I (&) = I ( ) = f i
- I ( v ) = I ( ) = f lub
- I (~ Φ ) = I ( Φ ) = I ( ) ( I ( Φ )) = f nie ( I ( Φ ))
- I ( Φ Ψ ) = I ( ) ( I ( Φ ), I ( Ψ )) = f oraz ( I ( Φ ), I ( Ψ ))
itp.
Zatem jeśli S jest zdaniem będącym ciągiem symboli składającym się z symboli logicznych v 1 ... v n reprezentujących logiczne łączniki i nielogicznych symboli c 1 ... c n , to wtedy i tylko wtedy , gdy I ( v 1 ) ... I ( v n ) zostały dostarczone, interpretując v 1 do v n za pomocą f nand (lub dowolnego innego zestawu funkcjonalnych pełnych funkcji prawdy), wtedy wartość prawdziwości jest całkowicie określona przez wartości prawdy c 1 ... c n , czyli z I ( c 1 ) ... I ( c n ) . Innymi słowy, zgodnie z oczekiwaniami i wymaganiami, S jest prawdą lub fałszem tylko przy interpretacji wszystkich nielogicznych symboli.
Informatyka
Operatory logiczne są zaimplementowane jako bramki logiczne w obwodach cyfrowych . Praktycznie wszystkie obwody cyfrowe (głównym wyjątkiem jest DRAM ) są zbudowane z NAND , NOR , NOT i bramek transmisyjnych . Bramki NAND i NOR z 3 lub więcej wejściami, a nie zwykłymi 2 wejściami, są dość powszechne, chociaż są logicznie równoważne kaskadzie bramek 2-wejściowych. Wszystkie inne operatory są implementowane poprzez rozbicie ich na logicznie równoważną kombinację 2 lub więcej powyższych bramek logicznych.
„Logiczna równoważność” „samego NAND”, „samego NOR” oraz „NOT i AND” jest podobna do równoważności Turinga .
Fakt, że wszystkie funkcje prawdy można wyrazić za pomocą samego NOR, pokazuje komputer naprowadzający Apollo .
Zobacz też
Uwagi
Bibliografia
- Ten artykuł zawiera materiał z TruthFunction on PlanetMath , który jest objęty licencją Creative Commons Attribution / Share-Alike License .
Dalsza lektura
- Józef Maria Bocheński (1959), A Précis of Mathematical Logic , przekład z wersji francuskiej i niemieckiej przez Otto Birda, Dordrecht, Holandia Południowa: D. Reidel.
- Alonzo Church (1944), Wprowadzenie do logiki matematycznej , Princeton, NJ: Princeton University Press. Zobacz wprowadzenie, aby zapoznać się z historią koncepcji funkcji prawdy.