Ndërtoni një shprehje logjike bazuar në tabelën e së vërtetës. Veprimet bazë të algjebrës së Bulit

Mësojmë të kompozojmë shprehje logjike nga deklaratat, përcaktojmë konceptin e "tabelës së së vërtetës", studiojmë sekuencën e veprimeve për ndërtimin e tabelave të së vërtetës, mësojmë të gjejmë vlerën e shprehjeve logjike duke ndërtuar tabela të së vërtetës.

Objektivat e mësimit:

1. Edukative:
   1. Mësoni të hartoni shprehje logjike nga deklarata
   2. Prezantoni konceptin e "tabelës së së vërtetës"
   3. Shqyrtoni sekuencën e veprimeve për ndërtimin e tabelave të së vërtetës
   4. Mësoni të gjeni kuptimin e shprehjeve logjike duke ndërtuar tabela të së vërtetës
   5. Prezantoni konceptin e ekuivalencës së shprehjeve logjike
   6. Mësoni të provoni ekuivalencën e shprehjeve logjike duke përdorur tabelat e së vërtetës
   7. Forconi aftësitë e gjetjes së vlerave të shprehjeve logjike duke ndërtuar tabela të së vërtetës
2. Zhvillimi:
   1. Zhvilloni të menduarit logjik
   2. Zhvilloni vëmendjen
   3. Zhvilloni kujtesën
   4. Zhvilloni fjalimin e nxënësve
3. Edukative:
   1. Kultivoni aftësinë për të dëgjuar mësuesit dhe shokët e klasës
   2. Edukoni saktësinë e mbajtjes së një fletoreje
   3. Nxit disiplinën

Gjatë orëve të mësimit

Koha e organizimit

Ç'kemi djema. Ne vazhdojmë të studiojmë bazat e logjikës dhe temën e mësimit tonë të sotëm "Përbërja e shprehjeve logjike. Tabelat e së vërtetës". Pas ekzaminimit Kjo temë, do të mësoni se si të hartoni forma logjike nga deklaratat dhe të përcaktoni vërtetësinë e tyre duke përpiluar tabela të së vërtetës.

Kontrolli i detyrave të shtëpisë

Shkruani zgjidhjen e problemeve shtëpiake në tabelë
Të gjithë të tjerët hapin fletoret, do të kaloj, do të kontrolloj se si i ke bërë detyrat e shtëpisë
Le të përsërisim veprimet logjike edhe një herë
Në cilin rast pohimi i përbërë do të jetë i vërtetë si rezultat i veprimit të shumëzimit logjik?
Një pohim i përbërë i formuar si rezultat i veprimit të shumëzimit logjik është i vërtetë nëse dhe vetëm nëse të gjitha pohimet e thjeshta të përfshira në të janë të vërteta.
Kur një pohim i përbërë do të jetë i rremë si rezultat i veprimit të mbledhjes logjike?
Një deklaratë e përbërë e formuar si rezultat i një operacioni të mbledhjes logjike është false kur të gjitha pohimet e thjeshta të përfshira në të janë false.
Si ndikon përmbysja në një deklaratë?
Përmbysja e bën një deklaratë të vërtetë false dhe, anasjelltas, false - e vërtetë.
Çfarë mund të thoni për nënkuptimin?
Ndjekja (nënkuptimi) logjik formohet duke kombinuar dy pohime në një me ndihmën e kthesës së të folurit "nëse ... atëherë ...".
Shënohet A-> V
Një pohim i përbërë i formuar nga operacioni i ndjekjes logjike (nënkuptimi) është i rremë nëse dhe vetëm nëse një përfundim i rremë rrjedh nga premisa e vërtetë (deklarata e parë) (deklarata e dytë).
Çfarë mund të thoni për veprimin logjik të ekuivalencës?
Barazia logjike (ekuivalenca) formohet duke kombinuar dy pohime në një me ndihmën e një kthese të të folurit "... nëse dhe vetëm nëse ...", "... nëse dhe vetëm nëse ..."
Një pohim i përbërë i formuar nga një veprim logjik i ekuivalencës është i vërtetë nëse dhe vetëm nëse të dy pohimet janë ose të rreme ose të vërteta në të njëjtën kohë.

Shpjegimi i materialit të ri

Mirë, ne kemi përsëritur materialin që kemi trajtuar dhe tani po kalojmë në një temë të re.

Në mësimin e fundit, ne gjetëm kuptimin e një deklarate të përbërë duke zëvendësuar vlerat fillestare të ndryshoreve hyrëse boolean. Dhe sot mësojmë se është e mundur të ndërtohet një tabelë e së vërtetës që përcakton vërtetësinë ose falsitetin e një shprehjeje logjike për të gjitha kombinimet e mundshme të vlerave fillestare të pohimeve të thjeshta (ndryshoret logjike) dhe se është e mundur të përcaktohen vlerat . të variablave logjikë fillestarë, duke ditur se çfarë lloj rezultati na nevojitet.

Le të shohim përsëri shembullin tonë nga mësimi i fundit.

dhe ndërtoni një tabelë të së vërtetës për këtë pohim të përbërë

Kur ndërtoni tabela të së vërtetës, ekziston një sekuencë e caktuar veprimesh. Le të shkruajmë

1. Është e nevojshme të përcaktohet numri i rreshtave në tabelën e së vërtetës.

• numri i rreshtave = 2 n, ku n është numri i ndryshoreve logjike

E kanë shkruar. Ndërtimi i një tabele të së vërtetës
Çfarë bëjmë fillimisht?
Përcaktoni numrin e kolonave në një tabelë
Si ta bëjmë atë?
Ne numërojmë numrin e variablave. Në rastin tonë, funksioni logjik përmban 2 variabla
Cilin?
A dhe B
Sa rreshta do të ketë në tabelë?
Numri i rreshtave në tabelën e së vërtetës duhet të jetë 4.
Po sikur të ketë 3 variabla?
Numri i rreshtave = 2³ = 8
E drejta. Çfarë të bëjmë më pas?
Përcaktoni numrin e kolonave = numrin e variablave boolean plus numrin e operacioneve boolean.
Sa do të jetë në rastin tonë?
Në rastin tonë, numri i variablave është dy, dhe numri i veprimeve logjike është pesë, domethënë numri i kolonave të tabelës së së vërtetës është shtatë.
Mirë. Më larg?
Ne ndërtojmë një tabelë me numrin e caktuar të rreshtave dhe kolonave, caktojmë kolonat dhe futim në tabelë grupet e mundshme të vlerave të variablave logjikë fillestarë dhe plotësojmë tabelën e së vërtetës sipas kolonave.
Cilin operacion do të kryejmë së pari? Merrni parasysh vetëm kllapat dhe prioritetet
Mund të bësh fillimisht një mohim logjik, ose të gjesh vlerën së pari në kllapin e parë, pastaj të kundërtën dhe vlerën në kllapin e dytë, pastaj vlerën midis këtyre kllapave

Tani mund të përcaktojmë vlerën e një funksioni boolean për çdo grup variablash boolean
Tani shkruajmë artikullin "Shprehje logjike ekuivalente".
Quhen shprehjet Boolean në të cilat kolonat e fundit të tabelave të së vërtetës përputhen ekuivalente. Shenja "=" përdoret për të treguar shprehje logjike ekuivalente,
Le të vërtetojmë se shprehjet logjike ┐ А & ┐В dhe AvB janë ekuivalente. Le të ndërtojmë fillimisht tabelën e së vërtetës së shprehjes logjike

Sa kolona do të ketë në tabelë? 5
Cilin operacion do të kryejmë së pari? Përmbysja A, përmbysja B

Tani le të ndërtojmë tabelën e së vërtetës së shprehjes logjike AvB
Sa rreshta do të ketë në tabelë? 4
Sa kolona do të ketë në tabelë? 4

Të gjithë e kuptojmë se nëse duhet të gjejmë mohimin për të gjithë shprehjen, atëherë përparësia, në rastin tonë, i përket disjunksionit. Prandaj, ne kryejmë së pari disjuksionin dhe më pas inversionin. Përveç kësaj, ne mund të rishkruajmë shprehjen tonë boolean AvB. Sepse ne duhet të gjejmë mohimin e të gjithë shprehjes, dhe jo të ndryshoreve individuale, atëherë anasjellta mund të merret jashtë kllapave ┐ (AvB), dhe ne e dimë që së pari e gjejmë vlerën në kllapa

Kanë ndërtuar tabela. Tani le të krahasojmë vlerat në kolonat e fundit të tabelave të së vërtetës, pasi janë kolonat e fundit që janë ato që rezultojnë. Ato përkojnë, prandaj shprehjet logjike janë ekuivalente dhe mund të vendosim shenjën “=” ndërmjet tyre.

Zgjidhja e problemeve

1.

Sa variabla përmban kjo formulë? 3
Sa rreshta dhe kolona do të ketë tabela? 8 dhe 8
Cila do të jetë sekuenca e veprimeve në shembullin tonë? (përmbysja, operacionet me kllapa, operacioni me kllapa)

2. Vërtetoni me ndihmën e tabelave të së vërtetës ekuivalencën e shprehjeve logjike të mëposhtme:

(A → B) DHE (Av┐B)

Çfarë përfundimi nxjerrim? Këto shprehje boolean nuk janë ekuivalente

Detyre shtepie

Vërtetoni duke përdorur tabelat e së vërtetës që shprehjet logjike

┐A v ┐B dhe A & B janë ekuivalente

Shpjegimi i materialit të ri (vazhdim)

Ne kemi përdorur konceptin e "tabela e së vërtetës" për disa mësime me radhë, dhe çfarë është tabela e së vërtetës, si mendoni?
Një tabelë e vërtetësisë është një tabelë që vendos një korrespondencë midis grupeve të mundshme të vlerave të ndryshoreve logjike dhe vlerave të funksioneve.
Si i bëtë detyrat e shtëpisë, cili ishte përfundimi juaj?
Shprehjet janë ekuivalente
Mos harroni, në mësimin e mëparshëm kemi bërë një formulë nga një deklaratë e përbërë, duke zëvendësuar pohimet e thjeshta 2 * 2 = 4 dhe 2 * 2 = 5 me ndryshoret A dhe B
Tani le të mësojmë të bëjmë shprehje logjike nga deklaratat.

Shkruani detyrën

Shkruajeni atë në formën e një formule logjike të deklaratës:

1) Nëse Ivanov është i shëndetshëm dhe i pasur, atëherë ai është i shëndetshëm

Ne analizojmë deklaratën. Zbulimi i deklaratave të thjeshta

A - Ivanov është i shëndetshëm
B - Ivanov është i pasur

Në rregull, si do të duket formula atëherë? Vetëm mos harroni, në mënyrë që kuptimi i deklaratës të mos humbasë, vendosni kllapa në formulë

2) Një numër është i thjeshtë nëse pjesëtohet vetëm me 1 dhe me vetveten

A - numri pjesëtohet vetëm me 1
B - numri është i pjesëtueshëm vetëm në vetvete
C - numri është i thjeshtë

3) Nëse një numër pjesëtohet me 4, ai pjesëtohet me 2

A - i pjesëtueshëm me 4
B - i pjesëtueshëm me 2

4) Një numër arbitrar është ose i pjesëtueshëm me 2 ose i plotpjesëtueshëm me 3

A - i pjesëtueshëm me 2
B - i pjesëtueshëm me 3

5) Një sportist i nënshtrohet skualifikimit nëse sillet në mënyrë të gabuar në raport me një kundërshtar ose një gjyqtar dhe nëse ka marrë "doping".

A - atleti i nënshtrohet skualifikimit
B - sillet në mënyrë të gabuar ndaj kundërshtarit
С - sillet në mënyrë të gabuar ndaj gjyqtarit
D - mori "doping".

Zgjidhja e problemeve

1. Ndërtoni një tabelë të së vërtetës për një formulë

((p & q) → (p → r)) v f

Duke shpjeguar sa rreshta dhe kolona do të ketë në tabelë? (8 dhe 7) Cila do të jetë sekuenca e veprimeve dhe pse?

Ne shikuam kolonën e fundit dhe arritëm në përfundimin se për çdo grup parametrash hyrëse, formula merr një vlerë të vërtetë, një formulë e tillë quhet tautologji. Le të shkruajmë përkufizimin:

Një formulë quhet një ligj i logjikës, ose një tautologji, nëse merr të njëjtën vlerë "të vërtetë" për çdo grup vlerash të variablave të përfshirë në këtë formulë.
Dhe nëse të gjitha vlerat janë false, çfarë mendoni për një formulë të tillë?
Mund të themi se formula nuk është e realizueshme

2. Shkruani në formën e një formule logjike të pohimit:

Administrata porti detar lëshoi ​​urdhrin e mëposhtëm:

1. Nëse kapiteni i anijes merr një udhëzim të veçantë, atëherë ai duhet të largohet nga porti në anijen e tij.
2. Nëse kapiteni nuk merr udhëzime të veçanta, atëherë ai nuk duhet të largohet nga porti, përndryshe do t'i hiqet hyrja në këtë port.
3. Kapitenit ose i mohohet hyrja në këtë port, ose nuk merr udhëzime të veçanta

Ne identifikojmë deklarata të thjeshta, hartojmë formula

• A - kapiteni merr një udhëzim të veçantë
• B - largohet nga porti
• C - është i privuar nga pranimi në port

1. ┐А → (┐В v С)
2. С v ┐А

3. Shkruani pohimin e përbërë “(2 * 2 = 4 dhe 3 * 3 = 9) ose (2 * 2 ≠ 4 dhe 3 * 3 ≠ 9)” në formën e një shprehjeje logjike. Ndërtoni një tabelë të së vërtetës.

A = (2 * 2 = 4) B = (3 * 3 = 9)

(A & B) v (┐A & ┐B)

Detyre shtepie

Zgjidhni një pohim të përbërë që ka të njëjtën tabelë të vërtetësisë si jo (jo A dhe jo (B dhe C)).

1. A&V ose CIA;
2. (A ose B) dhe (A ose C);
3. A dhe (B ose C);
4. A ose (jo B ose jo C).

Zgjidhni linjat ku
dhe ne shkruajmë lidhëzat e të gjitha ndryshoreve, për më tepër, nëse ndryshorja në këtë grup është e barabartë me 1, atëherë e shkruajmë atë, dhe nëse ndryshorja = 0, atëherë mohimi i saj.

Për këtë shembull

lidhja e këtyre ndarjeve do të jetë formula e dëshiruar:

Përkufizimi: Lidhëza thirrur elementare nëse të gjithë variablat e përfshirë në të janë të ndryshëm. Numri i shkronjave të përfshira në një lidhëz elementare ose në ndarje elementare quhet gradë.

Numri 1 konsiderohet një lidhje elementare e rangut 0. Një ndryshore konsiderohet një lidhje elementare ose një ndarje elementare e renditjes 1. Numri 0 konsiderohet një lidhje elementare e renditjes 0. Çdo lidhje e ndryshoreve që nuk është identike e gabuar mund të jetë reduktuar në një formë elementare, dhe çdo ndarje e shkronjave që nuk është identike e vërtetë, gjithashtu mund të reduktohet në një formë elementare. Për këtë është e nevojshme të zbatohen vetitë e komutativitetit, idempotencës dhe asociativitetit të lidhjes dhe disjunksionit.

Është vërtetuar rigorozisht se çdo formulë e algjebrës së Bulit mund të shprehet duke përdorur veprimet , &, . Intuitivisht, ky fakt është i qartë, le të kujtojmë algoritmin për hartimin e një formule sipas tabelës së së vërtetës. Megjithatë, ne përdorim vetëm këto operacione. Kjo formë shënimi quhet trajtë normale disjunctive(DNF). Ky është një lloj mekanizmi për normalizimin e formulave të algjebrës logjike.

Përkufizimi: DNFËshtë një ndarje e lidhëzave të ndryshme elementare (d.m.th., çdo lidhëz përbëhet nga pohime elementare ose mohimet e tyre).

CNF përcaktohet në mënyrë të ngjashme - forma normale konjuktive.

Përkufizimi: Nëse në një DNF të gjitha lidhëzat elementare kanë të njëjtën rang të barabartë me numrin e variablave nga të cilët varet DNF, atëherë quhet perfekte (SDNF).

Teorema. Për çdo funksion që nuk është identikisht fals, ekziston gjithashtu një SDNF unike.

Pasoja ... Çdo funksion Boolean që nuk është identikisht i gabuar mund të përfaqësohet si një mbivendosje &, , , dhe mohimi zbatohet vetëm për ndryshoret.

Përkufizimi: Një sistem veprimesh logjike quhet funksionalisht i plotë nëse, duke përdorur këto operacione dhe konstantat e këtij sistemi, mund të përfaqësohet çdo funksion i algjebrës së Bulit.

Sistemet (&, , ); (, ); (&, ), (/) - janë funksionalisht të plota

(&, ) - funksionalisht i paplotë.

Ne do t'i pranojmë këto fakte pa prova dhe gjatë zgjidhjes së problemeve, do të përpiqemi të paraqesim çdo formulë duke përdorur (&, , ). Më vonë do të diskutojmë në mënyrë më të detajuar çështjen e plotësisë funksionale dhe paplotësisë së sistemit të operacioneve.

Tema 1.7. Metodat e thjeshtimit për shprehjet logjike. Metodat për zgjidhjen e problemeve logjike.

Le të shqyrtojmë një shembull të zgjidhjes së një problemi logjik.

Shembull :

Pasi u diskutua për përbërjen e pjesëmarrësve të ekspeditës, u vendos që duhet të plotësohen dy kushte.

Nëse Arbuzov shkon, atëherë Bryukvin ose Vishnevsky duhet të shkojnë

Nëse Arbuzov dhe Vishnevsky shkojnë, atëherë Bryukvin do të shkojë

Hartoni një formulë logjike për marrjen e një vendimi në një formë simbolike, thjeshtoni formulën që rezulton dhe formuloni një kusht të ri për formimin e një ekspedite duke e përdorur atë.

Le të prezantojmë variablat dhe deklaratat e tyre elementare përkatëse.

- Arbuzov do të shkojë

- Bryukvin do të shkojë

- Vishnevsky do të shkojë

Atëherë kushtet e zhvilluara për formimin e ekspeditës do të duken kështu:

Le të hartojmë një formulë të përgjithshme dhe të thjeshtojmë shprehjen

ato. nëse Arbuzov shkon, Bryukvin do të shkojë.

Shembull:

Nëse moti është i mirë nesër, do të shkojmë në plazh ose do të shkojmë në pyll. Le të hartojmë një formulë për sjelljen tonë për nesër.

- Moti i mirë

- do të shkojmë në plazh

- do të shkojmë në pyll

Tani le të ndërtojmë një mohim të kësaj fraze.

pastaj. na del thënia “Nesër moti do të jetë i mirë dhe ne nuk do të shkojmë në pyll dhe plazh.

Të interesuarit mund të ndërtojnë një tabelë të së vërtetës dhe të kontrollojnë këtë deklaratë.

Shembull :

Brown, John dhe Smith janë arrestuar nën dyshimin për një krim. Njëri prej tyre është një plak i respektuar në qytet, i dyti është zyrtar dhe i treti është një mashtrues i njohur. Gjatë hetimeve, i moshuari ka thënë të vërtetën, mashtruesi ka gënjyer dhe i arrestuari i tretë në një rast ka thënë të vërtetën dhe në tjetrin ka gënjyer.

Ja çfarë thanë ata:

Brown: E bëra. Nuk është faji i Gjonit. (B dhe D)

John: Nuk është faji i Brown. Smith i jashtëligjshëm. (B&C)

Smith: Nuk është faji im. Faji Brown (C & B)

Le t'i përshkruajmë këto deklarata zyrtarisht:

- krimi u krye nga Brown

- krimi u krye nga Gjoni

- krimi u krye nga Smith

Pastaj fjalët e tyre përshkruhen me shprehjet e mëposhtme:

Kafe:

Gjoni:

Smith:

Sepse sipas kushteve të problemit, dy nga këto dhe janë të rreme dhe një është e vërtetë, atëherë

Le të hartojmë një tabelë të së vërtetës

Ka mbetur vetëm rasti 2, d.m.th. krimineli Smith, dhe të dyja deklaratat e tij janë të rreme.

prandaj - e rreme dhe - e vertete

= 1 - Gjon plak i dashur

Mbetet që Brown është zyrtar, dhe që nga ajo kohë - e rreme, pra - e vertete.

Duke përdorur ligjet dhe identitetet e algjebrës së Bulit, ju mund të thjeshtoni shprehjet logjike.

Shembull :

Ushtrimi:

Algjebra e logjikës

Algjebra e logjikës

Algjebra e logjikës(eng. algjebër e logjikës) - një nga seksionet kryesore të logjikës matematikore, në të cilën metodat e algjebrës përdoren në shndërrimet logjike.

Themeluesi i algjebrës së logjikës është matematikani dhe logjika anglez J. Boole (1815-1864), i cili e bazoi mësimin e tij logjik në analogjinë midis algjebrës dhe logjikës. Ai shkruante çdo deklaratë duke përdorur simbolet e gjuhës që zhvilloi dhe mori "ekuacione", vërtetësia ose falsiteti i të cilave mund të vërtetohej në bazë të ligjeve të caktuara logjike, si ligjet e ndërrimit, shpërndarjes, asociativitetit, etj.

Moderne algjebër e logjikësështë një degë e logjikës matematikore dhe studion veprimet logjike mbi pohime nga pikëpamja e vlerës së tyre të vërtetë (e vërtetë, e gabuar). Deklaratat mund të jenë të vërteta, të rreme ose të përmbajnë të vërteta dhe të rreme në përmasa të ndryshme.

Deklaratë logjikeËshtë ndonjë fjali deklarative në lidhje me të cilën mund të pohohet pa mëdyshje se përmbajtja e saj është e vërtetë ose e rreme.

Për shembull, "3 herë 3 është 9", "Arkhangelsk në veri të Vologdës" janë pohime të vërteta dhe "Pesë është më pak se tre", "Marsi është një yll" janë të rreme.

Natyrisht, jo çdo fjali mund të jetë një deklaratë logjike, pasi nuk ka gjithmonë kuptim të flasim për falsitetin ose të vërtetën e saj. Për shembull, thënia "Shkenca kompjuterike është një lëndë interesante" është e paqartë dhe kërkon informacion shtesë, dhe pohimi "Për një student të klasës 10-A AA Ivanov, shkenca kompjuterike është një lëndë interesante", në varësi të interesave të AA Ivanov, mund të marrë mbi kuptimin e "të vërtetës" ose "Gënjeshtrës".

përveç algjebër propozicionale me dy vlera, në të cilën pranohen vetëm dy vlera - "e vërtetë" dhe "e rreme", ekziston algjebër propozicionale me shumë vlera. Në një algjebër të tillë, përveç kuptimeve "e vërtetë" dhe "e rreme", përdoren vlera të tilla të vërteta si "ndoshta", "e mundur", "e pamundur", etj.

Në algjebër, logjikat ndryshojnë thjeshtë(fillore) thëniet, e shënuar me shkronja latine (A, B, C, D, ...), dhe komplekse(i përbërë), i përbërë nga disa të thjeshta që përdorin lidhje logjike, për shembull, si p.sh "Jo", "dhe", "ose", "atëherë dhe vetëm atëherë", "nëse ... atëherë"... E vërteta ose falsiteti i pohimeve komplekse të marra në këtë mënyrë përcaktohet nga kuptimi i pohimeve të thjeshta.

Le të shënojmë si A pohimi “Algjebra e logjikës zbatohet me sukses në teorinë e qarqeve elektrike”, dhe përmes V- "Algjebra e logjikës përdoret në sintezën e qarqeve rele-kontakt".

Pastaj pohimi i përbërë "Algjebra e logjikës zbatohet me sukses në teorinë e qarqeve elektrike dhe në sintezën e qarqeve të kontaktit rele" mund të shkruhet shkurtimisht si A dhe B; këtu "dhe" është një lidhje logjike. Natyrisht, që nga deklaratat elementare A dhe B janë të vërteta, atëherë pohimi i përbërë A dhe B.

Çdo lidhje logjike konsiderohet si një operacion mbi deklaratat logjike dhe ka emrin dhe emërtimin e vet.

Ekzistojnë vetëm dy vlera logjike: e vërtetë dhe e rreme (FALSE)... Kjo korrespondon me paraqitjen dixhitale - 1 dhe 0 ... Rezultatet e çdo operacioni logjik mund të regjistrohen në formën e një tabele. Tabela të tilla quhen tabela të së vërtetës.

Veprimet bazë të algjebrës së Bulit

1. Negacion logjik, përmbysje(lat. përmbysja- inversion) - një operacion logjik, si rezultat i të cilit një deklaratë e re merret nga një deklaratë e caktuar (për shembull, A) ( jo A), i cili quhet mohimi i deklaratës origjinale, e shënuar simbolikisht me një shirit sipër ($ A↖ (-) $) ose me konventa të tilla si ¬, "jo", dhe lexon: "Jo A", "A është e rreme", "nuk është e vërtetë që A", "mohim i A"... Për shembull, "Marsi është një planet i sistemit diellor" (duke thënë A); "Marsi nuk është një planet i sistemit diellor" ($ A↖ (-) $); pohimi "10 është një numër i thjeshtë" (deklarata B) është e rreme; thënia "10 nuk është numër i thjeshtë" (duke thënë B) është e vërtetë.

Një veprim i përdorur në lidhje me një sasi quhet unare... Tabela e vlerave të këtij operacioni ka formën

Deklarata $ A↖ (-) $ është e gabuar kur A është e vërtetë dhe e vërtetë kur A është e gabuar.

Gjeometrikisht, mohimi mund të përfaqësohet si më poshtë: nëse A është një grup pikash, atëherë $ A↖ (-) $ është plotësimi i bashkësisë A, domethënë të gjitha pikat që nuk i përkasin grupit A.

2.Lidhëza(lat. lidhore- lidhje) - shumëzim logjik, një operacion që kërkon të paktën dy vlera logjike (operandë) dhe lidh dy ose më shumë deklarata duke përdorur një lidhje "dhe"(për shembull, "A dhe B"), që simbolikisht shënohet me shenjën ∧ (A ∧ B) dhe shkruhet: "A dhe B". Shenjat e mëposhtme përdoren gjithashtu për të treguar lidhjen: A ∙ B; A & B, A dhe B, dhe nganjëherë nuk vihet asnjë shenjë ndërmjet pohimeve: AB. Një shembull i shumëzimit logjik: "Ky trekëndësh është dykëndësh dhe kënddrejtë". Një deklaratë e dhënë mund të jetë e vërtetë vetëm nëse plotësohen të dyja kushtet, përndryshe deklarata është e rreme.

Thënie A ∧ Vështë e vërtetë vetëm nëse të dyja pohimet - A dhe V janë të vërteta.

Gjeometrikisht, një lidhëz mund të paraqitet si më poshtë: nëse A, B A ∧ V ka një kryqëzim grupesh A dhe V.

3. Disjunksion(lat. ndarje- ndarje) - shtim logjik, një operacion që lidh dy ose më shumë deklarata duke përdorur një lidhje "ose"(për shembull, "A ose B"), që simbolikisht shënohet me shenjën ∨ (A∨ V) dhe lexon: "A ose B"... Shenjat e mëposhtme përdoren gjithashtu për të treguar ndarjen: A + B; A ose B; A | B... Një shembull i mbledhjes logjike: "Numri x është i pjesëtueshëm me 3 ose 5". Kjo deklaratë do të jetë e vërtetë nëse plotësohen të dyja kushtet ose të paktën një nga kushtet.

Tabela e së vërtetës së operacionit ka formën

Thënie A∨ V e rreme vetëm nëse të dyja deklaratat - A dhe V janë të rreme.

Shtesa gjeometrikisht logjike mund të paraqitet si vijon: nëse A, B Janë disa grupe pikash, atëherë A ∨ VËshtë bashkimi i bashkësive A dhe V, pra figura që bashkon katrorin dhe rrethin.

4. Ndarja rreptësisht e ndarë, shtimi mod dy- një operacion logjik që lidh dy deklarata duke përdorur një lidhje "ose", përdoret në kuptimin ekskluziv, i cili simbolikisht shënohet me shenjat ∨ ∨ ose ⊕ ( A ∨ ∨ B, A ⊕ V) dhe lexon: "Ose A ose B"... Një shembull i modulit dy të mbledhjes është thënia "Ky trekëndësh është i mpirë ose i mprehtë". Deklarata është e vërtetë nëse ndonjë prej kushteve është i vërtetë.

Tabela e së vërtetës së operacionit ka formën

Pohimi A ⊕ B është i vërtetë vetëm kur pohimet A dhe B kanë kuptime të ndryshme.

5. Implikimi(lat. implisito- i lidhur ngushtë) - një operacion logjik që lidh dy deklarata duke përdorur një pako "Nese atehere" në një deklaratë komplekse, e cila simbolikisht shënohet me shenjën → ( A → V) dhe lexon: "Nëse A, atëherë B", "A përfshin B", "B rrjedh nga A", "A nënkupton B"... Shenja ⊃ (A ⊃ B) përdoret gjithashtu për të treguar nënkuptimin. Një shembull i një implikimi: "Nëse katërkëndëshi që rezulton është një katror, ​​atëherë rreth tij mund të përshkruhet një rreth." Ky operacion lidh dy shprehje të thjeshta Boolean, nga të cilat e para është kusht dhe e dyta është pasojë. Rezultati i një operacioni është i rremë vetëm kur premisa është e vërtetë dhe efekti është i rremë. Për shembull, "Nëse 3 * 3 = 9 (A), atëherë Dielli është një planet (B)", rezultati i nënkuptimit A → B është i rremë.

Tabela e së vërtetës së operacionit ka formën

Për funksionimin e nënkuptimit, është e vërtetë se çdo gjë mund të pasojë nga një gënjeshtër dhe vetëm e vërteta mund të pasojë nga e vërteta.

6. Ekuivalencë, nënkuptim i dyfishtë, ekuivalencë(lat. aequalis- të barabartë dhe valentis- valid) - një operacion logjik që lejon dy pohime A dhe V merrni një deklaratë të re A ≡ B e cila lexon: "A është e barabartë me B"... Simbolet e mëposhtme përdoren gjithashtu për të treguar ekuivalencën: ⇔, ∼. Ky operacion mund të shprehet me ligamente "Atëherë dhe vetëm atëherë", "e nevojshme dhe e mjaftueshme", "ekuivalente"... Një shembull i ekuivalencës është pohimi: "Një trekëndësh do të jetë drejtkëndor nëse dhe vetëm nëse njëri prej këndeve është 90 gradë."

Tabela e vërtetësisë së veprimit të ekuivalencës ka formën

Operacioni i ekuivalencës është i kundërt i modulit të mbledhjes dy dhe ka rezultatin "e vërtetë" nëse dhe vetëm nëse vlerat e variablave përkojnë.

Duke ditur kuptimet e pohimeve të thjeshta, është e mundur të përcaktohen kuptimet e pohimeve komplekse në bazë të tabelave të së vërtetës. Është e rëndësishme të dini se tre operacione janë të mjaftueshme për të përfaqësuar çdo funksion të algjebrës së logjikës: lidhja, disjunksioni dhe mohimi.

Prioriteti i kryerjes së operacioneve logjike është si më poshtë: mohimi ( "jo") ka përparësinë më të lartë, pastaj lidhja ( "dhe"), pas lidhëzës - ndarjes ( "ose").

Me ndihmën e variablave logjikë dhe operacioneve logjike, çdo deklaratë logjike mund të zyrtarizohet, domethënë të zëvendësohet nga një formulë logjike. Në të njëjtën kohë, pohimet elementare që formojnë një pohim të përbërë mund të jenë krejtësisht të palidhura në kuptim, por kjo nuk ndërhyn në përcaktimin e së vërtetës ose falsitetit të një deklarate të përbërë. Për shembull, deklarata "Nëse pesë është më shumë se dy ( A), atëherë e marta vjen gjithmonë pas të hënës ( V) "- nënkuptim A→ V, dhe rezultati i operacionit në këtë rast është "i vërtetë". Në veprimet logjike, kuptimi i pohimeve nuk merret parasysh, merret parasysh vetëm e vërteta ose falsiteti i tyre.

Merrni, për shembull, ndërtimin e një deklarate të përbërë nga deklaratat A dhe V e cila do të ishte e gabuar nëse dhe vetëm nëse të dy pohimet janë të vërteta. Në tabelën e së vërtetës për veprimin e modulit të mbledhjes dy, gjejmë: 1 ⊕ 1 = 0. Dhe pohimi mund të jetë, për shembull, ky: "Ky top është plotësisht i kuq ose plotësisht blu." Prandaj, nëse deklarata A“Ky top është tërësisht i kuq” është i vërtetë dhe pohimi V"Ky top është plotësisht blu" është e vërtetë, atëherë deklarata e përbërë është një gënjeshtër, sepse topi nuk mund të jetë njëkohësisht i kuq dhe blu.

Shembuj të zgjidhjes së problemeve

Shembulli 1. Përcaktoni për vlerat e treguara të X vlerën e deklaratës logjike ((X> 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Zgjidhje. Sekuenca e veprimeve është si më poshtë: së pari kryhen operacionet e krahasimit në kllapa, më pas disjunksioni dhe i fundit është operacioni i nënkuptimit. Operacioni i disjuksionit ∨ është false nëse dhe vetëm nëse të dy operandët janë false. Tabela e së vërtetës për nënkuptimin është

Nga këtu marrim:

1) për X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) për X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) për X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Shembulli 2. Specifikoni grupin e vlerave të numrave të plotë X për të cilat shprehja ¬ ((X> 2) → (X> 5)) është e vërtetë.

Zgjidhje. Operacioni i mohimit zbatohet në të gjithë shprehjen ((X> 2) → (X> 5)), prandaj, kur shprehja ¬ ((X> 2) → (X> 5)) është e vërtetë, shprehja ((X > 2) → (X > 5)) është e rreme. Prandaj, është e nevojshme të përcaktohet se për cilat vlera të X shprehja ((X> 2) → (X> 5)) është e rreme. Operacioni i nënkuptimit merr vlerën "false" vetëm në një rast: kur false rrjedh nga e vërteta. Dhe kjo bëhet vetëm për X = 3; X = 4; X = 5.

Shembulli 3. Për cilën nga fjalët e dhëna është i gabuar pohimi ¬ (gërma e parë e një zanoreje ∧ shkronja e tretë e një zanoreje) ⇔ një varg me 4 karaktere? 1) assa; 2) biskota; 3) misër; 4) gabim; 5) burrë i fortë.

Zgjidhje. Le të shqyrtojmë të gjitha fjalët e sugjeruara në sekuencë:

1) për fjalën gomar marrim: ¬ (1 ∧ 0) ⇔ 1, 1 ⇔ 1 - pohimi është i vërtetë;

2) për fjalën kuku marrim: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - pohimi është i vërtetë;

3) për fjalën misër marrim: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - pohimi është i rremë;

4) për fjalën gabim, marrim: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - pohimi është i vërtetë;

5) për fjalën njeri i fortë marrim: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - pohimi është i rremë.

Shprehjet Boolean dhe transformimi i tyre

Nën shprehje logjike ju duhet të kuptoni një regjistrim të tillë që mund të marrë vlerën logjike "e vërtetë" ose "e gabuar". Me këtë përkufizim, është e nevojshme të dallohen shprehjet logjike:

• shprehje që përdorin operacione krahasimi ("më e madhe se", "më pak se", "e barabartë", "jo e barabartë", etj.) dhe marrin vlera logjike (për shembull, shprehja a> b, ku a = 5 dhe b = 7, është e barabartë me vlerën "false");
• shprehje të drejtpërdrejta logjike të lidhura me vlera logjike dhe operacione logjike (për shembull, A ∨ B ∧ C, ku A = e vërtetë, B = e gabuar dhe C = e vërtetë).

Shprehjet Boolean mund të përfshijnë funksione, operacione algjebrike, operacione krahasimi dhe operacione logjike. Në këtë rast, përparësia për kryerjen e veprimeve është si më poshtë:

1. llogaritja e varësive funksionale ekzistuese;
2. kryerja e veprimeve algjebrike (së pari shumëzimi dhe pjesëtimi, pastaj zbritja dhe mbledhja);
3. kryerja e operacioneve të krahasimit (pa rend të caktuar);
4. ekzekutimi i veprimeve logjike (në fillim kryhen operacionet e mohimit, pastaj operacionet e shumëzimit logjik, mbledhjes logjike, operacionet e fundit të nënkuptimit dhe ekuivalencës).

Shprehjet Boolean mund të përdorin kllapa që ndryshojnë rendin në të cilin kryhen operacionet.

Shembull. Gjeni vlerën e një shprehjeje:

1 $ ≤ a ∨ A ∨ sin (π / a - π / b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B) $ për a = 2, b = 3, A = e vërtetë, B = e gabuar.

Zgjidhje. Rendi i numërimit të vlerave:

1) b a + a b> a + b, pas zëvendësimit marrim: 3 2 + 2 3> 2 + 3, pra 17> 2 + 3 = e vërtetë;

2) A ∧ B = e vërtetë ∧ e gabuar = e rreme.

Prandaj, shprehja në kllapa është (b a + a b> a + b ∨ A ∧ B) = e vërtetë ∨ e gabuar = e vërtetë;

3) 1≤ a = 1 ≤ 2 = e vërtetë;

4) mëkat (π / a - π / b)< 1 = sin(π/2 - π/3) < 1 = истина.

Pas këtyre llogaritjeve, më në fund marrim: e vërteta ∨ А ∧ e vërtetë ∧ ¬В ∧ ¬vërtetë.

Tani duhet të kryhen veprimet e mohimit, të ndjekura nga shumëzimi dhe mbledhja logjike:

5) ¬В = ¬false = e vërtetë; ¬ e vërtetë = e rreme;

6) A ∧ e vërtetë ∧ e vërtetë ∧ e gabuar = e vërtetë ∧ e vërtetë ∧ e vërtetë ∧ e gabuar = e rreme;

7) e vërtetë ∨ e gabuar = e vërtetë.

Kështu, rezultati i një shprehjeje boolean vlerat e dhëna është "i vërtetë".

Shënim. Duke marrë parasysh se shprehja origjinale është, në fund, shuma e dy termave, dhe vlera e njërit prej tyre është 1 ≤ a = 1 ≤ 2 = e vërtetë, pa llogaritje të mëtejshme mund të themi se rezultati për të gjithë shprehjen është gjithashtu "e vertete".

Shndërrime identike të shprehjeve logjike

Në algjebrën e logjikës plotësohen ligjet bazë, të cilat bëjnë të mundur kryerjen e shndërrimeve identike të shprehjeve logjike.

Provat e këtyre deklaratave bëhen në bazë të ndërtimit të tabelave të së vërtetës për të dhënat përkatëse.

Shndërrimet ekuivalente të formulave logjike kanë të njëjtin qëllim si shndërrimet e formulave në algjebrën e zakonshme. Ato shërbejnë për të thjeshtuar formulat ose për t'i sjellë ato në një formë të caktuar duke përdorur ligjet bazë të algjebrës së logjikës. Nën thjeshtimi i formulës, i cili nuk përmban operacionet e nënkuptimit dhe ekuivalencës, kuptohet si një transformim ekuivalent që çon në një formulë që përmban ose më pak se numri origjinal i operacioneve ose më pak variabla.

Disa transformime të formulave logjike janë të ngjashme me transformimet e formulave në algjebër e zakonshme (duke marrë faktorin e përbashkët jashtë kllapave, duke përdorur ligjet e zhvendosjes dhe kombinimit, etj.), ndërsa transformimet e tjera bazohen në vetitë që nuk i kanë veprimet e algjebrës së zakonshme. (duke përdorur ligjin e shpërndarjes për lidhjen, ligjet e përthithjes, ngjitjes, de Morgan, etj.).

Le të shohim shembuj të disa teknikave dhe metodave të përdorura për të thjeshtuar formulat logjike:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2.

Për transformim këtu mund të aplikoni ligjin e idempotencës, ligjin e shpërndarjes; një veprim i ndryshueshëm i anasjelltë dhe një operacion konstant.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1.

Këtu, për thjeshtësi, zbatohet ligji i përthithjes.

3) ¬ (X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1.

Kur konvertohet, zbatohet rregulli i de Morgan, funksionimi i një ndryshore me përmbysjen e tij, një operacion me një konstante.

Shembuj të zgjidhjes së problemeve

Shembulli 1. Gjeni një shprehje Boolean ekuivalente me A ∧ ¬ (¬B ∨ C).

Zgjidhje. Zbatojmë rregullin e de Morganit për B dhe C: ¬ (¬B ∨ C) = B ∧ ¬C.

Marrim një shprehje të barazvlefshme me atë origjinale: A ∧ ¬ (¬B ∨ C) = A ∧ B ∧ ¬C.

Përgjigje: A ∧ B ∧ ¬C.

Shembulli 2. Tregoni vlerën e ndryshoreve logjike A, B, C, për të cilat vlera e shprehjes logjike (A ∨ B) → (B ∨ ¬C ∨ B) është e gabuar.

Zgjidhje. Veprimi i nënkuptimit është i rremë vetëm në rastin kur një e rreme rrjedh nga premisa e vërtetë. Prandaj, për një shprehje të caktuar, premisa A ∨ B duhet të marrë vlerën "e vërtetë", dhe pasoja, pra shprehja B ∨ ¬C ∨ B, duhet të marrë vlerën "e gabuar".

1) A ∨ B - rezultati i disjuksionit është "i vërtetë" nëse të paktën një nga operandët është "i vërtetë";

2) B ∨ ¬C ∨ B - shprehja është e gabuar nëse të gjithë termat kanë vlerën "false", domethënë B - "false"; ¬C - "false", dhe për rrjedhojë, ndryshorja C ka vlerën "e vërtetë";

3) nëse marrim parasysh premisën dhe marrim parasysh se B është "false", atëherë marrim se vlera e A është "e vërtetë".

Përgjigje: A është e vërtetë, B është e rreme, C është e vërtetë.

Shembulli 3. Cili është numri i plotë më i madh X për të cilin pohimi (35

Zgjidhje. Le të shkruajmë tabelën e së vërtetës për operacionin e nënkuptimit:

Shprehja X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Përgjigje: X = 5.

Përdorimi i shprehjeve Boolean për të përshkruar rajonet gjeometrike

Shprehjet Boolean mund të përdoren për të përshkruar zonat gjeometrike. Në këtë rast, problemi formulohet si më poshtë: për një rajon të caktuar gjeometrik, shkruani një shprehje logjike që merr vlerën "e vërtetë" për vlerat x, y nëse dhe vetëm nëse ndonjë pikë me koordinata (x; y) i përket rajonit gjeometrik.

Le të shqyrtojmë përshkrimin e një zone gjeometrike duke përdorur një shprehje logjike duke përdorur shembuj.

Shembulli 1. Përcaktohet një imazh i një zone gjeometrike. Shkruani një shprehje boolean që përshkruan grupin e pikave që i përkasin.

1) .

Zgjidhje. Një rajon gjeometrik i dhënë mund të përfaqësohet si një grup i rajoneve të mëposhtme: rajoni i parë - D1 - gjysmë plani $ (x) / (- 1) + (y) / (1) ≤ 1 $, i dyti - D2 - rrethi me qendër në origjinë $ x ^ 2 + y ^ 2 ≤ 1 $. Kryqëzimi i tyre D1 $ ∩ $ D2 është domeni i dëshiruar.

Rezultati: shprehja boolean $ (x) / (- 1) + (y) / (1) ≤ 1 ∧ x ^ 2 + y ^ 2 ≤ 1 $.

2)

Kjo zonë mund të shkruhet kështu: | x | ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1.

Shënim. Gjatë ndërtimit të një shprehjeje logjike përdoren pabarazi të dobëta, që do të thotë se edhe kufijtë e figurave i përkasin zonës së hijezuar. Nëse përdoren pabarazi të rrepta, atëherë kufijtë nuk do të merren parasysh. Kufijtë që nuk i përkasin rajonit zakonisht tregohen me një vijë me pika.

Ju mund të zgjidhni problemin e anasjelltë, domethënë: vizatoni një zonë për një shprehje logjike të dhënë.

Shembulli 2. Vizatoni dhe vizatoni një zonë për pikat e së cilës kushti logjik është i plotësuar y ≥ x ∧ y + x ≥ 0 ∧ y< 2 .

Zgjidhje. Zona e kërkuar është kryqëzimi i tre gjysmëplanëve. Ndërtojmë në rrafshin (x, y) drejtëza y = x; y = -x; y = 2. Këta janë kufijtë e zonës, dhe kufiri i fundit y = 2 nuk i përket zonës, prandaj e vizatojmë me një vijë me pika. Për të plotësuar mosbarazimin y ≥ x, është e nevojshme që pikat të jenë në të majtë të drejtëzës y = x, dhe mosbarazimi y = -x plotësohet për pikat që janë në të djathtë të drejtëzës y = -x. Kushti y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Përdorimi i funksioneve logjike për të përshkruar qarqet elektrike

Funksionet logjike janë shumë të dobishme për të përshkruar se si funksionojnë qarqet elektrike. Pra, për qarkun e paraqitur në Fig., ku vlera e ndryshores X është gjendja e çelësit (nëse është i ndezur, vlera e X është "e vërtetë", dhe nëse është e fikur, është "false") , kjo vlerë e Y është gjendja e llambës (nëse është ndezur - vlera është "e vërtetë", dhe nëse jo - "e gabuar"), funksioni logjik do të shkruhet si më poshtë: Y = X. Funksioni Y quhet funksioni i përcjellshmërisë.

Për qarkun e paraqitur në Fig., funksioni logjik Y ka formën: Y = X1 ∪ X2, pasi një çelës i ndezur mjafton që drita të digjet. Në diagramin në figurë, që llamba të digjet, duhet të ndizen të dy çelësat, prandaj funksioni i përcjellshmërisë ka formën: Y = X1 ∧ X2.

Për një qark më kompleks, funksioni i përcjellshmërisë do të jetë: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

Qarku mund të përmbajë gjithashtu kontakte mbyllëse. Në këtë rast, kontakti i hapur si çelës siguron që drita të ndizet kur butoni lëshohet dhe nuk shtypet. Për qarqe të tilla, çelësi i shkëputjes përshkruhet me mohim.

Të dy skemat quhen baraz me nëse rryma kalon nëpër njërën prej tyre kur kalon edhe në tjetrën. Nga dy qarqet ekuivalente, më i thjeshtë është qarku, funksioni i përcjellshmërisë së të cilit përmban më pak elementë. Detyra për të gjetur skemat më të thjeshta midis ekuivalenteve është shumë e rëndësishme.

Përdorimi i aparatit të algjebrës logjike në projektimin e qarqeve logjike

Algjebra e matematikës logjike është shumë e dobishme për të përshkruar se si funksionon hardueri i kompjuterit. Çdo informacion kur përpunohet në një kompjuter përfaqësohet në formë binare, domethënë është i koduar nga një sekuencë 0 dhe 1. Përpunimi i sinjaleve binare që korrespondojnë me 0 dhe 1 kryhet në kompjuter nga elementë logjikë. Portat logjike që kryejnë veprime logjike bazë DHE, OSE, JO, janë paraqitur në Fig.

Simbolet e elementeve logjike janë standarde dhe përdoren në hartimin e qarqeve logjike të një kompjuteri. Duke përdorur këto skema, ju mund të zbatoni çdo funksion logjik që përshkruan funksionimin e një kompjuteri.

Teknikisht, një element logjik kompjuterik zbatohet në formë qark elektrik, e cila është një lidhje e pjesëve të ndryshme: dioda, tranzistorë, rezistorë, kondensatorë. Hyrja e një elementi logjik, i cili gjithashtu quhet portë, merr sinjale elektrike të niveleve të tensionit të lartë dhe të ulët, dhe një sinjal dalës jepet gjithashtu ose nivel i lartë ose i ulët. Këto nivele korrespondojnë me një nga shtetet sistemi binar: dhjetë; E VËRTETA është E rreme. Çdo element logjik ka simbolin e tij, i cili shpreh funksionin e tij logjik, por nuk tregon se çfarë qarku elektronik është zbatuar në të. Kjo i bën qarqet komplekse logjike më të lehta për t'u shkruar dhe kuptuar. Funksionimi i qarqeve logjike përshkruhet duke përdorur tabelat e së vërtetës. Shënimi konvencional në qarkun OR, shenja "1" - nga shënimi i vjetëruar i disjunksionit si "> = 1" (vlera e disjunksionit është 1 nëse shuma e dy operandëve është më e madhe ose e barabartë me 1). Shenja "&" në diagramin AND është një shkurtim i fjalës angleze dhe.

Qarqet logjike elektronike përbëhen nga elementë logjikë që kryejnë operacione logjike më komplekse. Një grup elementesh logjike, i përbërë nga elementet NOT, OSE, DHE, me të cilat mund të ndërtoni një strukturë logjike të çdo kompleksiteti, quhet i kompletuar funksionalisht.

Ndërtimi i Tabelave të së Vërtetës së Shprehjeve Boolean

Për një formulë logjike, gjithmonë mund të shkruani tabela e së vërtetës, pra për të paraqitur një funksion të caktuar logjik në formë tabelare. Në këtë rast, tabela duhet të përmbajë të gjitha kombinimet e mundshme të argumenteve të funksionit (formula) dhe vlerat përkatëse të funksionit (formula rezulton në një grup të caktuar vlerash).

Një formë e përshtatshme shënimi për gjetjen e vlerave të një funksioni është një tabelë që përmban, përveç vlerave të ndryshoreve dhe vlerave të funksionit, edhe vlerat e llogaritjeve të ndërmjetme. Shqyrtoni një shembull të ndërtimit të një tabele të vërtetë për formulën $ (X1) ↖ (-) ∧ X2 ∨ (X1 ∨ X2) ↖ (-) ∨ X1 $.

Nëse një funksion merr vlerën 1 për të gjitha grupet e vlerave të variablave, ajo është identike e vërtetë; nëse për të gjitha grupet e vlerave hyrëse funksioni merr vlerën 0, është në mënyrë identike të rreme; nëse grupi i daljeve përmban edhe 0 edhe 1, thirret funksioni e realizueshme... Shembulli i mësipërm është një shembull i një funksioni identikisht të vërtetë.

Duke ditur formën analitike të një funksioni logjik, gjithmonë mund të shkoni te formë tabelare funksionet logjike. Me ndihmën e një tabele të dhënë të së vërtetës, mund të zgjidhet problemi i anasjelltë, përkatësisht: për një tabelë të caktuar, ndërtoni një formulë analitike për një funksion logjik. Ekzistojnë dy forma të ndërtimit të varësisë analitike të një funksioni logjik sipas një funksioni të caktuar tabele.

1. Forma normale disjunctive (DNF)- shuma e produkteve të formuara nga variablat dhe mohimet e tyre për vlera të rreme.

Algoritmi për ndërtimin e DNF është si më poshtë:

1. në tabelën e vërtetësisë së funksionit, zgjidhen grupe argumentesh për të cilat format logjike janë të barabarta me 1 ("e vërtetë");
2. të gjitha grupet logjike të zgjedhura regjistrohen si produkte logjike të argumenteve, duke i lidhur ato në mënyrë sekuenciale me njëra-tjetrën me anë të veprimit të një shume logjike (ndarje);
3. për argumentet që janë false, operacioni i mohimit zbatohet në rekordin e ndërtuar.

Shembull. Ndërtoni një funksion që përcakton se numri i parë është i barabartë me të dytin duke përdorur metodën DNF. Tabela e vërtetësisë së funksionit ka formën

Zgjidhje. Ne zgjedhim grupe vlerash argumentesh në të cilat funksioni është i barabartë me 1. Këto janë rreshtat e parë dhe të katërt të tabelës (rreshti i titullit nuk merret parasysh kur numërohet).

I shkruajmë produktet logjike të argumenteve të këtyre grupeve, duke i kombinuar me një shumë logjike: X1 ∧ X2 ∨ X1 ∧ X2.

Ne shkruajmë mohimin në lidhje me argumentet e grupeve të zgjedhura që kanë një vlerë false (rreshti i katërt i tabelës; grupi i dytë në formulë; elementët e parë dhe të dytë): X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

Përgjigje: F (X1, X2) = X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

2. Forma normale lidhore (CNF)- prodhimi i shumave të formuara nga ndryshoret dhe mohimet e tyre për vlerat e vërteta.

Algoritmi për ndërtimin e CNF është si më poshtë:

1. në tabelën e së vërtetës zgjidhen grupe argumentesh për të cilat format logjike janë të barabarta me 0 ("false");
2. të gjitha grupet logjike të zgjedhura si shuma logjike të argumenteve shkruhen në mënyrë sekuenciale, duke i lidhur ato së bashku me veprimin e një produkti logjik (lidhëz);
3. për argumentet që janë të vërteta, operacioni i mohimit vendoset në rekordin e ndërtuar.

Shembuj të zgjidhjes së problemeve

Shembulli 1. Konsideroni shembullin e mëparshëm, domethënë ndërtoni një funksion që përcakton se numri i parë është i barabartë me të dytin, duke përdorur metodën CNF. Për një funksion të caktuar, tabela e tij e së vërtetës ka formën

Zgjidhje. Ne zgjedhim grupe vlerash argumenti në të cilat funksioni është i barabartë me 0. Këto janë rreshtat e dytë dhe të tretë (rreshti i titullit nuk merret parasysh kur numërohet).

Ne shkruajmë shumat logjike të argumenteve të këtyre grupeve, duke i kombinuar me një produkt logjik: X1 ∨ X2 ∧ X1 ∨ X2.

Ne shkruajmë mohimin në lidhje me argumentet e grupeve të zgjedhura që kanë një vlerë të vërtetë (rreshti i dytë i tabelës, grupi i parë i formulës, elementi i dytë; për rreshtin e tretë, ky është grupi i dytë i formulës, elementi i parë): X1 ∨ $ (X2) ↖ (-) $ ∧ $ ( X1) ↖ (-) $ ∨ X2.

Kështu, është marrë një regjistrim i funksionit logjik në CNF.

Përgjigje: X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2.

Vlerat e funksionit të marra nga të dy metodat janë ekuivalente. Për të vërtetuar këtë pohim, ne përdorim rregullat e logjikës: F (X1, X2) = X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2 = X1 ∧ $ (X1) ↖ (-) $ ∨ X1 ∧ X2 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ $ (X2) ↖ (-) $ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $ (X2 ) ↖ (- ) $ ∧ $ (X1) ↖ (-) $ ∨ 0 = X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

Shembulli 2... Ndërtoni një funksion boolean për një tabelë të dhënë të së vërtetës:

Formula e kërkuar: X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ X2.

Mund të thjeshtohet: X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ X2 = X2 ∧ (X1 ∨ $ (X1) ↖ (-) $) = X2 ∧ 1 = X2.

Shembulli 3. Për tabelën e dhënë të së vërtetës, ndërtoni një funksion logjik duke përdorur metodën DNF.

Formula e kërkuar: X1 ∧ X2 ∧ X ∨ $ (X1) ↖ (-) $ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $ (X3) ↖ (-) $ ∪ X1 ∧ $ (X2) $ ↖ $ (X3) ↖ (-) $.

Formula është mjaft e rëndë dhe duhet thjeshtuar:

X1 ∧ X2 ∧ X3 ∨ $ (X1) ↖ (-) $ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $ (X3) ↖ (-) $ ∨ X1 ∧ $ (X2) ↈ (-) $ (X3) ↖ (-) $ = X2 ∧ X3 ∧ (X1 ∨ $ (X1) ↖ (-) $) ∨ X1 ∧ $ (X3) ↖ (-) $ ∧ (X2 ∨ $ (X2) ↖ (-) $) = X2 ∧ X3 ∨ X1 ∧ $ (X3) ↖ (-) $.

Tabelat e së vërtetës për zgjidhjen e problemeve logjike

Përpilimi i tabelave të së vërtetës është një nga mënyrat për të zgjidhur problemet logjike. Kur përdorni këtë zgjidhje, kushtet që përmban problemi rregullohen duke përdorur tabela të përpiluara posaçërisht.

Shembuj të zgjidhjes së problemeve

Shembulli 1. Krijo një tabelë të së vërtetës për një pajisje sigurie që përdor tre sensorë dhe aktivizohet kur vetëm dy prej tyre janë të mbyllura.

Zgjidhje. Natyrisht, zgjidhja do të rezultojë në një tabelë në të cilën funksioni i dëshiruar Y (X1, X2, X3) do të ketë vlerën "true" nëse çdo dy ndryshore kanë vlerën "true".

Shembulli 2. Bëni një orar mësimesh për ditën, duke marrë parasysh që një mësim i shkencës kompjuterike mund të jetë vetëm i pari ose i dyti, një mësim matematike - i pari ose i treti, dhe fizika - i dyti ose i treti. A është e mundur të krijohet një orar që plotëson të gjitha kërkesat? Sa opsione të planifikimit ka?

Zgjidhje. Problemi zgjidhet lehtësisht nëse hartoni tabelën e duhur:

Tabela tregon se ka dy opsione për orarin e dëshiruar:

1. matematikë, shkenca kompjuterike, fizikë;
2. informatikë, fizikë, matematikë.

Shembulli 3. Tre miq erdhën në kampin sportiv - Peter, Boris dhe Alexey. Secili prej tyre është i dhënë pas dy sporteve. Dihet se ka gjashtë sporte të tilla: futboll, hokej, ski, not, tenis, badminton. Gjithashtu dihet se:

1. Boris është më i vjetri;
2. ai që luan futboll është më i ri se ai që luan hokej;
3. duke luajtur futboll dhe hokej dhe Pjetri jetojnë në të njëjtën shtëpi;
4. kur lind një grindje midis një skiatori dhe një tenisti, Boris i pajton ata;
5. Peter nuk mund të luajë tenis apo badminton.

Çfarë lloj sportesh pëlqen secili nga djemtë?

Zgjidhje. Le të hartojmë një tabelë dhe të pasqyrojmë në të kushtet e problemit, duke plotësuar qelizat përkatëse me numrat 0 dhe 1, në varësi të faktit nëse pohimi përkatës është i rremë apo i vërtetë.

Meqenëse ka gjashtë lloje sportesh, rezulton se të gjithë djemtë janë të dhënë pas sporteve të ndryshme.

Nga kushti 4 del se Boris nuk është i dhënë pas skive apo tenisit, por nga kushtet 3 dhe 5 se Pjetri nuk di të luajë futboll, hokej, tenis dhe badminton. Prandaj, sportet e preferuara të Pjetrit janë skijimi dhe noti. Le ta fusim këtë në tabelë dhe të mbushim qelizat e mbetura të kolonave "Ski" dhe "Swimming" me zero.

Tabela tregon se vetëm Alexei mund të luajë tenis.

Nga kushtet 1 dhe 2 rezulton se Boris nuk është futbollist. Kështu, Alexey luan futboll. Vazhdojmë të plotësojmë tabelën. Le të fusim zero në qelizat boshe të rreshtit "Alexey".

Më në fund, kuptojmë se Boris është i dhënë pas hokejit dhe badmintonit. Tabela përfundimtare do të duket kështu:

Përgjigje: Pjetri është i dhënë pas skive dhe notit, Boris luan hokej dhe badminton, dhe Alexey luan futboll dhe tenis.

Funksioni logjikështë një funksion në të cilin variablat marrin vetëm dy vlera: njësi logjike ose zero logjike ... E vërteta ose falsiteti i gjykimeve komplekse është funksion i së vërtetës ose falsitetit të gjykimeve të thjeshta. Ky funksion quhet Funksioni i gjykimit Boolean f (a, b) .

Çdo funksion logjik mund të specifikohet duke përdorur një tabelë të së vërtetës, në anën e majtë të së cilës është shkruar një grup argumentesh, dhe në anën e djathtë - vlerat përkatëse të funksionit logjik. Kur ndërtohet një tabelë e së vërtetës, është e nevojshme të merret parasysh rendi në të cilin kryhen veprimet logjike.

Rendi i kryerjes së operacioneve logjike në një shprehje logjike komplekse:

1. përmbysja;

2. lidhëz;

3. shkëputje;

4. nënkuptim;

5. ekuivalencë.

Kllapat përdoren për të ndryshuar rendin e specifikuar të operacioneve.

Për çdo deklaratë të përbërë (shprehje logjike), mund të ndërtoni tabela e së vërtetës, i cili përcakton vërtetësinë ose falsitetin e tij për të gjitha kombinimet e mundshme të vlerave fillestare të pohimeve të thjeshta (ndryshoret logjike).

Kur ndërtoni një tabelë të së vërtetës, këshillohet që të udhëhiqeni nga një sekuencë e caktuar veprimesh.

Algoritmi për ndërtimin e tabelave të së vërtetës për shprehjet komplekse:

numri i rreshtave = 2 n + rreshti për kokën,

n- numri i pohimeve të thjeshta.

numri i kolonave = numri i variablave + numri i operacioneve logjike;

o të përcaktojë numrin e variablave (shprehje të thjeshta);

o përcakton numrin e veprimeve logjike dhe sekuencën e ekzekutimit të tyre.

3. Plotësoni kolonat me rezultatet e kryerjes së operacioneve logjike në sekuencën e treguar, duke marrë parasysh tabelat e vërtetësisë së operacioneve kryesore logjike.

Shembull: Krijoni një tabelë të së vërtetës për një shprehje logjike:

D = A & (B  C).

Zgjidhja: 

1. Përcaktoni numrin e rreshtave:

ka tre deklarata të thjeshta në hyrje: A, B, C pra n = 3 dhe numri i rreshtave = 2 3 +1 = 9.

2. Përcaktoni numrin e kolonave:

o shprehje të thjeshta (ndryshore): A, B, C ;

o rezultate të ndërmjetme (operacione logjike):

o A - përmbysja (shënoni me E );

o B  C është operacioni i disjuksionit (e shënojmë me F );

o si dhe vlerën përfundimtare të dëshiruar të shprehjes aritmetike:

o D = A & (B  C) ... ato. D = E & F është një operacion lidhor.

3. Plotësoni kolonat duke marrë parasysh tabelat e vërtetësisë së veprimeve logjike.

Krijo një funksion logjik për një tabelë të vërtetë të dhënë.

Rregullat për ndërtimin e një funksioni logjik sipas tabelës së tij të së vërtetës:

1. Zgjidhni në tabelën e së vërtetës ato rreshta në të cilat është vlera e funksionit 1 .

2. Shkruani formulën e kërkuar në formën e një ndarje të disa elementeve logjike. Numri i këtyre elementeve është i barabartë me numrin e rreshtave të zgjedhur.

3. Çdo element logjik në këtë disjunksion shkruhet si lidhëz i argumenteve të funksionit.

4. Nëse vlera e ndonjë argumenti funksioni në rreshtin përkatës të tabelës është 0 , atëherë ky argument merret me mohim.

Zgjidhje.

1. Në rreshtin e parë dhe të tretë të tabelës së vërtetës, vlera e funksionit është 1 .

2. Meqenëse ka dy rreshta, marrim ndarje dy elemente: () V () .

3. Çdo element logjik në këtë ndarje shkruhet në formë lidhëzat argumentet e funksionit X dhe Y : (X dhe Y) V (X dhe Y) .

4. Marrim një argument me mohim nëse vlera e tij në rreshtin përkatës të tabelës është 0 dhe marrim funksionin e kërkuar:

5. Z (X, Y) = (X & Y) V (X & Y) .

Shembulli 4. Përcaktoni pjesëmarrësin në krim bazuar në dy premisa:

1) "Nëse Ivanov nuk ka marrë pjesë ose Petrov ka marrë pjesë, atëherë Sidorov ka marrë pjesë";

2) 2) "Nëse Ivanov nuk mori pjesë, atëherë Sidorov nuk mori pjesë."

Zgjidhje

Le të hartojmë shprehje:

I- "Ivanov mori pjesë në krim";

P- "Petrov mori pjesë në krim";

S- "Sidorov mori pjesë në krim".

Le t'i shkruajmë parcelat në formën e formulave:

Le të kontrollojmë rezultatin duke përdorur tabelën e së vërtetës:

Përgjigje: Ivanov mori pjesë në krim.

Numri i variablave hyrëse në shprehjen e dhënë është tre (A, B, C)... Prandaj, numri i grupeve të hyrjes Q = 2 3 = 8.

Kolonat e tabelës së së vërtetës korrespondojnë me vlerat e shprehjeve origjinale A, B, C, rezultatet e ndërmjetme dhe ( B V C), si dhe vlerën përfundimtare të dëshiruar të një shprehje komplekse aritmetike:

Përkufizimi 1

Funksioni logjik- një funksion, variablat e të cilit marrin një nga dy vlerat: $ 1 $ ose $ 0 $.

Çdo funksion logjik mund të specifikohet duke përdorur tabelën e së vërtetës: grupi i të gjitha argumenteve të mundshme regjistrohet në anën e majtë të tabelës, dhe vlerat përkatëse të funksionit logjik janë në anën e djathtë.

Përkufizimi 2

Tabela e së vërtetës- një tabelë që tregon se çfarë vlerash do të marrë një shprehje e përbërë për të gjitha grupet e mundshme të vlerave të shprehjeve të thjeshta të përfshira në të.

Përkufizimi 3

Ekuivalente Quhen shprehje logjike, kolonat e fundit të tabelave të së vërtetës së të cilave janë të njëjta. Ekuivalenca tregohet me shenjën $ "=" $.

Kur përpiloni një tabelë të së vërtetës, është e rëndësishme të merrni parasysh rendin e mëposhtëm të kryerjes së operacioneve logjike:

Foto 1.

Kllapat kanë përparësi në rendin e ekzekutimit të operacioneve.

Algoritmi për ndërtimin e tabelës së vërtetësisë së një funksioni logjik

Përcaktoni numrin e rreshtave: numri i rreshtave= 2 $ ^ n + 1 $ (për shiritin e titullit), $ n $ - numri i shprehjeve të thjeshta. Për shembull, për funksionet e dy variablave ka kombinime $ 2 ^ 2 = 4 $ të grupeve të vlerave të variablave, për funksionet e tre variablave - $ 2 ^ 3 = 8 $, etj.

Përcaktoni numrin e kolonave: numri i kolonave = numri i variablave + numri i operacioneve logjike. Gjatë përcaktimit të numrit të operacioneve logjike, merret parasysh edhe rendi i ekzekutimit të tyre.

Plotësoni kolonat me rezultatet e operacioneve logjike në një sekuencë të caktuar, duke marrë parasysh tabelat e vërtetësisë së operacioneve kryesore logjike.

Figura 2.

Shembulli 1

Krijoni një tabelë të së vërtetës për shprehjen logjike $ D = \ bar (A) \ vee (B \ vee C) $.

Zgjidhja:

Le të përcaktojmë numrin e rreshtave:

numri i rreshtave = $ 2 ^ 3 + 1 = 9 $.

Numri i variablave është 3 $.

1. përmbysja ($ \ bar (A) $);
2. ndarje, sepse është në kllapa ($ B \ vee C $);

3. disjunksioni ($ \ overline (A) \ vee \ majtas (B \ vee C \ djathtas) $) është shprehja logjike e kërkuar.

   Numri i kolonave = $3 + 3=6$.

Le të plotësojmë tabelën, duke marrë parasysh tabelat e vërtetësisë së veprimeve logjike.

Figura 3.

Shembulli 2

Për këtë shprehje logjike, ndërtoni një tabelë të së vërtetës:

Zgjidhja:

Le të përcaktojmë numrin e rreshtave:

Numri i shprehjeve të thjeshta është $ n = 3 $, pra

numri i rreshtave = $2^3 + 1=9$.

Le të përcaktojmë numrin e kolonave:

Numri i variablave është 3 $.

Numri i operacioneve logjike dhe sekuenca e tyre:

1. mohim ($ \ bar (C) $);
2. ndarje, sepse është në kllapa ($ A \ vee B $);
3. lidhëza ($ (A \ vee B) \ bigwedge \ overline (C) $);
4. mohim, të cilin e shënojmë $ F_1 $ ($ \ overline ((A \ vee B) \ bigwedge \ overline (C)) $);
5. ndarje ($ A \ vee C $);
6. lidhëza ($ (A \ vee C) \ pykë e madhe B $);
7. mohim, të cilin e shënojmë $ F_2 $ ($ \ overline ((A \ vee C) \ bigwedge B) $);

8. disjunksioni është funksioni logjik i kërkuar ($ \ overline ((A \ vee B) \ bigwedge \ overline (C)) \ vee \ overline ((A \ vee C) \ bigwedge B) $).