Решаване на изпитни задачи по информатика с използване на елементи от алгебрата на логиката. Логически операции и техните свойства Редът на извършване на логически операции в сложен логически израз

Електрическа схема, предназначен да извършва всяка логическа операция с входни данни, се нарича логически елемент. Входните данни са представени тук под формата на напрежения от различни нива, а резултатът от логическата операция на изхода също се получава под формата на напрежение от определено ниво.

В този случай се подават операнди - на входа на логическия елемент се получават сигнали под формата на високо или ниско напрежение, които по същество служат като входни данни. И така, високото ниво на напрежение - това е логическа единица от 1 - означава истинската стойност на операнда, а ниското ниво на напрежение 0 - фалшивата стойност. 1 - ВЯРНО, 0 - НЕВЕРНО.

Логически елемент- елемент, който реализира определена логическа връзка между входните и изходните сигнали. Логическите порти обикновено се използват за изграждане на логически схеми изчислителни машини, дискретни схеми за автоматично управление и управление. Всички видове логически елементи, независимо от тяхната физическа природа, се характеризират с дискретни стойности на входните и изходните сигнали.

Логическите порти имат един или повече входа и един или два (обикновено инверсни един спрямо друг) изхода. Стойностите на "нули" и "единици" на изходните сигнали на логически елементи се определят от логическата функция, която елементът изпълнява, и стойностите на "нули" и "единици" на входните сигнали, които възпроизвеждат ролята на независимите променливи. Има елементарни логически функции, от който можете да съставите всяка сложна логическа функция.

В зависимост от устройството на веригата на елемента, от неговите електрически параметри, логическите нива (нива на високо и ниско напрежение) на входа и изхода имат еднакви стойности за високо и ниско (вярно и невярно) състояния.

Традиционно логическите елементи се произвеждат под формата на специални радиокомпоненти - интегрални схеми... Логически операции като конюнкция, дизюнкция, отрицание и събиране по модул (И, ИЛИ, НЕ, изключително ИЛИ) са основните операции, извършвани върху логически елементи от основни типове. След това нека разгледаме по-отблизо всеки от тези видове логически порти.

Логически елемент "И" - съвпад, логическо умножение, И

"И" е логически елемент, който извършва конюнкция или логическо умножение на входните данни. Този артикулможе да има от 2 до 8 (най-често срещаните в производството елементи "И" с 2, 3, 4 и 8 входа) входа и един изход.

На фигурата са показани символи на логически елементи "И" с различен брой входове. В текста логически елемент "И" с един или друг брой входове е обозначен като "2I", "4I" и т.н. - елемент "И" с два входа, с четири входа и т.н.

Таблицата на истинността за елемент 2I показва, че изходът на елемента ще бъде логическа единица само ако логическите единици са едновременно на първия вход И на втория вход. В останалите три възможни случая изходът ще бъде нула.

В западните диаграми иконата на елемента "И" има права линия на входа и закръгляване на изхода. На вътрешни диаграми - правоъгълник със символа "&".

Логически елемент "ИЛИ" - дизюнкция, логическо събиране, ИЛИ

„ИЛИ“ е логически елемент, който изпълнява операция за разделяне или логическо събиране на входните данни. Той, подобно на елемента “AND”, се произвежда с два, три, четири и т.н. входа и един изход. На фигурата са показани символи на логически елементи "ИЛИ" с различен брой входове. Тези елементи са обозначени, както следва: 2OR, 3OR, 4OR и т.н.

Таблицата на истинността за елемента "2OR" показва, че за появата на логическа единица на изхода е достатъчно логическата единица да е на първия вход ИЛИ на втория вход. Ако логическите са едновременно на два входа, изходът също ще бъде един.

В западните диаграми елементът ИЛИ има заоблен вход и закръглена точка на изхода. На вътрешни диаграми - правоъгълник със символа "1".

Логическа врата "НЕ" - отрицателна, инверторна, НЕ

„НЕ“ е логически елемент, който изпълнява операцията на логическо отрицание върху входните данни. Този елемент, който има един изход и само един вход, се нарича още инвертор, тъй като всъщност инвертира (превръща) входния сигнал. Фигурата показва конвенционалното обозначение на логическия елемент "НЕ".

Таблицата на истинността за инвертора показва, че висок потенциал на входа дава нисък потенциал на изхода и обратно.

В западните диаграми иконата на елемент "НЕ" има формата на триъгълник с кръг на изхода. На домашни вериги - правоъгълник със символ "1", с кръг на изхода.

Логически елемент "И-НЕ" - конюнкция (логическо умножение) с отрицание, NAND

"И-НЕ" - логически елемент, който изпълнява операцията на логическо събиране на входните данни и след това операцията на логическо отрицание, резултатът се подава на изхода. С други думи, по принцип това е елементът "И", допълнен от елемента "НЕ". Фигурата показва конвенционалното обозначение на логическия елемент "2I-NOT".

Таблицата на истинността за елемента И-НЕ е противоположна на таблицата за елемента И. Вместо три нули и едно, има три единици и нула. Елементът NAND се нарича още елемент на Шефер в чест на математика Хенри Морис Шефер, който за първи път отбелязва важността на това през 1913 г. Означава се като "И", само с кръгче на изхода.

Логически елемент "ИЛИ-НЕ" - дизюнкция (логическо събиране) с отрицание, НЕ

"ИЛИ-НЕ" - логически елемент, който изпълнява операцията на логическо събиране на входните данни и след това операцията на логическо отрицание, резултатът се подава на изхода. С други думи, това е елемент "ИЛИ", допълнен от елемент "НЕ" - инвертор. Фигурата показва конвенционалното обозначение на логическия елемент "2OR-NOT".

Таблицата на истинността за елемента ИЛИ-НЕ е противоположна на таблицата за елемента ИЛИ. Висок потенциал на изхода се получава само в един случай - ниски потенциали се прилагат на двата входа едновременно. Означава се като "ИЛИ", само с кръг на изхода, което показва инверсия.

Логически порт "изключително ИЛИ" - събиране по модул 2, XOR

"Изключително ИЛИ" - логически елемент, който извършва операция по логическо събиране на входни данни по модул 2, има два входа и един изход. Тези елементи често се използват в схемите за управление. Фигурата показва символа за този елемент.

Изображението в западните схеми - като в "ИЛИ" с допълнителна извита лента отстрани на входа, в домашните - като "ИЛИ", само вместо "1" ще бъде изписано "= 1".

Този логически елемент се нарича още "неравенство". Високо ниво на напрежение ще бъде на изхода само когато сигналите на входа не са равни (на една единица, на другата нула или на една нула и на другата), дори ако има две единици на входа в същото време изходът ще бъде нула - това е разликата от "OR". Тези логически елементи се използват широко в суматорите.

раздели: Информатика

В момента в приемните изпити по информатика има много задачи на тема „алгебра на логиката”. Целта на този урок е да се консолидират уменията за решаване на задачи за използване в компютърните науки с помощта на елементи от логическата алгебра.

Цели на урока:

Формиране на способност за прилагане на придобитите знания на практика;
Развитие на умението за конструиране на таблици на истинността по зададени формули;
Развитие на способността за решаване на текстови задачи, използвайки законите на логиката.

Цели на урока:

Образователни - развитие на познавателен интерес, логическо мислене.
Образователни- повторение на основите на математическата логика, изпълнение на практически задачи.
Развиващи се - развитие на логическото мислене, внимание.

По време на занятията

Повторение на логически операции и закони.
Прилагане на логически операции и закони в практиката.
Обяснение на домашната работа.

Днес завършваме темата "Основи на логиката" и ще приложим основните логически операции, закони на трансформация за решаване на задачите на USE в компютърните науки.

Урокът върви успоредно с презентацията.<Приложение1>

1. Повторение на логически операции и закони.

Алгебрата на логиката е клон на математическата логика, който изучава структурата на сложни логически твърдения и методи за установяване на тяхната истинност с помощта на алгебрични методи.

1. Основателят на формалната логика?

Аристотел.

2. Основателят на алгебрата на логиката?

Джордж Бул.

3. Избройте логическите операции:

¬ отрицание (обръщане)
&, / \ съединение („И“)
V дизюнкция („ИЛИ“)
логическо следствие (внушение)
еквивалентност (еквивалентност)

4. Какво е значението на закона за двойното отрицание?

Двойното отрицание изключва отрицанието.

5. Законите на Де Морган (закони на общата инверсия).

Отрицанието на дизюнкцията е съединението на отрицанията:

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

Отрицанието на конюнкция е дизюнкция на отрицания:

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

6. Законът за идемпотентността (идентичността).

7. Какво е значението на закона за изключване на третото?

От две противоречиви твърдения за едно и също, едното винаги е вярно, второто е невярно, третото не е дадено:

8. За какво е законът за противоречието?

Твърдението и неговото отрицание не могат да бъдат едновременно верни:

9. Законът за изключване на константите.

За логично добавяне:

A V 1 = 1 A V 0 = A

За логическо умножение:

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

10. Как да изразим импликацията чрез дизюнкция?

A B = ¬A V B

2. Прилагане на логически операции и закони в практиката.

Пример 1. ( Задача A11 от демонстрацията от 2004 г.)

За кое име е вярна поговорката:

¬ (Първа буква на гласна -> Четвърта буква на съгласна)?

Решение. Сложното изявление се състои от две прости изявления:

A - първата буква на името е гласна,

B - четвъртата буква на името е съгласна.

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

Приложими формули:

1. Импликация чрез дизюнкция A? B = ¬A V B

2. Законът на Де Морган ¬ (A V B) = ¬A / \ ¬B

3. Законът за двойното отрицание.

(Първата буква на името е гласна / \ Четвъртата буква на името е гласна)

Пример 2. ( Задача A12 от демонстрацията от 2004 г.)

Кой логически израз е същият като ¬ (A \ / ¬B)?

Решение. ¬ (A \ / ¬B) = ¬ A \ / ¬ (¬B) = ¬ A \ / B

Създайте таблица на истинността за формула

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

Редът на извършване на логически операции:

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

Начертайте таблица на истинността.

Колко реда ще има вашата таблица? 3 променливи: A, B, C; 2 3 = 8

Колко колони? 5 операции + 3 променливи = 8

А	Б	° С	(B / \ C)	¬ (B / \ C)	A / \ C	(A / \ C? B)	¬ (B / \ C) V (A / \ CБ)
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

Какви са отговорите в последната колона?

идентично вярноако приема стойности 1 за всички набори от прости изрази, включени в него. Идентично верните формули се наричат тавтологии.

Нека решим този пример с помощта на аналитичния метод:

опростяване на израза

¬ (B / \ C) V (A / \ C B) = (приложете формулата за импликацията)

¬ (B / \ C) V ¬ (A / \ C) V B = (приложете 1 и 2 законите на де Морган)

(¬B V ¬C) V (¬A V ¬C) V B = (премахване на скобите)

¬B V ¬C V ¬A V ¬C V B = (прилага се законът за транспониране)

¬B V B V ¬C V ¬C V ¬A = (законът за изключване на третото, законът за идемпотентността)

1 V ¬C V ¬A = 1 V ¬A = 1 (закон за елиминиране на константите)

Отговор: 1 , означава, че формулата е идентично вярна или е тавтология.

Булевият израз се нарича идентично фалшивоако приема стойностите 0 за всички набори от прости изрази, включени в него.

(задача 3 домашна)

Таблицата изброява заявките към сървъра за търсене. Подредете обозначенията на заявките във възходящ ред на броя страници, които търсачката ще намери за всяка заявка.

За обозначаване на логическата операция "ИЛИ" в заявката се използва символът I, а за логическата операция "И" - символът &.

Първият начин се основава на разсъждения. Логически разсъждавайки, виждаме, че повечето от страниците ще бъдат открити за заявката D, тъй като когато тя бъде изпълнена, страниците с думата „закони“ и страниците с думата „физика“ и страниците с думата „биология“ ще бъде намерен. Най-малко от всички страници ще бъдат намерени за заявка Б, тъй като тя съдържа и четирите думи на страницата за търсене. Остава да сравним заявки A и B. Чрез заявка B ще бъдат намерени всички страници, съответстващи на заявка A (тъй като последната задължително съдържа думата "закони"), както и страници, съдържащи както думите "физика", така и "биология" . Следователно, заявка B ще намери повече страници от заявка A. Така че, подреждайки заявките във възходящ ред на страници, получаваме WABG.

Отговор: WABG.

Вторият метод включва използването на графично представяне на операциите върху множества. (Вижте презентацията)

Пример 5. ( Задача A16 от демонстрацията от 2006 г.)

По-долу, в табличен вид, е представен фрагмент от базата данни за резултатите от студентски тестове (използва се стоточкова скала)

Фамилия	етаж	математика	руски език	Химия	Информатика	Биология
Аганян	е	82	56	46	32	70
Воронин	м	43	62	45	74	23
Григорчук	м	54	74	68	75	83
Роднина	е	71	63	56	82	79
Сергеенко	е	33	25	74	38	46
Черепанова	е	18	92	83	28	61

Колко записа в даден фрагмент отговарят на условието

„Пол = „m“ ИЛИ Химия> Биология“?

Изберете записите: Момчета (две) и Химия> Биология (три, но едно момче, вече е взело един път). В резултат на това 4 записа удовлетворяват условието.

Задача 6. ( Задача B4 от демонстрацията от 2007 г.)

В училищното първенство по тенис на маса първите четири включваха момичета: Наташа, Маша, Луда и Рита. Най-запалените фенове изразиха своите предположения за разпределението на местата в бъдещи състезания.

Един мисли, че Наташа ще бъде първата, а Маша ще бъде втората.

Друг фен чете Луда на второ място, а Рита, според него, ще заеме четвърто място.

Трети любител на тениса не се съгласи с тях. Той вярва, че Рита ще заеме трето място, а Наташа ще бъде втора.

Какво място заеха Наташа, Маша, Луда, Рита в шампионата?

(В отговора си избройте числата в ред без интервали, съответстващи на местата на момичетата в дадения ред на имената.)

Нека обозначим твърдения:

Н1 = „Наташа ще бъде първата“;

M2 = „втората ще бъде Маша“;

L2 = „вторият ще бъде Луда“;

P4 = „Рита ще бъде четвъртата“;

P3 = „Рита ще бъде третата“;

H2 = „Наташа ще бъде втората“.

Според условието:

от твърденията на 1 фен следва, че Н1VМ2 е вярно;

от твърденията2 на фена следва, че L2VP4 е вярно;

от твърденията на 3 фена следва, че Р3VН2 е вярно.

Следователно, съюзът

(H1VM2) / \ (L2VP4) / \ (P3VH2) = 1.

Разширявайки скобите, получаваме:

(H1VM2) / \ (L2VP4) / \ (P3VH2) = (H1 / \ L2V H1 / \ P4 V M2 / \ L2 V M2 / \ P4) / \ (P3VH2) =

H1 / \ L2 / \ P3 V H1 / \ P4 / \ P3 V M2 / \ L2 / \ P3 V M2 / \ P4 / \ P3 V H1 / \ L2 / \ H2 V H1 / \ P4 / \ H2 V M2 / \ L2 / \ H2 V M2 / \ P4 / \ H2 = H1 / \ L2 / \ P3 V 0 V 0 V 0 V 0 V 0 V 0 V = H1 / \ L2 / \ P3

Наташа-1, Луда-2, Рита-3 и Маша-4.

Отговор: 1423

3. Обяснение на домашната работа.

Упражнение 1. ( Задача B8 от демонстрацията от 2007 г.)

За обозначаване на логическата операция "ИЛИ" в заявката се използва символът |, а за логическата операция "И" - &.

Задача 2 ( Задача B4 от демонстрацията от 2008 г.)

Преди началото на Турнира на четиримата феновете направиха следните предположения за своите идоли:

А) Макс печели, Бил втори;

Б) Бил е третият. Ник е първият;

В) Макс е последният, а първият е Джон.

Когато състезанието приключи, се оказа, че всеки един от феновете е бил прав само в една своя прогноза.

Какво място заеха Джон, Ник, Бил, Макс в турнира?

(В отговора избройте местата на участниците в ред без интервали в дадения ред на имената.)

Съвпад или логическо умножение (в теорията на множеството това е пресечна точка)

Съвпадът е сложен логически израз, който е верен, ако и само ако и двата прости израза са верни. Тази ситуация е възможна само в единичен случай, във всички останали случаи съюзът е неверен.

Обозначение: &, $ \ клин $, $ \ cdot $.

Таблица на истинността за съвпад

Снимка 1.

Свойства на конюнкция:

Ако поне един от подизразите на конюнкцията е фалшив за някакъв набор от стойности на променливи, тогава цялата конюнкция ще бъде фалшива за този набор от стойности.
Ако всички изрази за конюнкция са верни за някакъв набор от стойности на променливите, тогава цялата конюнкция също ще бъде вярна.
Значението на цялото съединение на сложен израз не зависи от реда на писане на подизразите, към които се прилага (както в математиката, умножението).

Дизюнкция или логическо добавяне (в теорията на множествата това е съюз)

Дизюнкцията е сложен логически израз, който почти винаги е верен, освен когато всички изрази са неверни.

Обозначение: +, $ \ vee $.

Таблица на истинността за дизюнкция

Фигура 2.

Свойства на дизюнкция:

Ако поне един от подизразите на дизюнкцията е вярно за някакъв набор от стойности на променливите, тогава цялата дизюнкция приема истинска стойност за този комплектподизрази.
Ако всички изрази от определен списък с дизюнкции са фалшиви за определен набор от стойности на променливи, тогава цялата дизюнкция на тези изрази също е фалшива.
Значението на цялата дизюнкция не зависи от реда на записване на подизразите (както в математиката - събиране).

Отрицание, логическо отрицание или инверсия (в теорията на множеството това е отрицание)

Отрицание - означава, че частицата НЕ или думата ГРЕШНО се добавя към оригиналния логически израз КАКВО и в резултат получаваме, че ако оригиналният израз е вярно, тогава отрицанието на оригиналния ще бъде невярно и обратно, ако първоначалният израз е фалшив, тогава неговото отрицание ще бъде вярно.

Обозначение: не $ A $, $ \ bar (A) $, $ ¬A $.

Таблица на истинността за инверсия

Фигура 3.

Свойства на отрицание:

„Двойно отрицание“ $ ¬¬A $ е следствие от съждението $ A $, тоест има тавтология във формалната логика и е равно на самата стойност в булевата логика.

Внушение или логично следствие

Импликацията е сложен логически израз, който е вярно във всички случаи, освен от истината следва невярно. Тоест, тази логическа операция свързва два прости логически израза, от които първият е условие ($ A $), а вторият ($ A $) е следствие от условието ($ A $).

Обозначения: $ \ до $, $ \ Стрелка надясно $.

Таблица на истинността за внушение

Фигура 4.

Импликационни свойства:

$ A \ до B = ¬A \ vee B $.
Импликацията $ A \ към B $ е невярна, ако $ A = 1 $ и $ B = 0 $.
Ако $ A = 0 $, тогава импликацията $ A \ към B $ е вярна за всяка стойност на $ B $ (лъжата може да последва истината).

Еквивалентност или логическа еквивалентност

Еквивалентността е сложен булев израз, който се оценява на равни стойности за $ A $ и $ B $.

Обозначения: $ \ leftrightarrow $, $ \ Leftrightarrow $, $ \ equiv $.

Таблица на истинността за еквивалентност

Фигура 5.

Еквивалентни свойства:

Еквивалентността е вярна при равни набори от стойности на променливите $ A $ и $ B $.
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 $

Строга дизюнкция или събиране по модул 2 (в теорията на множествата това е обединението на две множества без тяхното пресичане)

Силната дизюнкция е вярна, ако стойностите на аргумента не са равни.

За електрониката това означава, че внедряването на схеми е възможно с помощта на един типичен елемент (въпреки че това е скъп елемент).

Редът на изпълнение на логически операции в сложен логически израз

Инверсия (отрицание);
Съвпад (логическо умножение);
Дизюнкция и строга дизюнкция (логическо добавяне);
Внушение (последствие);
Еквивалентност (идентичност).

За да промените посочения ред на изпълнение на логически операции, трябва да използвате скоби.

Общи свойства

За набор от $ n $ булеви променливи има точно $ 2 ^ n $ различни стойности. Таблицата на истинността за булев израз от $ n $ променливи съдържа $ n + 1 $ колони и $ 2 ^ n $ реда.

СВОЙСТВА НА ЛОГИЧЕСКИТЕ ОПЕРАЦИИ

1. Нотация

1.1. Символи за логически връзки (операции):

а) отрицание(инверсия, логическо НЕ) се означава с ¬ (например ¬A);

б) съчетание(логическо умножение, логическо И) се обозначава / \
(например A / \ B) или & (например A & B);

° С) дизюнкция(логическо събиране, логическо ИЛИ) се означава с \ /
(например A \ / B);

д) следвайки(импликация) се означава с → (например A → B);

д) самоличностозначено с ≡ (например A ≡ B). Изразът A ≡ B е вярно, ако и само ако стойностите на A и B са еднакви (или и двете са верни, или и двете са неверни);

е) символ 1 се използва за означаване на истината (вярно твърдение); символ 0 - за обозначаване на лъжа (невярно твърдение).

1.2. Извикват се два булеви израза, съдържащи променливи равносилно на (еквивалентно), ако стойностите на тези изрази съвпадат за всякакви стойности на променливите. Така че изразите A → B и (¬A) \ / B са еквивалентни, но A / \ B и A \ / B не са (стойностите на изразите са различни, например за A = 1, B = 0).

1.3. Булев приоритет:инверсия (отрицание), конюнкция (логическо умножение), дизюнкция (логическо събиране), импликация (следване), тъждество. По този начин, ¬A \ / B \ / C \ / D означава същото като

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

Възможно е да се напише A \ / B \ / C вместо (A \ / B) \ / C. Същото важи и за съюза: възможно е да се напише A / \ B / \ C вместо (A / \ B) / \ ° С.

2. Свойства

Списъкът по-долу НЕ е предназначен да бъде пълен, но се надяваме, че е достатъчно представителен.

2.1. Общи свойства

За комплект от нбулевите променливи съществуват точно 2 нразлични стойности. Таблица на истинността за булев израз от нпроменливи съдържа n + 1колона и 2 нлинии.

2.2 Дизюнкция

Ако поне един от подизразите, към които се прилага дизюнкцията, е вярно за някакъв набор от стойности на променливите, тогава цялата дизюнкция е вярна и за този набор от стойности.
Ако всички изрази от някакъв списък са верни за някакъв набор от стойности на променливи, тогава дизюнкцията на тези изрази също е вярна.
Ако всички изрази от определен списък са фалшиви за определен набор от стойности на променливи, тогава дизюнкцията на тези изрази също е фалшива.
Значението на дизюнкцията е независимо от реда на изписване на подизразите, към които се прилага.

2.3. Съчетание

Ако поне един от подизразите, към които се прилага конюнкцията, е фалшив за някакъв набор от стойности на променливите, тогава цялата конюнкция също е невярна за този набор от стойности.
Ако всички изрази от определен списък са верни за определен набор от стойности на променливи, тогава връзката на тези изрази също е вярна.
Ако всички изрази от определен списък са фалшиви за определен набор от стойности на променливи, тогава конюнкцията на тези изрази също е фалшива.
Значението на съюза не зависи от реда на писане на подизразите, към които се прилага.

2.4. Прости дизюнкции и съюзи

Ние наричаме (за удобство) съюза простоако подизразите, към които се прилага връзката, са различни променливи или техните отрицания. По същия начин се нарича дизюнкция простоако подизразите, към които се прилага дизюнкцията, са различни променливи или техни отрицания.

Простата конюнкция приема стойността 1 (истина) на точно един набор от променливи стойности.
Една проста дизюнкция приема стойността 0 (false) на точно един набор от променливи стойности.

2.5. Внушение

Внушение А →Бе еквивалентно на дизюнкция (¬ А) \ / Б.Тази дизюнкция може да се запише така: ¬ A \ / B.
Внушение А →Бприема стойността 0 (false) само ако А = 1и B = 0.Ако A = 0,след това внушението А →Бвярно за всяка стойност Б.

За бързо търсенеинформация в Интернет използвайте заявки за търсене. Думата за търсене е набор ключови думи, свързани със знаци на логически операции И, ИЛИ, НЕ.

Приоритетът на операциите, ако няма специално предоставени скоби, е следният: първо НЕ, след това И, след това ИЛИ.

Трябва да разберете, че операцията И (едновременно изпълнение на условия) намалява обема на резултата, а операцията ИЛИ (изпълнение на поне едно от условията), напротив, увеличава обема.

Ако заявката съдържа фраза в кавички, системата ще търси точно същата фраза в нейната цялост.

1. Подреждане на заявките възходящо (низходящо)

Операцията И (&) обозначава едновременното присъствие на ключови думи в търсените документи и следователно намалява количеството намерена информация. Колкото повече ключови думи са свързани чрез операцията „И“, толкова по-малко информация се намира. И обратно, операцията "ИЛИ" (|) обозначава наличието на поне една ключова дума в търсените документи и следователно увеличава количеството намерена информация.

Пример 1.

Таблицата изброява заявките към сървъра за търсене. Подредете обозначенията на заявките във възходящ ред на броя страници, които търсачката ще намери за всяка заявка.

Решение:

Най-малкият брой страници ще бъде избран от заявката с най-много операции "И" (заявка D). Най-големият брой страници ще бъдат избрани от заявката с най-много операции "ИЛИ" (заявка B). Заявка А ще избере повече страници от заявка Б, т.к заявка А съдържа повече ключови думи, свързани с ИЛИ.

Отговор: GWAB

2. Броене, намерено на страниците с заявка

Този тип задачи обикновено се решават чрез система от уравнения. Ще предложа по-визуален и опростен начин.

Принципът на подбор на информация за заявки за търсенеДиаграмата на Ойлер-Вен (окръжностите на Ойлер) илюстрира добре. На диаграмата множествата са представени с пресичащи се кръгове. Операцията И (&) е пресечната точка на окръжности, а операцията ИЛИ (|) е обединението на окръжностите.

Например, нека означим с кръгове наборите от ябълки, круши, банани. За Apples & Pears & Bananas ще бъде избрана пресечната точка (общата част) на трите кръга:

По заявка Ябълки | Крушите ще бъдат избрани от обединението на два кръга:

Пример 2.

Таблицата показва заявките и броя на страниците, които сървърът за търсене е намерил за тези заявки в определен сегмент от Интернет:

Колко страници (в хиляди) ще бъдат намерени за шах?

Решение:

Нека начертаем диаграма на Ойлер-Вен. Решението на проблема се състои в преброяване на броя страници, съответстващи на всяка област, ограничена от линиите:

Заявката за шах и тенис съответства на средния регион (1000 хиляди страници), а заявката за тенис съответства на целия десен кръг (5500 хиляди страници).

Тогава десният "изрязан кръг" е 5500-1000 = 4500:

Заявка за шах | тенисът отговаря на двата кръга (7770), тогава левият "изрязан кръг" е 7770-5500 = 2270