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ść.

Sprzeczność / fałsz
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna

"Dolny"
P ∧ ¬ P
O pq
  Q
0 1
P. 0    0   0 
1    0   0 
Venn0000.svg


Tautology / True
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna

"Top"
P ∨ ¬ P
V pq
  Q
0 1
P. 0    1   1 
1    1   1 
Venn1111.svg


Twierdzenie P
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P. p
I pq
  Q
0 1
P. 0    0   0 
1    1   1 
Venn0101.svg


Negacja P.
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
¬ P
~ P
N p
F pq
  Q
0 1
P. 0    1   1 
1    0   0 
Venn1010.svg


Twierdzenie Q
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
Q q
H pq
  Q
0 1
P. 0    0   1 
1    0   1 
Venn0011.svg


Negacja Q
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
¬ Q
~ Q
N q
G pq
  Q
0 1
P. 0    1   0 
1    1   0 
Venn1100.svg


Spójnik
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P i Q
P   ·   Q
P  ORAZ  Q
P ↛¬ Q
¬ P Q
¬ P ↓ ¬ Q
K pq
  Q
0 1
P. 0    0   0 
1    0   1 
Venn0001.svg


Alternatywne zaprzeczenie
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P | Q
P  NAND  Q
P → ¬ Q
¬ P Q
¬ P ∨ ¬ Q
D pq
  Q
0 1
P. 0    1   1 
1    1   0 
Venn1110.svg


Dysjunkcja
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P  LUB  Q
P ← ¬ Q
¬ P Q
¬ P ↑ ¬ Q
¬ (¬ P ∧ ¬ Q )
A pq
  Q
0 1
P. 0    0   1 
1    1   1 
Venn0111.svg


Wspólne zaprzeczenie
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P  NOR  Q
P ↚ ¬ Q
¬ P Q
¬ P ∧ ¬ Q
X pq
  Q
0 1
P. 0    1   0 
1    0   0 
Venn1000.svg


Materialne uproszczenie
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P Q P Q
P ∧ ¬ Q
¬ P Q
¬ P ↚ ¬ Q
L pq
  Q
0 1
P. 0    0   0 
1    1   0 
Venn0100.svg


Materialne implikacje
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P Q
P Q
P ↑ ¬ Q
¬ P Q
¬ P ← ¬ Q
C pq
  Q
0 1
P. 0    1   1 
1    0   1 
Venn1011.svg


Converse nonimplication
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P Q P Q
P ↓ ¬ Q
¬ P Q
¬ P ↛ ¬ Q
M pq
  Q
0 1
P. 0    0   1 
1    0   0 
Venn0010.svg


Implikacja odwrotna
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P Q
P Q
P ∨ ¬ Q
¬ P Q
¬ P → ¬ Q
B pq
  Q
0 1
P. 0    1   0 
1    1   1 
Venn1101.svg


Wyłączne rozłączenie
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q
P Q
P Q
P  XOR  Q
P ¬ Q ¬ P Q ¬ P ↮ ¬ Q J pq


  Q
0 1
P. 0    0   1 
1    1   0 
Venn0110.svg


Dwuwarunkowe
Notacja Równoważne
wzory
Tabela prawdy Diagram Venna
P Q PQ P  XNOR  Q P  IFF  Q


P ↮ ¬ Q
¬ P Q
¬ P ¬ Q E pq
  Q
0 1
P. 0    1   0 
1    0   1 
Venn1001.svg


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

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.