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

Logická pravda
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

Logická nepravda
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í:

Logická identita
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í:

Logická negace
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 015 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 pq , Xpq Logické NOR
2 (FFTF) (p, q) pq , Mpq Neimplikovat konverzaci
3 (FFTT) (p, q) ¬p , ~ str ¬p , Np , Fpq Negace
4 (FTFF) (p, q) pq , Lpq Materiální neimplikace
5 (FTFT) (p, q) ¬q , ~ q ¬q , Nq , Gpq Negace
6 (FTTF) (p, q) XOR pq , Jpq Exkluzivní disjunkce
7 (FTTT) (p, q) NAND pq , Dpq Logický NAND
8 (TFFF) (p, q) A pq , 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) pq pokud p, pak q , Cpq Věcná implikace
12 (TTFF) (p, q) p p , Ipq Projekční funkce
13 (TTFT) (p, q) pq p pokud q , Bpq Konverze implikace
14 (TTTF) (p, q) NEBO pq , 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í:

Logická konjunkce
p q pq
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 pq 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 pq je q , jinak pq 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í:

Logická disjunkce
p q pq
T T T
T F T
F T T
F F F

V angličtině je uvedeno, že pokud p , pak pq je p , jinak pq 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í:

Logické implikace
p q pq
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í:

Materiál podmíněný
p q pq
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í:

Logická rovnost
p q pq
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í:

Exkluzivní disjunkce
p q pq
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í:

Logický NAND
p q pq
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í:

Logické NOR
p q pq
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:

Logická ekvivalence:
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:

F T
F F F
T F T
F T
F F T
T T T

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