Tipovi dokaza:
p → q se dokazuje tako što se pretpostavi
da je p tačno i onda pokaže da iz toga sledi da je q tačno;p → q dokazuje se
njena kontrapozicija ¬q → ¬p;p → q je tačna
ukoliko je p uvek netačno - ovo nazivamo besmislenim dokazom ili
ukoliko je q uvek tačno - ovo nazivamo trivijalnim dokazom;p dokazujemo tako što pretpostavimo
suprotno - da je tačno ¬p i iz toga izvedemo kontradikciju;(p1 ∨ ... ∨ pn) → q dokazujemo
tako što pokazujemo da važi: p1 → q ∧ ... ∧ pn → q;p ↔ q dokazujemo tako što
dokazujemo p → q i q → pDokazati tvrdjenje P(0), ako je sa P(n) označeno tvrdjenje:
"ako je n pozitivan ceo broj veći od 1, tada je n² > n".
Koji tip dokaza se koristi?
Dokazati tvrdjenje P(1), ako je sa P(n) označeno tvrdjenje:
"ako su a i b pozitivni celi brojevi, tada je
(a + b)ⁿ ≥ aⁿ + bⁿ". Koji tip dokaza se koristi?
Dokazati da ako je n prirodan broj i n³ + 5 je neparno,
tada je n parno, koristeći:
Rešenje:
Dokazujemo tvrdjenje oblika p → q korišćenjem kontrapozicije ovog
tvrdjenja. U ovom primeru to znači da pretpostavimo da n nije
parno i hoćemo da dokažemo da onda n³ + 5 nije neparno, tj. da
je parno. Ako n nije parno, a prirodan je broj, to znači da je n
neparno, tj može se predstaviti u obliku: n = 2k − 1, k ∈ N.
Tada je n³ + 5 = (2k-1)³ = 8k³ - 12k^2 + 6k - 1 + 5, to jest parno je.
p → q tako što pretpostavimo suprotno,
da tvrdjenje nije tačno. To znači da važi:
¬(p → q) = ¬(¬p ∨ q) = p ∧ ¬q.
U ovom primeru to znači da pp da važi da je n³ + 5 neparno
i da je n neparno. Na osnovu dela pod (1.) izveli smo da ako je n
neparno, onda je n³ + 5 parno. Kontradikcija. Sledi da je polazno
tvrdjenje tačno.Dokazati da postoji 100 uzastopnih prirodnih brojeva koji nisu kvadrati nekog broja. Da li je dokaz konstruktivan ili nekonstruktivan?
Uputstvo: Izmedju 1002 i 1012 postoji više od 100 brojeva, a oni nisu kvadrati nekog prirodnog broja.
Dokazati ili opovrgnuti da postoji racionalan broj x i iracionalan broj y,
tako da je broj xʸ iracionalan.
Uputstvo: Razmotriti slučaj brojeva: x = 2, y = √2.
Dokazati da je proizvod dva od brojeva
65¹⁰⁰⁰ - 8²⁰⁰¹ + 3¹¹⁷, 79¹²¹² - 9²³⁹⁹ + 2²⁰⁰¹ i 24⁴⁴⁹³ - 5⁸¹⁹² + 7¹⁷¹⁷
nenegativan.
Dokazati da je najmanje jedan od brojeva a₁, a₂, ..., aₙ veći
ili jednak srednjoj vrednosti ovih brojeva. Koju vrstu dokaza koristimo?
Uputstvo: Pretpostavimo suprotno i izvedimo dokaz kontradikcijom
Ako je prvih deset prirodnih brojeva smešteno oko kruga u proizvoljnom rasporedu, tada postoje tri broja na susednim lokacijama koja imaju zbir veći ili jednak od 16.
Uputstvo: Pretpostavimo suprotno i izvedimo dokaz kontradikcijom. Iskoristiti činjenicu da ako za proizvoljan raspored brojeva oko kruga sumiramo sve moguće trojke uzastopnih brojeva, dobijamo trostruki zbir svih brojeva koji se rasporedjuju oko kruga.
Dokazati nejednakost trougla koja tvrdi da za realne brojeve x i y važi:
|x| + |y| ≥ |x + y|.
Uputstvo: Koristimo dokaz po slučajevima:
x ≥ 0 ∧ y ≥ 0x < 0 ∧ y < 0x ≥ 0 ∧ y < 0
x ≥ −yx < −yx < 0 ∧ y ≥ 0
x ≥ −yx < −yDokazati da ako su x i y realni brojevi, onda važi:
max(x, y) + min(x, y) = x + y.
Dokazati da se četvrti stepen celog broja završava na 0, 1, 5 ili 6.
Neka su a i b neparni celi brojevi tako da je a ≠ b. Pokazati da postoji
jedinstveni ceo broj c tako da važi: |a − c| = |b − c|.
Rešenje: Jednačina |a − c| = |b − c| je ekvivalentna dvema jednačinama:
a − c = b − c i a − c = −(b − c). Prva otpada kao rešenje jer je uslov
zadatka da je a ≠ b. Druga jednačina daje rešenje c = (a + b)/2, pri čemu
c jeste ceo broj jer su a i b prema pretpostavci zadatka neparni brojevi, te
je njihov zbir paran broj. Ovim se dobija jedinstveno rešenje problema.