Informatikos užklausos paieškos serveriui. Loginės operacijos ir jų savybės

17.10.2021

Elektros schema, skirtas atlikti tam tikrą loginę operaciją su įvesties duomenimis, vadinamas loginiu elementu. Įvesties duomenys čia pateikiami įvairių lygių įtampų pavidalu, o loginės operacijos rezultatas išėjime taip pat gaunamas tam tikro lygio įtampos forma.

Šiuo atveju tiekiami operandai - loginio elemento įvestyje gaunami signalai aukšto arba žemo lygio įtampos pavidalu, kurie iš esmės tarnauja kaip įvesties duomenys. Taigi aukšto lygio įtampa – loginis 1 – rodo tikrąją operando reikšmę, o žemo lygio įtampa 0 – klaidingą reikšmę. 1 – TEISINGA, 0 – NETIESA.

Loginis elementas- elementas, įgyvendinantis tam tikrus loginius ryšius tarp įvesties ir išvesties signalų. Loginiai elementai dažniausiai naudojami kompiuterių loginėms grandinėms ir atskiroms automatinėms stebėjimo ir valdymo grandinėms konstruoti. Visų tipų loginiams elementams, nepaisant jų fizinio pobūdžio, būdingos atskiros įvesties ir išvesties signalų reikšmės.

Loginiai elementai turi vieną ar daugiau įėjimų ir vieną arba du (dažniausiai atvirkštinius vienas kitam) išėjimus. Loginių elementų išvesties signalų „nulių“ ir „vienetų“ reikšmės nustatomos pagal elemento atliekamą loginę funkciją ir grojamų įvesties signalų „nulių“ ir „vienetų“ reikšmes. nepriklausomų kintamųjų vaidmuo. Yra bazinių logines funkcijas, iš kurios galima sudaryti bet kokią sudėtingą loginę funkciją.

Priklausomai nuo elementų grandinės konstrukcijos, nuo jos elektriniai parametrai, loginiai lygiai (aukštas ir žemi lygiaiįtampa) įvestis ir išvestis turi tas pačias aukštų ir žemų (teisingų ir klaidingų) būsenų reikšmes.

Tradiciškai loginiai elementai gaminami specialių radijo komponentų – integrinių grandynų – pavidalu. Loginės operacijos, tokios kaip konjunkcija, disjunkcija, neigimas ir modulio pridėjimas (IR, ARBA, NE, XOR) yra pagrindinės operacijos, atliekamos su pagrindiniais loginių vartų tipais. Toliau pažvelkime į kiekvieną iš šių loginių elementų tipų atidžiau.

Loginis elementas „AND“ – jungtukas, loginis daugyba, IR

„IR“ yra loginis elementas, atliekantis įvesties duomenų jungimo arba loginio daugybos operaciją. Šis elementas gali turėti nuo 2 iki 8 (gamyboje dažniausiai naudojami „AND“ elementai su 2, 3, 4 ir 8 įėjimais) įvestis ir vieną išvestį.

Loginių elementų simboliai "IR" su skirtingi kiekiaiįėjimai parodyti paveikslėlyje. Tekste loginis elementas „IR“ su tam tikru įėjimų skaičiumi žymimas „2I“, „4I“ ir tt - „AND“ elementas su dviem įėjimais, su keturiais įėjimais ir pan.

Elemento 2I tiesos lentelė rodo, kad elemento išvestis bus loginė tik tuo atveju, jei loginiai vienu metu bus pirmoje įėjime IR antroje įėjime. Likusiais trimis galimais atvejais išvestis bus lygi nuliui.

Vakarų diagramose I elemento piktograma turi tiesią liniją įvestyje ir suapvalintą liniją išvestyje. Įjungta vidaus schemos- stačiakampis su simboliu „&“.

Loginis elementas „ARBA“ – disjunkcija, loginis papildymas, ARBA

„ARBA“ yra loginis elementas, atliekantis įvesties duomenų atskyrimo arba loginio sudėjimo operaciją. Jis, kaip ir „I“ elementas, yra su dviem, trim, keturiais ir tt įėjimais ir vienu išėjimu. Loginių elementų simboliai „OR“ su skirtingu įėjimų skaičiumi parodyti paveikslėlyje. Šie elementai žymimi taip: 2OR, 3OR, 4OR ir kt.

Elemento „2OR“ tiesos lentelė rodo, kad loginiam išėjimui pakanka, kad loginis būtų pirmoje įėjime ARBA antrajame įėjime. Jei prie dviejų įėjimų vienu metu yra loginių, išvestis taip pat bus viena.

Vakarų diagramose „OR“ elemento piktograma turi suapvalintą įvestį ir suapvalintą smailią išvestį. Buitinėse diagramose yra stačiakampis su simboliu „1“.

Loginis elementas „NOT“ – neigimas, inverteris, NE

„NE“ yra loginis elementas, atliekantis įvesties duomenų loginio neigimo operaciją. Šis elementas, turintis vieną išėjimą ir tik vieną įėjimą, taip pat vadinamas inverteriu, nes jis iš tikrųjų invertuoja (atšaukia) įvesties signalą. Paveikslėlyje parodyta simbolis loginis elementas „NE“.

Inverterio tiesos lentelė rodo, kad didelis įvesties potencialas sukuria mažą išėjimo potencialą ir atvirkščiai.

Vakarų diagramose elemento „NE“ piktograma yra trikampio formos su apskritimu išvestyje. Buitinėse diagramose yra stačiakampis su simboliu „1“, kurio išvestyje yra apskritimas.

Loginis elementas „NAND“ – jungtis (loginis dauginimas) su neigimu, NAND

„AND-NOT“ yra loginis elementas, kuris atlieka loginę įvesties duomenų pridėjimo operaciją, o tada loginio neigimo operaciją, rezultatas siunčiamas į išvestį. Kitaip tariant, tai iš esmės yra „AND“ elementas, papildytas elementu „NE“. Paveikslėlyje parodytas loginio elemento „2AND-NOT“ simbolis.

NAND vartų tiesos lentelė yra priešinga AND vartų tiesos lentelei. Vietoj trijų nulių ir vieno yra trys vienetai ir nulis. NAND elementas taip pat vadinamas „Schaeffer elementu“ matematiko Henry Maurice'o Schaefferio garbei, kuris pirmą kartą atkreipė dėmesį į jo reikšmę 1913 m. Žymima kaip „aš“, tik su apskritimu išvestyje.

Loginis elementas "OR-NOT" - disjunkcija (loginis pridėjimas) su neigimu, NOR

„OR-NOT“ yra loginis elementas, kuris atlieka loginę įvesties duomenų pridėjimo operaciją, o po to loginio neigimo operaciją, rezultatas siunčiamas į išvestį. Kitaip tariant, tai yra „OR“ elementas, papildytas „NE“ elementu - keitikliu. Paveikslėlyje pavaizduotas loginio elemento simbolis „2OR-NOT“.

ARBA vartų tiesos lentelė yra priešinga ARBA vartų tiesos lentelei. Didelis išėjimo potencialas gaunamas tik vienu atveju – maži potencialai vienu metu taikomi abiem įėjimams. Jis žymimas kaip „OR“, tik su apskritimu prie išvesties, nurodančio inversiją.

Loginiai vartai "išskirtinis ARBA" - papildymas modulo 2, XOR

„Išskirtinis ARBA“ yra loginis elementas, atliekantis įvesties duomenų loginį papildymo operaciją modulo 2, turintis du įėjimus ir vieną išvestį. Dažnai šie elementai naudojami valdymo grandinėse. Paveikslėlyje parodytas šio elemento simbolis.

Vaizdas vakarietiškose grandinėse yra kaip „OR“ su papildoma lenkta juostele įvesties pusėje, buitinėse – kaip „OR“, tik vietoje „1“ bus rašoma „=1“.

Šis loginis elementas taip pat vadinamas „nelygiavertiškumu“. Aukštos įtampos lygis išėjime bus tik tada, kai signalai įėjime bus nevienodi (vienas yra vienas, kitas - nulis arba vienas yra nulis, o kitas - vienas), net jei įėjime yra du vienetai. tuo pačiu metu išvestis bus lygi nuliui - tai skirtumas nuo "ARBA". Šie loginiai elementai plačiai naudojami sumatoriuose.

Jungtis arba loginis daugyba (aibių teorijoje tai yra sankirta)

Jungtis yra sudėtinga loginė išraiška, kuri yra teisinga tada ir tik tada, kai abi paprastos išraiškos yra teisingos. Tokia situacija galima tik vienu atveju, visais kitais atvejais konjunkcija yra klaidinga.

Žymėjimas: &, $\pleištas$, $\cdot$.

Tiesos lentelė jungtukui

1 paveikslas.

Jungties savybės:

Jei bent viena iš jungtuko posakių yra klaidinga tam tikroje kintamųjų reikšmių rinkinyje, tada visa jungtis bus klaidinga šiai reikšmių rinkiniui.
Jei visos jungtuko išraiškos yra teisingos tam tikroje kintamųjų reikšmių rinkinyje, tada visa jungtis taip pat bus teisinga.
Visos sudėtingos išraiškos jungtuko reikšmė nepriklauso nuo posakių, kuriems ji taikoma, rašymo tvarkos (kaip matematikoje daugybos).

Disjunkcija arba loginis sudėjimas (aibių teorijoje tai yra sąjunga)

Disjunkcija yra sudėtinga loginė išraiška, kuri beveik visada yra teisinga, išskyrus atvejus, kai visos išraiškos yra klaidingos.

Žymėjimas: +, $\vee$.

Tiesos lentelė disjunkcijai

2 pav.

Disjunkcijos savybės:

Jei bent viena iš disjunkcijos poraiškių yra teisinga tam tikram kintamųjų reikšmių rinkiniui, tada visa disjunkcija įgauna tikrąją šios subraiškos rinkinio reikšmę.
Jei visos išraiškos iš tam tikro disjunkcijų sąrašo yra klaidingos tam tikroje kintamųjų reikšmių rinkinyje, tada visa šių išraiškų disjunkcija taip pat yra klaidinga.
Viso disjunkcijos reikšmė nepriklauso nuo posakių rašymo tvarkos (kaip matematikoje – sudėjimas).

Neigimas, loginis neigimas arba inversija (aibių teorijoje tai yra neigimas)

Neigimas reiškia, kad prie pradinės loginės išraiškos pridedama dalelė NE arba žodis FALSE, KAS ir dėl to gauname, kad jei pirminė išraiška teisinga, tai originalo neigimas bus klaidingas ir atvirkščiai, jei pradinė išraiška yra klaidingas, tada jo neigimas bus teisingas.

Žymėjimas: ne $A$, $\bar(A)$, $¬A$.

Tiesos lentelė inversijai

3 pav.

Neigimo savybės:

$¬¬A$ „dvigubas neigimas“ yra teiginio $A$ pasekmė, tai yra, tai yra tautologija formalioje logikoje ir yra lygi pačiai reikšmei Būlio logikoje.

Potekstė arba loginė pasekmė

Potekstė yra sudėtinga loginė išraiška, kuri yra teisinga visais atvejais, išskyrus atvejus, kai tiesa seka melą. Tai yra, ši loginė operacija sujungia dvi paprastas logines išraiškas, iš kurių pirmoji yra sąlyga ($A$), o antroji ($A$) yra sąlygos ($A$) pasekmė.

Žymėjimas: $\to$, $\Rightarrow$.

Tiesos lentelė implikacijai

4 pav.

Potekstės savybės:

$A \to B = ¬A \vee B$.
Potekstė $A \į B$ yra klaidinga, jei $A=1$ ir $B=0$.
Jei $A = 0$, tada implikacija $A \į B$ yra teisinga bet kuriai $B$ reikšmei (tiesa gali kilti iš false).

Lygiavertiškumas arba loginis lygiavertiškumas

Ekvivalentiškumas yra sudėtinga loginė išraiška, kuri tinka vienodoms kintamųjų $A$ ir $B$ reikšmėms.

Žymėjimas: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.

Tiesos lentelė lygiavertei

5 pav.

Lygiavertiškumo savybės:

Lygiavertiškumas galioja vienodoms kintamųjų $A$ ir $B$ verčių rinkiniams.
CNF $A \equiv B = (\bar(A) \vee B) \cdot (A \cdot \bar(B))$
DNF $A \equiv B = \bar(A) \cdot \bar(B) \vee A \cdot B$

Griežtas disjunkcija arba sudėjimas modulo 2 (aibių teorijoje tai yra dviejų aibių sąjunga be jų susikirtimo)

Griežtas disjunkcija yra teisinga, jei argumentų reikšmės nėra lygios.

Elektronikai tai reiškia, kad grandines galima įdiegti naudojant vieną standartinį elementą (nors tai brangus elementas).

Loginių operacijų tvarka sudėtingoje loginėje išraiškoje

Inversija(neigimas);
Jungtis (loginė daugyba);
Disjunkcija ir griežta disjunkcija (loginis papildymas);
implikacija (pasekmė);
Lygiavertiškumas (tapatumas).

Norėdami pakeisti nurodytą loginių operacijų tvarką, turite naudoti skliaustus.

Bendrosios savybės

$n$ loginių kintamųjų rinkiniui yra tiksliai $2^n$ skirtingos reikšmės. $n$ kintamųjų loginės išraiškos tiesos lentelėje yra $n+1$ stulpelių ir $2^n$ eilučių.

Skyriai: Informatika

Šiuo metu stojamuosiuose informatikos egzaminuose yra daug užduočių tema „logikos algebra“. Šios pamokos tikslas – įtvirtinti vieningo valstybinio egzamino užduočių sprendimo informatikos srityje įgūdžius, naudojant loginės algebros elementus.

Pamokos tikslai:

Gebėjimo įgytas žinias pritaikyti praktikoje formavimas;
Gebėjimo sudaryti tiesos lenteles pagal pateiktas formules ugdymas;
Gebėjimo spręsti tekstinius uždavinius taikant logikos dėsnius ugdymas.

Pamokos tikslai:

Švietimo – pažintinio intereso, loginio mąstymo ugdymas.
Švietimo– matematinės logikos pagrindų kartojimas, atliekant praktines užduotis.
Vystantis – loginio mąstymo, dėmesingumo ugdymas.

Per užsiėmimus

Loginių operacijų ir dėsnių kartojimas.
Loginių operacijų ir dėsnių taikymas praktikoje.
Namų darbų paaiškinimas.

Šiandien baigiame temą „Logikos pagrindai“ ir taikysime pagrindinius loginių operacijų ir transformacijų dėsnius, spręsdami vieningo valstybinio egzamino informatikos uždavinius.

Pamoka vyksta lygiagrečiai su pristatymu.<Приложение1>

1. Loginių operacijų ir dėsnių kartojimas.

Logikos algebra yra matematinės logikos šaka, tirianti sudėtingų loginių teiginių struktūrą ir jų tiesos nustatymo metodus naudojant algebrinius metodus.

1. Formaliosios logikos pradininkas?

Aristotelis.

2. Logikos algebros įkūrėjas?

Džordžas Būlis.

3. Išvardykite logines operacijas:

¬ neigimas (inversija)
&, /\jungtis („Ir“)
V disjunkcija („OR“)
loginė pasekmė (implikacija)
lygiavertiškumas (ekvivalentiškumas)

4. Ką reiškia dvigubo neigimo dėsnis?

Dvigubas neigiamas pašalina neigiamą.

5. De Morgano dėsniai (bendrosios inversijos dėsniai).

Disjunkcijos neigimas yra neigimų junginys:

¬(A V B) = ¬A /\ ¬B

Jungtinio neigimas yra neigimų disjunkcija:

¬(A /\B) = ¬A V ¬B

6. Idempotencijos (panašumo) dėsnis.

7. Ką reiškia trečiojo išskyrimo dėsnis?

Iš dviejų prieštaringų teiginių apie tą patį dalyką vienas visada yra teisingas, antrasis yra klaidingas, o trečiasis nepateikiamas:

8. Apie ką yra prieštaravimo dėsnis?

Teiginys ir jo neigimas negali būti teisingi vienu metu:

9. Konstantų išskyrimo dėsnis.

Logiškam papildymui:

A V 1 = 1 A V 0 = A

Loginiam dauginimui:

A /\ 1 = A A /\ 0 = 0

10. Kaip išreikšti implikaciją per disjunkciją?

A B = ¬A V B

2. Loginių operacijų ir dėsnių taikymas praktikoje.

1 pavyzdys. ( Užduotis A11 demonstracinė versija 2004)

Kuriam vardui teisingas teiginys:

¬ (Pirmoji vardo raidė yra balsė -> Ketvirta vardo raidė yra priebalsis)?

Sprendimas. Sudėtingas teiginys susideda iš dviejų paprastų teiginių:

A yra pirmoji vardo raidė, balsė,

B yra ketvirtoji vardo raidė, priebalsis.

¬ (A B) = ¬ (¬A V B) = (¬ (¬A) /\ ¬B) = A /\ ¬B

Naudojamos formulės:

1. Implikacija per disjunkciją A? B = ¬A V B

2. De Morgano dėsnis ¬(A V B) = ¬A /\ ¬B

3. Dvigubo neigimo dėsnis.

(Pirmoji vardo raidė yra balsė /\ Ketvirta vardo raidė yra balsė)

2 pavyzdys. ( Užduotis A12 demonstracinė versija 2004)

Kokia loginė išraiška atitinka išraišką ¬ (A \/ ¬B)?

Sprendimas. ¬ (A \/ ¬B) = ¬ A \/ ¬ (¬B) = ¬ A \/ B

Sukurkite formulės tiesos lentelę

¬ (B / C) V (A / C B)

Loginių operacijų tvarka:

¬ (B / C) V (A / C B)

Sukurkite tiesos lentelę.

Kiek eilučių bus jūsų lentelėje? 3 kintamieji: A, B, C; 2 3 =8

Kiek stulpelių? 5 operacijos + 3 kintamieji = 8

A	B	C	(B/\C)	¬ (B/\C)	A/\C	(A/\C ? B)	¬ (B /\C) V (A/\CB)
0	0	0	0	1	0	1	1
0	0	1	0	1	0	1	1
0	1	0	0	1	0	1	1
0	1	1	1	0	0	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	1
1	1	0	0	1	0	0	1
1	1	1	1	0	1	1	1

Kokius atsakymus gavote paskutiniame stulpelyje?

identiškai tiesa, jei visų į jį įtrauktų paprastų teiginių rinkinių reikšmės yra 1. Vadinamos identiškos tikrosios formulės tautologijos.

Išspręskime šį pavyzdį naudodami analitinį metodą:

supaprastinti išraišką

¬ (B /\ C) V (A/\C B)= (taikyti implikacijos formulę)

¬ (B /\ C) V ¬ (A /\ C) V B = (taikyti 1 ir 2 de Morgano įstatymus)

(¬B V ¬C) V (¬A V ¬C) V B = (pašalinti skliaustus)

¬B V ¬C V ¬A V ¬C V B= (taikyti komutacinį dėsnį)

¬B V B V ¬C V ¬C V ¬A = (vidurio išskyrimo dėsnis, idempotencijos dėsnis)

1 V ¬С V ¬A = 1 V ¬A = 1 (konstantų išskyrimo dėsnis)

Atsakymas: 1 , reiškia, kad formulė yra identiška tiesa arba tautologija.

Loginė išraiška vadinama identiškai klaidinga, jei visų į jį įtrauktų paprastų teiginių rinkinių reikšmės yra 0.

(3 namų užduotis)

Lentelėje pateikiamos užklausos paieškos serveriui. Išdėstykite užklausų pavadinimus didėjančia tvarka pagal puslapių skaičių, kurį paieškos variklis ras pagal kiekvieną užklausą.

Simbolis I naudojamas loginei operacijai „ARBA“ žymėti užklausoje, o simbolis & – loginei operacijai „IR“.

Pirmasis metodas pagrįstas samprotavimu. Logiškai samprotaujant matome, kad daugiausiai puslapių bus rasta užklausai G, nes ją įvykdžius puslapiai su žodžiu „įstatymai“ ir puslapiai su žodžiu „fizika“ bei puslapiai su žodžiu „biologija“ rasta. Mažiausias puslapių skaičius bus rastas pagal užklausą B, nes joje yra visi keturi ieškomame puslapyje esantys žodžiai. Belieka palyginti A ir B užklausas. Užklausoje B bus rasti visi A užklausą atitinkantys puslapiai (nes pastarojoje būtinai yra žodis „įstatymai“), taip pat puslapiai, kuriuose yra ir žodžiai „fizika“, ir „biologija“. Todėl pagal užklausą B bus rasta daugiau puslapių nei pagal užklausą A. Taigi, suskirstę užklausas puslapių didėjimo tvarka, gauname VABG.

Atsakymas: VABG.

Antrasis metodas apima grafinį aibių operacijų atvaizdavimą. (Žiūrėkite pristatymą)

5 pavyzdys. ( Užduotis A16 demonstracinė versija 2006)

Žemiau lentelės pavidalu pateikiamas studentų testavimo rezultatų duomenų bazės fragmentas (naudojama šimto balų skalė)

Pavardė	Grindys	Matematika	rusų kalba	Chemija	Informatika	Biologija
Aganyanas	ir	82	56	46	32	70
Voroninas	m	43	62	45	74	23
Grigorčiukas	m	54	74	68	75	83
Rodnina	ir	71	63	56	82	79
Sergeenko	ir	33	25	74	38	46
Čerepanova	ir	18	92	83	28	61

Kiek įrašų šiame fragmente tenkina sąlygą

„Lytis = „m“ ARBA chemija> biologija?

Atrenkame įrašus: Berniukai (du) ir Chemija>Biologija (trys, bet vienas berniukas, jau paimtas 1 kartą). Dėl to 4 įrašai atitinka sąlygą.

6 užduotis. ( Užduotis B4 demonstracinė versija 2007)

Moksleivių stalo teniso čempionate į geriausiųjų ketvertą pateko merginos: Nataša, Maša, Liuda ir Rita. Aistringiausi sirgaliai išsakė savo prielaidas dėl vietų pasiskirstymo tolimesnėse varžybose.

Manoma, kad Nataša bus pirma, o Maša – antra.

Kitas gerbėjas Ludai pranašauja antrąją vietą, o Rita, jo nuomone, užims ketvirtą vietą.

Trečias teniso gerbėjas su jais nesutiko. Jis tiki, kad Rita užims trečią vietą, o Nataša bus antra.

Kokią vietą čempionate užėmė Nataša, Maša, Liuda, Rita?

(Atsakyme iš eilės be tarpų surašykite mergaičių vietas atitinkančius skaičius nurodyta vardų tvarka.)

Pažymėkime teiginius:

H1 = „Nataša bus pirma“;

M2 = „Maša bus antra“;

L2 = „Luda bus antra“;

P4 = „Rita bus ketvirta“;

P3 = „Rita bus trečia“;

H2 = „Nataša bus antra“.

Pagal sąlygą:

iš 1 gerbėjo teiginių išplaukia, kad H1VM2 yra tiesa;

iš gerbėjo teiginių2 išplaukia, kad A2VP4 yra tiesa;

iš ventiliatoriaus 3 teiginių matyti, kad P3VH2 yra tiesa.

Todėl jungtukas taip pat teisingas

(H1VM2) /\ (L2VP4) /\ (Р3VН2) = 1.

Atidarę skliaustus gauname:

(Н1VM2) /\ (Л2VP4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\ (Р3VН2)=

Н1/\Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\Н2 V М2/ \Л2/\Н2 V М2/\Р4/\Н2 =Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3

Nataša-1, Liuda-2, Rita-3 ir Maša-4.

Atsakymas: 1423 m

3. Namų darbų paaiškinimas.

1 pratimas. ( Užduotis B8 demonstracinė versija 2007)

Lentelėje pateikiamos užklausos paieškos serveriui. Išdėstykite užklausos simbolius didėjančia tvarka pagal puslapių skaičių, kurį paieškos sistema ras pagal kiekvieną užklausą.

Norėdami užklausoje pažymėti loginę operaciją „OR“, naudokite simbolį |, o loginę operaciją „AND“ – &.

2 užduotis ( Užduotis B4 demonstracinė versija, 2008 m.)

Prieš ketverto turnyro pradžią gerbėjai padarė tokias prielaidas apie savo stabus:

A) Maksas laimės, Billas bus antras;

B) Billas yra trečias. Nikas yra pirmasis;

C) Maksas yra paskutinis, o pirmasis yra Jonas.

Pasibaigus konkursui paaiškėjo, kad kiekvienas gerbėjas buvo teisus tik vienoje iš savo prognozių.

Kokią vietą turnyre užėmė Johnas, Nickas, Billas, Maksas?

(Atsakyme dalyvių vietas surašykite iš eilės be tarpų nurodyta vardų tvarka.)

LOGINIŲ OPERACIJŲ SAVYBĖS

1. Pavadinimai

1.1. Loginių jungčių (operacijų) žymėjimas:

a) neigimas(inversija, loginis NE) žymimas ¬ (pavyzdžiui, ¬A);

b) jungtis(loginis daugyba, loginis IR) žymimas /\
(pavyzdžiui, A /\ B) arba & (pavyzdžiui, A & B);

c) disjunkcija(loginis papildymas, loginis ARBA) žymimas \/
(pavyzdžiui, A \/ B);

d) sekantis(implikacija) žymimas → (pvz., A → B);

e) tapatybęžymimas ≡ (pavyzdžiui, A ≡ B). Išraiška A ≡ B yra teisinga tada ir tik tada, kai A ir B reikšmės yra vienodos (arba jos abi teisingos, arba abi klaidingos);

f) simbolis 1 naudojamas tiesai (true teiginiui) žymėti; simbolis 0 – nurodyti melą (klaidingą teiginį).

1.2. Iškviečiamos dvi Būlio išraiškos, kuriose yra kintamųjų lygiavertis (lygiavertis), jei šių išraiškų reikšmės sutampa su bet kuriomis kintamųjų reikšmėmis. Taigi posakiai A → B ir (¬A) \/ B yra lygiaverčiai, bet A /\ B ir A \/ B ne (reiškinių reikšmės skiriasi, pvz., kai A = 1, B = 0 ).

1.3. Loginių operacijų prioritetai: inversija (neigimas), konjunkcija (loginis daugyba), disjunkcija (loginis sudėjimas), implikacija (sekimas), tapatumas. Taigi ¬A \/ B \/ C \/ D reiškia tą patį, ką

((¬A) \/ B) \/ (C \/ D).

Galima rašyti A \/ B \/ C vietoj (A \/ B) \/ C. Tas pats pasakytina ir apie jungtuką: galima rašyti A /\ B /\ C vietoj (A /\ B) ) /\ C.

2. Savybės

Žemiau pateiktas sąrašas NĖRA išsamus, bet, tikiuosi, pakankamai reprezentatyvus.

2.1. Bendrosios savybės

Už rinkinį n yra tiksliai loginiai kintamieji 2 n skirtingos reikšmės. Tiesos lentelė loginei išraiškai iš n kintamieji yra n+1 stulpelis ir 2 n linijos.

2.2.Disjunkcija

Jei bent viena iš posakių, kurioms taikoma disjunkcija, yra teisinga kai kurioms kintamųjų reikšmių rinkiniams, tada visa disjunkcija yra teisinga šiai reikšmių rinkiniui.
Jei visos išraiškos iš tam tikro sąrašo yra teisingos tam tikrame kintamųjų reikšmių rinkinyje, tada šių išraiškų disjunkcija taip pat yra teisinga.
Jei visos išraiškos iš tam tikro sąrašo yra klaidingos tam tikrame kintamųjų reikšmių rinkinyje, tada šių išraiškų disjunkcija taip pat yra klaidinga.
Disjunkcijos reikšmė nepriklauso nuo posakių, kuriems jis taikomas, rašymo tvarkos.

2.3. Jungtis

Jei bent vienas iš posakių, kuriems taikomas junginys, yra klaidingas tam tikroje kintamųjų reikšmių rinkinyje, tada visas šios reikšmių rinkinio junginys yra klaidingas.
Jei visos išraiškos iš tam tikro sąrašo yra teisingos tam tikrame kintamųjų reikšmių rinkinyje, tada šių išraiškų konjunkcija taip pat yra teisinga.
Jei visi reiškiniai iš tam tikro sąrašo yra klaidingi tam tikrame kintamųjų reikšmių rinkinyje, tada šių išraiškų konjunkcija taip pat yra klaidinga.
Jungtuko reikšmė nepriklauso nuo posakių, kuriems jis taikomas, rašymo tvarkos.

2.4. Paprastieji disjunkcijos ir jungtukai

Pavadinkime (patogumo dėlei) jungtuku paprastas, jei posakiai, kuriems taikomas jungtukas, yra skirtingi kintamieji arba jų neigimai. Panašiai vadinama disjunkcija paprastas, jei subreiškiniai, kuriems taikoma disjunkcija, yra skirtingi kintamieji arba jų neigimai.

Paprasta jungtis įvertinama 1 (teisinga) tiksliai viename kintamųjų reikšmių rinkinyje.
Paprastas disjunkcija įvertinama iki 0 (klaidinga) tiksliai viename kintamųjų reikšmių rinkinyje.

2.5. Potekstė

Potekstė A →B yra lygiavertis disjunkcijai (¬ A) \/ B.Šį disjunkciją taip pat galima parašyti taip: ¬ A\/B.
Potekstė A →Bįgauna reikšmę 0 (false) tik tada, jei A=1 Ir B=0. Jeigu A=0, tada implikacija A →B tiesa bet kokiai vertei B.

Dėl Greita paieška informacija internete naudojama paieškos užklausoms. Paieškos užklausa yra rinkinys raktinius žodžius, sujungti loginių operacijų AND, ARBA, NE ženklais.

Veiksmų prioritetas, jei nėra specialiai dedamų skliaustų, yra toks: pirmiausia NE, tada AND, tada ARBA.

Turite suprasti, kad operacija AND (vienalaikis sąlygų įvykdymas) sumažina gauto rezultato apimtį, o operacija ARBA (bent vienos iš sąlygų įvykdymas) priešingai padidina apimtį.

Jei užklausoje yra frazė kabutėse, sistema ieškos būtent šios frazės visos.

1. Užklausų išdėstymas didėjančia (mažėjančia) tvarka

Operacija „IR“ (&) reiškia raktinių žodžių buvimą ieškomuose dokumentuose vienu metu, taigi sumažina rastos informacijos kiekį. Kuo daugiau raktinių žodžių sujungiama naudojant operaciją „IR“, tuo mažiau informacijos randama. Ir atvirkščiai, operacija „ARBA“ (|) rodo, kad ieškomuose dokumentuose yra bent vienas raktinis žodis, todėl padidėja rastos informacijos kiekis.

1 pavyzdys.

Lentelėje pateikiamos užklausos paieškos serveriui. Išdėstykite užklausos simbolius didėjančia tvarka pagal puslapių skaičių, kurį paieškos sistema ras pagal kiekvieną užklausą.

Sprendimas:

Mažiausias puslapių skaičius bus pasirinktas pagal užklausą su didžiausias skaičius„IR“ operacijos (užklausa D), užklausai bus pasirinktas didžiausias puslapių skaičius su daugiausiai „OR“ operacijų (užklausa B). A užklausai bus pasirinkta daugiau puslapių nei užklausai B, nes A užklausoje yra daugiau OR raktinių žodžių.

Atsakymas: GWAB

2. Pagal pageidavimą rastų puslapių skaičiavimas

Tokio tipo problemos dažniausiai išsprendžiamos lygčių sistema. Pasiūlysiu vizualesnį ir paprastesnį būdą.

Informacijos atrankos pagal paieškos užklausas principą gerai iliustruoja Eulerio-Veno diagrama (Eulerio apskritimai). Diagramoje aibės vaizduojamos susikertančiais apskritimais. Operacija IR (&) yra apskritimų sankirta, o operacija OR (|) yra apskritimų sąjunga.

Pavyzdžiui, rinkinius Obuoliai, Kriaušės, Bananai pažymėkime apskritimais. Užklausa Obuoliai, kriaušės ir bananai pasirinks visų trijų apskritimų sankirtą (bendrą dalį):