8-Lesson №8

    Обоснование истинности или ложности высказываний даётся теми науками, к сфере которых эти высказывания относятся. Алгебра логики отвлекается от смысловой содержательности высказываний. Её интересует только, истинно или ложно данное высказывание.

    В алгебре логики высказывания обозначают буквами и называют логическими переменными. При этом если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей {А = 1), а если ложно — нулём (В = 0). 0 и 1, обозначающие значения логических переменных, называются логическими значениями.

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

    Оперируя логическими переменными, которые могут быть равны только 0 или 1, алгебра логики позволяет свести обработку информации к операциям с двоичными данными. Именно аппарат алгебры логики положен в основу компьютерных устройств хранения и обработки данных. С применением элементов алгебры логики вы будете встречаться и во многих других разделах информатики.

    Операция НЕ часто называется отрицанием или инверсией. В алгебре логики всего два возможных значения (0 и 1), поэтому логическое отрицание — это переход от одного значения к другому: от 1 к 0 или наоборот. Если высказывание А истинно, то НЕ А ложно, и наоборот.

Используя дополнительные источники, переведите на русский язык слово inverse, от которого произошло слово «инверсия».

    Операцию НЕ обозначают чертой сверху, например: Ā. В школьном алгоритмическом языке эта операция обозначается словом не, а в языке программирования Паскаль — английским словом not.

Используя дополнительные источники, найдите другие обозначения операции НЕ.

    Операцию НЕ можно задать в виде таблицы (рис. 2.1).

Эта таблица состоит из двух частей: слева перечисляются все возможные значения исходной величины (их всего два — 0 и 1), а в последнем столбце записывают результат выполнения логической операции для каждого из этих вариантов. Такая таблица называется таблицей истинности логической операции. Таблица истинности задаёт логическую функцию.

Логическая функция — это правило преобразования входных логических значений в логическое значение-результат.

Используя таблицу истинности на рис. 2.1, определите, как можно упростить выражение не(не А). Рассмотрите оба варианта: когда А = 0 и когда А = 1. Сделайте вывод.

    Из двух простых высказываний А и B (например, А = Сейчас идёт дождь, В = Форточка открыта) можно составить сложное высказывание А и B. Высказывание А и В истинно в том и только в том случае, когда оба высказывания, А и Б, истинны одновременно.

    Для понимания операции И можно представить себе простую схему, в которой для включения лампочки используются два выключателя, соединённых последовательно (рис. 2.2).

    Чтобы лампочка загорелась, нужно обязательно включить оба выключателя. Вместе с тем, чтобы выключить лампочку, достаточно выключить любой из них.

    Операция И (в отличие от НЕ) выполняется с двумя логическими значениями. В алгоритмическом языке системы КуМир операция И обозначается словом и, а в Паскале — словом and.

Используя дополнительные источники, найдите другие обозначения операции И.

    В таблице истинности операции И будет уже не один столбец с исходными данными, а два, мы обозначим исходные данные как А и В. Число строк также выросло, с 2 до 4, поскольку с помощью 2 бит можно записать 4 разных комбинации значений двух переменных: 00, 01, 10 и 11. Как следует из определения операции И, в последнем столбце будет всего одна единица, для варианта А = В = 1 (оба высказывания, А и В, истинны одновременно) — рис. 2.3.

Из значений А и В в каждой строке этой таблицы составьте двоичное число и запишите его в десятичной системе счисления. Почему строки в таблице расположены именно так?

    Легко проверить, что этот результат можно получить «обычным» умножением А на B, поэтому операцию И называют логическим умножением. Она часто обозначается знаком умножения (точкой): А • B.

    С точки зрения обычной математики, эта операция выбирает наименьшее из исходных значений. Математики используют ещё одно название операции И — конъюнкция.

Используя дополнительные источники, выясните, от какого слова произошло слово «конъюнкция» и что оно обозначает.

    С помощью таблицы истинности можно упрощать логические выражения. Например, рассмотрим выражение А и 1. По таблице истинности на рис. 2.3 получаем:

при А = 0:     А и 1 = 0 и 1 = 0

при А = 1:     А и 1 = 1 и 1 = 1.

    Можно заметить, что в любом случае результат совпадает с А, поэтому А и 1 = А.

Используя таблицу истинности операции И, упростите выражения: а) А и 0; б) А и А; в) А и (не А).

    Высказывание А или В (например, «Сейчас идет дождь или форточка открыта») истинно тогда, когда истинно хотя бы одно из входящих в него высказываний или оба одновременно.

    В алгоритмическом языке операция ИЛИ обозначается словом или, а в языке Паскаль — английским словом or.

Используя дополнительные источники, найдите другие обозначения операции ИЛИ.

    Для понимания операции ИЛИ можно представить себе схему с двумя выключателями, соединёнными параллельно (рис. 2.4).

    Чтобы лампочка загорелась, достаточно включить хотя бы один из выключателей. Чтобы выключить лампочку, необходимо обязательно выключить оба. В таблице истинности будет только один ноль — для варианта А = В = 0 (рис. 2.5).

    Операцию ИЛИ называют логическим сложением, потому что она похожа на обычное математическое сложение. Поэтому она часто обозначается знаком сложения: А+В. Единственное отличие — в последней строке таблицы истинности: в математике 1+1 равно 2, а в алгебре логики — единице.

    Можно считать, что в результате применения операции ИЛИ из исходных значений выбирается наибольшее. Другое название этой операции — дизъюнкция.

Используя дополнительные источники, выясните, от какого слова произошло слово «дизъюнкция» и что оно обозначает.

Запишите в тетради ответы на следующие вопросы.

— Сколько строк в таблице истинности функции с двумя переменными?

— Сколько существует возможных вариантов распределения нулей и единиц в последнем столбце?

— Сколько можно придумать различных логических функций с двумя переменными?

    Используя таблицу истинности операции ИЛИ, упростите выражения:

а) А или 0;     б) А или 1;     в) А или А;    г) А или (не А).

    Операции конъюнкция и дизъюнкция тесно связаны с такими известными вам операциями над множествами, как пересечение и объединение.

    Пересечением двух множеств X и Y называется множество их общих элементов (рис. 2.1).

    Объединением двух множеств X и У называется множество, состоящее из всех элементов этих множеств и не содержащее никаких других элементов.

    Пусть X — множество веб-страниц, на которых встречается слово «крейсер»; Y — множество веб-страниц, на которых встречается слово «линкор».

    Пересечением множеств X и У будет множество страниц, на которых встречаются оба эти слова одновременно. Другими словами, X П Y — это множество истинности высказывательной формы «На веб-странице встречается слово “крейсер” и слово “линкор”», представляющей собой конъюнкцию высказывательных форм «На веб-странице встречается слово “крейсер”», «На веб-странице встречается слово “линкор”».

    Объединением множеств X и У будет множество страниц, на которых встречается хотя бы одно из этих слов, а также оба эти слова одновременно. Другими словами, X U Y — это множество истинности высказывательной формы «На веб-странице встречается слово “крейсер” или слово “линкор”», представляющей собой дизъюнкцию высказывательных форм «На веб-странице встречается слово “крейсер”», «На веб-странице встречается слово “линкор”».

    Логическими операциями мы пользуемся при поиске информации в сети Интернет. При решении задач, связанных с количественными характеристиками результатов поиска, используются операции над множествами.

Пример 1

    В языке запросов поискового сервера для обозначения логической операции ИЛИ используется символ «|», а для обозначения логической операции И — символ «&».

    В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

    Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Какое количество страниц (в тысячах) будет найдено по запросу

крейсер & линкор ?

Решение

Изобразим условие задачи графически:

    Здесь множества страниц, найденных по соответствующим запросам, обозначены двумя пересекающимися кругами; непере- секающиеся области на полученной схеме обозначены цифрами 1, 2, 3.

    По схеме видно, что количество элементов, образующих множество К, равно сумме элементов, входящих в области 1 и 2; количество элементов, образующих множество Л, равно сумме элементов, входящих в области 2 и 3; количество элементов, образующих множество К ∪ Л, равно сумме элементов областей 1, 2 и 3. Наша задача — найти количество элементов, входящих в область 2.

    Дополним этой информацией исходную таблицу.

    Если просто сложить мощности множеств К и Л, то мы получим:

(N₁ + N₂) + (N₂ + N₃) = (N₁ + N₂ + N₃) + N₂.

    Следовательно:

N₂ = (N₁ + N₂) + (N₂+ N₃) — (N₁ + N₂ + N₃) = 4800 + 4500 — 7000 = 2300.

Ответ: по запросу крейсер & линкор будет найдено 2300 страниц (в тысячах).

Самостоятельно найдите количество элементов, входящих: в область 1; в область 3. Какие запросы будут соответствовать каждой из этих областей?

Выполнить домашнюю работу

Выполнить классную работу