Logika, skupovi i dokazivanje
Ovaj dio ispituje jezik matematike: tvrdnje, kvantifikatore, logičke operacije, skupove i osnovne tehnike dokazivanja. Traži se negiranje tvrdnje, provjera ekvivalencije, računanje sa skupovima i razlikovanje dokaza od provjere nekoliko primjera. Točan zapis i jasno navedene pretpostavke dio su rješenja.
Pravila
- Negacija univerzalne tvrdnje za svaki x vrijedi P(x) je postoji x za koji ne vrijedi P(x). Negacija egzistencijalne tvrdnje je univerzalna negacija.
- A⇒B nije isto što i B⇒A; obrat treba dokazati zasebno.
- Skupovne operacije: A∪B, A∩B, A∖B, komplement Aᶜ. Vrijedi De Morgan: (A∪B)ᶜ=Aᶜ∩Bᶜ, (A∩B)ᶜ=Aᶜ∪Bᶜ.
- Dokaz izravno: iz pretpostavke P izvodimo Q. Dokaz kontradikcijom: pretpostavimo ¬Q i dođemo do proturječja. Protuprimjer obara univerzalnu tvrdnju.
- Ekvivalencija se dokazuje u dva smjera.
Riješeni primjer
Dokažimo da je zbroj dvaju neparnih brojeva paran. Neka su m i n cijeli brojevi; neparni brojevi su oblika 2m+1 i 2n+1. Njihov zbroj je (2m+1)+(2n+1)=2m+2n+2=2(m+n+1). Budući da je m+n+1 cijeli broj, zbroj je oblika 2k, pa je paran. Time je tvrdnja dokazana za sve parove neparnih brojeva, a ne samo za primjer.
Zamke
Najčešće se pobrka negacija: nije svaki ne znači nijedan. Kod implikacije se pogrešno zaključi obrat ili se dokazuje samo nužnost. Kod skupova se zamijene unija i presjek te se zaboravi da je komplement relativan obzirom na univerzalni skup. Provjera na dva-tri primjera nije dokaz; za univerzalnu tvrdnju potreban je opći argument, a za nijekanje dovoljan je jedan protuprimjer.