Pravdivá tabulka - Truth table
Pravdivostní tabulka je matematický tabulky používané v logice -specifically v souvislosti s Booleova algebra , logických funkcí a výrokové logiky -Která stanovuje funkčních hodnot logických výrazů na každém ze svých funkčních tvrzení, že je pro každou kombinaci hodnot přijata podle jejich logických proměnných . Zejména pravdivostní tabulky lze použít k ukázání, zda je výrokový výraz pravdivý pro všechny legitimní vstupní hodnoty, tedy logicky platné .
Pravdivá tabulka má jeden sloupec pro každou vstupní proměnnou (například P a Q) a jeden poslední sloupec zobrazující všechny možné výsledky logické operace, kterou tabulka představuje (například P XOR Q). Každý řádek tabulky pravdivosti obsahuje jednu možnou konfiguraci vstupních proměnných (například P = true Q = false) a výsledek operace pro tyto hodnoty. Další vysvětlení viz níže uvedené příklady. Ludwig Wittgenstein se obecně zasloužil o vynalézání a popularizaci tabulky pravd ve svém Tractatus Logico-Philosophicus , který byl dokončen v roce 1918 a publikován v roce 1921. Takový systém byl také nezávisle navržen v roce 1921 Emil Leon Post . Ještě dřívější iterace pravdivostní tabulky byla také nalezena v nepublikovaných rukopisech Charlese Sanderse Peirce z roku 1893, anotujících obě publikace o téměř 30 let.
Unární operace
Existují 4 unární operace:
- Vždy pravda
- Nikdy pravda, unární falsum
- Unární identita
- Unární negace
Logická pravda
Výstupní hodnota je vždy true, bez ohledu na vstupní hodnotu p
p | T |
---|---|
T | T |
F | T |
Logická lež
Výstupní hodnota není nikdy pravdivá: to znamená vždy nepravda, bez ohledu na vstupní hodnotu p
p | F |
---|---|
T | F |
F | F |
Logická identita
Logická identita je operace s jednou logickou hodnotou p, pro kterou výstupní hodnota zůstává p.
Pravdivostní tabulka pro operátor logické identity je následující:
p | p |
---|---|
T | T |
F | F |
Logická negace
Logická negace je operace na jedné logické hodnotě , obvykle hodnotě propozice , která vytváří hodnotu true, pokud je její operand nepravdivá, a hodnotu false, pokud je její operand pravdivý.
Pravdivostní tabulka pro NOT p (také psaná jako ¬p , Np , Fpq nebo ~ p ) je následující:
p | ¬p |
---|---|
T | F |
F | T |
Binární operace
Existuje 16 možných pravdivostních funkcí dvou binárních proměnných :
Tabulka pravdy pro všechny binární logické operátory
Zde je rozšířená tabulka pravdy, která uvádí definice všech šestnácti možných pravdivostních funkcí dvou booleovských proměnných P a Q:
p | q | F 0 | NOR 1 | ↚ 2 | ¬p 3 | ↛ 4 | ¬q 5 | XOR 6 | NAND 7 | A 8 | XNOR 9 | q 10 | → 11 | p 12 | ← 13 | NEBO 14 | T 15 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
T | T | F | F | F | F | F | F | F | F | T | T | T | T | T | T | T | T | ||
T | F | F | F | F | F | T | T | T | T | F | F | F | F | T | T | T | T | ||
F | T | F | F | T | T | F | F | T | T | F | F | T | T | F | F | T | T | ||
F | F | F | T | F | T | F | T | F | T | F | T | F | T | F | T | F | T | ||
Com | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||||
Doc | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |||||||||||
Adj | F 0 | NOR 1 | ↛ 4 | ¬q 5 | ↚ 2 | ¬p 3 | XOR 6 | NAND 7 | A 8 | XNOR 9 | p 12 | ← 13 | q 10 | → 11 | NEBO 14 | T 15 | |||
Neg | T 15 | NEBO 14 | ← 13 | p 12 | → 11 | q 10 | XNOR 9 | A 8 | NAND 7 | XOR 6 | ¬q 5 | ↛ 4 | ¬p 3 | ↚ 2 | NOR 1 | F 0 | |||
Dvojí | T 15 | NAND 7 | → 11 | ¬p 3 | ← 13 | ¬q 5 | XNOR 9 | NOR 1 | NEBO 14 | XOR 6 | q 10 | ↚ 2 | p 12 | ↛ 4 | A 8 | F 0 | |||
L id | F | F | T | T | T, F | T | F | ||||||||||||
R id | F | F | T | T | T, F | T | F |
kde
- T = pravda.
- F = nepravda.
- Horní indexy 0 až 15 je číslo vyplývající ze čtení čtyř pravdivostních hodnot jako binárního čísla s F = 0 a T = 1.
- Com řádek indikuje, zda je subjekt, op , je komutativní - P op Q = op P .
- Assoc řádek indikuje, zda je subjekt, op , je asociativní - (P op Q) op R = P op (Q op R) .
- Adj řádek ukazuje provozovatel OP2 tak, že p op Q = OP2 P
- Tyto Neg řádek ukazuje provozovatel OP2 takové, že P op Q = ¬ (Q OP2 P)
- Tyto Dual řádek ukazuje dvojí provoz získané záměnou T F, i a s nebo.
- Tyto L id řádek ukazuje provozovatele levé identit pokud má - hodnoty, I tak, že jsem op Q = .
- R id řádek ukazuje provozovatele správné identity v případě, že obsahuje nějaké - hodnoty, I tak, že P op I = P .
Čtyři kombinace vstupních hodnot pro p, q se čtou po řádcích z výše uvedené tabulky. Výstupní funkce pro každou kombinaci p, q lze číst z tabulky po řádcích.
Klíč:
Následující tabulka je orientována podle sloupců, nikoli podle řádků. K zobrazení čtyř kombinací p, q jako vstupu existují spíše čtyři sloupce než čtyři řádky.
p : TTFF
q : TFTF
V tomto klíči je 16 řádků, jeden řádek pro každou binární funkci dvou binárních proměnných, p, q. Například v řádku 2 tohoto klíče je hodnota Neimplikace konverzace (' ') pouze T, pro sloupec označený jedinečnou kombinací p = F, q = T; zatímco v řádku 2 je hodnota této operace F pro tři zbývající sloupce p, q. Výstupní řádek pro je tedy
2: FFTF
a klíč 16 řádků je
operátor | Název operace | |||
---|---|---|---|---|
0 | (FFFF) (p, q) | ⊥ | nepravda , Opq | Rozpor |
1 | (FFFT) (p, q) | ANI | p ↓ q , Xpq | Logické NOR |
2 | (FFTF) (p, q) | ↚ | p ↚ q , Mpq | Neimplikovat konverzaci |
3 | (FFTT) (p, q) | ¬p , ~ str | ¬p , Np , Fpq | Negace |
4 | (FTFF) (p, q) | ↛ | p ↛ q , Lpq | Materiální neimplikace |
5 | (FTFT) (p, q) | ¬q , ~ q | ¬q , Nq , Gpq | Negace |
6 | (FTTF) (p, q) | XOR | p ⊕ q , Jpq | Exkluzivní disjunkce |
7 | (FTTT) (p, q) | NAND | p ↑ q , Dpq | Logický NAND |
8 | (TFFF) (p, q) | A | p ∧ q , Kpq | Logická konjunkce |
9 | (TFFT) (p, q) | XNOR | p Pokud a pouze pokud q , Epq | Logické dvoupodmínečné |
10 | (TFTF) (p, q) | q | q , Hpq | Projekční funkce |
11 | (TFTT) (p, q) | p → q | pokud p, pak q , Cpq | Věcná implikace |
12 | (TTFF) (p, q) | p | p , Ipq | Projekční funkce |
13 | (TTFT) (p, q) | p ← q | p pokud q , Bpq | Konverze implikace |
14 | (TTTF) (p, q) | NEBO | p ∨ q , Apq | Logická disjunkce |
15 | (TTTT) (p, q) | ⊤ | pravda , Vpq | Tautologie |
Logické operátory lze také zobrazit pomocí Vennův diagramů .
Logická konjunkce (AND)
Logická konjunkce je operace se dvěma logickými hodnotami , obvykle hodnotami dvou propozic , která vytváří hodnotu true, pokud jsou pravdivé oba její operandy.
Pravdivostní tabulka pro p AND q (psaná také jako p ∧ q , Kpq , p & q nebo p q ) je následující:
p | q | p ∧ q |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
V běžných jazykových termínech, pokud jsou oba p a q pravdivé, pak je spojka p ∧ q pravdivá. Pro všechna ostatní přiřazení logických hodnot k p a q je spojka p ∧ q nepravdivá.
Lze také říci, že pokud p , pak p ∧ q je q , jinak p ∧ q je p .
Logická disjunkce (NEBO)
Logická disjunkce je operace se dvěma logickými hodnotami , obvykle hodnotami dvou propozic , která vytváří hodnotu true, pokud je alespoň jeden z jejích operandů pravdivý.
Pravdivostní tabulka pro p OR q (psáno také jako p ∨ q , Apq , p || q nebo p + q ) je následující:
p | q | p ∨ q |
---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
V angličtině je uvedeno, že pokud p , pak p ∨ q je p , jinak p ∨ q je q .
Logické implikace
Logická implikace a materiální podmíněné jsou spojeny s operací na dvou logických hodnotách , obvykle hodnotách dvou propozic , která vytváří hodnotu false, pokud je první operand pravdivý a druhý operand je nepravdivý, a hodnotu true jinak.
Pravdivostní tabulka spojená s logickou implikací p implikuje q (symbolizováno jako p ⇒ q , nebo vzácněji Cpq ) je následující:
p | q | p ⇒ q |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Pravdivostní tabulka spojená s hmotnou podmínkou, jestliže p pak q (symbolizováno jako p → q ) je následující:
p | q | p → q |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Může být také užitečné poznamenat, že p ⇒ q a p → q jsou ekvivalentní ¬p ∨ q .
Logická rovnost
Logická rovnost (také známá jako biconditional nebo exclusive nor ) je operace na dvou logických hodnotách , obvykle hodnotách dvou tvrzení , která vytváří hodnotu true, pokud jsou oba operandy nepravdivé nebo oba operandy jsou pravdivé.
Pravdivostní tabulka pro p XNOR q (psáno také jako p ↔ q , Epq , p = q nebo p ≡ q ) je následující:
p | q | p ↔ q |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Takže p EQ q je pravdivé, pokud p a q mají stejnou pravdivostní hodnotu (obě pravdivé nebo obě nepravdivé), a nepravdivé, pokud mají různé pravdivostní hodnoty.
Exkluzivní disjunkce
Exkluzivní disjunkce je operace se dvěma logickými hodnotami , obvykle hodnotami dvou propozic , která vytváří hodnotu true, pokud je pravdivý jeden, ale ne oba její operandy.
Pravdivostní tabulka pro p XOR q (psaná také jako Jpq nebo p ⊕ q ) je následující:
p | q | p ⊕ q |
---|---|---|
T | T | F |
T | F | T |
F | T | T |
F | F | F |
Pro dvě tvrzení lze XOR také zapsat jako (p ∧ ¬q) ∨ (¬p ∧ q).
Logický NAND
Logický NAND je operace na dvou logických hodnot , typicky hodnoty dvou výroků , které produkuje hodnotu FALSE , pokud jsou splněny oba jeho operandy. Jinými slovy, vytváří hodnotu true, pokud je alespoň jeden z jejích operandů nepravdivý.
Pravdivostní tabulka pro p NAND q (psaná také jako p ↑ q , Dpq nebo p | q ) je následující:
p | q | p ↑ q |
---|---|---|
T | T | F |
T | F | T |
F | T | T |
F | F | T |
Často je užitečné vyjádřit logickou operaci jako složenou operaci, tj. Jako operaci, která je vytvořena nebo složena z jiných operací. Je možné mnoho takových kompozic, v závislosti na operacích, které jsou brány jako základní nebo "primitivní" a na operacích, které jsou brány jako kompozitní nebo "derivační".
V případě logického NAND je jasně vyjádřen jako sloučenina NOT a AND.
Negace spojky: ¬ ( p ∧ q ) a disjunkce negací: (¬ p ) ∨ (¬ q ) lze tabulkovat takto:
p | q | p ∧ q | ¬ ( p ∧ q ) | ¬ p | ¬ q | (¬ p ) ∨ (¬ q ) |
---|---|---|---|---|---|---|
T | T | T | F | F | F | F |
T | F | F | T | F | T | T |
F | T | F | T | T | F | T |
F | F | F | T | T | T | T |
Logické NOR
Logické NOR je operace na dvou logických hodnot , typicky hodnoty dvou výroků , které produkuje hodnotu pravda, pokud oba její operandy falešný. Jinými slovy, vytváří hodnotu false, pokud je alespoň jeden z jejích operandů pravdivý. ↓ je také známý jako šipka Peirce podle jejího vynálezce Charlese Sanderse Peirce a je dostatečným operátorem Sole .
Pravdivostní tabulka pro p NOR q (také psaná jako p ↓ q nebo Xpq ) je následující:
p | q | p ↓ q |
---|---|---|
T | T | F |
T | F | F |
F | T | F |
F | F | T |
Negace disjunkce ¬ ( p ∨ q ) a konjunkce negací (¬ p ) ∧ (¬ q ) lze tabulkovat takto:
p | q | p ∨ q | ¬ ( p ∨ q ) | ¬ p | ¬ q | (¬ p ) ∧ (¬ q ) |
---|---|---|---|---|---|---|
T | T | T | F | F | F | F |
T | F | T | F | F | T | F |
F | T | T | F | T | F | F |
F | F | F | T | T | T | T |
Kontrola tabelárních derivací pro NAND a NOR, při každém přiřazení logických hodnot funkčním argumentům p a q , vytváří identické vzorce funkčních hodnot pro ¬ ( p ∧ q ) jako pro (¬ p ) ∨ (¬ q ), a pro ¬ ( p ∨ q ) jako pro (¬ p ) ∧ (¬ q ). První a druhý výraz v každém páru jsou tedy logicky ekvivalentní a mohou být navzájem nahrazeny ve všech kontextech, které se týkají pouze jejich logických hodnot.
Tato ekvivalence je jedním z De Morganových zákonů .
Velikost pravdivostních tabulek
Pokud existuje n vstupních proměnných, pak existují 2 n možných kombinací jejich pravdivostních hodnot. Daná funkce může pro každou kombinaci vytvářet hodnotu true nebo false, takže počet různých funkcí n proměnných je dvojnásobná exponenciála 2 2 n .
n | 2 n | 2 2 n | |
---|---|---|---|
0 | 1 | 2 | |
1 | 2 | 4 | |
2 | 4 | 16 | |
3 | 8 | 256 | |
4 | 16 | 65 536 | |
5 | 32 | 4,294,967,296 | ≈ 4,3 × 10 9 |
6 | 64 | 18 446 744 073 709 551 616 | ≈ 1,8 × 10 19 |
7 | 128 | 340 282 366 920 938 463 463 374 607 431 768 211 456 | ≈ 3,4 × 10 38 |
8 | 256 | 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 | ≈ 1,1 × 10 77 |
Tabulky pravd pro funkce tří nebo více proměnných jsou uváděny jen zřídka.
Aplikace
Tabulky pravd lze použít k prokázání mnoha dalších logických ekvivalentů . Zvažte například následující tabulku pravdy:
T | T | F | T | T |
T | F | F | F | F |
F | T | T | T | T |
F | F | T | T | T |
To dokazuje skutečnost, že je logicky ekvivalent k .
Tabulka pravdy pro většinu běžně používaných logických operátorů
Zde je tabulka pravd, která uvádí definice 7 nejčastěji používaných ze 16 možných pravdivostních funkcí dvou booleovských proměnných P a Q :
P | Otázka | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
T | T | T | T | F | T | T | T | T | |||||||||
T | F | F | T | T | F | F | T | F | |||||||||
F | T | F | T | T | F | T | F | F | |||||||||
F | F | F | F | F | T | T | T | T | |||||||||
P | Otázka | ||||||||||||||||
AND (spojka) |
NEBO (disjunkce) |
XOR (exkluzivní nebo) |
XNOR (exkluzivní ani) |
podmíněné „kdyby-pak“ |
podmíněné „pak-kdyby“ |
biconditional "if-and-only-if" |
|||||||||||
kde T znamená pravdivé a F znamená falešný |
Zhuštěné pravdivostní tabulky pro binární operátory
U binárních operátorů se také používá zkrácená forma tabulky pravdivosti, kde záhlaví řádků a záhlaví sloupců určují operandy a buňky tabulky určují výsledek. Booleovská logika například používá tento zkrácený zápis tabulky pravd:
|
|
Tento zápis je užitečný zejména v případě, že jsou operace komutativní, i když lze navíc určit, že řádky jsou prvním operandem a sloupce druhým operandem. Tato zhuštěná notace je obzvláště užitečná při diskusích o vícehodnotových rozšířeních logiky, protože výrazně snižuje kombinatorickou explozi počtu řádků, které jsou jinak potřeba. Poskytuje také rychle rozpoznatelný charakteristický „tvar“ rozložení hodnot v tabulce, což může čtenáři pomoci rychleji porozumět pravidlům.
Tabulky pravdy v digitální logice
Pravdivé tabulky se také používají k určení funkce hardwarových vyhledávacích tabulek (LUT) v digitálních logických obvodech . Pro LUT s n-vstupem bude mít tabulka pravdivosti 2^ n hodnot (nebo řádků ve výše uvedeném tabulkovém formátu), což zcela specifikuje booleovskou funkci pro LUT. Představením každé booleovské hodnoty jako bitu v binárním čísle mohou být pravdivostní tabulky efektivně zakódovány jako celočíselné hodnoty v softwaru EDA (Electronic Design Automation) . Například 32bitové celé číslo může kódovat pravdivostní tabulku pro LUT s až 5 vstupy.
Při použití celočíselné reprezentace pravdivostní tabulky lze výstupní hodnotu LUT získat výpočtem bitového indexu k na základě vstupních hodnot LUT, v takovém případě je výstupní hodnota LUT k -tý bit celého čísla. Například pro vyhodnocení hodnoty výstupu LUT dána řada z n boolean vstupních hodnot se bit index výstupní hodnoty pravdy tabulky lze vypočítat takto: v případě, že i tý vstup je pravda, nechal , jinak nech . Pak k th bit binárního znázornění pravdivostní tabulky je výstupní hodnota LUT, kde .
Tabulky pravd jsou jednoduchým a přímým způsobem kódování booleovských funkcí, ale vzhledem k exponenciálnímu nárůstu velikosti s rostoucím počtem vstupů nejsou vhodné pro funkce s velkým počtem vstupů. Další reprezentace, které jsou efektivnější z hlediska paměti, jsou textové rovnice a binární rozhodovací diagramy .
Aplikace pravdivostních tabulek v digitální elektronice
V digitální elektronice a počítačové vědě (oblasti aplikované logiky a matematiky) lze pravdivostní tabulky použít k redukci základních booleovských operací na jednoduché korelace vstupů a výstupů, bez použití logických bran nebo kódu. Binární sčítání lze například znázornit pomocí tabulky pravd:
A B | C R 1 1 | 1 0 1 0 | 0 1 0 1 | 0 1 0 0 | 0 0 where A = First Operand B = Second Operand C = Carry R = Result
Tato tabulka pravdy se čte zleva doprava:
- Hodnotový pár (A, B) se rovná hodnotovému páru (C, R).
- Nebo v tomto případě A plus B rovná se výsledek R s Carry C.
Všimněte si, že tato tabulka nepopisuje logické operace nutné k implementaci této operace, ale spíše specifikuje funkci vstupů na výstupní hodnoty.
S ohledem na výsledek může být tento příklad aritmeticky vnímán jako binární sčítání modulo 2 a jako logicky ekvivalentní binární logické operaci exclusive-or (exclusive disjunction).
V tomto případě jej lze použít pouze pro velmi jednoduché vstupy a výstupy, například 1 s a 0 s. Pokud se však počet typů hodnot, které lze na vstupech mít, zvyšuje, velikost tabulky pravd se zvětší.
Například v operaci sčítání jeden potřebuje dva operandy, A a B. Každý může mít jednu ze dvou hodnot, nula nebo jedna. Počet kombinací těchto dvou hodnot je 2 × 2 nebo čtyři. Výsledkem jsou tedy čtyři možné výstupy C a R. Pokud by jeden použil základnu 3, velikost by se zvětšila na 3 × 3 neboli devět možných výstupů.
První příklad „přidání“ výše se nazývá poloviční sčítač. Úplný sčítač je, když je přenos z předchozí operace poskytnut jako vstup do dalšího sčítače. K popisu logiky úplné sčítačky by tedy byla zapotřebí pravdivostní tabulka o osmi řádcích :
A B C* | C R 0 0 0 | 0 0 0 1 0 | 0 1 1 0 0 | 0 1 1 1 0 | 1 0 0 0 1 | 0 1 0 1 1 | 1 0 1 0 1 | 1 0 1 1 1 | 1 1 Same as previous, but.. C* = Carry from previous adder
Dějiny
Výzkum Irvinga Anellise ukazuje, že CS Peirce se zdá být nejčasnějším logikem (v roce 1893), který vymyslel matici tabulky pravd. Ze shrnutí jeho příspěvku:
V roce 1997 John Shosky objevil na druhé straně stránky přepsaného přepisu přednášky Bertranda Russella z roku 1912 na matice tabulek pravdy „Filozofie logického atomismu“. Matice pro negaci je Russellova, vedle které je matice pro materiální implikace v rukou Ludwiga Wittgensteina. Ukazuje se, že nepublikovaný rukopis identifikovaný jako složený Peircem v roce 1893 obsahuje matici pravdivostní tabulky, která je ekvivalentní matici pro materiální implikace objevenou Johnem Shoským. Nepublikovaný rukopis od Peirce identifikovaný jako složený v letech 1883–84 v souvislosti se skladbou Peirceova „On the Algebra of Logic: A Contribution to the Philosophy of Notation“, který se objevil v American Journal of Mathematics v roce 1885, obsahuje příklad tabulka nepřímých pravd pro podmíněné.
Viz také
Poznámky
Reference
Citované práce
- Bocheński, Józef Maria (1959), A Précis of Mathematical Logic , přeložil z francouzského a německého vydání Otto Bird, Dordrecht, Jižní Holandsko: D. Reidel.
- Enderton, H. (2001). Matematický úvod do logiky , druhé vydání, New York: Harcourt Academic Press. ISBN 0-12-238452-0
- Quine, WV (1982), Methods of Logic , 4. vydání, Cambridge, MA: Harvard University Press.
externí odkazy
- „Tabulka pravdy“ , Encyklopedie matematiky , EMS Press , 2001 [1994]
- Pravdivé tabulky, tautologie a logická ekvivalence
- PEIRCEHO PRAVDĚFUNKČNÍ ANALÝZA A PŮVOD PRAVDIVNÝCH TABULEK od Irvinga H. Anellise
- Převádění pravdivostních tabulek na booleovské výrazy