Algebra iskaza. Booleove operacije

Plan

Izjave s vanjskom negacijom.

konjunktivni iskazi.

disjunktivni iskazi.

Strogo disjunktivni iskazi.

Izjave o ekvivalenciji.

Implicitne izjave.

Izjave s vanjskom negacijom.

Izjava s vanjskom negacijom je izjava (sud) u kojoj se potvrđuje odsutnost određene situacije. Najčešće se izražava rečenicom koja počinje rečenicom “nije istina da...” ili “pogrešno je da...”. Vanjska negacija je označena simbolom “ù”, koji se naziva znakom negacije. Ovaj znak je određen sljedećom tablicom istinitosti:

U izjavama s vanjskom negacijom poriče se situacija u A. Na primjer, ako A: “Volga se ulijeva u Crno more”, onda ùA: “Nije istina da se Volga ulijeva u Crno more.”

konjunktivni iskazi.

Konjunktivni iskazi su oni u kojima se potvrđuje istovremeno postojanje dviju situacija. Konjunktivni iskazi tvore se od dva iskaza pomoću sindikata “i”, “a”, “ali”. Oblik konjunktivnog iskaza: (A&B). Svaka od izjava A i B može uzeti i vrijednost "true" i vrijednost "false". Ove vrijednosti su zbog kratkoće označene slovima ja, l. Tablica istinitosti za konjunktivne izjave je sljedeća:

U konjunktivnim izjavama navodi se da se situacija opisana u A i u B odvija istovremeno. Primjeri konjunktivnih izjava: “Zemlja je planet, a Mjesec je satelit”; “Petrov je dobro svladao logiku, ali je Sidorov loše svladao logiku”; “Vani je mrak i u dvorani su upaljena svjetla”; “Petrov je službeniku dao mito u gotovini, a Sidorov mu je dao bocu.”

disjunktivni iskazi.

Disjunktivni iskazi su iskazi koji potvrđuju postojanje barem jedne od dvije situacije opisane u A i B. Disjunkcija je označena simbolom V i izražena je prirodnim jezikom unijom "ili".

Tablična definicija znaka disjunkcije je sljedeća:

Primjer disjunktivne izjave: "Roman Sergejevič Ivanov je učitelj, ili Roman Sergejevič Ivanov je diplomirani student."

Strogo disjunktivni iskazi.

Strogo disjunktivni iskazi su oni koji potvrđuju postojanje točno jedne od dvije situacije opisane u A i B. Takve se izjave najčešće izvode pomoću rečenica sa spojem "ili ..., ili ..." ("ili ..., ili ...”). Stroga disjunkcija je označena simbolom V* (čita se "ili... ili...").

Tablična definicija znaka stroge disjunkcije je sljedeća:

Primjer striktno disjunktivne izjave: "Ili je vani sunčano, ili pada kiša."

Vrijednost istine

Ovaj članak ili odjeljak je grubi prijevod članka na drugom jeziku (pogledajte Provjera prijevoda). Mogao ga je generirati prevoditeljski program ili ga je izradio netko tko malo poznaje izvorni jezik. ¬( Uzorak:Mvar∧Uzorak:Mvar) ⇔ ¬Uzorak:Mvar ∨ ¬Uzorak:Mvar ¬( Uzorak:Mvar∨Uzorak:Mvar) ⇔ ¬Uzorak:Mvar ∧ ¬Uzorak:Mvar Viševrijedna logika Viševrijedna logika (na primjer, neizrazita logika dopušta više od dvije istinite vrijednosti, možda sadržavajući neke unutarnje strukture. Algebarska semantika Nisu svi logički sustavi istinski vrijednosni sustavi u smislu da se logički spojevi mogu tumačiti kao istinitost funkcija. Na primjer, intuicionističkoj logici nedostaje potpuni skup vrijednosti istine jer je njezina semantika definirana u smislu dokazivosti uvjeta, a ne izravno u smislu obvezne valjanosti formula. U drugim teorijama Intuicionistička teorija tipova koristi tipove umjesto vrijednosti istine. Teorija toposa koristi vrijednosti istine u posebnom smislu: vrijednost istine toposa je globalni element x podobjekt klasifikatora. Imati vrijednost istine u ovom smislu nema vrijednosnu logiku istine. vidi također Linkovi Zaklada Wikimedia. 2010 . Pogledajte što je "Vrijednost istine" u drugim rječnicima: Sadržaj označen jednim ili drugim jezičnim izrazom riječju, rečenicom, znakom itd. Pitanje Z. jezičnih izraza proučava lingvistika, semiotika i logička semantika. Razlikovati subjekt, semantičko i ekspresivno Z. jezično ... Filozofska enciklopedija Vrijednost istine (u logici), vrijednost koju Izjava (rečenica, presuda) zauzima, razmatrana u odnosu na sadržaj prikazan u njoj. U običnoj (klasičnoj) logici dva I. z. "točno netočno"; u… … Velika sovjetska enciklopedija Tablica istinitosti je tablica koja opisuje logičku funkciju. Pod "logičkom funkcijom" u ovom slučaju podrazumijeva se funkcija u kojoj vrijednosti varijabli (parametara funkcije) i vrijednost same funkcije izražavaju logičku istinu. ... ... Wikipedia. Tablica koja utvrđuje vrijednost istinitosti složenog iskaza s obzirom na vrijednosti njegovih jednostavnih izjava. U klasičnoj matematičkoj logici pretpostavlja se da je svaki prosti (koji ne sadrži logički ... ... Rječnik logičkih pojmova Denotatum (od lat. denotatum označen), pojam lingvistike i ekstenzijske logike, koji označava 1) proširenje, 2) designatum, 3) referent i 4) semantičku jezgru značenja. Sadržaj 1 Oznaka kao ekstenzija 2 Oznaka kao oznaka ... Wikipedia Jedna od mogućih karakteristika iskaza u smislu njegove korespondencije s opisanim fragmentom stvarnosti. Ako se pretpostavi da je svaka izjava ili istinita ili lažna (tj. da je ili istinita... Rječnik logičkih pojmova Skup logičkih sustava temeljenih na principu dvosmislenosti. U klasičnoj dvovrijednoj logici izrazi tijekom interpretacije poprimaju samo dvije vrijednosti “true” i “false”, u M.l. uzimaju se u obzir i druge vrijednosti, npr. "neograničeno" ...... Filozofska enciklopedija - (od lat. factum učinjeno, ostvareno) 1) sinonim za pojmove "istina", "događaj", "rezultat"; nešto stvarno za razliku od izmišljenog; konkretno, pojedinačno u suprotnosti s apstraktnim i općim; 2) u filozofiji znanosti posebne vrste p ... Filozofska enciklopedija - (u logistici) - istinitost rečenice (presude, izjave), zbog, za razliku od tzv. logično istina, sadržaj ove rečenice. Drugim riječima, rečenica je zapravo istinita kada njezina istinitost ovisi o vrijednostima... Filozofska enciklopedija Stereometrijska semantika- tumačenje logike kao znanosti o dobivanju istinitih posljedica iz istinitih premisa sve više ustupa mjesto širem konceptu koji se odnosi ili na generalizaciju koncepta slijeđenja, temeljenog na tradicionalnoj procjeni istine i na praktičnim ... ... Projektivni filozofski rječnik knjige Kako iskreno vjerovati u Boga, ili jedino što je bitno za razvoj vjere, Vrajev V. okruženje sa...

propoziciona logika , također nazvana propozicijska logika - grana matematike i logike koja proučava logičke oblike složenih iskaza izgrađenih od jednostavnih ili elementarnih iskaza pomoću logičkih operacija.

Logika propozicija apstrahira se od smislenog opterećenja propozicija i proučava njihovu istinitost, odnosno je li propozicija istinita ili lažna.

Slika iznad je ilustracija fenomena poznatog kao paradoks lažova. Istodobno, prema mišljenju autora projekta, takvi su paradoksi mogući samo u sredinama koje nisu oslobođene političkih problema, gdje se netko može a priori okarakterizirati kao lažov. U prirodnom slojevitom svijetu na predmet "istine" ili "neistine" ocjenjuje se samo odvojeno uzetim iskazima . I kasnije u ovoj lekciji, bit ćete upoznati s prilika za procjenu mnogih izjava o ovoj temi (a zatim pogledajte točne odgovore). Uključujući složene iskaze u kojima su jednostavniji međusobno povezani znakovima logičkih operacija. Ali prvo razmotrimo ove operacije na samim prijedlozima.

Propozicijska logika se koristi u informatici i programiranju u obliku deklariranja logičkih varijabli i dodjele im logičkih vrijednosti "netočno" ili "true", o čemu ovisi tijek daljnjeg izvršavanja programa. U malim programima u kojima je uključena samo jedna logička varijabla, toj booleovoj varijabli često se daje ime, kao što je "zastava", a "zastava" se podrazumijeva kada je vrijednost te varijable "true" i "zastava je dolje" kada je vrijednost ova varijabla je "lažna". U velikim programima, u kojima postoji nekoliko ili čak puno logičkih varijabli, stručnjaci moraju smisliti nazive logičkih varijabli koje imaju oblik iskaza i semantičko opterećenje koje ih razlikuje od drugih logičkih varijabli i koje je razumljivo drugima. profesionalci koji će čitati tekst ovog programa.

Dakle, može se deklarirati logička varijabla s imenom "UserRegistered" (ili njezin ekvivalent na engleskom), koja ima oblik izjave, kojoj se može dodijeliti logička vrijednost "true" ako su ispunjeni uvjeti da se podaci za registraciju šalju od strane korisnika i te podatke program prepoznaje kao valjane. U daljnjim izračunima, vrijednosti varijabli mogu se mijenjati ovisno o tome koju logičku vrijednost ("true" ili "false") ima varijabla "UserLogged in". U drugim slučajevima, varijabli, na primjer, s nazivom "Više od tri dana do dana", može se dodijeliti vrijednost "True" do određenog bloka izračuna, a tijekom daljnjeg izvršavanja programa ova vrijednost može biti spremljeni ili promijenjeni u "false" i tijek daljnjeg izvršavanja ovisi o vrijednosti ove varijable programa.

Ako program koristi nekoliko logičkih varijabli čija imena imaju oblik propozicija, a od njih se grade složeniji prijedlozi, tada je mnogo lakše razviti program ako se prije razvoja sve operacije iz propozicija zapisuju u obliku formula koristimo u propozicionoj logici nego što to činimo tijekom ove lekcije i učinimo to.

Logičke operacije nad iskazima

Za matematičke iskaze uvijek se može birati između dvije različite alternative "točno" i "netočno", ali za izjave date "verbalnim" jezikom pojmovi "točno" i "netočno" su nešto nejasniji. Međutim, na primjer, takvi glagolski oblici kao što su "Idi kući" i "Pada li kiša?" nisu izgovori. Stoga je jasno da iskazi su verbalni oblici u kojima se nešto navodi . Upitne ili usklične rečenice, apeli, kao i želje ili zahtjevi nisu iskazi. Ne mogu se ocijeniti vrijednostima "true" i "false".

Propozicije se, s druge strane, mogu promatrati kao veličina koja može poprimiti dvije vrijednosti: "točno" i "netočno".

Na primjer, daju se presude: "pas je životinja", "Pariz je glavni grad Italije", "3

Prva od ovih izjava može se ocijeniti simbolom "točno", druga - "netočno", treća - "točno", a četvrta - "netočno". Takvo tumačenje propozicija predmet je propozicijske algebre. Izjave ćemo označavati velikim latiničnim slovima A, B, ..., i njihove vrijednosti, odnosno istinite i lažne I i L. U običnom govoru koriste se veze između izjava "i", "ili" i drugih.

Ove veze omogućuju, kombiniranjem različitih iskaza, formiranje novih izjava - složene izjave . Na primjer, hrpa "i". Neka se daju izjave: π veći od 3" i izjava " π manje od 4. Možete organizirati novu - složenu izjavu " π više od 3 i π manje od 4". Izjava "ako π iracionalno, dakle π ² je također iracionalan" dobiva se povezivanjem dvaju iskaza s vezom "ako - onda". Konačno, možemo dobiti novu - složenu izjavu - iz bilo koje izjave - koja negira izvornu izjavu.

Razmatranje prijedloga kao veličina koje poprimaju vrijednosti I i L, definiramo dalje logičke operacije nad izjavama , koji nam omogućuju dobivanje novih - složenih iskaza iz tih izjava.

Neka su data dva proizvoljna iskaza A i B.

1 . Prva logička operacija nad tim iskazima - konjunkcija - je formiranje novog iskaza, koji ćemo označiti A ∧ B a što je istina ako i samo ako A i B pravi. U običnom govoru, ova operacija odgovara povezivanju iskaza s hrpom "i".

Tablica istine za konjunkciju:

A	B	A ∧ B
I	I	I
I	L	L
L	I	L
L	L	L

2 . Druga logička operacija nad izjavama A i B- disjunkcija izražena kao A ∨ B, definira se na sljedeći način: istinito je ako i samo ako je barem jedan od izvornih iskaza istinit. U običnom govoru ova operacija odgovara povezivanju iskaza s hrpom "ili". Međutim, ovdje imamo nerazdvojeno "ili", što se razumije u smislu "ili-ili" kada A i B oboje ne može biti istinito. U definiciji propozicijske logike A ∨ B istinito ako je samo jedan od iskaza točan i ako su obje tvrdnje istinite A i B.

Tablica istine za disjunkciju:

A	B	A ∨ B
I	I	I
I	L	I
L	I	I
L	L	L

3 . Treća logička operacija nad izjavama A i B, izraženo kao A → B; rezultirajuća izjava je lažna ako i samo ako A istina, i B lažno. A pozvao parcela , B - posljedica , i izjava A → B - slijedeći , također se naziva implikacija. U običnom govoru, ova operacija odgovara vezi "ako - onda": "ako A, onda B Ali u definiciji propozicijske logike, ova je tvrdnja uvijek istinita, bez obzira na to je li tvrdnja istinita ili lažna B. Ova se okolnost može ukratko formulirati na sljedeći način: "sve što vam se sviđa proizlazi iz lažnog." Zauzvrat, ako A istina, i B lažna, onda cijela izjava A → B lažno. Bit će istina ako i samo ako A, i B pravi. Ukratko, to se može formulirati na sljedeći način: "lažno ne može slijediti iz istinitog".

Tablica istine koja slijedi (implikacija):

A	B	A → B
I	I	I
I	L	L
L	I	I
L	L	I

4 . Četvrta logička operacija nad iskazima, točnije nad jednom tvrdnjom, naziva se negacija iskaza. A a označava se sa ~ A(također možete pronaći upotrebu ne simbola ~, već simbola ¬, kao i nadcrta A). ~ A postoji izjava koja je lažna kada A istinito, i istinito kada A lažno.

Tablica istine za negaciju:

A	~ A
L	I
I	L

5 . I, konačno, peta logička operacija nad propozicijama naziva se ekvivalencija i označava se A ↔ B. Rezultirajuća izjava A ↔ B je istinita izjava ako i samo ako A i B obje istinite ili obje lažne.

Tablica istine za ekvivalentnost:

A	B	A → B	B → A	A ↔ B
I	I	I	I	I
I	L	L	I	L
L	I	I	L	L
L	L	I	I	I

Većina programskih jezika ima posebne simbole za logičke vrijednosti propozicija, oni su napisani u gotovo svim jezicima kao istinito (true) i false (false).

Sumirajmo gore navedeno. propoziciona logika proučava veze koje su potpuno određene načinom na koji se neki iskazi grade od drugih, koji se nazivaju elementarnim. Elementarni iskazi se smatraju cjelinama, a ne raščlanjivi na dijelove.

U tablici ispod sistematiziramo nazive, oznake i značenje logičkih operacija nad iskazima (uskoro će nam ponovno trebati za rješavanje primjera).

Paket	Oznaka	Naziv operacije
ne		negacija
i		konjunkcija
ili		disjunkcija
ako tada...		implikacija
tada i samo tada		ekvivalencija

Jer logičke operacije su istinite zakoni algebre logike, koji se može koristiti za pojednostavljenje logičkih izraza. Istodobno, treba napomenuti da su u logici prijedloga apstrahirani od semantičkog sadržaja prijedloga i ograničeni na njegovo razmatranje s pozicije da je istinit ili lažan.

Primjer 1

1) (2 = 2) I (7 = 7);

2) Ne (15;

3) ("bor" = "hrast") ILI ("trešnja" = "javor");

4) Ne("bor" = "hrast") ;

5) (Ne (15 20) ;

6) ("Oči su dane da vide") i ("Pod trećim katom je drugi kat");

7) (6/2 = 3) ILI (7*5 = 20) .

1) Vrijednost iskaza u prvim zagradama je "true", vrijednost izraza u drugim zagradama je također istinita. Oba su iskaza povezana logičkom operacijom "AND" (pogledajte pravila za ovu operaciju iznad), tako da je logička vrijednost cijele ove izjave "true".

2) Značenje iskaza u zagradama je "netočno". Ovoj izjavi prethodi operacija logičke negacije, tako da je logička vrijednost cijele ove izjave "true".

3) Značenje iskaza u prvim zagradama je "netočno", značenje izjave u drugim zagradama je također "netočno". Izjave su povezane logičkom operacijom "ILI" i niti jedan od izraza nema vrijednost "true". Stoga je logično značenje cijele ove izjave “lažno”.

4) Značenje iskaza u zagradama je "netočno". Ovoj izjavi prethodi operacija logičke negacije. Stoga je logično značenje cijele dane tvrdnje "istinito".

5) U prvim se zagradama negira izjava u unutarnjim zagradama. Ova izjava u zagradama daje vrijednost "netočno", tako da će njezina negacija biti procijenjena na logičku vrijednost "true". Izjava u drugim zagradama ima vrijednost "false". Ove dvije izjave povezuju se logičkom operacijom "AND", odnosno dobiva se "true AND false". Stoga je logičko značenje cijele dane tvrdnje "netočno".

6) Značenje iskaza u prvim zagradama je "točno", značenje iskaza u drugim zagradama također je "točno". Ove dvije tvrdnje povezuje logička operacija "I", odnosno dobiva se "istina I istina". Stoga je logično značenje cijele dane tvrdnje "istinito".

7) Značenje iskaza u prvim zagradama je "točno". Značenje izjave u drugim zagradama je "netočno". Ove dvije izjave povezuju se logičkom operacijom "ILI", odnosno dobiva se "točno ILI netočno". Stoga je logično značenje cijele dane tvrdnje "istinito".

Primjer 2 Zapišite sljedeće složene izjave koristeći logičke operacije:

1) "Korisnik nije registriran";

2) "Danas je nedjelja i neki zaposlenici su na poslu";

3) "Korisnik je registriran kada i samo kada se utvrdi da su podaci koje je korisnik poslao ispravni."

1) str- pojedinačna izjava "Korisnik je registriran", logička operacija: ;

2) str- pojedinačna izjava "Danas je nedjelja", q- "Neki zaposlenici su na poslu", logična operacija: ;

3) str- pojedinačna izjava "Korisnik je registriran", q- "Podaci koje šalje korisnik su valjani", logička operacija: .

Sami riješite primjere propozicionalne logike, a zatim pogledajte rješenja

Primjer 3 Izračunajte booleove vrijednosti sljedećih iskaza:

1) ("U minuti ima 70 sekundi") ILI ("Sat koji radi pokazuje vrijeme");

2) (28 > 7) I (300/5 = 60) ;

3) ("TV - električni aparat") i ("Staklo - drvo");

4) Ne((300 > 100) ILI ("Žeđ se može utažiti vodom"));

5) (75 < 81) → (88 = 88) .

Primjer 4 Zapišite sljedeće složene izraze koristeći logičke operacije i izračunajte njihove logičke vrijednosti:

1) "Ako sat ne pokazuje točno vrijeme, onda možete doći na nastavu u pogrešno vrijeme";

2) "U ogledalu možete vidjeti svoj odraz i Pariz - glavni grad SAD-a";

Primjer 5 Odrediti Boolean izraz

(str → q) ↔ (r → s) ,

str = "278 > 5" ,

q= "Jabuka = ​​Naranča",

str = "0 = 9" ,

s= "Šešir pokriva glavu".

Propozicijske logičke formule

Uz pomoć pojma specificira se pojam logičkog oblika složenog iskaza propozicionalne logičke formule .

U primjerima 1 i 2 naučili smo pisati složene iskaze pomoću logičkih operacija. U stvari, one se nazivaju propozicionalnim logičkim formulama.

Za označavanje iskaza, kao u gornjem primjeru, nastavit ćemo koristiti slova

str, q, r, ..., str 1 , q 1 , r 1 , ...

Ova slova će igrati ulogu varijabli koje uzimaju istinite vrijednosti "true" i "false" kao vrijednosti. Ove varijable se također nazivaju propozicionalne varijable. Od sada ćemo ih zvati elementarne formule ili atoma .

Za konstruiranje propozicionalnih logičkih formula, osim gornjih slova, koriste se i znakovi logičkih operacija

~, ∧, ∨, →, ↔,

kao i simboli koji daju mogućnost jednoznačnog čitanja formula – lijeve i desne zagrade.

koncept propozicionalne logičke formule definirati kako slijedi:

1) elementarne formule (atomi) su formule propozicijske logike;

2) ako A i B- propozicionalne logičke formule, zatim ~ A , (A ∧ B) , (A ∨ B) , (A → B) , (A ↔ B) su također formule propozicijske logike;

3) samo oni izrazi su propozicijske logičke formule za koje to slijedi iz 1) i 2).

Definicija propozicionalne logičke formule sadrži nabrajanje pravila za formiranje ovih formula. Prema definiciji, svaka formula propozicijske logike je ili atom ili je nastala od atoma kao rezultat uzastopne primjene pravila 2).

Primjer 6 Neka bude str- pojedinačna izjava (atom) "Svi racionalni brojevi su realni", q- "Neki realni brojevi su racionalni brojevi", r- "neki racionalni brojevi su stvarni". Prevedite u oblik verbalnih prijedloga sljedeće formule propozicijske logike:

6) .

1) "nema realnih brojeva koji su racionalni";

2) "ako nisu svi racionalni brojevi realni, onda ne postoje racionalni brojevi koji su realni";

3) "ako su svi racionalni brojevi realni, onda su neki realni brojevi racionalni brojevi, a neki racionalni brojevi realni";

4) "svi realni brojevi su racionalni brojevi i neki realni brojevi su racionalni brojevi, a neki racionalni brojevi su realni brojevi";

5) "svi racionalni brojevi su stvarni ako i samo ako nije slučaj da nisu svi racionalni brojevi realni";

6) "nije da nije slučaj da nisu svi racionalni brojevi realni i da nema realnih brojeva koji su racionalni ili nema racionalnih brojeva koji su realni."

Primjer 7 Napravite tablicu istinitosti za propozicionu logičku formulu , što se u tablici može označiti f .

Odluka. Počinjemo sastavljati tablicu istinitosti bilježeći vrijednosti ("true" ili "false") za pojedinačne izjave (atome) str , q i r. Sve moguće vrijednosti upisane su u osam redaka tablice. Nadalje, prilikom određivanja vrijednosti operacije implikacije i pomicanja udesno u tablici, zapamtite da je vrijednost jednaka "false" kada "true" implicira "false".

str	q	r					f
I	I	I	I	I	I	I	I
I	I	L	I	I	I	L	I
I	L	I	I	L	L	L	L
I	L	L	I	L	L	I	I
L	I	I	L	I	L	I	I
L	I	L	L	I	L	I	L
L	L	I	I	I	I	I	I
L	L	L	I	I	I	L	I

Imajte na umu da nijedan atom nema oblik ~ A , (A ∧ B) , (A ∨ B) , (A → B) , (A ↔ B) . To su složene formule.

Broj zagrada u propozicionalnim logičkim formulama može se smanjiti pod pretpostavkom da

1) u složenoj formuli izostavit ćemo vanjski par zagrada;

2) poredajte znakove logičkih operacija "po stažu":

↔, →, ∨, ∧, ~ .

Na ovom popisu znak ↔ ima najveći opseg, a znak ~ najmanji opseg. Pod opsegom znaka operacije podrazumijevaju se oni dijelovi propozicionalne logičke formule na koje se primjenjuje (djeluje) razmatrana pojava ovog znaka. Dakle, moguće je izostaviti u bilo kojoj formuli one parove zagrada koji se mogu vratiti, uzimajući u obzir "redoslijed prvenstva". A prilikom vraćanja zagrada prvo se postavljaju sve zagrade koje se odnose na sve pojave znaka ~ (u ovom slučaju se krećemo s lijeva na desno), zatim na sva pojavljivanja znaka ∧ i tako dalje.

Primjer 8 Vratite zagrade u propozicionu logičku formulu B ↔ ~ C ∨ D ∧ A .

Odluka. Zagrade se vraćaju korak po korak na sljedeći način:

B ↔ (~ C) ∨ D ∧ A

B ↔ (~ C) ∨ (D ∧ A)

B ↔ ((~ C) ∨ (D ∧ A))

(B ↔ ((~ C) ∨ (D ∧ A)))

Ne može se svaka propozicionalna logička formula napisati bez zagrada. Na primjer, u formulama ALI → (B → C) i ~( A → B) daljnje brisanje zagrada nije moguće.

Tautologije i proturječnosti

Logičke tautologije (ili jednostavno tautologije) takve su formule propozicijske logike da ako se slova proizvoljno zamjenjuju propozicijama (točnim ili netočnim), tada će rezultat uvijek biti istinit prijedlog.

Budući da istinitost ili netočnost složenih iskaza ovisi samo o značenjima, a ne o sadržaju iskaza, od kojih svaki odgovara određenom slovu, onda se test da li je dati iskaz tautologija može zamijeniti na sljedeći način. U izrazu koji se proučava, vrijednosti 1 i 0 (odnosno, "true" i "false") zamjenjuju se za slova na sve moguće načine, a pomoću logičkih operacija izračunavaju se logičke vrijednosti izraza. Ako su sve ove vrijednosti jednake 1, tada je izraz koji se proučava tautologija, a ako barem jedna zamjena daje 0, onda to nije tautologija.

Dakle, propozicionalna logička formula koja uzima vrijednost "true" za bilo koju distribuciju vrijednosti atoma uključenih u ovu formulu naziva se identično istinita formula ili tautologija .

Suprotno značenje je logička kontradikcija. Ako su sve vrijednosti prijedloga 0, tada je izraz logička kontradikcija.

Dakle, propozicionalna logička formula koja uzima vrijednost "netočno" za bilo koju distribuciju vrijednosti atoma uključenih u ovu formulu naziva se identično pogrešna formula ili kontradikcija .

Osim tautologija i logičkih proturječnosti, postoje formule propozicijske logike koje nisu ni tautologije ni proturječnosti.

Primjer 9 Napravite tablicu istinitosti za propozicijsku logičku formulu i odredite je li to tautologija, kontradikcija ili nijedno.

Odluka. Izrađujemo tablicu istine:

I	I	I	I	I
I	L	L	L	I
L	I	L	I	I
L	L	L	L	I

U značenjima implikacije ne nailazimo na red u kojem "istinito" implicira "netočno". Sve vrijednosti izvorne izjave jednake su "true". Stoga je ova propozicionalna logička formula tautologija.

Tema programa: Izjave i operacije na njima.

Ciljevi lekcije:

1) Sažmite teorijska znanja na temu: "Izjave i operacije nad njima."

2) Razmotriti algoritme za rješavanje zadataka na temu "Izjave i operacije na njima", riješiti probleme.

3) Formirati sposobnost predviđanja vlastite aktivnosti, sposobnost organiziranja vlastite aktivnosti i njezine analize.

Vrijeme isporuke: 1 sat.

Teorijska osnova

Osnovni koncept matematičke logike je koncept "jednostavne izjave". Pod iskazom se obično podrazumijeva svaka izjavna rečenica kojom se nešto o nečemu tvrdi, a ujedno možemo reći je li to točno ili netočno u datim uvjetima mjesta i vremena. Logičke vrijednosti izjava su "točno" i "netočno".

Primjeri izraza.
1) Moskva stoji na Nevi.
2) London je glavni grad Engleske.
3) Sokol nije riba.
4) Broj 6 je djeljiv sa 2 i 3.
Izjave 2), 3), 4) su istinite, a tvrdnja 1) je netočna.
Očito, rečenica "Živjela Rusija!" nije izjava.
Postoje dvije vrste izjava.
Izjava, koja je jedna izjava, obično se naziva jednostavnom ili elementarnom. Primjeri elementarnih prijedloga su propozicije 1) i 2).
Izjave koje se dobivaju od elementarnih uz pomoć gramatičkih veziva "ne", "i", "ili", "ako .... onda ...", "onda i samo tada", obično se nazivaju složenim ili složenim .
Dakle, tvrdnja 3) dobivena je iz jednostavne tvrdnje „Sokol je riba“ uz pomoć negacije „ne“, izjava 4) formirana je od elementarnih tvrdnji „Broj 6 je djeljiv s 2“, "Broj 6 je djeljiv s 3", povezan je spojem "i".
Slično, složeni iskazi mogu se dobiti iz jednostavnih iskaza pomoću gramatičkih veznika "ili", "ako i samo tada".
U algebri logike svi se iskazi razmatraju samo s gledišta njihova logičkog značenja, a njihov se svjetovni sadržaj apstrahira. Vjeruje se da je svaka izjava ili istinita ili lažna, a niti jedna izjava ne može biti i istinita i lažna.
Elementarne izjave označene su malim slovima latinske abecede: x, y, z, ..., a, b, c, ...; prava vrijednost iskaza je broj 1, a lažna vrijednost je slovo broj 0.
Ako izjava a istina, napisat ćemo a = 1, i ako a lažno, dakle a = 0.

Logičke operacije nad iskazima

Negacija.

Negacija iskaza x naziva se novim prijedlogom, što je istinito ako je prijedlog x lažna, i lažna ako je izjava x pravi.

Odbijanje izjave x označeno i pročitano "ne X" ili "nije istina da je x".

Logička značenja iskaza mogu se opisati pomoću tablice.

Tablice ove vrste nazivaju se tablicama istine.
Neka bude x izjava. Budući da je ujedno i iskaz, moguće je formirati negaciju iskaza, odnosno iskaz, koji se naziva dvostruka negacija iskaza x. Jasno je da su logička značenja iskaza x i podudaraju se.

Na primjer, za izjavu "Putin je predsjednik Rusije" negativna bi bila izjava "Putin nije predsjednik Rusije", a dvostruka negacija bi bila izjava "Nije istina da Putin nije predsjednik Rusije".

Konjunkcija.

Konjunkcija (logičko množenje) dvaju iskaza x i y naziva se novi prijedlog, koji se smatra istinitim ako oba prijedloga x i y istinito, a netočno ako je barem jedan od njih lažan.
spoj prijedloga x i y označena simbolom x&y ( , xy), čitati "x i y". izreke x i y nazivaju se članovima veznika.
Logičke vrijednosti konjunkcije opisane su sljedećom tablicom istinitosti:

Na primjer, za izjave "6 je djeljivo sa 2", "6 je djeljivo sa 3", njihova će konjunkcija biti izjava "6 je djeljivo s 2 i 6 je djeljivo s 3", što je očito točno.

Iz definicije operacije veznika može se vidjeti da se unija "i" u algebri logike koristi u istom smislu kao i u svakodnevnom govoru. Ali u običnom govoru nije uobičajeno kombinirati dvije izjave koje su po sadržaju udaljene jedna od druge sa sjedištem "i", au algebri logike razmatra se spoj bilo koje dvije izjave.

Disjunkcija

Disjunkcija (logičko zbrajanje) dvaju iskaza x i y naziva se novi prijedlog koji se smatra istinitim ako je barem jedan od prijedloga x, y istinito i netočno ako su oba lažna. Disjunkcija prijedloga x, y označena simbolom "x V y", čitati "x ili y". izreke x, y nazivaju se termini disjunkcije.
Logičke vrijednosti disjunkcije opisane su sljedećom tablicom istinitosti:

U svakodnevnom govoru, unija "ili" se koristi u drugačijem smislu: isključivo i neisključivo. U algebri logike, unija "ili" se uvijek koristi u neisključivom smislu.

Implikacija.

Implikacija dvaju iskaza x i y Poziva se nova tvrdnja koja je netočna ako je x istinit, a y netočan, te istinit u svim ostalim slučajevima.
Implikacija izjava x, y označena simbolom , čitati "ako je x, onda y" ili "iz x slijedi y". izjava x nazvan uvjetom ili premisa, izjava na- posljedica ili zaključak, izjava sljedeće ili implikacije.

Logičke vrijednosti operacije implikacije opisane su sljedećom tablicom istinitosti:

Upotreba riječi "ako....onda..." u algebri logike razlikuje se od njihove upotrebe u svakodnevnom govoru, gdje smo skloni misliti da ako izjava x lažna, zatim izjava "Ako je x, onda y" uopće nema smisla. Osim toga, građenje rečenice oblika "ako je x onda y" u svakodnevnom govoru uvijek mislimo da rečenica na proizlazi iz prijedloga x. Upotreba riječi "ako ... onda ..." u matematičkoj logici to ne zahtijeva, budući da se u njoj ne razmatra značenje iskaza.
Implikacija igra važnu ulogu u matematičkim dokazima, budući da su mnogi teoremi formulirani u uvjetnom obliku. "Ako je x, onda y." Ako se ipak zna da x je istinit i istinitost implikacije je dokazana , onda možemo zaključiti da je zaključak istinit na .

Ekvivalencija.

Ekvivalencija dvaju iskaza x i y naziva se novi prijedlog, koji se smatra istinitim kada su oba prijedloga x, y ili oba istinita ili obje lažna, i lažna u svim ostalim slučajevima.

Ekvivalencija iskaza x, y označena simbolom, čitaj "kako bi za x, potrebno je i dovoljno da y" ili "x ako i samo ako y". izreke x, y nazivaju se pojmovima ekvivalencije.
Logičke vrijednosti operacije ekvivalencije opisane su sljedećom tablicom istinitosti:

Ekvivalencija igra važnu ulogu u matematičkim dokazima. Poznato je da je značajan broj teorema formuliran u obliku nužnih i dovoljnih uvjeta, odnosno u obliku ekvivalencije. U ovom slučaju, znajući istinitost ili netočnost jednog od dva pojma ekvivalencije i dokazujući istinitost same ekvivalencije, zaključujemo da je drugi pojam ekvivalentnosti istinit ili netočan.

Praktični zadaci

1. Uspostavi logičku strukturu sljedećih rečenica i zapiši ih jezikom propozicijske logike:

• Ako se metal zagrije, on se topi.
• Nije točno da su filozofski sporovi nerješivi.
• Novac je proizvod spontanog razvoja robnih odnosa, a ne rezultat dogovora ili nekog drugog svjesnog čina.

2. Zapišite sljedeće tvrdnje u logičku formulu:

a) ako vani pada kiša, onda trebate ponijeti kišobran sa sobom ili ostati kod kuće;

B) ako su - pravokutne i stranice jednake, onda

3. Provjerite istinitost tvrdnje:

i ako, .

b) ako, .

c) ako, .

4. Provjerite istinitost tvrdnje:

a) Da bih sutra otišao na nastavu, moram rano ustati. Ako danas odem u kino, kasno ću ići u krevet. Ako idem kasno spavati, kasno ću se probuditi. Stoga, ili neću ići u kino, ili neću ići na nastavu.

b) Ići ću ili u kino ili na bazen. Ako odem u kino, dobit ću estetski užitak. Ako odem na bazen, dobit ću fizički užitak. Stoga, ako dobijem fizički užitak, neću dobiti estetski užitak.

5 . Na pitanje: "Tko je od tri učenika studirao diskretnu matematiku?" dobiven je točan odgovor: „Ako je učio prvo, onda je učio i treće, ali nije istina da ako je učio drugo, onda je učio i treće.” Tko je studirao diskretnu matematiku?

6. Odredi koji je od četiri studenta položio ispit, ako je poznato:

ako je prvi prošao, onda je prošao i drugi;

ako je drugi prošao, onda je prošao treći ili prvi nije prošao;

ako četvrti nije prošao, onda je prošao prvi, a treći nije prošao;

ako je četvrti prošao, onda je prošao prvi.

test pitanja

1. Koji elementi su uključeni u jezik logike?

2. Koje načine utvrđivanja valjanosti neke formule logike poznajete?

Bibliografija

Vježba br. 10-11

Tema programa: Formule propozicijske algebre.

Svojstva

Razmotrite nekoliko svojstava kartezijanskog proizvoda:

1. Ako A,B su onda konačni skupovi A× B- konačno. I obrnuto, ako je jedan od skupova množitelja beskonačan, tada je rezultat njihovog proizvoda beskonačan skup.

2. Broj elemenata u kartezijanskom umnošku jednak je umnošku brojeva elemenata skupova množitelja (ako su, naravno, konačni): | A× B|=|A|⋅|B| .

3. A np ≠(A n) str- u prvom slučaju preporučljivo je rezultat kartezijanskog proizvoda uzeti u obzir kao matricu dimenzija 1× np, u drugom - kao matrica veličina n× str .

4. Komutativni zakon nije ispunjen, jer parovi elemenata rezultata kartezijanskog proizvoda su poredani: A× B≠B× A .

5. Zakon o udruživanju nije ispunjen: ( A× B)× C≠A×( B× C) .

6. Postoji distributivnost s obzirom na osnovne operacije na skupovima: ( A∗B)× C=(A× C)∗(B× C),∗∈{∩,∪,∖}

11. Pojam iskaza. Elementarni i složeni iskazi.

izjava je izjava ili izjavna rečenica za koju se može reći da je istinita (T-1) ili lažna (L-0), ali ne oboje u isto vrijeme.

Na primjer, "Danas pada kiša", "Ivanov je završio laboratorijski rad broj 2 iz fizike."

Ako imamo nekoliko početnih izjava, onda od njih koristeći logičke unije ili čestice možemo oblikovati nove tvrdnje čija istinitost ovisi samo o vrijednostima istinitosti izvornih iskaza i o specifičnim veznicima i česticama koje sudjeluju u izgradnji nove tvrdnje. Riječi i izrazi "i", "ili", "ne", "ako...onda", "dakle", "ako i samo tada" primjeri su takvih veznika. Izvorne izjave se zovu jednostavan , i nove izjave konstruirane od njih uz pomoć određenih logičkih sindikata - sastavni . Naravno, riječ "jednostavno" nema nikakve veze sa suštinom ili strukturom izvornih izjava, koje same po sebi mogu biti prilično složene. U ovom kontekstu, riječ "jednostavno" je sinonim za riječ "izvorno". Važno je da se istinite vrijednosti jednostavnih propozicija trebaju znati ili dati; u svakom slučaju, o njima se ni na koji način ne raspravlja.

Iako izjava poput "Danas nije četvrtak" nije sastavljena od dvije različite jednostavne tvrdnje, zbog ujednačenosti konstrukcije ona se također tretira kao složena, budući da je njezina istinitost određena istinitošću druge tvrdnje "Danas je četvrtak "

Primjer 2 Sljedeće izjave tretiraju se kao složene izjave:

Čitao sam Moskovsky Komsomolets i čitao sam Kommersant.

Ako je to rekao, onda je to istina.

Sunce nije zvijezda.

Ako je sunčano i temperatura prijeđe 25 0 , stići ću vlakom ili autom

Jednostavni iskazi uključeni u složene iskaze mogu sami biti potpuno proizvoljni. Konkretno, oni sami mogu biti kompozitni. Osnovni tipovi složenih iskaza opisani u nastavku definirani su neovisno o jednostavnim iskazima koji ih tvore.

12. Operacije nad izjavama.

1. operacija negacije.

Negacija izjave ALI ( glasi "ne ALI"," to nije istina ALI"), što je istina kada ALI lažno i lažno kada ALI- istina.

Negativne izjave ALI i pozvao suprotan.

2. radnja spojnice.

konjunkcija izjave ALI i NA naziva se izjava A B(čitati " ALI i NA”), čija se prava značenja određuju ako i samo ako obje izjave ALI i NA pravi.

Konjunkcija iskaza naziva se logički proizvod i često se označava AB.

Neka izjava ALI– “u ožujku temperatura zraka od 0 S na + 7 C»i govoreći NA- "U Vitebsku pada kiša." Zatim A B bit će sljedeća: „u ožujku temperatura zraka od 0 S na + 7 C a u Vitebsku pada kiša." Ovaj će veznik biti istinit ako postoje izjave ALI i NA pravi. Ako se pokaže da je temperatura bila manja 0 S ili u Vitebsku tada nije bilo kiše A B bit će lažna.

3 . rad disjunkcije.

disjunkcija izjave ALI i NA naziva se izjava A B (ALI ili NA), što je istinito ako i samo ako je barem jedan od iskaza točan i netočan - kada su obje tvrdnje netočne.

Disjunkcija propozicija naziva se i logički zbroj A+B.

Izjava " 4<5 ili 4=5 ' je istina. Od izjave " 4<5 "točno je, a izjava" 4=5 ' je dakle lažno A B je istinita izjava 4 5 ».

4 . operacija implikacije.

implikacija izjave ALI i NA naziva se izjava A B("ako ALI, onda NA", "od ALI trebao bi NA”), čija je vrijednost lažna ako i samo ako ALI istina, i NA lažno.

U implikaciji A B izjava ALI pozvao temelj, ili slanje i izjava NA – posljedica, ili zaključak.

13. Tablice istinitosti iskaza.

Tablica istinitosti je tablica koja uspostavlja korespondenciju između svih mogućih skupova logičkih varijabli uključenih u logičku funkciju i vrijednosti funkcije.

Tablice istine koriste se za:

Izračunavanje istinitosti složenih izjava;

Uspostavljanje ekvivalencije iskaza;

Definicije tautologija.

Utvrđivanje istinitosti složenih izjava.

Primjer 1 Utvrdite istinitost tvrdnje C

Odluka. Sastav složene izjave uključuje 3 jednostavne izjave: A, B, C. Stupci u tablici su ispunjeni vrijednostima (0, 1). Naznačene su sve moguće situacije. Proste su rečenice odvojene od složenih dvostrukom okomitom crtom.
Prilikom sastavljanja tablice treba paziti da se ne pomiješa redoslijed radnji; popunjavajući stupce, treba se kretati "iznutra prema van", t.j. od elementarnih formula do sve složenijih; posljednji stupac za popunjavanje sadrži vrijednosti izvorne formule.

ALI	NA	S		A+		· SA

Tablica pokazuje da je ova tvrdnja istinita samo ako je A=0, B=1, C=1. U svim ostalim slučajevima je lažna.

14. Ekvivalentne formule.

Dvije formule ALI i NA nazivaju se ekvivalentnima ako uzimaju iste logičke vrijednosti za bilo koji skup vrijednosti elementarnih propozicija uključenih u formulu.

Ekvivalencija je označena znakom "". Za transformaciju formula u ekvivalentne važnu ulogu imaju osnovne ekvivalencije koje izražavaju neke logičke operacije u terminima drugih, ekvivalentnosti koje izražavaju osnovne zakone algebre logike.

Za bilo koje formule ALI, NA, S ekvivalencije su valjane.

I. Osnovne ekvivalencije

zakon idempotencije

1-točno

0-netočno

Zakon kontradikcije

Zakon isključene sredine

zakon apsorpcije

formule za cijepanje

zakon o vezivanju

II. Ekvivalencije koje izražavaju neke logičke operacije u terminima drugih.

de Morganov zakon

III. Ekvivalencije koje izražavaju osnovne zakone algebre logike.

komutativno pravo

asocijativno pravo

distributivno pravo

15. Formule propozicijske logike.

Vrste formula u klasičnoj propozicionalnoj logici- u propozicijskoj logici razlikuju se sljedeće vrste formula:

1. Zakoni(identično istinite formule) - formule koje za bilo koju interpretaciju propozicijskih varijabli poprimaju vrijednost "pravi";

2. proturječnosti(identično lažne formule) - formule koje za bilo koju interpretaciju propozicijskih varijabli poprimaju vrijednost "lažno";

3. Zadovoljive formule- one koje poprimaju značenje "pravi" za barem jedan skup vrijednosti istinitosti propozicijskih varijabli uključenih u njih.

Osnovni zakoni klasične propozicijske logike:

1. Zakon o identitetu: ;

2. Zakon kontradikcije: ;

3. Zakon isključene sredine: ;

4. Zakoni komutativnosti i: , ;

5. Zakoni distributivnosti su relativni na , i obrnuto: , ;

6. Zakon uklanjanja pravog pojma veznika: ;

7. Zakon uklanjanja lažnog člana disjunkcije: ;

8. Zakon kontrapozicije: ;

9. Zakoni međusobne ekspresivnosti propozicijskih veziva: , , , , , .

Postupak rješivosti- metoda koja omogućuje svakoj formuli da utvrdi je li to zakon, proturječnost ili izvediva formula. Najčešći postupak razlučivosti je metoda tablice istinitosti. Međutim, on nije jedini. Učinkovita metoda rješivosti je metoda normalni oblici za propozicijske logičke formule. normalan oblik propozicionalna logička formula je oblik koji ne sadrži znak implikacije "". Postoje konjunktivni i disjunktivni normalni oblici. Konjunktivni oblik sadrži samo znakove veznika "". Ako formula reducirana na konjunktivni normalni oblik sadrži podformulu oblika , tada je cijela formula u ovom slučaju kontradikcija. Disjunktivni oblik sadrži samo disjunktivne znakove "". Ako formula svedena na disjunktivni normalni oblik sadrži podformulu oblika , tada je cijela formula u ovom slučaju zakon. U svim ostalim slučajevima, formula je zadovoljavajuća formula.

16. Predikati i operacije nad njima. Kvantifikatori.

Poziva se rečenica koja sadrži jednu ili više varijabli i koja je za određene vrijednosti varijabli izjava propozicijski oblik ili predikat.

Ovisno o broju varijabli uključenih u prijedlog, razlikuju se jednostruke, dvostruke, trostruke itd. predikati označeni redom: A( x), AT( x, na), SA ( x, na, z).

Ako je zadan neki predikat, tada su mu pridružena dva skupa:

1. Skup (domena) definicije X, koji se sastoji od svih vrijednosti varijabli, kada se zamijene u predikat, potonji se pretvara u izjavu. Kada se specificira predikat, obično se specificira njegov opseg.

2. Skup istine T, koji se sastoji od svih tih vrijednosti varijabli, kada se zamijene u predikat, dobiva se istinita tvrdnja.

Skup istinitosti predikata uvijek je podskup njegove domene, tj.

Možete izvesti iste operacije na predikatima kao i na iskazima.

1. Poricanje predikat A( x) definiran na skupu X naziva se predikat istinit za one vrijednosti za koje je predikat A( x) pretvara se u lažnu izjavu, i obrnuto.

Iz ove definicije slijedi da su predikati A( x) i B( x) nisu negacije jedna na drugu ako postoji barem jedna vrijednost za koju predikati A( x) i B( x) pretvoriti u prijedloge s istim vrijednostima istine.

Skup istinitosti predikata je dopuna skupu istine predikata A( x). Označimo sa T A skup istinitosti predikata A( x), i kroz T - skup istinitosti predikata . Zatim .

2. konjunkcija predikati A( x) i B( xx) AT( x x X, pod kojim se oba predikata pretvaraju u istinite iskaze.

Skup istinitosti konjunkcije predikata je presjek skupova istinitosti predikata A( x) AT( x). Ako skup istinitosti predikata A(x) označimo s T A, a skup istine predikata B(x) s T B i skup istinitosti predikata A(x) B(x) s , tada

3. disjunkcija predikati A( X) i B( x) definiran na skupu X naziva se predikat A( x) AT( x), što se pretvara u pravi prijedlog za te i samo te vrijednosti x X, pod kojim se barem jedan od predikata pretvorio u istinit iskaz.

Skup istine disjunkcije predikata je unija skupova istine predikata koji ga tvore, t.j. .

4.implikacija predikati A( x) i B( x) definiran na skupu X naziva se predikat A( x) AT( x), što je netočno za one i samo one vrijednosti varijable za koje prvi predikat postaje istinit, a drugi lažan.

Skup istinitosti implikacije predikata je unija skupa istinitosti predikata B( x) s dodatkom skupa istinitosti predikata A( x), tj.

5. Ekvivalencija predikati A( x) i B( x) definiran na skupu X naziva se predikat koji se pretvara u istinit iskaz za sve one i samo one vrijednosti varijable za koje se oba predikata pretvaraju ili u istinite izjave ili u lažne iskaze.

Skup istine ekvivalenta predikata je sjecište skupa istinitosti predikata sa skupom istinitosti predikata.

Operacije kvantifikatora nad predikatima

Predikat se može prevesti u iskaz metodom supstitucije i metodom “visećeg kvantifikatora”.

O brojevima 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 možete reći: a) svi dati brojevi su prosti; b) neki zadanih brojeva su parni.

Budući da se za ove rečenice može reći da su istinite ili netočne, rezultirajuće rečenice su prijedlozi.

Uklonimo li riječ “svi” iz rečenice “a”, a riječ “neki” iz rečenice “b”, onda ćemo dobiti sljedeće predikate: “ovi brojevi su prosti”, “ovi brojevi su neparni”.

Riječi "svi" i "neki" nazivaju se kvantifikatorima. Riječ "kvantifikator" latinskog je porijekla i znači "koliko", odnosno kvantifikator pokazuje koliko (svih ili nekih) objekata se spominje u određenoj rečenici.

Postoje dvije glavne vrste kvantifikatora: opći kvantifikator i egzistencijalni kvantifikator.

Pojmovi zovu se "bilo koji", "bilo koji", "svatko". – univerzalni kvantifikator. Određeno .

Neka A( x) je određeni predikat zadan na skupu X. Pod izrazom A( x) shvatit ćemo da je izjava istinita kada A( x) je istinit za svaki element skupa X, a inače je netočan.

U primjeru 1 za R1 domena definicije: , skup vrijednosti - . Za R2 domena definicije: , skup vrijednosti: .

U mnogim slučajevima prikladno je koristiti grafički prikaz binarne relacije. Izvodi se na dva načina: uz pomoć točaka na ravnini i uz pomoć strelica.

U prvom slučaju, dvije međusobno okomite linije biraju se kao vodoravna i okomita os. Na vodoravnoj osi položite elemente skupa A i kroz svaku točku povucite okomitu crtu. Na okomitoj osi položite elemente skupa B kroz svaku točku povucite vodoravnu crtu. Točke sjecišta vodoravnih i okomitih linija prikazuju elemente izravnog proizvoda

18. Metode postavljanja binarnih relacija.

Bilo koji podskup kartezijanskog proizvoda A × B naziva se binarna relacija definirana na paru skupova A i B (na latinskom "bis" znači "dvaput"). U općem slučaju, po analogiji s binarnim relacijama, n-arnih relacija možemo također smatrati uređenim nizovima od n elemenata uzetih iz jednog od n skupova.

Za označavanje binarne relacije koristi se simbol R. Kako je R podskup skupa A×B, možemo napisati R⊆A×. Ako je potrebno naznačiti da (a, b) ∈ R, tj. da postoji relacija R između elemenata a ∈ A i b ∈ B, tada napišite aRb.

Načini određivanja binarnih odnosa:

1. Ovo je uporaba pravila prema kojem su naznačeni svi elementi uključeni u ovaj odnos. Umjesto pravila, možete navesti elemente dane relacije direktnim nabrajanjem;

2. Tabelarni, u obliku grafikona i pomoću odjeljaka. Osnova tabularne metode je pravokutni koordinatni sustav, gdje se duž jedne osi ucrtavaju elementi jednog skupa, a po drugoj elementi drugog skupa. Sjecišta koordinata tvore točke koje označavaju elemente kartezijanskog proizvoda.

Na (slika 1.16) prikazana je koordinatna mreža za skupove. Točke presjeka tri okomite linije sa šest horizontalnih odgovaraju elementima skupa A×B. Krugovi na mreži označavaju elemente relacije aRb, pri čemu a ∈ A i b ∈ B, R označava relaciju “dijeli”.

Binarni odnosi su dani dvodimenzionalnim koordinatnim sustavima. Očito, svi elementi kartezijanskog proizvoda triju skupova mogu se na sličan način predstaviti u trodimenzionalnom koordinatnom sustavu, četiri skupa u četverodimenzionalnom sustavu, itd.;

3. Metoda specificiranja relacija pomoću sekcija koristi se rjeđe, pa je nećemo razmatrati.

19. Refleksivnost binarne relacije. Primjer.

U matematici se binarna relacija na skupu naziva refleksivna ako je svaki element tog skupa u odnosu na sebe.

Svojstvo refleksivnosti za dane relacije matricom karakterizira činjenica da su svi dijagonalni elementi matrice jednaki 1; za zadane relacije grafom, svaki element ima petlju - luk (x, x).

Ako ovaj uvjet nije zadovoljen ni za jedan element skupa, tada se relacija naziva antirefleksivnom.

Ako je antirefleksivna relacija dana matricom, tada su svi dijagonalni elementi jednaki nuli. Kada je takav odnos zadan grafom, svaki vrh nema petlju – nema lukova oblika (x, x).

Formalno se antirefleksivnost relacije definira kao: .

Ako uvjet refleksivnosti nije zadovoljen za sve elemente skupa, kaže se da je relacija nerefleksivna.

©2015-2019 stranica
Sva prava pripadaju njihovim autorima. Ova stranica ne tvrdi autorstvo, ali omogućuje besplatno korištenje.
Datum izrade stranice: 12.04.2016