Pravdivá tabulka - Truth table

A pravdivostní tabulka je matematická tabulka použito v logika — Konkrétně v souvislosti s Booleova algebra, booleovské funkce, a výrokový kalkul —Který stanoví funkční hodnoty logiky výrazy na každém z jejich funkčních argumentů, tedy na každém kombinace hodnot převzatých jejich logickými proměnnými.^[1] Zejména tabulky pravdivosti lze použít k ukázání, zda je výrokový výraz pravdivý pro všechny legitimní vstupní hodnoty, tj. logicky platné.

Tabulka pravdivosti 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. Pro další vysvětlení viz níže uvedené příklady. Ludwig Wittgenstein je obecně připočítán s vynalézáním a popularizací tabulky pravd v jeho Tractatus Logico-Philosophicus, který byl dokončen v roce 1918 a publikován v roce 1921.^[2] Takový systém také nezávisle navrhl v roce 1921 Emil Leon Post.^[3] Ještě dřívější iteraci pravdivostní tabulky našel také v nepublikovaných rukopisech Charles Sanders Peirce z roku 1893, antedatující obě publikace o téměř 30 let.^[4]

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 pravdivá, bez ohledu na vstupní hodnotu p

Logické nepravdivé

Výstupní hodnota není nikdy true: to znamená, že je vždy false, bez ohledu na vstupní hodnotu p

Logická identita

Logická identita je úkon na jednom logická hodnota p, pro kterou výstupní hodnota zůstává p.

Tabulka pravdivosti pro operátor logické identity je následující:

Logická negace

Logická negace je úkon na jednom logická hodnota, typicky hodnota a tvrzení, který produkuje hodnotu skutečný pokud je jeho operand nepravdivý a má hodnotu Nepravdivé pokud je jeho operand pravdivý.

Pravdivá tabulka pro NE str (také psáno jako ¬p, Np, Fpqnebo ~ str) je následující:

Binární operace

Existuje 16 možných funkce pravdy ze dvou binární proměnné:

Tabulka pravdivosti pro všechny binární logické operátory

Zde je tabulka rozšířené pravdy poskytující definice všech možných funkcí pravdy dvou booleovských proměnných P a Q:^{[poznámka 1]}

kde

T = pravda.

F = nepravda.

The Com řádek označuje, zda operátor, op, je komutativní - P op Q = Q op P.

The Doc řádek označuje, zda operátor, op, je asociativní - (P op Q) op R = P op (Q op R).

The Adj řádek zobrazuje operátora op2 takhle P op Q = Q op2 P

The Neg řádek zobrazuje operátora op2 takhle P op Q = ¬ (Q op2 P)

The Dvojí řádek ukazuje duální provoz získáno záměnou T s F a AND s OR.

The L id řádek ukazuje číslo operátora levá identita pokud má nějaké - hodnoty Já takhle I op Q = Q.

The Identifikační číslo řádek ukazuje číslo operátora správné identity pokud má nějaké - hodnoty Já takhle P op I = P.^{[poznámka 2]}

Čtyři kombinace vstupních hodnot pro p, q jsou čteny po řádcích z výše uvedené tabulky. Funkci výstupu pro každou kombinaci p, q lze číst po řádcích z tabulky.

Klíč:

Následující tabulka je orientována podle sloupce, nikoli podle řádku. K dispozici jsou čtyři sloupce, nikoli čtyři řádky, které zobrazují čtyři kombinace p, q jako vstup.

p: T T F F
q: T F T F

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 hodnota Konverzní neimplikace ('${ displaystyle nleftarrow}$') je pouze T, pro sloupec označený jedinečnou kombinací p = F, q = T; zatímco v řádku 2 je hodnota toho '${ displaystyle nleftarrow}$'operace je F pro tři zbývající sloupce p, q. Výstupní řádek pro ${ displaystyle nleftarrow}$ je tedy

2: F F T F

a 16 řádků^[5] klíč je

Logické operátory lze také vizualizovat pomocí Vennovy diagramy.

Logická spojka (AND)

Logická spojka je úkon na dva logické hodnoty, obvykle hodnoty dvou propozice, který produkuje hodnotu skutečný pokud jsou oba jeho operandy pravdivé.

Pravdivá tabulka pro p AND q (také psáno jako p ∧ q, Kpq, p & qnebo p ${ displaystyle cdot}$ q) je následující:

V běžném jazyce, pokud obojí p a q jsou pravdivé, pak spojení p ∧ q je pravda. Pro všechna ostatní přiřazení logických hodnot k p a do q spojení p ∧ q je nepravdivé.

Lze také říci, že pokud p, pak p ∧ q je q, v opačném případě p ∧ q je p.

Logická disjunkce (NEBO)

Logická disjunkce je úkon na dva logické hodnoty, obvykle hodnoty dvou propozice, který produkuje hodnotu skutečný pokud je alespoň jeden z jeho operandů pravdivý.

Pravdivá tabulka pro p NEBO q (také psáno jako p ∨ q, Apq, p || qnebo p + q) je následující:

Uvedeno v angličtině, pokud p, pak p ∨ q je p, v opačném případě p ∨ q je q.

Logické důsledky

Logické důsledky a materiál podmíněný jsou spojeny s úkon na dva logické hodnoty, obvykle hodnoty dvou propozice, který produkuje hodnotu Nepravdivé pokud je první operand true a druhý operand je false a má hodnotu skutečný v opačném případě.

Pravdivostní tabulka spojená s logickou implikací p znamená q (symbolizováno jako p ⇒ q, nebo vzácněji Cpq) je následující:

Pravdivostní tabulka spojená s materiálem podmíněná pokud p pak q (symbolizováno jako p → q) je následující:

Může být také užitečné si to uvědomit p ⇒ q a p → q jsou ekvivalentní k ¬p ∨ q.

Logická rovnost

Logická rovnost (také známý jako dvojpodmínečné nebo exkluzivní ani ) je úkon na dva logické hodnoty, obvykle hodnoty dvou propozice, který produkuje hodnotu skutečný pokud jsou oba operandy nepravdivé nebo jsou oba operandy pravdivé.

Pravdivá tabulka pro p XNOR q (také psáno jako p ↔ q, Epq, p = qnebo p ≡ q) je následující:

Takže p EQ q je pravda, pokud p a q mají stejné pravdivostní hodnota (oba pravdivé nebo oba nepravdivé) a nepravdivé, pokud mají různé hodnoty pravdy.

Exkluzivní disjunkce

Exkluzivní disjunkce je úkon na dva logické hodnoty, obvykle hodnoty dvou propozice, který produkuje hodnotu skutečný pokud je pravdivý jeden, ale ne oba jeho operandy.

Pravdivá tabulka pro p XOR q (také psáno jako Jpqnebo p ⊕ q) je následující:

Pro dva návrhy, XOR lze také zapsat jako (p ∧ ¬q) ∨ (¬p ∧ q).

Logické NAND

The logický NAND je úkon na dva logické hodnoty, obvykle hodnoty dvou propozice, který produkuje hodnotu Nepravdivé pokud jsou oba jeho operandy pravdivé. Jinými slovy, produkuje hodnotu skutečný pokud je alespoň jeden z jeho operandů nepravdivý.

Pravdivá tabulka pro p NAND q (také psáno jako p ↑ q, Dpqnebo p | q) je následující:

Často je užitečné vyjádřit logickou operaci jako slouč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é se berou jako základní nebo „primitivní“ a na operacích, které se berou jako kompozitní nebo „derivativní“.

V případě logického NAND je jasně vyjádřitelný jako sloučenina NOT a AND.

Negace spojky: ¬ (p ∧ q) a disjunkce negací: (¬p) ∨ (¬q) lze uvést do tabulky následovně:

Logické NOR

The logický NOR je úkon na dva logické hodnoty, obvykle hodnoty dvou propozice, který produkuje hodnotu skutečný pokud jsou oba jeho operandy nepravdivé. Jinými slovy, produkuje hodnotu Nepravdivé pokud je alespoň jeden z jeho operandů pravdivý. ↓ je také známý jako Šipka peirce po jeho vynálezci, Charles Sanders Peirce, a je Jediný dostatečný operátor.

Pravdivá tabulka pro p NOR q (také psáno jako p ↓ qnebo Xpq) je následující:

Negace disjunkce ¬ (p ∨ q) a spojení negací (¬p) ∧ (¬q) lze uvést do tabulky následovně:

Kontrola tabulkový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áří stejné vzory funkčních hodnot pro ¬ (p ∧ q) pokud jde o (¬p) ∨ (¬q) a pro ¬ (p ∨ q) pokud jde o (¬p) ∧ (¬q). První a druhý výraz v každé dvojici 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 rovnocennost je jednou z De Morganovy zákony.

Aplikace

Tabulky pravdy lze použít k prokázání mnoha dalších logické ekvivalence. Zvažte například následující tabulku pravdivosti:

Logická ekvivalence: ${ displaystyle (p Rightarrow q) equiv ( lnot p lor q)}$

${ displaystyle p}$	${ displaystyle q}$	${ displaystyle lnot p}$	${ Displaystyle lnot p lor q}$	${ displaystyle p Rightarrow q}$
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 ${ displaystyle p Rightarrow q}$ je logicky ekvivalentní na ${ Displaystyle lnot p lor q}$.

Tabulka pravdivosti pro nejčastěji používané logické operátory

Zde je tabulka pravd, která poskytuje definice 6 nejčastěji používaných z 16 možných pravdivostních funkcí dvou booleovských proměnných P a Q:

P	Q	${ displaystyle P land Q}$	${ displaystyle P lor Q}$	${ displaystyle P { podtržení { lor}} Q}$	${ displaystyle P { podtržení { land}} Q}$	${ displaystyle P Rightarrow Q}$	${ displaystyle P Leftarrow Q}$	${ displaystyle P Leftrightarrow Q}$
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

kde

T

skutečný

F

Nepravdivé

${ displaystyle land}$

A (logická spojka)

${ displaystyle lor}$

NEBO (logická disjunkce)

${ displaystyle { underline { lor}}}$

XOR (exkluzivní nebo)

${ displaystyle { underline { land}}}$

XNOR (exkluzivní ani)

${ displaystyle Rightarrow}$

podmíněné „pokud-pak“

${ displaystyle Leftarrow}$

podmíněné „pak-pokud“

${ displaystyle Leftrightarrow}$

biconditional "if-and-only-if".

Zhuštěné pravdivostní tabulky pro binární operátory

U binárních operátorů se také používá zkrácená forma tabulky pravdy, kde záhlaví řádků a záhlaví sloupců určují operandy a buňky tabulky určují výsledek. Například, Logická logika používá tento zkrácený zápis do tabulky pravdivosti:

Tato notace je užitečná, zejména pokud jsou operace komutativní, i když lze navíc určit, že řádky jsou prvním operandem a sloupce druhým operandem. Tato zkrácená notace je zvláště užitečná při diskusi o vícehodnotových rozšířeních logiky, protože významně snižuje kombinatorickou explozi počtu řádků, které jsou jinak potřebné. Poskytuje také rychle rozeznatelný charakteristický „tvar“ rozložení hodnot v tabulce, což může čtenáři pomoci při rychlejším uchopení pravidel.

Tabulky pravdy v digitální logice

Tabulky pravdy se také používají k určení funkce hardwarové vyhledávací tabulky (LUT) v digitální logické obvody. Pro n-vstup LUT bude mít pravdivostní tabulka 2 ^n hodnoty (nebo řádky ve výše uvedeném tabulkovém formátu), zcela specifikující booleovskou funkci pro LUT. Představováním každé booleovské hodnoty jako a bit v binární číslo, hodnoty tabulky pravdivosti lze efektivně kódovat jako celé číslo hodnoty v elektronická automatizace designu (EDA) software. Například 32bitové celé číslo může kódovat pravdivostní tabulku pro LUT s až 5 vstupy.

Při použití celočíselného vyjádření 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í hodnotou LUT hodnota kth bit celého čísla. Například k vyhodnocení výstupní hodnoty LUT dané pole z n booleovské vstupní hodnoty, bitový index výstupní hodnoty tabulky pravdy lze vypočítat takto: pokud iten vstup je pravdivý, nechť ${ displaystyle V_ {i} = 1}$, jinak ${ displaystyle V_ {i} = 0}$. Pak kth bitem binární reprezentace pravdivostní tabulky je výstupní hodnota LUT, kde ${ displaystyle k = V_ {0} krát 2 ^ {0} + V_ {1} krát 2 ^ {1} + V_ {2} krát 2 ^ {2} + tečky + V_ {n} krát 2 ^ {n}}$.

Tabulky pravdy jsou jednoduchý a přímý způsob kódování booleovských funkcí, ale vzhledem k tomu exponenciální růst vzhledem k tomu, jak se zvyšuje počet vstupů, nejsou vhodné pro funkce s velkým počtem vstupů. Další reprezentace, které jsou paměťově efektivnější, 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ého logického inženýrství a matematiky) lze pravdivostní tabulky použít ke snížení základních booleovských operací na jednoduchou korelaci vstupů s výstupy bez použití logické brány nebo kód. Například binární doplněk může být reprezentován tabulkou pravdy:

A B | C R1 1 | 1 01 0 | 0 10 1 | 0 10 0 | 0 0 kdeA = První operandB = Druhý operandC = CarryR = Výsledek

Tato tabulka pravdy se čte zleva doprava:

• Hodnotový pár (A, B) se rovná hodnotovému páru (C, R).
• Nebo pro tento příklad A plus B stejný výsledek R, s Carry C.

Všimněte si, že tato tabulka nepopisuje logické operace potřebné k implementaci této operace, spíše jednoduše určuje funkci vstupů k výstupním hodnotám.

S ohledem na výsledek lze tento příklad aritmeticky považovat za binární sčítání modulo 2 a za logicky ekvivalentní binární logické operaci exclusive-nebo (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 ale zvýší počet typů hodnot, které lze na vstupech mít, zvětší se velikost pravdivostní tabulky.

Například v operaci přidání potřebujete dva operandy, A a B. Každý může mít jednu ze dvou hodnot, nulu nebo jednu. 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 měl jeden použít základnu 3, velikost by se zvýšila na 3 × 3 neboli devět možných výstupů.

První příklad „sčítání“ výše se nazývá poloviční sčítač. Plná sčítačka je, když je přenos z předchozí operace poskytnut jako vstup do další sčítačky. K popisu a by tedy byla zapotřebí tabulka pravdivosti osmi řádků plný zmije logika:

A B C * | C R0 0 0 | 0 00 1 0 | 0 11 0 0 | 0 11 1 0 | 1 00 0 1 | 0 10 1 1 | 1 01 0 1 | 1 01 1 1 | 1 1 Stejné jako předchozí, ale ... C * = Přenést z předchozího zmije

Dějiny

Výzkum Irving Anellis to ukazuje C.S. Peirce se jeví jako první logik (v roce 1893), který vytvořil matici tabulky pravdivosti.^[4][6] Ze shrnutí jeho příspěvku:

V roce 1997 John Shosky objevil na naopak stránky strojopisného přepisu Bertrand Russell přednáška z roku 1912 na téma "Filozofie logického atomismu", tabulky pravdivostních tabulek. Matice pro negaci je Russellova, vedle níž je matice pro materiální implikaci v rukou Ludwiga Wittgensteina. Je prokázáno, že nepublikovaný rukopis, jehož autorem je Peirce v roce 1893, obsahuje matici tabulky pravdivosti, která je ekvivalentní matici pro materiální implikaci objevené Johnem Shosky. Nepublikovaný rukopis Peirce označil za složený v letech 1883–1884 v souvislosti s kompozicí Peirceova „O algebře logiky: příspěvek k filozofii notace“, která se objevila v American Journal of Mathematics v roce 1885 obsahuje příklad tabulky nepřímé pravdy pro podmíněné.

Poznámky

Viz také

Reference

Citované práce

• Bocheński, Józef Maria (1959), Précis matematické logiky, z francouzského a německého vydání přeložili 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, W.V. (1982), Metody logiky, 4. vydání, Cambridge, MA: Harvard University Press.

externí odkazy

• „Pravdivá tabulka“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Tabulky pravdy, tautologie a logická ekvivalence
• PEIRCEOVA PRAVDIVĚ FUNKČNÍ ANALÝZA A PŮVOD PRAVIDELNÝCH TABULEK Irving H. Anellis
• Převádění tabulek pravdy na booleovské výrazy