Таблица на вистинитост

Таблица на вистинитост математичка таблица која се употребува во логиката, особено во Буловата алгебра, Буловите функции и логичките искази за да се пресмета функционалната вредност на логичките изрази на секој од нејзините функционални аргументи, а тоа е секоја комбинација од вредности дадена за нејзините логички променливи. Освен тоа, таблицата на вистинитост може да се користи за да се каже дали еден логички исказ е вистинит за сите можни вредности, што ја претставува валидноста.

Вовед

уреди

Според некои докази, таблиците на вистинитост биле Фрегеви, Персови и Шредерови од 1880 година. Таблиците биле значајни во литературата од 1920 (Лукасјевич, Пост, Витгенштајн) (Квајн, 39). Луис Керол ги создал таблиците на вистинитоста порано од 1894 година за да реши неколку проблеми, но неговите ракописи со неговата работа над предметот не биле откриени сè до 1977 година [1]. Во Витгејнштајновиот Логико-филозофски трактат логичките функции се поделени во серии. Големото влијание на ова дело довело до брзо ширење на примената на логичките таблици.

Таблиците на вистинитост се применуваат во пресметувањето на вредностите на логичките изрази како делотворен начин, којшто понекогаш е познат како проблем на одлучување. Логичкиот израз е или атомска формула, логичка константа, логичка променлива или логичка функција (на пр. Px или P(x)) или составено од атомските формули со значење на логичките операции, како на пример И ( ), ИЛИ ( ), НЕ ( ). На пример,   е логички израз.

Почетната колона на таблицата на вистинитост ги покажува (i) логичките функции со и/или променливите и (ii) вистинито-функционален израз составен од овие логички функции или променливи и операции. Редиците покажуваат дека секоја можна вредност на т или се стреми до (i) и (ii). Со други зборови секој ред е точно определен за (i) и (ii).

Таблиците на вистинитост за класичната логика се ограничени на Буловите логички системи, во кои само две логички вредности се можни, точно или неточно, често претставени со Т и , или понекогаш со 0 и 1.

Логички операции

уреди

Логичка негација

уреди

Негацијата е операција над една логичка вредност, обично вредност на исказ, кој има вредност точно, ако е невистинит и неточно, ако е вистинит.

Таблицата на вистинитост за p (~p) е следнава:

Негација
   
т
т

Логичка конјункција

уреди

Логичката конјункција е операција над две логички вредности, обично вредност на исказ, која има вредност точно само ако и двата искази се вистинити.

Таблицата на вистинитост за p ∧ q (p и q или p q) е следнава:

Логичка конјункција
      .  
т т т
т
т

Кога и двата искази, p и q се вистинити, тогаш конјункцијата pq е точна. Во сите други случаи логичката вредност за исказите p и q, конјункцијата pq е неточна.

Може да се рече, ако p, тогашpq е q или обратно, pq е p.

Логичка дисјункција

уреди

Логичката дисјункција е операција над две логички вредности, обично вредност на исказ, која има вредност неточно ако и само ако и двата искази се невистинити.

Таблицата на вистинитост за p или q ( p ∨ q, p || q или p + q) е следнава:

Логичка дисјункција
     
т т т
т т
т т

Ако p, тогаш pq е p и обратно, pq е q.

Логичка импликација

уреди

Логичката импликација е операција над две логички вредности, обично вредност на исказ, која има вредност неточно само во случај кога првиот исказ е вистинит, а вториот невистинит.

Таблицата на вистинитост за материјалниот услов не само p туку и q (со симболи p → q) и логичката импликација p имплицира q (со симболиp ⇒ q) е следнава:

Логичка импликација
      
т т т
т
т т
т

Логичка еквиваленција

уреди

Логичката еквиваленција е операција над две логички вредности, обично вредност на исказ, која има вредност точно само во случај кога и двата искази се вистинити или невистинити.

Таблицата на вистинитост за p ↔ q ( p = q или p ≡ q) е следнава:

Логичка еквиваленција
      
т т т
т
т
т

Исклучителна дисјункција

уреди

Исклучителната дисјункција е операција над две логички вредности, обично вредност на исказ, која има вредност точно само ако еден, но не и двата искази е вистинит.

Таблицата на вистинитост за p ЕКСИЛИ q ( p + q, p ⊕ q или p ≠ q) е следнава:

Исклучителна дисјункција
      
т т
т т
т т

За два искази, ЕКСИЛИ може да се запише како (p = 1 ∧ q = 0) ∨ (p = 0 ∧ q = 1).

Шеферова црта

уреди

Шеферовата црта е операција над две логички вредности, обично вредност на исказ, која има вредност неточно ако и само ако и двата искази се вистинити. Со други зборови, исказот има вредност точно ако и само ако најмалку еден од исказите е невистинит.

Таблицата за вистинитост за p НИ q (p | q или p ↑ q) е следнава:

Шеферова црта
      
т т
т т
т т
т

Ова доста се применува за да се изрази логичката операција како пресметковна операција која е составена од други операции. Многу состави се можни, зависно од операциите кои се земени за основни или „примитивни“ и операциите кои се земени како сложени или „изведени“.

Во случајот со Шеферовата црта, јасно изразливо е како пресметка на НЕ и И.

Негацијата од конјункцијата   и дисјункцијата од негациите   се претставени во табелата:

             
т т т
т т т т
т т т т
т т т т

Заедничка негација

уреди

Заедничката негација е операција над две логички вредности, обично вредност на исказ, која има вредност точно ако и само ако и двата искази се невистинити. Со други зборови, исказот има вредност неточно ако и само ако еден од исказите е вистинит.

Таблицата на вистинитост за p НИЛИ q (p ⊥ q или p ↓ q) е следнава:

Заедничка негација
      
т т
т
т
т

Негацијата од дисјункцијата  и конјункцијата од негациите   се претставени во табелата:

             
т т т
т т т
т т т
т т т т

Прегледот на табеларните изведувања НИ и НИЛИ, под секое одредување на логичката вредност за функционалните аргументи   и  дава идентични примери за функционални вредности за   како за   и за   како за  . Освен првите и вторите изрази, во секој пар има логички еквивалент и може да биде заменет со секој друг во сите контексти кои припаѓаат единствено на нивната логичка вредност.

Оваа еквиваленција е една од Де Моргановите закони.

Примена

уреди

Таблиците за вистинитост може да се употребуваат за да се докажат многу логички еквиваленции. На пример, набљудувајќи ја следнава таблица на вистинитост:

Логичка еквиваленција : (p → q) = (p ∨ q)
p q p p ∨ q p → q
т т т
т т т т
т
т т т т

Ова го потврдува фактот дека pq е логичка еквиваленција за pq.

Таблицата за вистинитост за најупотребуваните логички оператори

уреди

Ова е таблица на вистинитост за шесте најприменувани од шеснаесетте можни вистинитосни функции за 2 бинарни променливи (P,Q се Булови променливи):

               
т т т
т т т т
т т т т
т т т т т т т
т = точно,⊥ = неточно
  = И (логичка конјункција)
  = ИЛИ (логичка дисјункција)
  = ЕКСИЛИ (исклучителна дисјункција)
  = НИЛИ (исклучителна негација)
  = импликација „ако-тогаш“
  = импликација „тогаш-ако“
  двојната импликација или „ако и само ако“ е логичка еквиваленција за  : НИЛИ (исклучителна негација).

Џонстоновите дијаграми, слични на Веновите дијаграми и Ојлеровите дијаграми, обезбедуваат начин за создавање на таблица на вистинитоста. Интерактивниот Џонстонов дијаграм ја илустрира таблицата на вистинитост на Logicтutorial.com Архивирано на 27 август 2005 г.

Кондензирани таблици на вистинитост за бинарни оператори

уреди

За бинарните оператори, се употребува кондензираната форма на таблица на вистинитоста, каде воведните редови и колони се однесуваат на исказите, а таблицата дава специфични резултати. На пример, Буловата логика користи кондензирана таблица на вистинитост:

т
т т
т
т
т т т

Оваа нотација е корисна, особено ако операциите се комутативни, иако една може дополнително да наведе дека редовите се првиот исказ, а колоните вториот. Оваа кондензирана нотација е делумно корисна во претставувањето на повеќевредносните опсези на логиката, како што значително го пресекува на комбинаторната експлозија на бројот од редовите кој е потребен. Тоа исто така обезбедува за брзо препознатливите одлики „облик“ на пренесувањето на вредностите во табелата, што може да му помогне на читателот да ги сфати правилата за кратко време.

Таблици на вистинитост во дигиталната логика

уреди

Таблиците на вистинитост се користат и во функционирањето на хардверските look-up табели во дигиталната електроника. За n-влезниот LUт, таблицата на вистинитост има 2^n вредности (или редови во горниот табеларен формат), целосно наведувајќи ја Буловата функција за LUт. Со претставување на секоја Булова вредност како бит во бинарен број, вредностите во таблицата на вистинитост може да бидат успешно шифрирани како цел број во EDA софтверот. На пример, 32-битен цел број може да биде шифриран со таблицата на вистинитост за LUт со 5 влеза.

При користењето на цел број претставен во таблицата на вистинитост, влезната вредност на LUт може да се добие со пресметување на битниот индекс k, кој се наоѓа на вредноста на влезот на LUт, во кој случај вредноста на влезот на LUт е kти бит на цел број. На пример, за да се вреднува вредноста на влезот LUт даден на низата од n Буловите влезни вредности, индексот на битот на влезната вредност во таблицата на вистинитост може да биде пресметан на следниот начин: ако iтиот влез е вистинит, нека Vi = 1 и нека Vi = 0. Тогаш kтиот бит од бинарното претставување на таблицата на вистинитост е влезната вредност на LUт, каде k = V0*2^0 + V1*2^1 + V2*2^2 + ... + Vn*2^n.

Таблиците на вистинитост се едноставни и лесни за да се шифрираат Буловите функции, и покрај дадениот експоненцијален раст во обем како број на зголемување на влезовите, тие не одговараат за функции со голем број на влезови. Други успешни претставувања се текстуалните равенки и бинарниот дијаграм на одлучување.

Примена на таблиците на вистинитост во дигиталната електроника

уреди

Во дигиталната електроника (информатиката, полиња на инженерството со примена на логика и математика), таблиците на вистинитост може да се применат за да се намалат основните Булови операции до едноставни корелации меѓу влезовите и излезите, без употребата на логички порти или шифри. На пример, бинарниот додаток може да биде претставен со таблица на вистинитост:

A B | C R
1 1 | 1 0
1 0 | 0 1
0 1 | 0 1
0 0 | 0 0

каде

A = прв исказ
B = втор исказ
C = изведување 
R = резултат

Оваа таблица на вистинитост се чита од лево кон десно:

  • Вредноста на парот (A,B) е еднаква со вредноста на парот (C,R).
  • Или за овој пример, A + B = R + C.

За одбележување е дека ова не ги опишува логичките операции потребни за воведување на оваа операција, отколку што е едноставно наведена функцијата меѓу вредноста на влезот и излезот.

Во овој случај, може да се употребува само за многу едноставни влезови и излези, како 1 и 0, но ако бројот на видови на вредности на влезови се зголеми, големината на таблицата на вистинитост ќе се зголеми.

На пример, во додатна операција, се јавува потребата од два искази, А и B. Секој може да има една од двете вредности, нула или еден. Бројот на комбинации од овие две вредности е 2x2, односно 4. Па, резултатот е 4 можни излези за C и R. Ако еден се користеше со основа 3, тогаш големината би се зголемила на 3x3, односно 9 можни излези.

Првиот „додавач“, примерот горе е наречен полудодавач. Целиот додавач е кога изведувањето од претходната операција е обезбедено како влез до следниот додавач. Освен тоа, таблицата на вистинитост од осум редови треба да се опише како логика на целосен додавач:

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

Исто како претходно, но ... 
C* = изведување од претходниот додавач

Поврзано

уреди
Основни логички оператори
Поврзани теми

Наводи

уреди
  1. „архивски примерок“. Архивирано од изворникот на 2006-09-25. Посетено на 2009-02-16.

Користена литература

уреди
  • Quine, W.V. (1982), Methods of Logic, IV издание, Harvard University Press, Cambridge, MA.

Надворешни врски

уреди