Datorzinātnes vaicājumi meklēšanas serverim. Loģiskās operācijas un to īpašības

17.10.2021

Elektriskā shēma, kas paredzēts, lai veiktu kādu loģisku darbību ar ievaddatiem, tiek saukts par loģisko elementu. Ievaddati šeit tiek attēloti dažādu līmeņu spriegumu veidā, un loģiskās darbības rezultāts izejā tiek iegūts arī noteikta līmeņa sprieguma veidā.

Šajā gadījumā tiek piegādāti operandi - loģiskā elementa ieejā tiek saņemti signāli augsta vai zema līmeņa sprieguma veidā, kas būtībā kalpo kā ievades dati. Tādējādi augsta līmeņa spriegums - loģika 1 - norāda operanda patieso vērtību, bet zema līmeņa spriegums 0 - nepatiesu vērtību. 1 — PATIESI, 0 — NEPAREIZI.

Loģiskais elements- elements, kas realizē noteiktas loģiskas attiecības starp ieejas un izejas signāliem. Loģiskos elementus parasti izmanto, lai izveidotu datoru loģiskās shēmas un diskrētas automātiskās uzraudzības un vadības shēmas. Visu veidu loģiskiem elementiem, neatkarīgi no to fiziskā rakstura, ir raksturīgas diskrētas ieejas un izejas signālu vērtības.

Loģiskajiem elementiem ir viena vai vairākas ieejas un viena vai divas (parasti apgrieztas viena otrai) izejas. Loģisko elementu izejas signālu “nulles” un “vieninieku” vērtības nosaka loģiskā funkcija, ko elements veic, un ieejas signālu “nulles” un “vieninieku” vērtības, kas tiek atskaņotas. neatkarīgo mainīgo lomu. Ir pamata loģiskās funkcijas, no kuras var izveidot jebkuru sarežģītu loģisko funkciju.

Atkarībā no elementu ķēdes konstrukcijas, no tā elektriskie parametri, loģiskie līmeņi (augsti un zems līmenis spriegums) ieejai un izvadei ir vienādas vērtības augstam un zemam (patiesam un nepatiesam) stāvoklim.

Tradicionāli loģiskie elementi tiek ražoti īpašu radio komponentu veidā - integrālās shēmas. Loģiskās darbības, piemēram, konjunkcija, disjunkcija, noliegums un moduļu pievienošana (UN, VAI, NAV, XOR), ir pamata darbības, kas tiek veiktas ar galvenajiem loģisko vārtu veidiem. Tālāk aplūkosim katru no šiem loģikas elementu veidiem tuvāk.

Loģiskais elements "UN" - savienojums, loģiskā reizināšana, UN

“UN” ir loģisks elements, kas ievades datiem veic savienošanas vai loģiskās reizināšanas darbību. Šis vienums var būt no 2 līdz 8 (izplatītākie ražošanā ir “UN” elementi ar 2, 3, 4 un 8 ieejām) ievades un viena izeja.

Loģisko elementu simboli "UN" ar dažādas summas ieejas ir parādītas attēlā. Tekstā loģiskais elements “UN” ar noteiktu ieeju skaitu tiek apzīmēts kā “2I”, “4I” utt. - “UN” elements ar divām ieejām, ar četrām ievadēm utt.

Elementa 2I patiesības tabula parāda, ka elementa izvade būs loģiska tikai tad, ja loģiskie vienlaicīgi atrodas pirmajā ieejā UN otrajā ieejā. Atlikušajos trīs iespējamajos gadījumos izvade būs nulle.

Rietumu diagrammās I elementa ikonai ir taisna līnija ieejā un noapaļota līnija pie izejas. Ieslēgts vietējām shēmām- taisnstūris ar simbolu “&”.

Loģiskais elements "OR" - disjunkcija, loģiskā saskaitīšana, VAI

“OR” ir loģisks elements, kas ievades datiem veic disjunkcijas vai loģiskās pievienošanas darbību. Tas, tāpat kā “I” elements, ir pieejams ar divām, trim, četrām utt. ieejām un vienu izeju. Loģisko elementu simboli "OR" ar dažādu ieeju skaitu ir parādīti attēlā. Šie elementi ir apzīmēti šādi: 2OR, 3OR, 4OR utt.

Elementa “2OR” patiesības tabula parāda, ka, lai izejā parādītos loģiskais, pietiek ar to, ka loģiskais atrodas pirmajā ieejā VAI otrajā ieejā. Ja pie divām ieejām vienlaikus ir loģiskie, arī izvade būs viena.

Rietumu diagrammās elementa “OR” ikonai ir noapaļota ievade un noapaļota, smaila izvade. Iekšzemes diagrammās ir taisnstūris ar simbolu “1”.

Loģiskais elements "NOT" - noliegums, invertors, NOT

“NOT” ir loģisks elements, kas veic ievades datu loģiskās noliegšanas darbību. Šo elementu, kuram ir viena izeja un tikai viena ieeja, sauc arī par invertoru, jo tas faktiski invertē (apgriež) ieejas signālu. Attēlā redzams simbols loģiskais elements "NAV".

Invertora patiesības tabula parāda, ka augsts ievades potenciāls rada zemu izejas potenciālu un otrādi.

Rietumu diagrammās elementa ikonai “NOT” ir trīsstūra forma ar apli izvadā. Iekšzemes diagrammās ir taisnstūris ar simbolu “1”, kura izvadā ir aplis.

Loģiskais elements "NAND" - savienojums (loģiskā reizināšana) ar noliegumu, NAND

“UN-NOT” ir loģisks elements, kas ievades datiem veic loģisku pievienošanas darbību un pēc tam loģiskās noliegšanas darbību, rezultāts tiek nosūtīts uz izvadi. Citiem vārdiem sakot, tas būtībā ir “UN” elements, ko papildina elements “NOT”. Attēlā parādīts loģiskā elementa simbols “2AND-NOT”.

Patiesības tabula NAND vārtiem ir pretēja patiesības tabulai UN vārtiem. Trīs nulles un viena vietā ir trīs vieninieki un nulle. NAND elementu sauc arī par “Šefera elementu” par godu matemātiķim Henrijam Morisam Šēferam, kurš pirmo reizi atzīmēja tā nozīmi 1913. gadā. Apzīmēts kā “I”, tikai ar apli izejā.

Loģiskais elements "OR-NOT" - disjunkcija (loģiskā saskaitīšana) ar noliegumu, NOR

“OR-NOT” ir loģisks elements, kas ievades datiem veic loģisku pievienošanas darbību un pēc tam loģiskās noliegšanas darbību, rezultāts tiek nosūtīts uz izvadi. Citiem vārdiem sakot, tas ir “OR” elements, ko papildina elements “NOT” - invertors. Attēlā parādīts loģiskā elementa simbols “2OR-NOT”.

VAI vārtu patiesības tabula ir pretēja VAI vārtu patiesības tabulai. Augsts potenciāls izejā tiek iegūts tikai vienā gadījumā - zemi potenciāli tiek pielietoti vienlaikus abām ieejām. Tas ir apzīmēts kā “OR”, tikai ar apli pie izejas, kas norāda uz inversiju.

Loģiskie vārti "ekskluzīvi VAI" - papildinājums modulo 2, XOR

“ekskluzīvs VAI” ir loģisks elements, kas veic loģisku pievienošanas operāciju modulo 2 ievades datiem, kuram ir divas ieejas un viena izeja. Bieži vien šie elementi tiek izmantoti vadības ķēdēs. Attēlā parādīts šī elementa simbols.

Rietumu shēmās attēls ir kā “OR” ar papildu izliektu sloksni ievades pusē, vietējās tas ir kā “OR”, tikai “1” vietā būs rakstīts “=1”.

Šo loģisko elementu sauc arī par “neekvivalenci”. Augsts sprieguma līmenis izejā būs tikai tad, ja signāli ieejā nav vienādi (viens ir viens, otrs ir nulle vai viens ir nulle, bet otrs ir viens), pat ja ieejā ir divi. tajā pašā laikā izvade būs nulle - tā ir atšķirība no "OR". Šie loģiskie elementi tiek plaši izmantoti summatoros.

Savienojums vai loģiskā reizināšana (kopu teorijā tas ir krustojums)

Saiklis ir sarežģīta loģiska izteiksme, kas ir patiesa tad un tikai tad, ja abas vienkāršās izteiksmes ir patiesas. Šī situācija ir iespējama tikai vienā gadījumā, visos citos gadījumos konjunkcija ir nepatiesa.

Apzīmējums: &, $\wedge$, $\cdot$.

Patiesības tabula savienojumam

1. attēls.

Savienojuma īpašības:

Ja vismaz viena no savienojuma apakšizteiksmēm ir nepatiesa kādai mainīgo vērtību kopai, tad visa konjunkcija būs nepatiesa šai vērtību kopai.
Ja visas savienojuma izteiksmes ir patiesas uz kādu mainīgo vērtību kopu, tad arī visa saite būs patiesa.
Visa kompleksa izteiksmes savienojuma nozīme nav atkarīga no secības, kādā tiek rakstītas apakšizteiksmes, kurām tā tiek piemērota (piemēram, reizināšana matemātikā).

Disjunkcija vai loģiskā saskaitīšana (kopu teorijā tā ir savienība)

Disjunkcija ir sarežģīta loģiska izteiksme, kas gandrīz vienmēr ir patiesa, izņemot gadījumus, kad visas izteiksmes ir nepatiesas.

Apzīmējums: +, $\vee$.

Patiesības tabula disjunkcijai

2. attēls.

Disjunkcijas īpašības:

Ja vismaz viena no disjunkcijas apakšizteiksmēm ir patiesa noteiktai mainīgo vērtību kopai, tad visa disjunkcija iegūst patieso vērtību šai apakšizteiksmju kopai.
Ja visas izteiksmes no kāda disjunkciju saraksta ir nepatiesas uz kādu mainīgo vērtību kopu, tad arī visa šo izteiksmju disjunkcija ir nepatiesa.
Visas disjunkcijas nozīme nav atkarīga no apakšizteikumu rakstīšanas secības (kā matemātikā - saskaitīšana).

Noliegums, loģisks noliegums vai inversija (kopu teorijā tas ir noliegums)

Noliegums nozīmē, ka oriģinālajai loģiskajai izteiksmei tiek pievienota daļiņa NOT vai vārds FALSE, KAS un rezultātā mēs iegūstam, ja sākotnējā izteiksme ir patiesa, tad sākotnējā noliegums būs nepatiess un otrādi, ja sākotnējā izteiksme ir nepatiess, tad tā noliegums būs patiess.

Apzīmējums: nevis $A$, $\bar(A)$, $¬A$.

Patiesības tabula inversijai

3. attēls.

Nolieguma īpašības:

$¬¬A$ “dubultā noliegums” ir priekšlikuma $A$ sekas, tas ir, formālajā loģikā tā ir tautoloģija un ir vienāda ar pašu vērtību Būla loģikā.

Implikācija vai loģiskas sekas

Implikācija ir sarežģīta loģiska izteiksme, kas ir patiesa visos gadījumos, izņemot gadījumus, kad patiesība seko nepatiesībai. Tas nozīmē, ka šī loģiskā darbība savieno divas vienkāršas loģiskās izteiksmes, no kurām pirmā ir nosacījums ($A$), bet otrā ($A$) ir nosacījuma ($A$) sekas.

Apzīmējums: $\to$, $\Rightarrow$.

Patiesības tabula implicēšanai

4. attēls.

Implikācijas īpašības:

$A \to B = ¬A \vee B$.
Implikācija $A \uz B$ ir nepatiesa, ja $A=1$ un $B=0$.
Ja $A=0$, tad imlikācija $A \uz B$ ir patiesa jebkurai $B$ vērtībai (patiesa var izrietēt no nepatiesa).

Ekvivalence vai loģiskā ekvivalence

Ekvivalence ir sarežģīta loģiska izteiksme, kas ir patiesa mainīgo $A$ un $B$ vienādām vērtībām.

Apzīmējumi: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.

Patiesības tabula līdzvērtībai

5. attēls.

Ekvivalences īpašības:

Ekvivalence ir patiesa uz vienādām mainīgo $A$ un $B$ vērtību kopām.
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$

Stingra disjunkcija vai saskaitīšana modulo 2 (kopu teorijā šī ir divu kopu savienība bez to krustpunkta)

Stingra disjunkcija ir patiesa, ja argumentu vērtības nav vienādas.

Elektronikai tas nozīmē, ka ķēžu ieviešana ir iespējama, izmantojot vienu standarta elementu (lai gan tas ir dārgs elements).

Loģisko operāciju secība sarežģītā loģiskā izteiksmē

Inversija(negācija);
Saikne (loģiskā reizināšana);
Disjunkcija un strikta disjunkcija (loģisks papildinājums);
Implikācija (sekas);
Ekvivalence (identitāte).

Lai mainītu norādīto loģisko darbību secību, jāizmanto iekavas.

Vispārējās īpašības

$n$ Būla mainīgo kopai ir tieši $2^n$ atšķirīgas vērtības. Patiesības tabula priekš loģiskā izteiksme no $n$ mainīgajiem ir $n+1$ kolonnas un $2^n$ rindas.

Sadaļas: Informātika

Pašlaik datorzinātņu iestājeksāmenos ir daudz uzdevumu par tēmu “loģikas algebra”. Šīs nodarbības mērķis ir nostiprināt prasmes risināt Vienotā valsts pārbaudījuma uzdevumus datorzinātnēs, izmantojot loģiskās algebras elementus.

Nodarbības mērķi:

Prasmes pielietot iegūtās zināšanas veidošana praksē;
Attīstīt spēju konstruēt patiesības tabulas, izmantojot dotās formulas;
Attīstīt spēju risināt teksta uzdevumus, izmantojot loģikas likumus.

Nodarbības mērķi:

Izglītojoši – kognitīvās intereses, loģiskās domāšanas attīstība.
Izglītojoši– matemātiskās loģikas pamatu atkārtošana, veicot praktiskus uzdevumus.
Attīstošs – loģiskās domāšanas, vērīguma attīstība.

Nodarbības progress

Loģisko darbību un likumu atkārtošana.
Loģisko operāciju un likumu pielietošana praksē.
Mājas darba skaidrojums.

Šodien pabeidzam tēmu “Loģikas pamati” un pielietosim loģikas pamatoperācijas un transformācijas likumus Vienotā valsts eksāmena uzdevumu risināšanai datorzinātnēs.

Nodarbība notiek paralēli prezentācijai.<Приложение1>

1. Loģisko darbību un likumu atkārtošana.

Loģikas algebra ir matemātiskās loģikas nozare, kas pēta sarežģītu loģisko apgalvojumu struktūru un metodes to patiesuma noteikšanai, izmantojot algebriskās metodes.

1. Formālās loģikas pamatlicējs?

Aristotelis.

2. Loģikas algebras dibinātājs?

Džordžs Būls.

3. Uzskaitiet loģiskās darbības:

¬ noliegums (inversija)
&, /\savienojums (“Un”)
V disjunkcija (“OR”)
loģiskas sekas (implikācija)
līdzvērtība (ekvivalence)

4. Ko nozīmē dubultās noliegšanas likums?

Dubults negatīvs novērš negatīvo.

5. De Morgana likumi (vispārējās inversijas likumi).

Disjunkcijas noliegums ir noliegumu konjunkcija:

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

Saikļa noliegums ir noliegumu disjunkcija:

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

6. Idempotences (vienādības) likums.

7. Ko nozīmē trešās izslēgšanas likums?

No diviem pretrunīgiem apgalvojumiem par vienu un to pašu, viens vienmēr ir patiess, otrs ir nepatiess, bet trešais netiek sniegts:

8. Par ko ir pretrunu likums?

Apgalvojums un tā noliegums nevar būt patiesi vienlaikus:

9. Konstantu izslēgšanas likums.

Loģiskam papildinājumam:

A V 1 = 1 A V 0 = A

Loģiskai reizināšanai:

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

10. Kā izteikt implikāciju, izmantojot disjunkciju?

A B = ¬A V B

2. Loģisko darbību un likumu pielietošana praksē.

1. piemērs. ( Uzdevuma A11 demonstrācijas versija 2004)

Kuram vārdam ir patiess apgalvojums:

¬ (Vārda pirmais burts ir patskanis -> Vārda ceturtais burts ir līdzskaņs)?

Risinājums. Sarežģīts paziņojums sastāv no diviem vienkāršiem paziņojumiem:

A ir vārda pirmais burts, patskanis,

B ir vārda ceturtais burts, līdzskaņs.

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

Izmantotās formulas:

1. Implikācija caur disjunkciju A? B = ¬A V B

2. De Morgana likums ¬(A V B) = ¬A /\ ¬B

3. Dubultās noliegšanas likums.

(Vārda pirmais burts ir patskanis /\ Vārda ceturtais burts ir patskanis)

2. piemērs. ( Uzdevums A12 demonstrācijas versija 2004)

Kura loģiskā izteiksme ir ekvivalenta izteiksmei ¬ (A \/ ¬B)?

Risinājums. ¬ (A \/ ¬B) = ¬ A \/ ¬ (¬B) = ¬ A \/ B

Izveidojiet formulas patiesības tabulu

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

Loģisko darbību secība:

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

Izveidojiet patiesības tabulu.

Cik rindu būs jūsu tabulā? 3 mainīgie: A, B, C; 2 3 =8

Cik kolonnu? 5 darbības + 3 mainīgie = 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

Kādas atbildes saņēmāt pēdējā slejā?

identiski patiess, ja visās tajā iekļautajās vienkāršos priekšrakstu kopās tiek ņemtas vērtības 1. Tiek sauktas identiski patiesas formulas tautoloģijas.

Atrisināsim šo piemēru, izmantojot analītisko metodi:

vienkāršot izteiksmi

¬ (B /\ C) V (A/\C B)= (izmantojiet formulu implicēšanai)

¬ (B /\ C) V ¬ (A /\ C) V B = (piemērojiet 1. un 2. de Morgana likumus)

(¬B V ¬C) V (¬A V ¬C) V B = (noņemt iekavas)

¬B V ¬C V ¬A V ¬C V B= (piemērot komutatīvo likumu)

¬B V B V ¬C V ¬C V ¬A = (vidus izslēgšanas likums, idempotences likums)

1 V ¬С V ¬A = 1 V ¬A = 1 (konstantu izslēgšanas likums)

Atbilde: 1 , nozīmē, ka formula ir identiski patiesa vai tautoloģija.

Tiek saukta loģiskā izteiksme identiski nepatiess, ja visās tajā iekļautajās vienkāršos priekšrakstu kopās tiek ņemtas vērtības 0.

(3. mājas uzdevums)

Tabulā ir parādīti vaicājumi meklēšanas serverim. Sakārtojiet vaicājumu apzīmējumus augošā secībā pēc lapu skaita, ko meklētājprogramma atradīs katram vaicājumam.

Simbols I tiek izmantots, lai apzīmētu loģisko darbību “OR” vaicājumā, un simbols & tiek izmantots, lai apzīmētu loģisko darbību “UN”.

Pirmā metode ir balstīta uz argumentāciju. Loģiski argumentējot, redzam, ka visvairāk lapu tiks atrasts vaicājumam G, jo pēc tā izpildes tiks rādītas lapas ar vārdu “likumi” un lapas ar vārdu “fizika” un lapas ar vārdu “bioloģija”. atrasts. Vismazākais lapu skaits tiks atrasts vaicājumam B, jo tajā ir ietverti visi četri vārdi meklētajā lapā. Atliek salīdzināt vaicājumus A un B. Vaicājums B atradīs visas lapas, kas atbilst vaicājumam A (jo pēdējais obligāti satur vārdu “likumi”), kā arī lapas, kurās ir gan vārdi “fizika”, gan “bioloģija”. Tāpēc vaicājumam B tiks atrasts vairāk lapu nekā vaicājumam A. Tātad, sakārtojot vaicājumus lapu augošā secībā, mēs iegūstam VABG.

Atbilde: VABG.

Otrā metode ietver darbību grafiskā attēlojuma izmantošanu kopās. (Skatīt prezentāciju)

5. piemērs. ( Uzdevuma A16 demonstrācijas versija 2006)

Zemāk iekšā tabulas forma tiek parādīts datu bāzes fragments par studentu pārbaudes rezultātiem (izmantota simts punktu skala)

Uzvārds	Stāvs	Matemātika	krievu valoda	Ķīmija	Informātika	Bioloģija
Aganjans	un	82	56	46	32	70
Voroņins	m	43	62	45	74	23
Grigorčuks	m	54	74	68	75	83
Rodniņa	un	71	63	56	82	79
Sergejenko	un	33	25	74	38	46
Čerepanova	un	18	92	83	28	61

Cik ierakstu šajā fragmentā atbilst nosacījumam

“Dzimums=’m’ VAI ķīmija>bioloģija”?

Izvēlamies ierakstus: Zēni (divi) un Ķīmija>Bioloģija (trīs, bet viens puika, jau ņemts 1 reizi). Rezultātā 4 ieraksti apmierina nosacījumu.

6. uzdevums. ( Task B4 demonstrācijas versija 2007)

Skolēnu čempionātā galda tenisā labāko četriniekā iekļuva meitenes: Nataša, Maša, Ļuda un Rita. Dedzīgākie līdzjutēji izteica savus pieņēmumus par vietu sadalījumu turpmākajās sacensībās.

Cilvēks uzskata, ka Nataša būs pirmā, bet Maša – otrā.

Cits līdzjutējs Ludai prognozē otro vietu, un Rita, viņaprāt, ieņems ceturto vietu.

Trešais tenisa fans viņiem nepiekrita. Viņš uzskata, ka Rita ieņems trešo vietu, bet Nataša būs otrā.

Kādu vietu čempionātā ieņēma Nataša, Maša, Luda, Rita?

(Atbildē pēc kārtas bez atstarpēm norādiet meiteņu vietām atbilstošos skaitļus norādītajā vārdu secībā.)

Apzīmēsim apgalvojumus:

H1 = "Nataša būs pirmā";

M2 = "Maša būs otrā";

L2 = “Luda būs otrā”;

P4 = “Rita būs ceturtā”;

P3 = “Rita būs trešā”;

H2 = "Nataša būs otrā."

Saskaņā ar nosacījumu:

no 1 fana apgalvojumiem izriet, ka H1VM2 ir patiess;

no ventilatora apgalvojumiem2 izriet, ka A2VP4 ir patiess;

no fana 3 apgalvojumiem izriet, ka P3VH2 ir patiess.

Tāpēc arī savienojums ir patiess

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

Atverot iekavas, mēs iegūstam:

(Н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, Luda-2, Rita-3 un Maša-4.

Atbilde: 1423

3. Mājas darba skaidrojums.

1. uzdevums. ( Uzdevuma B8 demonstrācijas versija 2007)

Tabulā ir parādīti vaicājumi meklēšanas serverim. Sakārtojiet vaicājuma simbolus augošā secībā pēc lapu skaita, ko meklētājprogramma atradīs katram vaicājumam.

Lai vaicājumā apzīmētu loģisko darbību “OR”, izmantojiet simbolu |, bet loģiskās darbības apzīmēšanai “UN” – &.

2. uzdevums ( Uzdevuma B4 demonstrācijas versija 2008)

Pirms četrinieku turnīra sākuma fani izteica šādus pieņēmumus par saviem elkiem:

A) Makss uzvarēs, Bils būs otrais;

B) Bils ir trešais. Niks ir pirmais;

C) Makss ir pēdējais, un pirmais ir Jānis.

Kad konkurss beidzās, izrādījās, ka katram no līdzjutējiem bija taisnība tikai vienā no savām prognozēm.

Kādu vietu turnīrā ieņēma Džons, Niks, Bils, Makss?

(Atbildē dalībnieku vietas norādiet rindā bez atstarpēm norādītajā vārdu secībā.)

LOĢISKO DARBĪBU ĪPAŠĪBAS

1. Apzīmējumi

1.1. Loģisko savienojumu (operāciju) apzīmējumi:

a) noliegums(inversija, loģiskā NAV) tiek apzīmēta ar ¬ (piemēram, ¬A);

b) savienojums(loģiskā reizināšana, loģiskā UN) tiek apzīmēta ar /\
(piemēram, A /\ B) vai & (piemēram, A un B);

c) disjunkcija(loģisks papildinājums, loģiskais VAI) ir apzīmēts ar \/
(piemēram, A \/ B);

d) sekojot(implikācija) tiek apzīmēta ar → (piemēram, A → B);

e) identitāte apzīmē ar ≡ (piemēram, A ≡ B). Izteiksme A ≡ B ir patiesa tad un tikai tad, ja A un B vērtības ir vienādas (vai nu tās ir patiesas, vai abas ir nepatiesas);

f) simbols 1 tiek izmantots patiesības apzīmēšanai (patiess apgalvojums); simbols 0 – lai norādītu uz meliem (nepatiess apgalvojums).

1.2. Tiek izsauktas divas Būla izteiksmes, kas satur mainīgos ekvivalents (ekvivalents), ja šo izteiksmju vērtības sakrīt ar jebkuru mainīgo vērtību. Tādējādi izteiksmes A → B un (¬A) \/ B ir ekvivalentas, bet A /\ B un A \/ B nav (izteiksmju nozīmes ir atšķirīgas, piemēram, ja A = 1, B = 0 ).

1.3. Loģisko operāciju prioritātes: inversija (negācija), konjunkcija (loģiskā reizināšana), disjunkcija (loģiskā saskaitīšana), implikācija (sekošana), identitāte. Tādējādi ¬A \/ B \/ C \/ D nozīmē to pašu, ko

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

Ir iespējams rakstīt A \/ B \/ C vietā (A \/ B) \/ C. Tas pats attiecas uz savienojumu: ir iespējams rakstīt A /\ B /\ C vietā (A /\ B) ) /\ C.

2. Īpašības

Zemāk esošais saraksts NAV paredzēts pilnīgs, taču mēs ceram, ka tas būs pietiekami reprezentatīvs.

2.1. Vispārējās īpašības

Par komplektu n ir tieši loģiski mainīgie 2 n dažādas nozīmes. Patiesības tabula loģiskai izteiksmei no n mainīgie satur n+1 kolonnu un 2 n līnijas.

2.2.Disjunkcija

Ja vismaz viena no apakšizteiksmēm, kurām tiek piemērota disjunkcija, ir patiesa kādai mainīgo vērtību kopai, tad šai vērtību kopai ir patiesa visa disjunkcija.
Ja visas izteiksmes no noteikta saraksta ir patiesas uz noteiktu mainīgo vērtību kopu, tad arī šo izteiksmju disjunkcija ir patiesa.
Ja visas izteiksmes no noteikta saraksta ir nepatiesas uz noteiktu mainīgo vērtību kopu, tad arī šo izteiksmju disjunkcija ir nepatiesa.
Disjunkcijas nozīme nav atkarīga no apakšizteikumu rakstīšanas secības, kurām tā tiek piemērota.

2.3. Savienojums

Ja vismaz viena no apakšizteiksmēm, kurām tiek lietota saite, ir nepatiesa kādai mainīgo vērtību kopai, tad visa konjunkcija ir nepatiesa šai vērtību kopai.
Ja visas izteiksmes no noteikta saraksta ir patiesas uz noteiktu mainīgo vērtību kopu, tad arī šo izteiksmju konjunkcija ir patiesa.
Ja visas izteiksmes no noteikta saraksta ir nepatiesas uz noteiktu mainīgo vērtību kopu, tad arī šo izteiksmju konjunkcija ir nepatiesa.
Saikļa nozīme nav atkarīga no apakšizteiksmju rakstīšanas secības, kurām tas tiek piemērots.

2.4. Vienkārši disjunkcijas un konjunkcijas

Sauksim (ērtības labad) saikni vienkārši, ja apakšizteiksmes, kurām tiek lietots savienojums, ir atšķirīgi mainīgie vai to noliegumi. Līdzīgi sauc arī disjunkciju vienkārši, ja apakšizteiksmes, kurām tiek piemērota disjunkcija, ir atšķirīgi mainīgie vai to noliegumi.

Vienkārša savienojuma vērtība ir 1 (patiesa) tieši vienā mainīgo vērtību kopā.
Vienkārša disjunkcija tiek novērtēta līdz 0 (false) tieši vienai mainīgo vērtību kopai.

2.5. Ietekme

Ietekme A →B ir līdzvērtīgs disjunkcijai (¬ A) \/ B.Šo disjunkciju var uzrakstīt arī šādi: ¬ A\/B.
Ietekme A →Bņem vērtību 0 (false) tikai tad, ja A=1 Un B=0. Ja A=0, tad sekas A →B patiess jebkurai vērtībai B.

Par ātra meklēšana informāciju internetā izmanto meklēšanas vaicājumi. Meklēšanas vaicājums ir kopa atslēgvārdi, kas savienoti ar loģisko darbību zīmēm UN, VAI, NĒ.

Darbību prioritāte, ja nav speciāli ievietotas iekavas, ir šāda: vispirms NOT, tad UN, tad VAI.

Jums jāsaprot, ka operācija UN (vienlaicīga nosacījumu izpilde) samazina iegūtā rezultāta apjomu, bet operācija VAI (vismaz viena nosacījuma izpilde) tieši pretēji palielina apjomu.

Ja pieprasījumā ir frāze pēdiņās, sistēma meklēs tieši šo frāzi pilnībā.

1. Vaicājumu sakārtošana augošā (dilstošā) secībā

Operācija “UN” (&) apzīmē vienlaicīgu atslēgvārdu klātbūtni meklētajos dokumentos un tādējādi samazina atrastās informācijas apjomu. Jo vairāk atslēgvārdu tiek savienoti, izmantojot operāciju “UN”, jo mazāk informācijas tiek atrasts. Un otrādi, operācija “OR” (|) norāda uz vismaz viena atslēgvārda klātbūtni meklētajos dokumentos un tādējādi palielina atrastās informācijas apjomu.

1. piemērs.

Tabulā ir parādīti vaicājumi meklēšanas serverim. Sakārtojiet vaicājuma simbolus augošā secībā pēc lapu skaita, ko meklētājprogramma atradīs katram vaicājumam.

Risinājums:

Vaicājumam ar vislielāko “I” darbību skaitu (vaicājums D) tiks atlasīts vismazākais lapu skaits, visvairāk liels skaits lapas tiks atlasītas, pamatojoties uz vaicājumu ar lielāko “OR” darbību skaitu (vaicājums B). Vaicājumam A tiks atlasīts vairāk lapu nekā vaicājumam B, jo Vaicājumā A ir vairāk VAI atslēgvārdu.

Atbilde: GWAB

2. Pēc pieprasījuma atrasto lapu skaitīšana

Šāda veida problēmas parasti risina ar vienādojumu sistēmu. Es ieteikšu vizuālāku un vienkāršāku veidu.

Informācijas atlases principu, pamatojoties uz meklēšanas vaicājumiem, labi ilustrē Eilera-Vena diagramma (Eilera apļi). Diagrammā kopas ir attēlotas ar krustojošiem apļiem. Operācija UN (&) ir apļu krustpunkts, bet darbība VAI (|) ir apļu savienojums.

Piemēram, kopas Āboli, Bumbieri, Banāni apzīmēsim ar apļiem. Pieprasījumā Āboli, bumbieri un banāni atlasīs visu trīs apļu krustojumu (kopējo daļu):