Osnovne operacije sa iskazima

Iskaz je rečenica koja sima tačno jednu istinitosnu vrednost - tačno ili netačno. Tačan iskaz označavamo sa $\top$, a netačan sa $\bot$. Istinitosnu vrednost iskaza $p$ zapisujemo kao $\tau(p)$. Na primer, iskaz $2+1=3$ ima vrednost $\tau(2+1=3)=\top$, dok iskaz $2+1=4$ ima vrednost $\tau(2+1=4)=\bot$.

Netačna rečenica i dalje može biti iskaz. Važno je da njena istinitosna vrednost bude jednoznačno određena. Subjektivna rečenica, poput „Jabuke su najukusnije voće”, nije iskaz jer zavisi od ličnog mišljenja. Rečenica čija tačnost zavisi od nedostajućeg podatka takođe nije iskaz. Na primer, bez podatka o godini rečenica „Februar ima 28 dana” nema jednu određenu istinitosnu vrednost.

Sadržaj

1. Osnovne logičke operacije
2. Tablice istinitosti i tautologije
3. De Morganovi zakoni

1. Osnovne logičke operacije

Od jednostavnih iskaza možemo graditi složene iskaze pomoću logičkih operacija. Ako su $p$ i $q$ iskazi, osnovne operacije su:

Operacija	Zapis	Čitanje
Negacija	$\neg p$	nije $p$
Konjunkcija	$p\land q$	$p$ i $q$
Disjunkcija	$p\lor q$	$p$ ili $q$
Implikacija	$p\Rightarrow q$	ako $p$, onda $q$
Ekvivalencija	$p\Leftrightarrow q$	$p$ ako i samo ako $q$

Negacija

Negacija menja istinitosnu vrednost iskaza. Ako je $p$ tačan, $\neg p$ je netačan, a ako je $p$ netačan, $\neg p$ je tačan:

$p$	$\neg p$
$\top$	$\bot$
$\bot$	$\top$

Na primer, negacija iskaza „Broj 7 je prost” glasi „Broj 7 nije prost”. Prvi iskaz je tačan, pa je njegova negacija netačna.

Konjunkcija

Konjunkcija $p\land q$ tačna je samo kada su oba iskaza tačna. Dovoljno je da jedan iskaz bude netačan pa da cela konjunkcija bude netačna.

$p$	$q$	$p\land q$
$\top$	$\top$	$\top$
$\top$	$\bot$	$\bot$
$\bot$	$\top$	$\bot$
$\bot$	$\bot$	$\bot$

Disjunkcija

Disjunkcija $p\lor q$ tačna je kada je bar jedan iskaz tačan. Netačna je samo kada su oba iskaza netačna. Simbol $\lor$ predstavlja uključivo „ili”, pa je disjunkcija tačna i kada su oba iskaza tačna.

$p$	$q$	$p\lor q$
$\top$	$\top$	$\top$
$\top$	$\bot$	$\top$
$\bot$	$\top$	$\top$
$\bot$	$\bot$	$\bot$

Implikacija

U implikaciji $p\Rightarrow q$, iskaz $p$ je pretpostavka, a iskaz $q$ zaključak. Implikacija je netačna samo kada je pretpostavka tačna, a zaključak netačan:

$p$	$q$	$p\Rightarrow q$
$\top$	$\top$	$\top$
$\top$	$\bot$	$\bot$
$\bot$	$\top$	$\top$
$\bot$	$\bot$	$\top$

$$\top\Rightarrow\bot=\bot.$$

U svim ostalim slučajevima implikacija je tačna. Posebno treba zapamtiti da je implikacija sa netačnom pretpostavkom uvek tačna:

$$\bot\Rightarrow\top=\top, \qquad \bot\Rightarrow\bot=\top.$$

Ekvivalencija

Ekvivalencija $p\Leftrightarrow q$ tačna je kada iskazi $p$ i $q$ imaju istu istinitosnu vrednost. Zato su i $\top\Leftrightarrow\top$ i $\bot\Leftrightarrow\bot$ tačni, dok je ekvivalencija iskaza različitih vrednosti netačna.

$p$	$q$	$p\Leftrightarrow q$
$\top$	$\top$	$\top$
$\top$	$\bot$	$\bot$
$\bot$	$\top$	$\bot$
$\bot$	$\bot$	$\top$

Redosled izvršavanja operacija

Kod složenih formula operacije izvršavamo sledećim redosledom:

1. izrazi u zagradama;
2. negacija $\neg$;
3. konjunkcija $\land$;
4. disjunkcija $\lor$;
5. implikacija $\Rightarrow$;
6. ekvivalencija $\Leftrightarrow$.

Zagrade uvek imaju prednost. Kada formula sadrži više operacija, najbezbednije je izračunavati vrednost podformula jednu po jednu i svaki rezultat zameniti sa $\top$ ili $\bot$.

Kada su iskazi $p$, $q$ i $r$ zadati matematičkim ili tekstualnim tvrđenjima, najpre određujemo vrednost svakog od njih. Tek zatim te vrednosti unosimo u složenu formulu.

2. Tablice istinitosti i tautologije

Tablica istinitosti prikazuje vrednost formule za sve moguće kombinacije istinitosnih vrednosti njenih iskaznih slova. Ako formula sadrži $n$ različitih iskaznih slova, tablica ima $2^n$ redova:

Tablicu sastavljamo postupno:

1. ispišemo sve kombinacije vrednosti iskaznih slova;
2. izdvojimo podformule prema zagradama i redosledu operacija;
3. za svaku podformulu napravimo posebnu kolonu;
4. poslednju kolonu popunimo vrednostima cele formule.

Formula koja je tačna za svaku kombinaciju istinitosnih vrednosti naziva se tautologija. Ako je formula netačna za svaku kombinaciju, naziva se kontradikcija. Formula koja je za neke kombinacije tačna, a za neke netačna nije tautologija.

Da bismo dokazali da formula nije tautologija, nije potrebno proveravati sve redove ako pronađemo jednu kombinaciju za koju je formula netačna. Takva kombinacija naziva se kontraprimer.

3. De Morganovi zakoni

De Morganovi zakoni opisuju kako negacija deluje na konjunkciju i disjunkciju:

$$\neg(p\land q)\equiv\neg p\lor\neg q,$$ $$\neg(p\lor q)\equiv\neg p\land\neg q.$$

Kada negaciju prenesemo preko zagrade, svako iskazno slovo se negira, a operacija se menja:

• $\land$ prelazi u $\lor$;
• $\lor$ prelazi u $\land$.

Prvi zakon kaže da konjunkcija $p\land q$ nije tačna kada je bar jedan od iskaza netačan. Zato negacija konjunkcije znači da je netačan $p$ ili da je netačan $q$.

Drugi zakon kaže da disjunkcija $p\lor q$ nije tačna samo kada su oba iskaza netačna. Zato negacija disjunkcije znači da je netačan $p$ i da je netačan $q$.

De Morganovi zakoni važe i za više iskaza:

$$\neg(p\land q\land r) \equiv\neg p\lor\neg q\lor\neg r,$$ $$\neg(p\lor q\lor r) \equiv\neg p\land\neg q\land\neg r.$$

Provera pomoću tablice istinitosti

Oba zakona možemo proveriti u jednoj tablici:

$p$	$q$	$\neg(p\land q)$	$\neg p\lor\neg q$	$\neg(p\lor q)$	$\neg p\land\neg q$
$\top$	$\top$	$\bot$	$\bot$	$\bot$	$\bot$
$\top$	$\bot$	$\top$	$\top$	$\bot$	$\bot$
$\bot$	$\top$	$\top$	$\top$	$\bot$	$\bot$
$\bot$	$\bot$	$\top$	$\top$	$\top$	$\top$

Kolone $\neg(p\land q)$ i $\neg p\lor\neg q$ jednake su u svakom redu. Isto važi za kolone $\neg(p\lor q)$ i $\neg p\land\neg q$. Zato su obe ekvivalencije tautologije.