Tablice istinitosti
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
Logički identitet uredi
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:
| p | p |
|---|---|
| tvrdnja | vrednost |
| T | T |
| F | F |
Logička negacija uredi
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) :
| p | ¬p |
|---|---|
| T | F |
| F | T |
Binarne operacije uredi
Tablica instinitosti za sve binarne logičke operacije uredi
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
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:
| p | q | p ∧ q |
|---|---|---|
| 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 p ∧ q tačna, u suprotnom je lažna.
Može se takođe reći da ako p onda p ∧ q sledi q u suprotnom p ∧ q sledi p
Logička disjunkcija uredi
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:
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Prosto srpski, ako p, onda p ∨ q je p, u suprotnom p ∨ q je q.
Logička implikacija uredi
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:
| p | q | p → q |
|---|---|---|
| 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
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:
| p | q | p ≡ q |
|---|---|---|
| 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
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:
| p | q | p ⊕ q |
|---|---|---|
| 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
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:
| p | q | p ↑ q |
|---|---|---|
| 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
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:
| p | q | p ↓ q |
|---|---|---|
| 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
Tablice istinitosti se mogu koristiti za dokazivanje raznih logičkih ekvivalencija, kao na primer:
| p | q | ¬p | ¬p ∨ q | p → q |
|---|---|---|---|---|
| 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 p → q logično ekvivalentno ¬p ∨ q.
Tablica istinitosti za najčešće korišćene operatore uredi
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
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:
|
|
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
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
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
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
Reference uredi
- ^ 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.
- ^ Post, Emil (1921). „Introduction to a general theory of elementary propositions”. American Journal of Mathematics. 43 (3): 163—185. JSTOR 2370324. doi:10.2307/2370324. hdl:2027/uiuo.ark:/13960/t9j450f7q.
Literatura uredi
- 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. Nedostaje ili je prazan parametar
|title=(pomoć). - Quine, W.V. (1982), Methods of Logic, 4th edition, Cambridge, MA: Harvard University Press.
Dodatna literatura uredi
Spoljašnje veze uredi
- Hazewinkel Michiel, ur. (2001). „Truth table”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104.
- Truth Tables, Tautologies, i Logic equivalence
- Online Truth Table Generator