Funkce pravdy - Truth function

V logice , je logická funkce je funkce , která přijímá pravdivostní hodnotu jako vstup a vytváří jedinečnou pravdivostní hodnotu jako výstup. Jinými slovy: Vstup a výstup funkce pravdivosti jsou všechny hodnoty pravdy; funkce pravdivosti vždy vygeneruje přesně jednu hodnotu pravdy; a zadáním stejné hodnoty pravdy bude vždy vydána stejná hodnota pravdy. Typickým příkladem je výroková logika , kde je složený příkaz konstruován pomocí jednotlivých příkazů spojených logickými spojkami ; pokud je pravdivostní hodnota složeného výrazu zcela určena pravdivostními hodnotami složených výroků, složené tvrzení se nazývá pravdivostní funkce a všechny použité logické spojky se považují za pravdivé .

Klasická výroková logika je logika pravdivosti a funkce v tom, že každý výrok má přesně jednu hodnotu pravdy, která je buď pravdivá nebo nepravdivá, a každé logické spojovací slovo je pravdivé funkční (s odpovídající tabulkou pravdivosti ), takže každý složený výrok je pravdivou funkcí. Na druhou stranu je modální logika nefunkční.

Přehled

Logické pojivové je pravda-funkční, pokud je pravda, hodnota souvětí je závislá na pravdivostní hodnoty jeho dílčích vět. Třída spojek je pravdivá, pokud je každý její člen. Například spojovací výraz „ a “ je pravdivý, protože věta typu „ Jablka jsou ovoce a mrkev jsou zelenina “ platí pouze tehdy, a pouze tehdy, když každá z jejích podvětí „ jablka jsou ovoce “ a „ mrkev je zelenina “ je true a jinak je false. Některé spojky přirozeného jazyka, například angličtina, nejsou pravdivé.

Spojky ve tvaru „x věří, že ...“ jsou typickými příklady spojek, které nejsou pravdivé. Pokud se například Mary mylně domnívá, že Al Gore byl prezidentem USA 20. dubna 2000, ale nevěří, že Měsíc je vyroben ze zeleného sýra, pak věta

„ Mary věří, že Al Gore byl prezidentem USA 20. dubna 2000 “

je to pravda

„ Mary věří, že měsíc je ze zeleného sýra “

je nepravdivé. V obou případech je každá složková věta (tj. „ Al Gore byl prezidentem USA 20. dubna 2000 “ a „ Měsíc je vyroben ze zeleného sýra “) nepravdivá, ale každá složená věta vytvořená předponou „ Mary věří, že "se liší v hodnotě pravdy. To znamená, že pravdivostní hodnota věty ve tvaru „ Mary věří, že ... “ není určena pouze pravdivostní hodnotou její složkové věty, a proto (unární) spojovací (nebo jednoduše operátor, protože je unární) ) je nefunkční.

Třída klasických logických spojek (např. & , → ) používaných při konstrukci vzorců je funkčně pravdivá. Jejich hodnoty pro různé pravdivostní hodnoty jako argument jsou obvykle dány pravdivostními tabulkami . Pravdově funkční výrokový kalkul je formální systém, jehož vzorce lze interpretovat jako pravdivé nebo nepravdivé.

Tabulka funkcí binární pravdy

Ve dvou-cenil logiku, existují šestnáct možných pravdivostní funkce, nazývané také logické funkce , dvou vstupů P a Q . Kterákoli z těchto funkcí odpovídá pravdivostní tabulce určité logické spojky v klasické logice, včetně několika zvrhlých případů, jako je funkce nezávislá na jednom nebo obou jejích argumentech. Pravda a nepravda jsou v následujících tabulkách pravdy kvůli stručnosti označeny jako 1, respektive 0.

Rozpor / nepravda Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram ${\ displaystyle \ bot}$ "dno" P ∧ ¬ P O pq   Q 0 1 P 0    0   0  1    0   0	Tautologie / pravda Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram ${\ displaystyle \ top}$ "horní" P ∨ ¬ P V pq   Q 0 1 P 0    1   1  1    1   1
Propozice P Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P p I pq   Q 0 1 P 0    0   0  1    1   1	Negace P Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram ¬ P ~ P N p F pq   Q 0 1 P 0    1   1  1    0   0
Návrh Q Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram Q q H pq   Q 0 1 P 0    0   1  1    0   1	Negace Q Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram ¬ Q ~ Q N q G pq   Q 0 1 P 0    1   0  1    1   0
Spojení Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P ∧ Q P & Q P   ·   Q P  A  Q P ↛¬ Q ¬ P ↚ Q ¬ P ↓ ¬ Q K pq   Q 0 1 P 0    0   0  1    0   1	Alternativní popření Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram 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
Disjunkce Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P ∨ Q P  NEBO  Q P ← ¬ Q ¬ P → Q ¬ P ↑ ¬ Q ¬ (¬ P ∧ ¬ Q ) A pq   Q 0 1 P 0    0   1  1    1   1	Společné popření Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P ↓ Q P  NOR  Q P ↚ ¬ Q ¬ P ↛ Q ¬ P ∧ ¬ Q X pq   Q 0 1 P 0    1   0  1    0   0
Zjednodušení materiálu Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P ↛ Q P Q P Q${\ displaystyle \ not \ supset}$ ${\ displaystyle>}$ P ∧ ¬ Q ¬ P ↓ Q ¬ P ↚ ¬ Q L pq   Q 0 1 P 0    0   0  1    1   0	Materiální implikace Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P → Q P ⊃ Q P Q${\ displaystyle \ leq}$ P ↑ ¬ Q ¬ P ∨ Q ¬ P ← ¬ Q C pq   Q 0 1 P 0    1   1  1    0   1
Konverzní neimplikace Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P ↚ Q P Q P Q${\ displaystyle \ not \ podmnožina}$ ${\ displaystyle <}$ P ↓ ¬ Q ¬ P ∧ Q ¬ P ↛ ¬ Q M pq   Q 0 1 P 0    0   1  1    0   0	Konverzní implikace Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P ← Q P ⊂ Q P Q${\ displaystyle \ geq}$ P ∨ ¬ Q ¬ P ↑ Q ¬ P → ¬ Q B pq   Q 0 1 P 0    1   0  1    1   1
Exkluzivní disjunkce Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P ↮ Q P ≢ Q P ⨁ Q P  XOR  Q P ¬ Q ¬ P Q ¬ P ↮ ¬ Q J pq${\ displaystyle \ leftrightarrow}$ ${\ displaystyle \ leftrightarrow}$   Q 0 1 P 0    0   1  1    1   0	Dvojpodmínečné Zápis Ekvivalentní vzorce Pravdivá tabulka Vennův diagram P Q P ≡ Q P  XNOR  Q P  IFF  Q${\ displaystyle \ leftrightarrow}$ P ↮ ¬ Q ¬ P ↮ Q ¬ P ¬ Q E pq${\ displaystyle \ leftrightarrow}$   Q 0 1 P 0    1   0  1    0   1

Funkční úplnost

Protože funkce může být vyjádřena jako kompozice , logický kalkul s pravdou a funkcí nemusí mít vyhrazené symboly pro to, aby byly všechny výše uvedené funkce funkčně úplné . To je vyjádřeno v propozičním počtu jako logická ekvivalence určitých složených příkazů. Například, klasická logika má ¬ P  ∨  Q odpovídající P  →  Q . Podmíněný operátor „→“ proto není pro klasický logický systém nutný, pokud se „¬“ (ne) a „∨“ (nebo) již používají.

Minimální sadu operátorů, který může vyjádřit každý výrok expressible ve výrokové logiky se nazývá minimální funkčně kompletní sada . Minimálně úplné sady operátorů dosáhne samotný NAND {↑} a samotný NOR {↓}.

Toto jsou minimální funkčně úplné sady operátorů, jejichž hodnoty nepřesahují 2:

Jeden prvek

{↑}, {↓}.

Dva prvky

${\ displaystyle \ {\ vee, \ neg \}}$ , , , , , , , , , , , , , , , , , . ${\ displaystyle \ {\ klín, \ neg \}}$${\ displaystyle \ {\ to, \ neg \}}$${\ displaystyle \ {\ dostane, \ neg \}}$${\ displaystyle \ {\ to, \ bot \}}$${\ displaystyle \ {\ dostane, \ bot \}}$${\ displaystyle \ {\ to, \ nleva pravá šipka \}}$${\ displaystyle \ {\ gets, \ nleftrightarrow \}}$${\ displaystyle \ {\ to, \ npravý šíp \}}$${\ displaystyle \ {\ to, \ nleftarrow \}}$${\ displaystyle \ {\ dostane, \ npravý šíp \}}$${\ displaystyle \ {\ gets, \ nleftarrow \}}$${\ displaystyle \ {\ nrightarrow, \ neg \}}$${\ displaystyle \ {\ nleftarrow, \ neg \}}$${\ displaystyle \ {\ nrightarrow, \ top \}}$${\ displaystyle \ {\ nleftarrow, \ top \}}$${\ displaystyle \ {\ npravá šipka, \ levá šipka \}}$${\ displaystyle \ {\ nleftarrow, \ leftrightarrow \}}$

Tři prvky

${\ displaystyle \ {\ lor, \ leftrightarrow, \ bot \}}$ , , , , , . ${\ displaystyle \ {\ lor, \ leftrightarrow, \ nleftrightarrow \}}$${\ displaystyle \ {\ lor, \ nleva pravá šipka, \ nahoru \}}$${\ displaystyle \ {\ land, \ leftrightarrow, \ bot \}}$${\ displaystyle \ {\ land, \ leftrightarrow, \ nleftrightarrow \}}$${\ displaystyle \ {\ země, \ nleva doprava, \ nahoru \}}$

Algebraické vlastnosti

Některé pravdivostní funkce mají vlastnosti, které mohou být vyjádřeny ve větách obsahujících odpovídající pojivo. Některé z těchto vlastností, které může mít funkce binární pravdy (nebo odpovídající logické pojivo), jsou:

• asociativita : V rámci výrazu obsahujícího dvě nebo více stejných asociativních spojek v řadě nezáleží na pořadí operací, pokud se nezmění sekvence operandů.
• komutativita : Operandy pojiva lze vyměnit, aniž by to ovlivnilo pravdivostní hodnotu výrazu.
• distributivita : Spojovací výraz označený · distribuuje přes další spojovací výraz označený +, pokud a · ( b + c ) = ( a · b ) + ( a · c ) pro všechny operandy a , b , c .
• idempotence : Kdykoli jsou operandy operace stejné, spojnice dává operandu jako výsledek. Jinými slovy, operace zachovává pravdu i lež (viz níže).
• absorpce : Dvojice spojek splňuje zákon absorpce, pokud pro všechny operandy a , b . ${\ displaystyle \ land, \ lor}$${\ displaystyle a \ land (a \ lor b) = a}$

Sada funkcí pravdy je funkčně úplná právě tehdy, pokud pro každou z následujících pěti vlastností obsahuje alespoň jednoho člena, který ji nemá:

• monotónní : Pokud f ( a ₁ , ..., a _n ) ≤ f ( b ₁ , ..., b _n ) pro všechny a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0,1} takové, že a ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . Např . ${\ displaystyle \ vee, \ klín, \ top, \ bot}$
• afinní : Pro každou proměnnou změna její hodnoty buď vždy, nebo nikdy nezmění pravdivostní hodnotu operace, pro všechny pevné hodnoty všech ostatních proměnných. Například , . ${\ displaystyle \ neg, \ leftrightarrow}$${\ displaystyle \ not \ leftrightarrow, \ top, \ bot}$
• self dual : Čtení přiřazení pravdivostní hodnoty pro operaci shora dolů na její tabulce pravdivosti je stejné jako převzetí doplňku jejího čtení zdola nahoru; jinými slovy, f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). Např . ${\ displaystyle \ neg}$
• zachovávání pravdy : Interpretace, podle které jsou všem proměnným přiřazeny pravdivostní hodnoty „true“, vytváří v důsledku těchto operací pravdivostní hodnotu „true“. Např . (viz platnost ) ${\ displaystyle \ vee, \ klín, \ top, \ rightarrow, \ leftrightarrow, \ podmnožina}$
• zachování nepravdivosti : Interpretace, podle které jsou všem proměnným přiřazeny pravdivostní hodnoty 'false', vytváří v důsledku těchto operací pravdivostní hodnotu 'false'. Např . (viz platnost ) ${\ displaystyle \ vee, \ wedge, \ nleftrightarrow, \ bot, \ not \ podmnožina, \ not \ supset}$

Arity

Konkrétní funkce může být také označována jako operátor . V logice se dvěma hodnotami existují 2 nulární operátory (konstanty), 4 unární operátory , 16 binárních operátorů , 256 ternárních operátorů a n -ary operátory. V logice se třemi hodnotami jsou 3 operátoři nully (konstanty), 27 unárních operátorů , 19683 binárních operátorů , 7625597484987 ternárních operátorů a n -ary operátorů. V k -hodnotové logice existuje k nullary operátory, unární operátory, binární operátory, ternární operátory a n -ary operátory. N -ary operátor k cenil logika je funkce z . Proto je počet takových operátorů , což je způsob, jakým byla odvozena výše uvedená čísla. ${\ displaystyle 2 ^ {2 ^ {n}}}$ ${\ displaystyle 3 ^ {3 ^ {n}}}$ ${\ displaystyle k ^ {k}}$${\ displaystyle k ^ {k ^ {2}}}$${\ displaystyle k ^ {k ^ {3}}}$${\ displaystyle k ^ {k ^ {n}}}$ ${\ displaystyle \ mathbb {Z} _ {k} ^ {n} \ to \ mathbb {Z} _ {k}}$${\ displaystyle | \ mathbb {Z} _ {k} | ^ {| \ mathbb {Z} _ {k} ^ {n} |} = k ^ {k ^ {n}}}$

Některé z operátorů určité arity jsou však ve skutečnosti degenerované formy, které provádějí operaci s nižší arititou na některých vstupech a zbytek vstupů ignoruje. Z 256 výše uvedených ternárních booleovských operátorů jsou to takové zvrhlé formy binárních operátorů nebo operátorů s nižší arititou, které používají princip zahrnutí – vyloučení . Ternární operátor je jeden takový operátor, který je ve skutečnosti unárním operátorem aplikovaným na jeden vstup a ignoruje další dva vstupy. ${\ displaystyle {\ binom {3} {2}} \ cdot 16 - {\ binom {3} {1}} \ cdot 4 + {\ binom {3} {0}} \ cdot 2}$${\ displaystyle f (x, y, z) = \ ne x}$

„Ne“ je unární operátor , trvá to jediný výraz (¬ P ). Zbytek jsou binární operátoři , kteří k vytvoření složeného příkazu používají dva termíny ( P ∧ Q , P ∨ Q , P → Q , P ↔ Q ).

Sada logických operátorů Ω může být rozdělena do disjunktních podmnožin následovně:

${\ displaystyle \ Omega = \ Omega _ {0} \ cup \ Omega _ {1} \ cup \ ldots \ cup \ Omega _ {j} \ cup \ ldots \ cup \ Omega _ {m} \ ,.}$

V tomto oddílu je sada operátorských symbolů arity j . ${\ displaystyle \ Omega _ {j}}$

Ve známějších výrokových kalkulích se obvykle dělí takto: ${\ displaystyle \ Omega}$

operátoři nullary: ${\ displaystyle \ Omega _ {0} = \ {\ bot, \ top \}}$

unární operátoři: ${\ displaystyle \ Omega _ {1} = \ {\ lnot \}}$

binární operátoři: ${\ displaystyle \ Omega _ {2} \ subseteq \ {\ land, \ lor, \ rightarrow, \ leftrightarrow \}}$

Zásada kompozičnosti

Místo použití pravdivostních tabulek lze logické spojovací symboly interpretovat pomocí interpretační funkce a funkčně kompletní sady pravdivostních funkcí (Gamut 1991), jak je podrobně popsáno na principu kompozičnosti významu. Nechť mi být funkční výklad, ať Φ , Ψ být jakékoliv dvě věty a nechat logická funkce f _NAND je definován jako:

• f _nand (T, T) = F; f _nand (T, F) = f _nand (F, T) = f _nand (F, F) = T

Poté, pro pohodlí, f _ne , F _nebo F _a a tak dále jsou definovány pomocí f _NAND :

• f _ne ( x ) = f _nand ( x , x )
• f _nebo ( x , y ) = f _nand ( f _ne ( x ), f _ne ( y ))
• f _a ( x , y ) = f _ne ( f _nand ( x , y ))

nebo alternativně f _ne , F _{, nebo} F _a a tak dále jsou definovány přímo:

• f _ne (T) = F; f _ne (F) = T;
• f _nebo (T, T) = f _nebo (T, F) = f _nebo (F, T) = T; f _nebo (F, F) = F
• f _a (T, T) = T; f _a (T, F) = f _a (F, T) = f _a (F, F) = F

Pak

atd.

Pokud tedy S je věta, která je řetězcem symbolů skládajících se z logických symbolů v ₁ ... v _n představujících logické spojky, a nelogických symbolů c ₁ ... c _n , pak právě tehdy, když I ( v ₁ ) ... I ( v _n ) byly poskytnuty interpretaci v ₁ až v _n pomocí f _nand (nebo jakékoli jiné sady funkčních úplných pravdivých funkcí), pak je pravdivostní hodnota zcela určena pravdivostními hodnotami c ₁ ... c _n , tj. I ( c ₁ ) ... I ( c _n ) . Jinými slovy, podle očekávání a požadavku je S pravdivé nebo nepravdivé pouze při interpretaci všech jeho nelogických symbolů. ${\ displaystyle I (s)}$

Počítačová věda

Logické operátory jsou implementovány jako logické brány v digitálních obvodech . Prakticky všechny digitální obvody (hlavní výjimkou je DRAM ) jsou sestaveny z NAND , NOR , NOT a přenosových bran . Brány NAND a NOR se 3 nebo více vstupy než s obvyklými 2 vstupy jsou poměrně běžné, i když jsou logicky ekvivalentní kaskádě 2-vstupních bran. Všechny ostatní operátory jsou implementovány jejich rozdělením do logicky ekvivalentní kombinace 2 nebo více výše uvedených logických bran.

„Logická ekvivalence“ „NAND samotná“, „NOR samotná“ a „NE a AND“ je podobná Turingově ekvivalenci .

Fakt, že všechny funkce pravdy lze vyjádřit pouze pomocí NOR, ukazuje naváděcí počítač Apollo .

Viz také

Poznámky

Reference

• Tento článek obsahuje materiál z TruthFunction na PlanetMath , který je licencován pod Creative Commons Attribution / Share-Alike License .

Další čtení

• Józef Maria Bocheński (1959), Précis of Mathematical Logic , přeložil z francouzské a německé verze Otto Bird, Dordrecht, Jižní Holandsko: D. Reidel.
• Alonzo Church (1944), Introduction to Mathematical Logic , Princeton, NJ: Princeton University Press. Viz úvod pro historii konceptu funkce pravdy.