Tablice istinitosti

S Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

Tablica istinitosti je matematička tablica korišćena u logici — posebno u kombinaciji sa Bulovom algebrom. Praktično, tablice istinitosti se koriste da bi utvrdili da li je predloženi izraz istinit za date vrednosti, tj da li je logički tačan ili lažan.

Tablica istinitosti je sačinjena od jedne kolone za svaku zadatu promenljivu (na primer, A ili B), i jedne konačne kolone za sve moguće rezultate logičkih operacija koje je tabela trebalo da predstavi (na primer, A, eks ili B). Svaki red tablice sadrži po jednu moguću kombinaciju zadatih parametara i njihovog jedinstvenog rešenja. Pogledajte primere radi boljeg razumevanja.[1][2]

Unarne operacije[uredi | uredi izvor]

Logički identitet[uredi | uredi izvor]

Logički identitet je logička operacija na jednoj logičkoj vrednosti, tipično vrednost tvrdnje, koji može biti tačan ukoliko je vrednost tačna ili lažan ukoliko je vrednost lažna. - Tablica istinitosti za logički identitet izgleda ovako:

Logički identitet
p p
tvrdnja vrednost
T T
F F

Logička negacija[uredi | uredi izvor]

Logička negacija je logička operacija na jednoj logičkoj vrednosti, tipično vrednost tvrdnje , koja proizvodi vrednost tačno ili lažno.

Tablica instinitosti za Ne p (drugačije ¬p, Np, Fpq, ili ~p) :

Logička negacija
p ¬p
T F
F T

Binarne operacije[uredi | uredi izvor]

Tablica instinitosti za sve binarne logičke operacije[uredi | uredi izvor]

Ovde imamo tablicu instinitosti koja nam definiše svih 16 mogućih istinitosnih funkcija za 2 binarne vrednosti (P,Q su logičke vrednosti):

P Q  F0   NILI1   Xq2   ¬p3   4   ¬q5   HILI6   NILI7   I8   XNILI9  q10 ako/onda11 p12 onda/ako13 I14 T15
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

Gde je T = tačno i F = netačno.

Ključ:

Naziv operacije
0 Opq F lažno Kontradikcija
1 Xpq NILI Logičko NILI
2 Mpq Xq Inverzna neimplikacija
3 Fpq Np ¬p Negacija
4 Lpq Xp Materijalna neimplikacija
5 Gpq Nq ¬q Negacija
6 Jpq XI Isključiva disjunkcija
7 Dpq NI Logočko NI
8 Kpq I Logičko raskršće
9 Epq XNI ako i samo ako Logički biokondicional
10 Hpq q Funkcija projekcije
11 Cpq XNp ako/onda Materijalna implikacija
12 Ipq p Funkcija projekcije
13 Bpq XNq onda/ako Obrnuta implikacija
14 Apq ILI Logička disjunkcija
15 Vpq T tačno Tautologija

Logičke operacije se mogu vizualizovati korišćenjem Venovog dijagrama.

Logička konjunkcija[uredi | uredi izvor]

Logička konjunkcija je logička operacija na dve logičke vrednosti, tipično vrednosti dva predloga, koja proizvodi vrednost tačno ako su obe operacije tačne.

Tablica istinitosti za p i q (drugačije napisani p ∧ q, Kpq, p & q, ILI p q) izgleda ovako:

Logička konjunkcija
p q pq
T T T
T F F
F T F
F F F

Prostim jezikom, ako su obe vrednosti p i q tačne, onda je konjunkcija pq tačna, u suprotnom je lažna.

Može se takođe reći da ako p onda pq sledi q u suprotnom pq sledi p

Logička disjunkcija[uredi | uredi izvor]

Logička disjunkcija je logička operacija na dve logičke vrednosti, tipično vrednost dva predloga, tako da daju vrednost tačno ukoliko je bar jedan od operanata tačan.

Tablica istinitosti za p ILI q (takođe definisana kao p ∨ q, Apq, p || q, ILI p + q) izgleda ovako:

Logička disjunkcija
p q pq
T T T
T F T
F T T
F F F

Prosto srpski, ako p, onda pq je p, u suprotnom pq je q.

Logička implikacija[uredi | uredi izvor]

Logička implikacija i materijalni kondicional su povezani sa logičkom operacijom na dve logičke vrednosti, tipično vrednosti predloga, koji ima vrednost lažno kao su singularnom slučaju kada je jedan operant tačan a drugi lažan.

Tablica istinitosti povezana sa materijalnim kondicionalom ako p onda q (označeno i kao p → q) i logička implikacija p implicira q (označeno i kao p ⇒ q, ILI Cpq) izgleda ovako:

Logička implikacija
p q pq
T T T
T F F
F T T
F F T

Korisno je reći da p → q je ekvivalentno ¬p ∨ q.

Logička jednakost[uredi | uredi izvor]

Na engleskom Logical equality,biconditional. (detanjnije informacije na engleskoj vikipediji) Logička jednakost (takođe poznata kao bikondicional, materijalni biokondicional) je logička operacija na dve logičke vrednosti, tipično vrednost dva predloga, koja proizvodi vrednost tačno ako su ova operanta lažna ili oba su tačna.

Tablica istinitosti za p HNI q (takođe označeno kao p ↔ q, Epq, p = q, ILI p ≡ q) izgleda ovako:

Logička jednakost
p q pq
T T T
T F F
F T F
F F T

Znači p EQ q je tačno ako su p i q oba tačna ili oba lažna, i lažna ako imaju različite istinitosne vrednosti.

Isključiva disjunkcija[uredi | uredi izvor]

Isključiva disjunkcija je logička operacija na dve logičke vrednosti, tipično vrednost dva predloga, koja proizvodi vrednost tačno ako je bar jedan od operanata istinit tj tačan.

Tablica istinitosti za p HILI q (takođe označeno kao p ⊕ q, Jpq, ILI p ≠ q) izgleda ovako:

Isključiva disjunkcija
p q pq
T T F
T F T
F T T
F F F

za dva predloga, HILI može da se napiše ovako (p = 1 ∧ q = 0) ∨ (p = 0 ∧ q = 1).

Logičko NI[uredi | uredi izvor]

Logičko NI je logička operacija na dve logičke vrednosti, tipično vrednost dva predloga, koja proizvodi vrednost lažno ako su oba operanta tačna. Drugim rečima, daje vrednost tačno ako je bar jedan od operanata lažan.

Tablica istinitosti za p NI q (takođe označeno kao p ↑ q, Dpq, ILI p | q) izgleda ovako:

Logičko NI
p q pq
T T F
T F T
F T T
F F T

Često složenije operacije mozemo izraziti kombinacijom elementarnih.

Logičko NI je očigledno NE I I.

Negacija konjunkcije: ¬(p ∧ q), i disjunkcija negacije: (¬p) ∨ (¬q) mogu se prikazati na sledeći način:

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

Logičko NILI[uredi | uredi izvor]

Logičko NILI je logička operacija na dve logičke vrednosti, tipično vrednost dva predloga, koja proizvodi vrednost tačno ako su oba operanta lažna. Drugim rečima, daje vrednost lažno ako je bar jedan od operanata tačan. ↓ je takođe poznato kao Pirsova strelica po pronalazaču , Čarls Sanders Pers , i naziva se samo zadovoljavajući operator.

Tablica istinitosti za p NILI q (takođe označeno kao p ↓ q, Xpq, ILI p ⊥ q) izgleda ovako:

Logičko NILI
p q pq
T T F
T F F
F T F
F F T

Negacija disjunkcije ¬(p ∨ q), i konjunkcija negacije (¬p) ∧ (¬q) mogu se prikazati ovako:

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

Obratite pažnju na jednakost vrednosti za ¬(p ∨ q) i ¬(p ∧ q). Ova jednakost je jedna od, i objašnjena je u De morganovim zakonima

Korišćenje[uredi | uredi izvor]

Tablice istinitosti se mogu koristiti za dokazivanje raznih logičkih ekvivalencija, kao na primer:

Logička ekvivalencija : (pq) = (¬pq)
p q ¬p ¬pq pq
T T F T T
T F F F F
F T T T T
F F T T T

Ovo demonstrira činjenicu da je pq logično ekvivalentno ¬pq.

Tablica istinitosti za najčešće korišćene operatore[uredi | uredi izvor]

Ovo je tablica koja daje definicje najčešće korišćenih 6 operanata.

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

Ključ:

T = tačno, F = lažno
= I (Logička konjunkcija)
= ILI (Logička disjunkcija)
= HILI (ekskluzivno ILI)
= HNILI (ekskluzivno NILI)
= kondicional "ako-onda"
= kondicional "(onda)-ako"
bikondicional ILI "ako-i-samo-ako" je logička ekvivalencija : HNILI (ekskluzivno NILI).

Logički operatori mogu biti vizualizovani pomoću Venovog dijagrama.

Podrazumevane tablice istinitosti za binarne operatore[uredi | uredi izvor]

Za binarne operatore, se takođe koristi skraćena forma istinitosne tablice, gde nazivi redova i kolona ukazuju na operatore i ćelije tablice ukazuju na rezultat. Na primer Boolean logika koristi ovu sažetu notacuju tablicu istinitosti:

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

Ova notacija je korisna pogotovo ako su operacije komutativne, iako se može dodatno specifikovati da su redovi prvi operand a kolone su drugi. Ova uproscena notacija je pogotovo korisna u diskutovanju logičkih ekstenzija sa više vrednosti, jer značajno smanjuje broj redova koji nam je drugačije potreban. Takođe nam daje i preglednost.

Tablice istinitosti u digitalnoj logici[uredi | uredi izvor]

Tablice istinitosti se takođe koriste da specifikuju funkcionalnost hardverske look-up tablice(LUT)]] u digitalnoj logici. Za n-unos LUT, tablica istinitosti će imati 2^n vrednosti (ili redova u goreprikazanom tabularnom formatu), potpuno specifikujući boolean funkciju za LUT. Predstavljajući svaku boolean vrednost kao bit u binarni broj, vrednost u istinitosnoj tablici se može efikasno kodirati kao intedžer vrednost u automizaciji elektronskog dizajna (EDA) softver. Na primer, 32-bitni intidžer može da se kodira istinitosnu tablicu za LUT sa do 5 unosa.

Kad se koristi intidžer reprezentaciju za istinitosnu tablicu, izlazna vrednost LUT se može dobiti računanjem bitnog indeksa k baziranog na ulaznim vrednostima LUT, u tom slučaju LUT 'ova izlazna vrednost je k'ti bit intidžera.

Na primer, da bismo ispitali izlaznu vrednost LUT 'a datog u nizu od n boolean ulaznih vrednosti, bitni ideks izlaznih vrednosti tablice istinitosti može biti izračunat na sledeći način: ako je iti unos tačan, neka Vi = 1, u suprotnom neka Vi = 0. Onda će kti bit binarne reprezentacije tablice istinitosti biti i LUT'ova izlazna vrednost, gdek = V0*2^0 + V1*2^1 + V2*2^2 + ... + Vn*2^n.

Tablice istinitosti su jednostavne i praktičan način enkodovanja boolean funkcija, međutim sa eksponencijalnim rastom kako se broj ulaza poveđava, nisu baš praktične i pregledne. Druge reprezentacije koje su više efikasne, memorijski su tekstualne jednačine i binarni dijagram.

Primena tablica istinitosti u digitalnoj elektronici[uredi | uredi izvor]

U digitalnoj elektronici i računarskim naukama, tablice istinitosti se mogu koristiti da smanje osnovne bulove operacije bez upotrebe logičke kapije ili koda.

Na primer binarno sabiranje se može predstaviti sledećom tablicom istinitosti:

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

где

A = Први операнд
B = Други операнд
C = Пренос
R = Резултат

Ova tablica istinitosti se čita sleva nadesno:

  • Vrednost para (A,B) jednak je vrednosti para (C,R).
  • Ili na ovom primeru, A+B = R, sa prenosom C.

Obratite pažnju da ova tablica ne opisuje logičke operatore potrebne za implementaciju ove operacije, pre ona naglašava funkciju odnosa vrednosti unosa i izlaza

Ovo rešenje može se gledati i aritmetički kao moduo 2 binernog sabiranja, i kao logički ekvivalent ekskluzivnom ili tj ekskluzivnoj disjunkciji.

U ovom slučaju može se uzeti za samo veoma jednostavne ulazne i izlazne vrednosti, kao sto su 1 i 0, ipak kako se broj promenljivih povećava tako će i tablica rasti.

Na primer , u operaciji sabiranja, potrebna su dva operanta, A i B. Svaki od njih može da ima jednu od dve vrednosti, 0 ili 1 . Broj kombinacija je 2h2, ili 4. TJ, imamo 4 moguća izlaza za S i R. Ako bi za bazu koristili 3, veličina bi bila 3h3, iliti 9 mogućih rešenja.

Prvi primer sabiranja se zove polu-sabirač. Potpuni-sabirač dobijamo kada prenos iz prethodne operacije upotrebimo kao ulaz za sledeće sabiranje. Za to nam je potrebna tablica istinitosti od 8 redova kako bismo opisali problem.

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* = Пренос из претходног додавања

Istorija[uredi | uredi izvor]

Irving Anellis je uradio istraživanje da pokaze da je C.S. Pierce najraniji logičar(1893). Citat iz teksta:

Džon Šoski je, gledajući zadnju stranu Bertrand Raselovog predavanja o Filozofiji Logičkog Atomizma, 1997 godine otkrio matrice tablice istinitosti. Matrica za negaciju je Raselova, u skladu je sa matricom za materijalnu implikaciju, koja je delo Vitgenštajna. Pokazano je da jedan neobjavljeni Pirsov rukopis iz 1893 sadrži tablicu istinitosti koja je ekvivalentna matrici materijalne implikacije koju je otkrio Džon Šoski. Neobjavljeni Pirsov rukopis, za koji je pokazano da potiče iz 1883-84, u vezi sa Pirsovim delom „O Algebri Logike: Doprinos Filozofiji Notacije“, objavljenom u American Journal of Mathematics iz 1885, sadrži u sebi primer indirektne tablice istinitosti za kondicional.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ Georg Henrik von Wright (1955). „Ludwig Wittgenstein, A Biographical Sketch”. The Philosophical Review. 64 (4): 527—545 (p. 532, note 9). JSTOR 2182631. doi:10.2307/2182631. 
  2. ^ Emil Post (1921). „Introduction to a general theory of elementary propositions”. American Journal of Mathematics. 43 (3): 163—185. JSTOR 2370324. doi:10.2307/2370324. 

Literatura[uredi | uredi izvor]

  • Bocheński, Józef Maria (1959), A Précis of Mathematical Logic, translated from the French i German editions by Otto Bird, Dordrecht, South Holland: D. Reidel.
  • Enderton, H. (2001). A Mathematical Introduction to Logic, second edition, New York: Harcourt Academic Press. ISBN 978-0-12-238452-3.
  • Quine, W.V. (1982), Methods of Logic, 4th edition, Cambridge, MA: Harvard University Press.

Spoljašnje veze[uredi | uredi izvor]