Отнт. А. Ю. Босова Москва бином. Лаборатория знаний 10 класс Базовый уровень Учебник
 Скачать 6.18 Mb.
|
|
§20 Следовательно, множеством истинности этого предиката являются такие числа x, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и й, и й, и й, и й биты числа x нулевые, то высказывание x & 45 ≠ 0 будет лож- ным. Рассмотрим предикат K(x) = (x & 17 = 0). В числе 17 = 10001 й, й и й биты содержат нули, й и й — единицы. Побитовая конъюнкция 17 и x будет равна нулю, если в числе x й и й биты будут содержать нули. Множество истинности этого предиката — все x с нулями в мим битах. По условию задачи надо, чтобы ( ( ) ( ))& ( ) M x N x K x ∨ ∨ A(x) = 1. Запишем это выражение для рассмотренных множеств истинности А = Так как A ∪ A = U, примем A = (M ∪ N) ∩ Объединением множеств Ми являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством K будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, те. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А. Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной x: x & a ≠ 0, и кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 101100 2 . Действительно, единицы в нём стоят в тех, и только в тех битах, которые нужны для выполнения условия x & a ≠ Итак, требуемое число 101100 2 или 44 Приведите пример такого десятичного числа a, что для него x & a ≠ 0 при любом неотрицательном целом значении десятичной переменной x, но само число a не является минимально возмож- ным. Пример 5. Выясним, сколько решений имеет следующая система из двух уравнений ) & ( ) & ( ) = 1; ( ) & ( ) 1 2 2 3 3 4 1 2 2 3 x x x x x x y y y y & & ( ) = 1. 3 4 y y Глава 4. теория множеств и алгебра логики Рассмотрим первое уравнение →É x 2 ) & (x 2 →É x 3 ) & (x 3 →É x 4 ) = Конъюнкция истинна тогда и только тогда, когда истинны все образующие её высказывания. Следовательно, каждая из трёх входящих в конъюнкцию импликаций должна быть равна Начнем строить дерево решений, представив на нём значения переменных x 1 и x 2 при которых x 1 →É x 2 = Продолжим строить дерево решений. Значения переменной будем выбирать такими, чтобы при имеющихся x 2 импликация x 2 → x 3 оставалась истинной. То же самое проделаем для переменной На дереве видно, что рассматриваемое нами уравнение имеет 5 решений — 5 разных наборов значений логических переменных x 1 , x 2 , x 3 , x 4 , при которых выполняется равенство (x 1 →É x 2 ) & (x 2 →É x 3 ) & (x 3 →Éx 4 ) = Так как a →É b = a ∨ b, второе уравнение системы y 1 ∨ y 2 ) & ( y 2 ∨ y 3 ) & ( y 3 ∨ y 4 ) = можно преобразовать к виду →É y 2 ) & (y 2 →É y 3 ) & (y 3 →É y 4 ) = Следовательно, как и первое уравнение, это уравнение имеет 5 решений. Представим их в табличной форме 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 преобразование логических выражений §20 Решение исходной системы логических уравнений — это множество различных наборов значений логических переменных x 1 , x 2 , x 3 , x 4 , y 1 , y 2 , y 3 , y 4 таких, что при подстановке каждого из них в систему оба уравнения превращаются в истинные равен- ства. Начнём строить такие наборы или двоичные цепочки. Их началом может служить любой из пяти наборов — решений первого уравнения, а концом — любой из пяти наборов — решений второго уравнения. Например, на основе одного из решений первого уравнения можно построить следующие пять решений системы 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 Всего мы можем построить 5 · 5 = 25 решений системы. Вспомните, как называется теорема комбинаторики, которую мы применили для подсчёта количества решений системы Логические функции Значение любого логического выражения определяется значениями входящих в него логических переменных. Тем самым логическое выражение может рассматриваться как способ задания логической функции. Совокупность значений n аргументов удобно интерпретировать как строку нулей и единиц длины n. Существует ровно 2 n различных двоичных строк длины n. Так как на каждой такой строке некая функция может принимать значение 0 или 1, общее количество различных булевых функций от n аргументов равно 2 Для n = 2 существует 16 различных логических функций Глава 4. теория множеств и алгебра логики Рассмотрим их подробнее B F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 F 12 F 13 F 14 F 15 F 16 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 F 1 (A, B) = 0 — константа ложь F 2 (A, B) = A & B — конъюнкция F 3 (A, B) = A B → — отрицание импликации F 4 (A, B) = A — функция, равная первому аргументу F 5 (A, B) = B A → — отрицание обратной импликации F 6 (A, B) = B — функция, равная второму аргументу F 7 (A, B) = A ⊕ B — строгая дизъюнкция F 8 (A, B) = A ∨ B — дизъюнкция F 9 (A, B) = A ↓ B — стрелка Пирса (отрицание дизъюнкции, ИЛИ-НЕ); F 10 (A, B) = A ↔ B — эквиваленция; F 11 (A, B) = B — отрицание второго аргумента, B) = B → A — обратная импликация, B) = A — отрицание первого аргумента, B) = A → B — импликация, B) = A | B — штрих Шеффера (отрицание конъюнкции, И-НЕ); F 16 (A, B) = 1 — константа «истина». С увеличением числа аргументов количество логических функций резко возрастает. Так, для трёх переменных существует 256 различных логических функций Но изучать их все нет никакой необходимости. Дело в том, что путём преобразований функция любого количества переменных может быть выражена через функции только двух переменных. Более того, можно использовать не все, а лишь некоторые логические функции двух переменных. Например 1) F 2 и F 11 (конъюнкция и отрицание второго аргумента 2) F 8 и F 13 (дизъюнкция и отрицание первого аргумента 3) F 9 (стрелка Пирса, отрицание дизъюнкции 4) F 15 (штрих Шеффера, отрицание конъюнкции преобразование логических выражений §20 Два последних примера говорят о том, что при желании всю алгебру логики можно свести к одной функции Но чаще всего логические функции записываются в виде логического выражения через отрицание, конъюнкцию и дизъюнкцию составление логического выражения по таблице истинности и его упрощение Ранее мы выяснили, что для любого логического выражения можно составить таблицу истинности. Справедливо и обратное для всякой таблицы истинности можно составить соответствующее ей логическое выражение. Алгоритм составления логического выражения по таблице истинности достаточно прост. Для этого надо 1) отметить в таблице истинности наборы переменных, при которых значение логического выражения равно единице 2) для каждого отмеченного набора записать конъюнкцию всех переменных следующим образом если значение некоторой переменной в этом наборе равно 1, тов конъюнкцию включаем саму переменную, в противном случае — её отрицание 3) все полученные конъюнкции связать операциями дизъюнк- ции. Пример 6. Имеется следующая таблица истинности 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 Глава 4. теория множеств и алгебра логики После выполнения двух первых шагов алгоритма получим 1 0 1 A & B & C 0 1 1 1 A & B & СВ После выполнения третьего шага получаем логическое выражение Попробуем упростить полученное логическое выражение. Прежде всего, вынесем за скобки B — общий сомножитель, имеющийся у всех трёх слагаемых, затем — сомножитель A , а далее используем законы алгебры логики & B & C ∨ A & B & C ∨ A & B & C = = B & ( A & C ∨ A & СВ СВ В & ( A ∨ A & C ) = В & ( A ∨ A) & ( A ∨ C ) = = B & 1 & ( A ∨ C ) = B & ( A ∨ C ) = B & A C & самое ГЛаВное Способ определения истинности логического выражения путём построения его таблицы истинности становится неудобным при увеличении количества логических переменных, т. к. за счёт существенного увеличения числа строк таблицы становятся громоздкими. В таких случаях выполняются преобразования логических выражений в равносильные. Для этого используют свойства логических операций, которые иначе называют законами алгебры логики. Аналогичные законы имеют место ив алгебре множеств. Логическая функция может быть задана с помощью таблицы истинности или аналитически, тес помощью логического выражения. Для всякой таблицы истинности можно составить соответствующее ей логическое выражение. преобразование логических выражений §20 Вопросы и задания 1. Какие из рассмотренных законов алгебры логики аналогичны законам алгебры чисел, а какие нет 2. Докажите второй закон де Моргана с помощью таблиц истинности 3. Путём преобразования докажите равносильность следующих высказываний: а) ( ) ( ) A B B C & & ∨ и ( A & B ) ∨ ( A & C) ∨ (B & б) (A & В) ∨ ( ) A C & и (A & В) ∨ A ∨ C . 4. Упростите логические формулы: а) (A & B & C ) ∨ (A & B & C) ∨ (A & б) (A & В ∨ A & В & C ∨ В & C ∨ C) & ( C ∨ A & C ∨ A & В & C ). 5. Найдите X, если ( ) ( ) X A X A ∨ ∨ ∨ = B. 6. На числовой прямой даны два отрезка P = [10; 25] и Q = [20; 55]. Укажите наибольшую возможную длину такого отрезка A, что выражение (x ∈ A) É→ ((x ∈ P) ∨ (x ∈ Q)) истинно при любом значении переменной x. 7. Элементами множеств A, P и Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12} и Q = {2, 6, 12, 18, 24}. Известно, что выражение (x ∈ Q) → (( x A ∈ ) → ( x P ∈ )) истинно при любом значении переменной x. Определите наименьшее возможное количество элементов множества A. 8. На числовой прямой даны два отрезка Ми. Укажите наименьшую возможную длину такого отрезка A, что выражение (x ∈ М) → (((x ∈ N) & ( x A ∈ )) → → ( x M ∈ )) истинно при любом значении переменной x. 9. Для какого наименьшего неотрицательного целого десятичного числа A формула x & 25 ≠ 0 → (x & 17 = 0 → x & A ≠ 0) тождественно истинна, те. принимает значение 1 при любом неотрицательном целом значении десятичной переменной (Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел Глава 4. теория множеств и алгебра логики. Определите наибольшее натуральное десятичное число A, при котором выражение ((x &46= 0) ∨ (x & 18 = 0)) → → ((x & 115 ≠ 0) ∨ (x & A = 0)) тождественно истинно, те. принимает значение 1 при любом натуральном значении десятичной переменной x. (Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел. Сколько различных решений имеет система уравнений) x x x x x x x x 1 2 3 4 3 4 5 6 = 1; = 1. 2) x x x x x x x x x x x 1 2 3 4 3 4 5 6 5 6 7 = 1; = 1; = 1; = 1. 8 7 8 9 10 x x x x x 12. Сколько существует различных логических функций отче- тырёх переменных. По заданной таблице истинности составьте логические выражения для функций F 1 , F 2 А В F 1 F 2 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 14. По известным таблицам истинности запишите аналитическое представление импликации, эквиваленции и строгой дизъюнкции. Логические функции штрих Шеффера и стрелка Пирса названы так в честь математиков, исследовавших их свойства. Подготовьте краткую биографическую справку об одном из этих учёных. 16. По заданной таблице истинности составьте логические выражения для функций F 1 , F 2 Элементы схемотехники Логические схемы §21 А B C F 1 F 2 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 17. Запишите логическое выражение для логической функции F(A, В, С, равной 1 на наборах 011, 101, 110, 111. Попытайтесь упростить полученное выражение Элементы схемотехники. Логические схемы Любое устройство компьютера, выполняющее арифметические или логические операции, может рассматриваться как преобразователь двоичной информации значения входных переменных для него — последовательность нулей и единица значение выходной функции — новая двоичная последовательность. Необходимые преобразования информации в блоках компьютера производятся логическими устройствами двух типов комбинационными схемами и цифровыми автоматами с памятью. В комбинационной схеме набор выходных сигналов в любой момент времени полностью определяется набором входных сиг- налов. В цифровых автоматах с памятью набор выходных сигналов зависит не только от набора входных сигналов, но и от внутреннего состояния данного устройства. Такие устройства всегда имеют память Глава 4. теория множеств и алгебра логики схемотехника — научно-техническое направление, занимающееся проектированием, созданием и отладкой электронных схем и электронных устройств различного назначения Логические элементы Логический элемент — это устройство с n входами и одним выходом, которое преобразует входные двоичные сигналы в двоичный сигнал на выходе. Работу любого логического элемента математически удобно описать как логическую функцию, которая упорядоченному набору из нулей и единиц ставит в соответствие значение, также равное нулю или единице. В схемотехнике широко используются логические элементы, представленные в таблице Таблица Условные обозначения типовых логических элементов Наименование элемента Условное обозначение Название функции и её формула И Конъюнкция F = A & B ИЛИ Дизъюнкция F = A ∨ B НЕ Инверсия F = A И-НЕ Штрих Шеффера F = A & B ИЛИ-НЕ Стрелка Пирса = A ∨ B Элементы схемотехники Логические схемы §21 Логический элемент И (конъюнктор) реализует операцию логического умножения. Единица на выходе этого элемента появится тогда и только тогда, когда на всех входах будут единицы. Опишите подобным образом логические элементы ИЛИ (дизъюн- ктор), НЕ (инвертор, И-НЕ, ИЛИ-НЕ. Однотипность сигналов на входах и выходах позволяет подавать сигнал, вырабатываемый одним элементом, на вход другого элемента. Это позволяет из двухвходовых элементов собирать многовходовые элементы (риса также синтезировать произвольные комбинационные схемы, соединяя в цепочки отдельные логические элементы. рис. 4.7. Схема и обозначение четырёхвходового конъюнктора Пример. По заданной логической функции F(A, B) = = A & B ∨ A & B построим комбинационную схему (рис. 4.8). Построение начнём с логической операции, которая должна выполняться последней. В данном случае такой операцией является логическое сложение, следовательно, на выходе логической схемы должен быть дизъюнктор. На него сигналы подаются с двух конъюнкторов, на которые в свою очередь подаются один входной сигнал нормальный и один инвертированный (с инверторов). рис. 4.8. Комбинационная схема функции F(A, B) = A & B ∨ A & B Глава 4. теория множеств и алгебра логики сумматор Из отдельных логических элементов можно составить устройства, производящие арифметические операции над двоичными чис лами. Электронная логическая схема, выполняющая суммирование двоичных чисел, называется сумматором. рис. 4.9. Схема сложения двух разрядных двоичных чисел Вспомним схему сложения двух разрядных двоичных чисел (рис. Заметим, что при сложении цифр в м разряде мы должны сложить цифру a i числа a, цифру b i числа b, а также p i — перенос из (i – го разряда. В результате сложения должны получиться цифра результата s i и цифра переноса или 1) в следующий разряд Основываясь на этих рассуждениях, построим таблицу истинности для функций, которые в зависимости от цифр a i , b i и p i получают цифры s i и p i+1 Входы Выходы a i b i p i s i p i+1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 Элементы схемотехники Логические схемы §21 Вам известен алгоритм построения логического выражения по таблице истинности. Воспользуемся ими запишем выражение для функции p i+1 : p i+1 = a i & b i & p i ∨ a i & b i & p i ∨ a i & b i & p i ∨ a i & b i & Попытаемся упростить это выражение, воспользовавшись тем, что A ∨ A = A. Основываясь на этом законе, включим в имеющуюся дизъюнкцию ещё два слагаемых вида a i & b i & p i , причём на основании коммутативного и ассоциативного законов преобразуем полученное выражение к виду = ( a i & b i & p i ∨ a i & b i & p i )∨ (a i & b i & p i ∨ a i & b i & p i )∨ ∨ (a i & b i & p i ∨ a i & b i & p i ) = по законам дистрибутивности = = b i & p i &( a i ∨ a i )∨ a i & p i & ( b i ∨ b i )∨ a i & b i &( p i ∨ p i ) = = по закону исключённого третьего = b i & p i ∨ a i & p i ∨ a i & Полученное выражение означает, что функция p i+1 принимает значение 1 только для таких комбинаций входных переменных, когда хотя бы две переменные имеют единичные значения. Обратите внимание на то, что такой вывод можно сделать ив результате анализа таблицы истинности. По таблице истинности можем записать выражение для s i : s i = a i & b i & p i ∨ a i & b i & p i ∨ a i & b i & p i ∨ a i & b i & Его также можно попытаться преобразовать к более короткому виду. Но можно пойти другим путём и провести более тщательный анализ таблицы истинности для функции Из таблицы видно, что значение s i равно 1, если все входные сигналы равны 1. Этому соответствует выражение a i & b i & p i = Или значение s i равно 1, если в комбинации входных сигналов есть единственная 1, те. единица среди переменных есть, нонет одновременно двух переменных, значения которых равны 1. Это можно записать так b i ∨ p i ) & p i +1 = Следовательно s i можно записать так = (a i ∨ b i ∨ p i ) & p i +1 ∨ a i & b i & Можно попытаться самостоятельно провести преобразование логического выражения, полученного по таблице истинности для s i к итоговому виду. Но, чтобы убедиться в равносильности этих двух выражений, достаточно построить таблицу истинности для второго из них Глава 4. теория множеств и алгебра логики Полученные выражения позволяют реализовать одноразрядный двоичный сумматор схемой, представленной на рисунке рис 4.10. Схема одноразрядного сумматора Выразить и p i+1 можно и другими формулами. Например, самое короткое выражение для s i имеет вид s i = a i ⊕ b i ⊕ p i , что позволяет построить сумматор, используя другие логические элементы Сложение разрядных двоичных чисел осуществляется с помощью комбинации одноразрядных сумматоров (условное обозначение одноразрядных сумматоров приведено на рисунке слева триггер триггер (от англ. trigger — защёлка, спусковой крючок) — логический элемент, способный хранить один разряд двоичного числа. Триггер был изобретён в 1918 году МА. Бонч-Бруевичем. Элементы схемотехники Логические схемы §21 Михаил Александрович Бонч-Бруевич (1988–1940) — русский и советский радиотехник, основатель отечественной радиоламповой промышленности. Работал в области радиовещания и дальней связи на коротких волнах. В 1918 году МА. Бонч-Бруевич предложил схему переключающего устройства, имеющего два устойчивых рабочих состояния, под названием катодное реле. Это устройство впоследствии было названо триггером. Самый простой триггер — RS. Он состоит из двух логических элементов ИЛИ-НЕ, входы и выходы которых соединены кольцом выход первого соединён со входом второго и выход второго — со входом первого. Схема триггера представлена на рисунке Триггер имеет два входа S (от англ. set — установка) и R (от англ. reset — сброс) и два выхода Q (прямой) и Q (инверсный. Принцип его работы иллюстрирует следующая таблица истинности: режим работы триггера Входы состояние триггера Хранение предыдущего состояния Установка триггера в 1 0 1 Установка триггера в 0 1 0 0 Запрещённое состояние 1 Недопустимо Если на входы поступают сигналы R = 0 и S = 0, то триггер находится в режиме хранения — на выходах Q и Q сохраняются установленные ранее значения. Если на установочный вход S на короткое время поступает сигнал, то триггер переходит в состояние 1 и после того, как сигнал на входе S станет равен 0, триггер будет сохранять это состояние, те. будет хранить При подаче 1 на вход R триггер перейдет в состояние Подача на оба входа S и R логической единицы может привести к неоднозначному результату, поэтому такая комбинация входных сигналов запрещена. рис. 4.11. Логическая схема триггера Глава 4. теория множеств и алгебра логики Триггер используется для хранения информации в оперативной памяти компьютера, а также во внутренних регистрах процессора. Для хранения одного байта информации необходимо 8 триггеров, для килобайта — 8 · 1024 триггеров. Оперативная память современных компьютеров содержит миллионы триггеров. В целом же компьютер состоит из огромного числа логических устройств, образующих все его узлы и память. самое ГЛаВное Необходимые преобразования информации в блоках компьютера производятся логическими устройствами двух типов комбинационными схемами и цифровыми автоматами с памятью. В комбинационной схеме набор выходных сигналов в любой момент времени полностью определяется набором входных сигналов. Дискретный преобразователь, который выдаёт после обработки двоичных сигналов значение одной из логических операций, называется логическим элементом. Электронная логическая схема, выполняющая суммирование двоичных чисел, называется сумматором. В цифровых автоматах с памятью набор выходных сигналов зависит не только от набора входных сигналов, но и от внутреннего состояния данного устройства. Такие устройства всегда имеют память. Триггер — логический элемент, способный хранить один разряд двоичного числа. Оперативная память современных компьютеров содержит миллионы триггеров. В целом же компьютер состоит из огромного числа логических устройств, образующих все его узлы и память. Вопросы и задания 1. Что такое логический элемент Перечислите базовые логические элементы 2. По логическому выражению ( ) & & ( ) & A B C B A C ∨ ∨ требуется разработать логическое устройство. Какие логические элементы необходимы для его создания 3. Найдите значение выходного сигнала в приведенной схеме, если: а) Аи в) Аи б) Аи г) Аи Элементы схемотехники Логические схемы 4. Определите логическое выражение преобразования, выполняемого схемой 5. Постройте логические схемы для следующих функций F = ( & & ) & A B C B C A ∨ ∨ ; 2) F = B ∨ (C & A ) ∨ (A & B). 6. Постройте схему устройства, выполняющего преобразование информации в соответствии сданной таблицей истинности 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 Глава 4. теория множеств и алгебра логики 7. Пусть в некотором конкурсе вопрос о допуске того или иного участника к следующему туру решается тремя членами жюри A, В и С. Решение положительно тогда и только тогда, когда хотя бы двое членов жюри высказываются за допуск, причём среди них обязательно должен быть председатель жюри A. Необходимо разработать устройство для голосования, в котором каждый член жюри нажимает на одну из двух кнопок — За или Против, а результат голосования всех трёх членов жюри определяется потому, загорится (участник допускается) или нет участник не допускается) сигнальная лампочка. Составьте схему устройства, которое на выходе выдавало бы 1, если участник допускается к следующему туру, и 0, если не допускается 8. Существует 16 логических устройств, имеющих два входа (16 логических функций от двух переменных. Реализуйте их комбинационные схемы с помощью логических элементов И, ИЛИ, НЕ 9. Если при суммировании не учитывается признак переноса, то соответствующая логическая схема называется полусумматором. По имеющейся таблице истинности постройте логическую схему полусумматора. Входы Выходы a i b i s i p i+1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 10. Что такое триггер В чём основное отличие триггера от таких логических элементов, как инвертор или конъюнк- тор. Подготовьте краткую биографическую справку о нашем выдающемся соотечественнике МА. Бонч-Бруевиче. В чём заключается его вклад в развитие вычислительной техники Логические задачи и способы их решения Логические задачи и способы их решения Исходными данными в логических задачах являются высказывания. При этом высказывания и взаимосвязи между ними бывают так сложны, что разобраться в них без использования специальных методов бывает достаточно трудно метод рассуждений Основная идея этого метода состоит в том, чтобы последовательно анализировать всю информацию, имеющуюся в задаче, и делать на этой основе выводы. Пример 1. На одной улице стоят вряд дома, в каждом из них живёт по одному человеку. Их зовут Василий, Семён, Геннадий и Иван. Известно, что все они имеют разные профессии скрипач, столяр, охотники врач. Известно, что 1) столяр живёт правее охотника 2) врач живёт левее охотника 3) скрипач живёт с краю 4) скрипач живёт рядом с врачом 5) Семён не скрипачи не живёт рядом со скрипачом 6) Иван живёт рядом с охотником 7) Василий живёт правее врача 8) Василий живёт через дом от Ивана. Определим, кто где живёт. Изобразим дома прямоугольниками и пронумеруем их 2 3 Известно, что скрипач живёт с краю (3). Следовательно, он может жить в доме 1 или в доме 4. 1 2 3 4 скрипач? скрипач? Глава 4. теория множеств и алгебра логики Скрипач живёт рядом с врачом (4), те. врач может жить правее (дом 2) или левее (дом 3) скрипача 2 3 4 скрипач? врач? врач? скрипач? Но врач живёт левее охотника (2), следовательно, скрипач не может жить в доме 4, т. кв противном случае получится, что врач, живущий с ним рядом, живёт правее охотника, а это противоречит условию (2). Таким образом, скрипач живёт в доме 1, а врач — рядом с ним, в доме 2. 1 2 3 скрипач врач Так как врач живёт левее охотника (2), а столяр — правее охотника (1), то охотнику достаётся дома столяру — дом 4. 1 2 3 скрипач врач охотник столяр Так как Семён не скрипачи не живёт рядом со скрипачом (5), то он может жить в доме 3 или в доме 4. 1 2 3 скрипач врач охотник столяр Не Семён Не Семён Семён? Семён? Так как Иван живёт рядом с охотником (6), то он может жить в доме 2 или 4. 1 2 3 скрипач врач охотник столяр Не Семён Не Иван Не Семён Иван? Семён? Не Иван Семён? Иван Логические задачи и способы их решения §22 Так как Василий живёт правее врача (7), то он может жить в доме 3 или 4. 1 2 3 скрипач врач охотник столяр Не Семён Не Иван Не Василий Не Семён Иван? Не Василий Семён? Не Иван Василий? Семён? Иван? Василий? Подводим итоги с учётом того, что Василий живёт через дом от Ивана (8): в доме 1 может жить только Геннадий, в доме 2 — Иван, в доме 4 — Василий, в доме 3 — Семён. 1 2 3 скрипач врач охотник столяр Геннадий Иван Семён Василий Как видите, далеко не самая сложная задача потребовала достаточно серьёзных рассуждений. Этот метод, как правило, применяется для решения простых задач Задачи о рыцарях и лжецах Задачи о рыцарях и лжецах — это такой класс логических задач, в которых фигурируют персонажи рыцарь — человек, всегда говорящий правду лжец — человек, всегда говорящий ложь обычный человек — человек, который в одних ситуациях может говорить правду, а в других — лгать. Решение подобных задач сводится к перебору вариантов и исключению тех из них, которые приводят к противоречию. Пример 2. Двое жителей острова A и В разговаривали между собой в саду. Проходивший мимо незнакомец спросил у A: Вы рыцарь или лжец. Тот ответил, но так неразборчиво, что незнакомец не смог ничего понять. Тогда незнакомец спросил у В Что сказал А. «A сказал, что он лжец, — ответил В. Может ли незнакомец доверять ответу В Могли сказать, что он лжец Глава 4. теория множеств и алгебра логики Если A — рыцарь, то он скажет правду и сообщит, что он рыцарь. Если A — лжец, то он скроет правду и сообщит, что он ры- царь. Это значит, что В, утверждающий, что «A сказал, что он лжец заведомо лжёт; он — лжец. Определить же, кем является A, в данной ситуации невозможно. Пример 3. Рядом стоят два города город Лжецов (Ли город Правдивых (П. В городе Лжецов живут лжецы, а в городе Правдивых — правдивые люди. Лжецы всегда лгут, а правдивые всегда говорят правду. Лжецы и правдивые ходят друг к другу в гости. Вы попали в одни из городов, а в какой не знаете. Вам нужно у первого встречного, задав простой вопрос, узнать, в каком вы городе. Ответом на вопрос может быть только Да или «Нет». Нужен простой вопрос, ответ на который точно известен вашему респонденту. Например Вы находитесь в своём городе Надо задать вопрос и проанализировать варианты ответов с учетом того, кто их мог дать. Самостоятельно разберитесь с решением задачи, рассмотрев блок- схему на рис. рис 4.12. Блок-схема для анализа ответов Логические задачи и способы их решения §22 Пример 4. Перед нами три человека A, В и С. Один из них рыцарь, другой — лжец, третий — нормальный человек. При этом неизвестно, кто есть кто. Эти люди утверждают следующее 1) А я нормальный человек 2) В это правда 3) С я ненормальный человек. Кто такие А, В и С? Для решения этой задачи следует рассмотреть всевозможные варианты распределения ролей. Начнём с A. Он может быть рыцарем (Р, лжецом (Лили нормальным человеком (Н. Если А — рыцарь, то В может быть лжецом или нормальным человеком и т. д. Представим все варианты распределения ролей в таблице: А В С Р Л Н Р Н Л Л Р Н Л Н Р Н Р Л Н Л Р Проанализируем имеющиеся три утверждения, считая что роли между А, В и С распределены в соответствии с первой строкой таблицы. Итак, А утверждает, что он нормальный человек (1). Но, согласно первой строке таблицы, — он рыцарь, который не может так о себе сказать. Получено противоречие. Следовательно, первая строка не удовлетворяет условию задачи. Самостоятельно проанализируйте оставшиеся строки таблицы и дайте ответ на вопрос, поставленный в задаче Задачи на сопоставление табличный метод Многие логические задачи связаны с рассмотрением нескольких конечных множеств и связей между их элементами. Для решения таких задач зачастую прибегают к помощи таблиц или графов. Оттого, насколько удачно выбрана их структура, во многом зависит успешность решения задачи Глава 4. теория множеств и алгебра логики Пример 5. В летнем лагере водной палатке жили Алёша, Боря, Витя и Гриша. Все они разного возраста, учатся в разных классах (с го пой) и занимаются в разных кружках математическом, авиамодельном, шахматном и фотокружке. Выяснилось, что фотограф старше Гриши, Алёша старше Вити, а шахматист старше Алёши. В воскресенье Алёша с фотографом играли в тенниса Гриша в тоже время проиграл авиамоделисту в городки. Определим, кто в каком кружке занимается. В этой задаче речь идёт о высказывательной форме (предикате) вида Ученик x занимается в кружке y». Требуется определить такие значения x и y, чтобы высказывательная форма превратилась в истинное высказывание. Составим таблицу: y x Математика Авиамоде- лирование Шахматы Фотография Алёша Боря Витя Гриша Рассмотрим условия 1) фотограф старше Гриши 2) Алёша старше Вити, а шахматист старше Алёши; 3) в воскресенье Алёша с фотографом играли в тенниса Гриша в тоже время проиграл авиамоделисту в городки. Можем сделать выводы Гриша — не фотограф (1); шахматист не Алёша и не Витя (2); Алёша — не фотограф и не авиамоделист, Гриша — не фотограф и не авиамоделист (3). Отметим это в таблице: y x Математика Авиамоде- лирование Шахматы Фотография Алёша 0 0 0 Боря Витя 0 Гриша 0 0 Логические задачи и способы их решения §22 Имеющейся информации достаточно для того, чтобы утверждать, что Алёша занимается математикой, а Гриша — шахма- тами: y x Математика Авиамоде- лирование Шахматы Фотография Алёша 1 0 0 Боря Витя Гриша 0 1 Из того, что Гриша — шахматист и условий (1) и (2) можем расположить учеников по возрасту (в порядке возрастания Витя — Алёша — шахматист Гриша — фотограф. Следовательно, Боря — фотограф. Этого достаточно, чтобы окончательно заполнить таблицу: y x Математика Авиамоде- лирование Шахматы Фотография Алёша 1 0 0 Боря 0 0 Витя 1 0 Гриша 0 1 Итак, Алёша занимается в математическом кружке, Боря — в фотокружке, Витя — в авиамодельном кружке, Гриша — вшах- матном кружке. Самостоятельно сделайте вывод о том, кто из ребят в каком классе учится Использование таблиц истинности для решения логических задач Аппарат алгебры логики позволяет применять к широкому классу логических задач универсальные методы, основанные на формализации условий задачи Глава 4. теория множеств и алгебра логики Одним из таких методов является построение таблицы истинности по условию задачи и её анализ. Для этого следует 1) выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами 2) записать условие задачи на языке алгебры логики, соединив простые высказывания в составные с помощью логических операций 3) построить таблицу истинности для полученных логических выражений 4) выбрать решение — набор логических переменных (элементарных высказываний, при котором значения логических выражений соответствуют условиям задачи 5) убедиться, что полученное решение удовлетворяет всем условиям задачи. Пример 6. Три подразделения A, B, C торговой фирмы стремились получить по итогам года максимальную прибыль. Экономисты высказали следующие предположения 1) если A получит максимальную прибыль, то максимальную прибыль получат B и C; 2) A и C получат или не получат максимальную прибыль одновременно) необходимым условием получения максимальной прибыли подразделением является получение максимальной прибыли подразделением По завершении года оказалось, что одно из трёх предположений ложно, а остальные два истинны. Выясним, какие из названных подразделений получили максимальную прибыль. Рассмотрим элементарные высказывания A — «A получит максимальную прибыль B — «B получит максимальную прибыль C — «C получит максимальную прибыль». Запишем на языке алгебры логики прогнозы, высказанные экономистами 1) F 1 = A →É B & C; 2) F 2 = A & C ∨ A & C ; 3) F 3 = C →É Составим таблицу истинности для F 1 , F 2 , F 3 Логические задачи и способы их решения 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1 Теперь вспомним, что из трёх прогнозов F 1 , F 2 , F 3 одинока- зался ложным, а два других — истинными. Эта ситуация соответствует четвёртой строке таблицы. Таким образом, максимальную прибыль получили подразделения и C. 22.5. решение логических задач путём упрощения логических выражений Следующий формальный способ решения логических задач состоит в том, чтобы 1) выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами 2) записать условие задачи на языке алгебры логики, соединив простые высказывания в составные с помощью логических операций 3) составить единое логическое выражение, учитывающее все требования задачи 4) используя законы алгебры логики, упростить полученное выражение и вычислить его значение 5) выбрать решение — набор логических переменных (элементарных высказываний, при котором построенное логическое выражение является истинным 6) убедиться, что полученное решение удовлетворяет всем условиям задачи Глава 4. теория множеств и алгебра логики Пример 7. На вопрос, кто из трёх учащихся изучал логику, был получен ответ Если изучал первый, то изучали второй, но неверно, что если изучал третий, то изучали второй. Кто из учащихся изучал логику? Обозначим через A, B, C простые высказывания A = Первый ученик изучал логику B = Второй ученик изучал логику C = Третий ученик изучал логику». Из условия задачи следует истинность высказывания: ( )&( ) A B C B → → Упростим получившееся высказывание) ( )&( ) A B C B A B C B ( )& & A B C B A C B B C B & & & & = A C B & Получившееся высказывание будет истинным только в случае, если C — истина, аи ложь. А это значит, что логику изучал только третий ученика первый и второй не изучали. самое ГЛаВное Исходными данными в логических задачах являются высказывания. При этом высказывания и взаимосвязи между ними бывают так сложны, что разобраться в них без использования специальных методов бывает достаточно трудно. Основная идея метода рассуждений состоит в том, чтобы последовательно анализировать всю информацию, имеющуюся в задаче, и делать на этой основе выводы. Многие логические задачи связаны с рассмотрением нескольких конечных множеств и связей между их элементами. Для решения таких задач зачастую прибегают к помощи таблиц или графов. Оттого, насколько удачно выбрана их структура, во многом зависит успешность решения задачи. Аппарат алгебры логики позволяет применять к широкому классу логических задач универсальные методы, основанные на формализации условий задачи. К ним относятся методы 1) построения таблицы истинности по условию задачи и её анализ 2) составления и упрощения логического выражения Логические задачи и способы их решения §22 Вопросы и задания 1. Вы встретили 10 островитян, стоящих по кругу. Каждый из них произнёс фразу Следующие 4 человека, стоящие после меня почасовой стрелке, лжецы. Сколько среди них лжецов. Однажды некий путешественник гостил на острове рыцарей и лжецов. Там ему встретились два местных жителя. Путешественник спросил одного из них «Кто-нибудь из вас рыцарь Его вопрос не остался без ответа, ион узнал то, что хотел. Кем был островитянин, к которому путешественник обратился с вопросом, — рыцарем или лжецом Кем был другой островитянин 3. В старинном индийском храме восседали три богини Правда, Ложь и Мудрость. Правда говорит только правду, Ложь всегда лжёт, а Мудрость может сказать правду или солгать. Паломник, посетивший храм, спросил у богини слева Кто сидит рядом с тобой Правда, — ответила та. Тогда он спросил у средней Кто ты Мудрость, — отвечала она. Наконец он спросил у той, что справа Кто твоя соседка Ложь, — ответила богиня. И после этого паломник точно знал, кто есть кто. Определите, на каком месте сидит каждая из богинь 4. В симфонический оркестр приняли на работу трёх музыкантов Борисова, Сергеева и Васечкина, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. Каждый из музыкантов владеет двумя инструментами Известно, что) Сергеев — самый высокий) играющий на скрипке меньше ростом играющего на флейте) играющие на скрипке и флейте и Борисов любят пиццу) когда между альтистом и трубачом возникает ссора, Сергеев мирит их) Борисовне умеет играть ни на трубе, ни на гобое Выясните, на каких инструментах играет каждый из музыкантов. В педагогическом институте Аркадьева, Бабанова, Корсако- ва, Дашков, Ильин и Флёров преподают экономическую географию, английский язык, немецкий язык, историю, французский язык, математику Глава 4. теория множеств и алгебра логики Известно, что) преподаватель немецкого языка и преподаватель математики в студенческие годы занимались художественной гимнастикой) Ильин старше Флёрова, но стаж работы у него меньше, чему преподавателя экономической географии) будучи студентками, Аркадьева и Бабанова учились вместе водном университете. Все остальные окончили педагогический институт) Флёров — сын преподавателя французского языка, но студентом у него не был) преподаватель французского языка — самый старший из всех по возрасту и у него самый большой стаж работы. Он работает в педагогическом институте с тех пор, как окончил его. Преподаватели математики и истории — его бывшие студенты) Аркадьева старше преподавателя немецкого языка Кто какой предмет преподаёт? 6. На вопрос Кто из девушек собирается прийти надень рождения к Саше был получен уклончивый ответ Если Марина придёт надень рождения, то Надя тоже придёт, а Таня не придёт. Если Надя придёт, то Таня придёт в томи только в том случае, если не придёт Марина. Можно ли по этой информации точно установить, кто из девушек придёт к Саше, а кто нет 7. В бюро переводов приняли на работу троих сотрудников Диму, Сашу и Юру. Каждый из них знает ровно два иностранных языка из следующего набора немецкий, японский, шведский, китайский, французский и греческий Известно, что) ни Дима, ни Юра не знают японского) переводчик со шведского старше переводчика с немецкого) переводчик с китайского, переводчик с французского и Саша родом из одного города) переводчик с греческого, переводчик с немецкого и Юра учились втроём водном институте) Дима — самый молодой из всех троих, ион не знает греческого) Юра знает два европейских языка Логические задачи и способы их решения Укажите имена переводчика со шведского языка и переводчика с китайского языка 8. Ребята знали, что у четырёх подруг — Маши, Кати, Вали и Наташи — дни рождения приходятся на разное время года, ноне могли точно вспомнить, у кого на какое. Попытка вспомнить закончилась следующими утверждениями) у Вали день рождения зимой, ау Кати — летом) у Кати день рождения осенью, ау Маши — весной) весной празднует день рождения Наташа, а Валя отмечает его летом Позже выяснилось, что в каждом утверждении только одно из двух высказываний истинно. В какое время года день рождения у каждой из девушек 9. В санатории на берегу моря отдыхают отец O, мать М, сын S и две дочери D 1 и D 2 . До завтрака члены семьи часто купаются в море, причём известно, что если отец утром отправляется купаться, то с ним обязательно идут мать и сын если сын идет купаться, то его сестра D 1 отправляется вместе с ним вторая дочь D 2 купается тогда и только тогда, когда купается мать каждое утро купается по крайней мере один из родителей. Если в воскресенье утром купалась в море лишь одна из дочерей, то кто из членов семьи в это утро ходил на море. В нарушении правил обмена валюты подозреваются четыре работника банка — Антипов (А, Борисов (В, Цветков (Си Дмитриев (D). Известно, что) если A нарушил, то и B нарушил правила обмена валюты) если B нарушил, то и C нарушил или A не нарушал) если D не нарушал, то A нарушила не нарушал) если D нарушил, то и A нарушил Кто из подозреваемых нарушил правила обмена валюты? Дополнительные материалы к главе смотрите в авторской мастерской Глава 5 соВременные теХноЛоГИИ соЗданИя И обработКИ ИнформацИонныХ объеКтоВ соВременные ИнформацИонные теХноЛоГИИ Традиционно понятие технология трактуется как совокупность методов и инструментов для достижения желаемого результата в некоторой области человеческой деятельности. Информационные технологии (ИТ) — это совокупность методов, производственных процессов, программно-технических и лингвистических средств, объединённых с целью сбора, обработки, хранения, распространения, отображения и использования информации, представленной в цифровой форме. Синонимом этого понятия в русском языке выступает понятие «информационно-коммуникационные технологии (ИКТ). Используемые англоязычные аббревиатуры — IT, В отличие от технологий материальных и исходным материалом, и результатом применения информационных технологий всегда являются данные. Информационная технология — это процедура автоматизированного преобразования данных, формирования на их основе новых данных. Целью разработки и применения всех информационных технологий является максимальная автоматизация тех информационных процессов, которые ранее требовали ручного человеческого труда, зачастую рутинного, предполагавшего значительные временные затраты. Информационные технологии как отдельная отрасль деятельности получили наибольшее развитие с появлением и распространением компьютеров — универсальных автоматических средств обработки данных. Существует большое количество оснований для классификации информационных технологий. Их делят на индивидуальные текстовые документы §23 и коллективные, локальные и сетевые, технологии управления данными и процессами, защиты информации, разработки программного обеспечения и т. д. В курсе информатики основной школы информационные технологии были представлены (классифицированы) по видам обрабатываемой информации. Вы знакомы и, скорее всего, используете в учебной деятельности, технологии обработки текста и графической информации, мультимедийные технологии, электронные таблицы, базы данных. Знание базовых принципов обработки информации, владение наиболее распространенными технологиями необходимый навык для любого современного человека текстовые документы Виды текстовых документов В различных словарях можно найти следующие толкования понятия текст 1) упорядоченный набор слов, предназначенный для того, чтобы выразить некий смысл 2) всякая записанная речь (литературное произведение, сочинение, документ и т. па также часть, отрывок из них 3) последовательность языковых и иных знаков, образующая единое целое, служащее объектом изучения. С позиции информатики, текст — это последовательность знаков некоторого алфавита. Вам известно, что в памяти компьютера тексты представляются в двоичном коде 1) за каждым символом алфавита закрепляется определённый двоичный код 2) в двоичном коде представляется и информация о типе и размере используемого шрифта, положении строк, полей, отступов и прочая дополнительная ин- формация. Практически в любой профессиональной деятельности работник сталкивается с необходимостью подготовки текстовых документов 234 |