Logiikkayhtälöt. Loogiset yhtälöjärjestelmät tietojenkäsittelytieteen tentin tehtävissä

Palvelutehtävä. Online-laskin on suunniteltu totuustaulukon rakentaminen loogiselle lausekkeelle.
Totuustaulukko - taulukko, joka sisältää kaikki mahdolliset syöttömuuttujien yhdistelmät ja niitä vastaavat lähtöarvot.
Totuustaulukko sisältää 2n riviä, joissa n on syötemuuttujien lukumäärä ja n+m ovat sarakkeita, joissa m ovat lähtömuuttujia.

Ohje. Kun syötät näppäimistöltä, käytä seuraavia käytäntöjä:

Esimerkiksi looginen lauseke abc+ab~c+a~bc on syötettävä seuraavasti: a*b*c+a*b=c+a=b*c
Käytä tätä palvelua syöttääksesi tiedot loogisen kaavion muodossa.

Logiikkafunktion syöttösäännöt

Käytä +-merkkiä v:n sijaan (disjunktio, TAI).
Ennen loogista funktiota sinun ei tarvitse määrittää funktion nimeä. Esimerkiksi F(x,y)=(x|y)=(x^y) sijaan kirjoitat yksinkertaisesti (x|y)=(x^y) .
Muuttujien enimmäismäärä on 10.

Tietokonelogiikkapiirien suunnittelu ja analysointi suoritetaan matematiikan erityisen osan - logiikan algebran - avulla. Logiikkaalgebrassa voidaan erottaa kolme pääasiallista loogista funktiota: "EI" (negaatio), "AND" (konjunktio), "OR" (disjunktio).
Minkä tahansa loogisen laitteen luomiseksi on tarpeen määrittää kunkin lähtömuuttujan riippuvuus nykyisistä tulomuuttujista, tällaista riippuvuutta kutsutaan kytkentäfunktioksi tai loogisen algebran funktioksi.
Loogista algebrafunktiota kutsutaan täysin määritellyksi, jos sen kaikki 2 n arvoa on annettu, missä n on lähtömuuttujien lukumäärä.
Jos kaikkia arvoja ei ole määritetty, funktiota kutsutaan osittain määritetyksi.
Laitetta kutsutaan loogiseksi, jos sen tilaa kuvataan logiikkaalgebran funktiolla.
Seuraavia menetelmiä käytetään esittämään logiikkaalgebrafunktio:
Algebrallisessa muodossa on mahdollista rakentaa kaavio loogisesta laitteesta käyttämällä loogisia elementtejä.

Kuva 1 - Loogisen laitteen kaavio

Kaikki logiikan algebran toiminnot on määritelty totuustaulukot arvot. Totuustaulukko määrittää toiminnon suorittamisen tuloksen kohteelle kaikki mahdolliset x alkuperäisten lauseiden loogiset arvot. Operaatioiden soveltamisen tulosta heijastavien vaihtoehtojen määrä riippuu loogisen lausekkeen lauseiden määrästä. Jos loogisen lausekkeen lauseiden määrä on N, niin totuustaulukko sisältää 2 N riviä, koska mahdollisia argumenttiarvoja on 2 N erilaista yhdistelmää.

Operaatio NOT - looginen negaatio (inversio)

Loogista operaatiota EI sovelleta yhteen argumenttiin, joka voi olla joko yksinkertainen tai monimutkainen looginen lauseke. Operaation tulos EI ole seuraava:

jos alkuperäinen lauseke on tosi, sen negatiivisen tuloksen tulos on epätosi;
jos alkuperäinen lauseke on epätosi, niin sen negatiivisen tuloksen tulos on tosi.

Seuraavia käytäntöjä EI hyväksytä negaatiooperaatiolle:
ei A, Ā, ei A, ¬A, !A
Negaatiooperaation tulosta EI määritä seuraava totuustaulukko:

A	ei A
0	1
1	0

Negaatiooperaation tulos on tosi, kun alkuperäinen lause on epätosi ja päinvastoin.

Operaatio TAI - looginen lisäys (disjunktio, yhdistäminen)

Looginen TAI-operaatio suorittaa kahden lauseen yhdistämisen, jotka voivat olla joko yksinkertainen tai monimutkainen looginen lauseke. Loogisen toiminnon alussa olevia lauseita kutsutaan argumenteiksi. TAI-operaation tulos on lauseke, joka on tosi, jos ja vain jos vähintään yksi alkuperäisistä lausekkeista on tosi.
Käytetyt nimitykset: A tai B, A V B, A tai B, A||B.
TAI-operaation tulos määräytyy seuraavan totuustaulukon avulla:
TAI-operaation tulos on tosi, kun A on tosi tai B on tosi tai sekä A että B ovat tosi, ja epätosi, kun sekä A että B ovat epätosi.

Operaatio AND - looginen kertolasku (konjunktio)

Looginen operaatio AND suorittaa kahden lauseen (argumentin) leikkauspisteen, joka voi olla joko yksinkertainen tai monimutkainen looginen lauseke. AND-operaation tulos on lauseke, joka on tosi, jos ja vain jos molemmat alkuperäiset lausekkeet ovat tosi.
Käytetyt symbolit: A ja B, A Λ B, A & B, A ja B.
JA-operaation tulos määräytyy seuraavan totuustaulukon avulla:

A	B	A ja B
0	0	0
0	1	0
1	0	0
1	1	1

Operaation JA tulos on tosi silloin ja vain, jos lauseet A ja B ovat molemmat tosi ja epätosi kaikissa muissa tapauksissa.

Operaatio "IF-THEN" - looginen seuraus (implikaatio)

Tämä operaatio yhdistää kaksi yksinkertaista loogista lauseketta, joista ensimmäinen on ehto ja toinen tämän ehdon seuraus.
Käytetyt nimitykset:
jos A, niin B; A houkuttelee B:tä; jos A niin B; A → B.
Totuustaulukko:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Seurauksen (implikaatio) operaation tulos on epätosi vain silloin, kun premissi A on tosi ja johtopäätös B (seuraus) on epätosi.

Operaatio "A jos ja vain jos B" (ekvivalenssi, vastaavuus)

Sovellettava nimitys: A ↔ B, A ~ B.
Totuustaulukko:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Modulo 2 -lisäystoiminto (XOR, yksinoikeus tai tiukka disjunktio)

Käytetty merkintä: A XOR B, A ⊕ B.
Totuustaulukko:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Ekvivalenssioperaation tulos on tosi vain, jos sekä A että B ovat molemmat tosi tai molemmat epätosi.

Loogisten operaatioiden etusija

Toiminnot suluissa
Inversio
Konjunktio (&)
Disjunktio (V), Exclusive OR (XOR), modulo 2 summa
Implisaatio (→)
Vastaavuus (↔)

Täydellinen disjunktiivinen normaalimuoto

Kaavan täydellinen disjunktiivinen normaalimuoto(SDNF) on sitä vastaava kaava, joka on alkeiskonjunktioiden disjunktio, jolla on seuraavat ominaisuudet:

Jokainen kaavan looginen termi sisältää kaikki funktioon F(x 1 ,x 2 ,...x n) sisältyvät muuttujat.
Kaikki kaavan loogiset termit ovat erilaisia.
Mikään looginen termi ei sisällä muuttujaa ja sen negaatiota.
Mikään kaavan looginen termi ei sisällä samaa muuttujaa kahdesti.

SDNF voidaan saada joko käyttämällä totuustaulukoita tai käyttämällä vastaavia muunnoksia.
Jokaiselle funktiolle SDNF ja SKNF määritellään yksilöllisesti permutaatioon asti.

Täydellinen konjunktiivinen normaalimuoto

Kaavan täydellinen konjunktiivinen normaalimuoto (SKNF) on sitä vastaava kaava, joka on alkeisdisjunktioiden konjunktio, joka täyttää seuraavat ominaisuudet:

Kaikki alkeisdisjunktiot sisältävät kaikki funktioon F(x 1 ,x 2 ,...x n) sisältyvät muuttujat.
Kaikki alkeisdisjunktiot ovat erilaisia.
Jokainen alkeisdisjunktio sisältää muuttujan kerran.
Mikään alkeisdisjunktio ei sisällä muuttujaa ja sen negaatiota.

Yhtälöiden käyttö on yleistä elämässämme. Niitä käytetään monissa laskelmissa, rakenteiden rakentamisessa ja jopa urheilussa. Ihminen on käyttänyt yhtälöitä muinaisista ajoista lähtien ja sen jälkeen niiden käyttö on vain lisääntynyt. Matematiikassa on tiettyjä tehtäviä, jotka on omistettu lauseiden logiikalle. Tämän kaltaisen yhtälön ratkaisemiseksi sinulla on oltava tietty määrä tietoa: tietoa lauselogiikan laeista, tietoa 1 tai 2 muuttujan loogisten funktioiden totuustaulukoista, menetelmiä loogisten lausekkeiden muuntamiseen. Lisäksi sinun tulee tietää seuraavat loogisten operaatioiden ominaisuudet: konjunktiot, disjunktiot, inversiot, implikaatiot ja ekvivalenssit.

Mikä tahansa looginen funktio arvosta \ variables - \ voidaan määrittää totuustaulukolla.

Ratkaistaan joitain loogisia yhtälöitä:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Aloitetaan ratkaisu \[X1\]:lla ja määritetään, mitä arvoja tämä muuttuja voi ottaa: 0 ja 1. Seuraavaksi harkitse kutakin yllä olevaa arvoa ja katso mitä \[X2.\] voi olla tässä tapauksessa

Kuten taulukosta voidaan nähdä, loogisessa yhtälössämme on 11 ratkaisua.

Mistä voin ratkaista loogisen yhtälön verkossa?

Voit ratkaista yhtälön verkkosivustollamme https: //. Ilmaisen online-ratkaisijan avulla voit ratkaista minkä tahansa monimutkaisen online-yhtälön sekunneissa. Sinun tarvitsee vain syöttää tietosi ratkaisijaan. Voit myös katsoa video-ohjeet ja oppia ratkaisemaan yhtälön verkkosivuillamme. Ja jos sinulla on kysyttävää, voit kysyä niitä Vkontakte-ryhmässämme http://vk.com/pocketteacher. Liity joukkoomme, autamme sinua aina mielellämme.

On olemassa useita tapoja ratkaista loogisia yhtälöjärjestelmiä. Tämä on pelkistämistä yhteen yhtälöön, totuustaulukon rakentamista ja hajottamista.

Tehtävä: Ratkaise looginen yhtälöjärjestelmä:

Harkitse pelkistysmenetelmä yhteen yhtälöön . Tämä menetelmä sisältää loogisten yhtälöiden muuntamisen siten, että niiden oikeat puolet ovat yhtä suuret kuin totuusarvo (eli 1). Käytä tätä varten loogista negaatiota. Sitten, jos yhtälöissä on monimutkaisia loogisia operaatioita, korvaamme ne perusoperaatioilla: "AND", "OR", "NOT". Seuraava askel on yhdistää yhtälöt yhdeksi, joka vastaa järjestelmää käyttämällä loogista operaatiota "AND". Sen jälkeen sinun tulee tehdä muunnoksia tuloksena olevasta yhtälöstä logiikan algebran lakien perusteella ja saada systeemille erityinen ratkaisu.

Ratkaisu 1: Käytä inversiota ensimmäisen yhtälön molemmille puolille:

Esitetään implikaatio perusoperaatioilla "OR", "NOT":

Koska yhtälöiden vasen puoli on yhtä suuri kuin 1, voit yhdistää ne AND-operaatiolla yhdeksi yhtälöksi, joka vastaa alkuperäistä järjestelmää:

Avaamme ensimmäisen hakasulkeen de Morganin lain mukaan ja muunnamme tuloksen:

Tuloksena olevalla yhtälöllä on yksi ratkaisu: A=0, B=0 ja C=1.

Seuraava tapa on totuustaulukoiden rakentaminen . Koska loogisilla suureilla on vain kaksi arvoa, voit yksinkertaisesti käydä läpi kaikki vaihtoehdot ja löytää niiden joukosta ne, joille annettu yhtälöjärjestelmä täyttyy. Toisin sanoen rakennamme yhden yhteisen totuustaulukon kaikille järjestelmän yhtälöille ja löydämme rivin halutuilla arvoilla.

Ratkaisu 2: Tehdään totuustaulukko järjestelmälle:








0	0	1	1	0	1

Lihavoitu on viiva, jolla ongelman ehdot täyttyvät. Joten A = 0, B = 0 ja C = 1.

Tapa hajoaminen . Ajatuksena on kiinnittää yhden muuttujan arvo (asettaa se 0:ksi tai 1:ksi) ja siten yksinkertaistaa yhtälöitä. Sitten voit korjata toisen muuttujan arvon ja niin edelleen.

Ratkaisu 3: Olkoon A = 0, sitten:

Ensimmäisestä yhtälöstä saadaan B = 0 ja toisesta - С=1. Järjestelmäratkaisu: A = 0, B = 0 ja C = 1.

Tietojenkäsittelytieteen KÄYTÖSSÄ on hyvin usein tarpeen määrittää ratkaisujen lukumäärä loogisten yhtälöjen järjestelmään ilman, että itse ratkaisuja löydetään, tähän on myös tiettyjä menetelmiä. Pääasiallinen tapa löytää ratkaisujen lukumäärä loogiselle yhtälöjärjestelmälle onmuuttujien muutos. Ensinnäkin on tarpeen yksinkertaistaa kutakin yhtälöä mahdollisimman paljon logiikan algebran lakien perusteella ja sitten korvata yhtälöiden monimutkaiset osat uusilla muuttujilla ja määrittää ratkaisujen lukumäärä uuteen järjestelmään. Palaa sitten korvaavaan tilaan ja määritä sille ratkaisujen määrä.

Tehtävä: Kuinka monta ratkaisua yhtälöllä (A → B ) + (C → D ) = 1 on? Missä A, B, C, D ovat loogisia muuttujia.

Ratkaisu: Otetaan käyttöön uudet muuttujat: X = A → B ja Y = C → D . Uudet muuttujat huomioon ottaen yhtälö kirjoitetaan muotoon: X + Y = 1.

Disjunktio on tosi kolmessa tapauksessa: (0;1), (1;0) ja (1;1), kun taas X ja Y ovat implikaatio, eli se on tosi kolmessa tapauksessa ja epätosi yhdessä. Siksi tapaus (0;1) vastaa kolmea mahdollista parametrien yhdistelmää. Tapaus (1;1) - vastaa yhdeksää mahdollista alkuperäisen yhtälön parametrien yhdistelmää. Näin ollen tälle yhtälölle on 3+9=15 mahdollista ratkaisua.

Seuraava tapa määrittää loogisen yhtälöjärjestelmän ratkaisujen lukumäärä on − binäärinen puu. Tarkastellaan tätä menetelmää esimerkin avulla.

Tehtävä: Kuinka monta eri ratkaisua loogisella yhtälöjärjestelmällä on:

Annettu yhtälöjärjestelmä vastaa yhtälöä:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

Teeskennetäänpä sitä x 1 on totta, niin ensimmäisestä yhtälöstä saamme sen x 2 myös totta, toisesta - x 3 =1 ja niin edelleen kunnes x m= 1. Tämä tarkoittaa, että m yksikön joukko (1; 1; …; 1) on järjestelmän ratkaisu. Anna nyt x 1 =0, niin ensimmäisestä yhtälöstä meillä on x 2 =0 tai x 2 =1.

Kun x 2 tosi, saadaan, että muutkin muuttujat ovat tosi, eli joukko (0; 1; ...; 1) on järjestelmän ratkaisu. klo x 2 =0 ymmärrämme sen x 3 =0 tai x 3 =, ja niin edelleen. Jatkamalla viimeiseen muuttujaan, saadaan, että yhtälön ratkaisut ovat seuraavat muuttujajoukot (m + 1 ratkaisu, jokaisessa ratkaisussa on m muuttujan arvoa):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Tätä lähestymistapaa havainnollistaa hyvin binääripuun rakentaminen. Mahdollisten ratkaisujen lukumäärä on rakennetun puun eri oksien lukumäärä. On helppo nähdä, että se on yhtä suuri kuin m + 1.

	Puu	Päätösten määrä
x 1
x2
x 3
		…

Jos päättelyssä on vaikeuksia niyah ja rakentaminen deratkaisuja, voit etsiä ratkaisua käyttämällä totuustaulukot, yhdelle tai kahdelle yhtälölle.

Kirjoitamme yhtälöjärjestelmän uudelleen muotoon:

Ja tehdään totuustaulukko erikseen yhdelle yhtälölle:

x 1	x2	(x 1 → x 2)

Tehdään totuustaulukko kahdelle yhtälölle:

x 1	x2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

Oppitunnin aihe: Loogisten yhtälöiden ratkaiseminen

Koulutuksellinen - loogisten yhtälöiden ratkaisutapojen tutkiminen, taitojen ja kykyjen muodostaminen ratkaista loogisia yhtälöitä ja rakentaa looginen lauseke totuustaulukon mukaan;

Koulutuksellinen - luoda olosuhteet opiskelijoiden kognitiivisen kiinnostuksen kehittymiselle, edistää muistin, huomion, loogisen ajattelun kehitystä;

Koulutuksellinen : edistää kykyä kuunnella muiden mielipiteitä, tahtoa ja sinnikkyyttä lopputulosten saavuttamiseksi.

Oppitunnin tyyppi: yhdistetty oppitunti

Laitteet: tietokone, multimediaprojektori, esitys 6.

Tuntien aikana

Perustietojen toisto ja päivittäminen. Kotitehtävien tarkistaminen (10 minuuttia)

Edellisillä tunneilla tutustuimme logiikan algebran peruslakeihin, opimme käyttämään näitä lakeja loogisten lausekkeiden yksinkertaistamiseen.

Katsotaanpa kotitehtävä loogisten lausekkeiden yksinkertaistamisesta:

1. Mikä seuraavista sanoista täyttää loogisen ehdon:

(ensimmäinen konsonantti → toinen konsonantti)٨ (viimeisen kirjaimen vokaali → toiseksi viimeinen kirjainvokaali)? Jos tällaisia sanoja on useita, merkitse pienin niistä.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Otetaan käyttöön merkintä:

A on konsonantin ensimmäinen kirjain

B on konsonantin toinen kirjain

S on viimeinen vokaali

D - toiseksi viimeinen vokaali

Tehdään ilmaus:

Tehdään taulukko:

2. Ilmoita, mikä looginen lauseke vastaa lauseketta

Yksinkertaistetaan alkuperäisen lausekkeen ja ehdotettujen vaihtoehtojen kirjoittamista:

3. Lausekkeen F totuustaulukon fragmentti annetaan:

Mikä lauseke vastaa F:tä?

Määritetään näiden lausekkeiden arvot määritetyille argumenttien arvoille:

Oppitunnin aiheeseen tutustuminen, uuden materiaalin esittely (30 minuuttia)

Jatkamme logiikan perusteiden ja tämän päivän oppitunnin aiheen "Loogisten yhtälöiden ratkaiseminen" opiskelua. Tämän aiheen opiskelun jälkeen opit perustavat loogisten yhtälöiden ratkaisemiseen, saat taidot ratkaista näitä yhtälöitä käyttämällä logiikkaalgebran kieltä ja kykyä laatia looginen lauseke totuustaulukossa.

1. Ratkaise looginen yhtälö

(¬K M) → (¬L M N) = 0

Kirjoita vastauksesi neljän merkin merkkijonona: muuttujien K, L, M ja N arvot (tässä järjestyksessä). Joten esimerkiksi rivi 1101 vastaa K=1, L=1, M=0, N=1.

Ratkaisu:

Muunnetaan lauseke(¬K  M) → (¬L  M  N)

Lauseke on epätosi, kun molemmat termit ovat vääriä. Toinen termi on yhtä suuri kuin 0, jos M=0, N=0, L=1. Ensimmäisessä termissä K = 0, koska M = 0 ja
.

Vastaus: 0100

2. Kuinka monta ratkaisua yhtälöllä on (ilmoita vastauksessasi vain numero)?

Ratkaisu: muunna lauseke

(A+B)*(C+D)=1

A+B=1 ja C+D=1

Tapa 2: Totuustaulukon laatiminen

3 tapaa: SDNF:n rakenne - täydellinen disjunktiivinen normaalimuoto funktiolle - disjunktio täydellisistä säännöllisistä alkeiskonjunktioista.

Muunnetaan alkuperäinen lauseke, avataan sulut saadaksesi konjunktioiden disjunktion:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Täydennetään konjunktiot täydellisiksi konjunktioiksi (kaikkien argumenttien tulo), avataan sulut:

Harkitse samoja yhteyksiä:

Tuloksena saadaan SDNF, joka sisältää 9 konjunktia. Siksi tämän funktion totuustaulukon arvo on 1 9 rivillä 2 4 =16 muuttujaarvojoukosta.

3. Kuinka monta ratkaisua yhtälöllä on (ilmoita vastauksessasi vain numero)?

Yksinkertaistetaan lausetta:

3 tapaa: SDNF:n rakentaminen

Harkitse samoja yhteyksiä:

Tuloksena saamme SDNF:n, joka sisältää 5 konjunktia. Siksi tämän funktion totuustaulukon arvo on 1 viidellä 2 4 =16 muuttujaarvojoukolla.

Loogisen lausekkeen rakentaminen totuustaulukon mukaan:

kullekin totuustaulukon riville, joka sisältää luvun 1, muodostetaan argumenttien tulo, ja muuttujat, jotka ovat yhtä suuria kuin 0, sisällytetään tuloon negatiivisesti, eikä muuttujia, jotka ovat yhtä suuria, kuin 1, ei negaatiota. Haluttu lauseke F muodostuu saatujen tuotteiden summasta. Sitten, jos mahdollista, tätä ilmaisua tulisi yksinkertaistaa.

Esimerkki: lausekkeen totuustaulukko on annettu. Rakenna looginen lauseke.

Ratkaisu:

3. Kotitehtävät (5 minuuttia)

Ratkaise yhtälö:

Kuinka monta ratkaisua yhtälöllä on (vastaa vain numero)?

Tee annetun totuustaulukon mukaan looginen lauseke ja

yksinkertaistaa sitä.