Методика проведения практикума-интенсива по решению задач еге по разделу основы алгебры логики


Бергер Полина Григорьевна, учитель информатики и ИКТ высшей квалификационной категории МБОУ «Гимназия № 96», г. Казань, Республика Татарстан
МЕТОДИКА ПРОВЕДЕНИЯ ПРАКТИКУМА-ИНТЕНСИВАПО РЕШЕНИЮ ЗАДАЧ ЕГЭ
ПО РАЗДЕЛУ «ОСНОВЫ АЛГЕБРЫ ЛОГИКИ»
Логика - это Бог мыслящих.
Л. Фейхтвангер.
Введение
Раздел «Основы алгебры логики» - один из сложнейших в курсе информатики. В КИМ ЕГЭ по информатике присутствуют задания базового и повышенного уровня сложности, для решения которых требуются глубокие теоретические познания и хорошо сформированные практические навыки. Выпускники, изучающие информатику на базовом уровне, при подготовке к ЕГЭ сталкиваются с объективными трудностями. Во-первых, в учебниках базового уровня эта тема рассматривается в усеченном варианте и поверхностно в рамках тем «Базы данных» и «Электронные таблицы». Во-вторых, сложность задач за последние годы резко возросла, о чем свидетельствует значительное снижение результатов сдачи ЕГЭ по информатике. Так, по данным Минобрнауки, средний тестовый балл понизился с 63,5 в 2013 г. до 57,2 в 2014 г. и 54 балла в 2015 г. С заданием №18 «Проверка истинности логического выражения» в 2015 году справились менее 15% выпускников. С заданием №23 «Системы логических уравнений» в 2015 году справились менее 5 % выпускников [1, 2].
В настоящее время в сети Интернет широко представлены материалы по подготовке к ЕГЭ по информатике, где дается обширный материал по теории, разбор типовых задач, а также предлагаются тесты on-line. Однако учащимся и учителям необходимы методические материалы, в которых в сжатой форме разбираются оптимальные методы решения и тематические подборки заданий с ключами для экспресс-подготовки к экзамену по информатике.
Данная методическая разработка предназначена для учителей, которые обучают информатике на базовом уровне и готовят учеников ЕГЭ по предмету. Она содержит методические рекомендации и дидактические материалы для проведения занятий в формате практикума-интенсива по разделу «Основы алгебры логики». Материалы для практикума будут интересны и полезны выпускникам при подготовке к экзаменам и при углубленном изучении раздела «Основы алгебры логики».
При подготовке учащихся к ЕГЭ по информатике учитель информатики зачастую сталкивается с их неумением самостоятельно решать задачи по разделу «Основы алгебры логики». В приведенной ниже таблице перечислены вопросы, стоящие перед учителем, и способы их разрешения.
Табл.1
Вопросы, стоящие перед учителем Ответы
Как эффективно организовать обобщающее повторение? Использовать домашнее задание накануне практикума:
а) выучить специально разработанный опорный конспект (см Приложение 1)
б) ознакомиться с демо-версией 2016 года и попробовать решить задания по теме «Основы алгебры логики» (см Приложение 3)
Как быстро актуализировать основные понятия по теме? Провести опрос с помощью облака понятий по теме «Алгебра логики» (см Приложение 2)
Как проконтролировать усвоение базовых знаний? Провести обучающий тест на этапе актуализации (см Приложение 4)
Как повысить плотность урока? Организовать контроль в высоком темпе, использовать мультимедийную презентацию для самопроверки теста, раздаточные материалы: опорный конспект, списки задач (Приложение 5 Проверочная работа)
Как научить решать задачи повышенной сложности по теме «Основы алгебры логики»? Отобрать задачи с низким уровнем решаемости на экзамене и разобрать некоторые из них (см Приложение 6 Практическая работа)
Как обучить старшеклассников решению задач ЕГЭ оптимальными методами? Решить задачу несколькими способами и обосновать выбор оптимального способа, удовлетворяющего критериям надежности, простоты и малых временных затрат.
Проанализировав ошибки учащихся при решении задач ЕГЭ по теме «Основы алгебры логики», мы обозначили следующие проблемы и наметили пути их решения.
Табл.2
Проблема Решение
Незнание свойств логических операций, законов алгебры логики Опорный конспект
Низкая скорость Тренировка в высоком темпе с контролем времени с повышением уровня сложности
Неумение алгоритмизировать свою деятельность Метод вопросов и ответов на каждом этапе решения задачи
Использование нерациональных методов решения Обучение выбору оптимального метода решения
Невнимательность при чтении условия задачи Визуализация (краткая запись)
Для решения этих проблем было принято решение разработать серию занятий в формате практикума-интенсива.
Методика подготовки и проведения практикума-интенсива [4]:
Учитель готовит опорный конспект по теме практикума.
Накануне каждый ученик получает опорный конспект и задание выучить ту его часть, которая пригодится на практикуме.
В начале практикума обязательна разминка – опрос по теории или разбор домашнего задания в высоком темпе, обучающий тест.
Практика в решении задач проводится с помощью специальной подборки задач, состоящей из 2-х вариантов задач различных типов возрастающей сложности.
Учитель заранее распечатывает 2 варианта работы: сначала задачу из 1-го варианта решают у доски, при этом обсуждаются эффективные приемы решения, затем учащимся предлагается самостоятельно решить подобную задачу из 2-го варианта.
Задание на дом содержит задачи повышенной сложности.
Алгоритм изучения условия задачи для определения проверяемых умений учащихся и выбора вспомогательных материалов
В тексте задачи идет речь о логической функции и приводится ее фрагмент или полная таблица истинности Эта задача проверяет умения строить и анализировать таблицы истинности логических выражений; понадобятся:
таблицы истинности и свойства основных логических операций;
алгоритм построения таблицы истинности;
законы алгебры логики;
(см Приложение 1)
В задаче говорится о запросах к поисковому серверу Эта задача проверяет умение составлять сложные запросы для поиска информации в сети Интернет; понадобятся:
свойства основных логических операций;
геометрический смысл дизъюнкции, конъюнкции (диаграммы Эйлера-Венна);
(см Приложение 1)
В задаче упоминаются числовые отрезки, множества, делимость чисел или побитовые конъюнкции Эта задача проверяет знание основных понятий и законов алгебры логики; понадобятся:
свойства основных логических операций;
законы алгебры логики;
геометрический смысл дизъюнкции, конъюнкции (диаграммы Эйлера-Венна);
(см Приложение 1)
В задаче предлагается определить количество решений системы логических уравнений Эта задача проверяет умение строить и преобразовывать логические выражения;
понадобятся:
свойства основных логических операций;
законы алгебры логики, (см Приложение 1);
основные методы решения систем логических уравнений; [6]
приемы решения типовых логических уравнений.
Обзор задач демо-версии ЕГЭ-2016 года по теме «Основы алгебры логики» (см. Приложение 2)
Тема «Составление таблицы истинности логической функции» (задание №2)
а)Преобразуем логическую функцию, применив сначала распределительный закон, а затем формулу исключения импликации:
(z)x xy = x ((z) y) = x (z y);
б) Анализируем приведенную таблицу истинности:
Чего меньше в столбце значений F: единиц или нулей? Единиц.
В каких случаях выражение x (z y) истинно? Когда х и импликация (z y) истинны. Значит, переменная, которая истинна при истинности F, - это х (переменная 3).
Замечаем, что что на наборе 101 х – истина, а F – ложь. Это означает, что (z y) – ложь, а это возможно только при z = 1 и y= 0.
Вывод: переменной 1 соответствует z, а переменной 2 – y.
Запишем ответ: zyx
Тема «Поиск информации в Интернете» (задание №17)
42995858636000Строим диаграммы Эйлера-Венна для 3-ёх множеств: Гомер, Илиада и Одиссея; нумеруем каждую область цифрами от 1 до 7 и выделяем искомую область;
Гомер & Илиада – пересечение этих множеств (5 + 7); Гомер & (Одиссея Илиада) – пересечение множества Гомер с объединением множеств Одиссея и Илиада (4 + 5 + 7); Гомер & Одиссея – их пересечение (4 + 7);
680085618490Составим систему уравнений, обозначив через Ni количество запросов соответствующей области:N5 + N7 =200
N4 + N5 + N7 = 470
N4 + N7 = 355
Найдем N4 из 2-го уравнения: 470 - N5 + N7 = 470 – 200 = 270;
Искомое количество запросов N7 = 355 – 270 = 85.
Тема «Проверка истинности логического выражения» (задание №18)
Введем обозначения: P = x & 25 0; Q = x & 17 0; A = x & A 0.
Перепишем исходную формулу в виде: P (Q A) = 1.
Преобразуем логическое выражение, используя формулу исключения имплиации: P Q A = 1.
А будет принимать наименьшее значение, когда выражение P Q будет ложно.
P Q = 0 при P = 1; Q = 0.
Переведем числа 25 и 17 в двоичную систему счисления, представив их в виде суммы степеней числа 2:
2510 = 16 + 8 + 1 = 24 + 23 + 20 = 110012;
1710 = 16 + 1 = 24 + 20 = 100012.
Составим таблицу истинности, где число x – разрядное слагаемое двоичной системы счисления из множества 1, 2, 4, 8, 16, 32:
x10 x2 P Q A
x & 11001 0 x & 10001 0 x & A 0
1 1 1 1 0
2 10 0 0 0
4 100 0 0 0
8 1000 1 0 1
16 10000 1 1 0
32 100000 0 0 0
В столбце A проставляем 1 в тех строках, где P = 1 и Q = 0.
Из таблицы видно, что А содержит двоичный разряд на позиции, соответствующей числу 8. Это искомое число.
Тема «Решение систем логических уравнений» (задание №23)
Для решения данной системы логических уравнений используем метод замены независимых переменных.
Обозначим: z1 = (x1 y1); z2 = (x2 y2); z3 = (x3 y3); z4 = (x4 y4); z5= (x5 y5); z6 = (x6 y6); z7 = (x7 y7); z8 = (x8 y8); z9 = (x9 y9);
Перепишем систему:
z1 z2
z2 z3
. . .
z8 z9
Заполним таблицу истинности, предположив сначала, что z1 = 0 (1- строка), а затем z1 = 1:
z1 z2 z3 z4 z5 z6 z7 z8 z9
0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1

Возвращаемся к замене. Zi – это эквиваленция. По свойству эквиваленции zi = 0 в 2-ух случаях, когда xi и yi различны, и zi = 1 также в 2-ух случаях, когда xi и yi имеют одинаковые значения.
Перемножив количество вариантов в первой строке, получим:
2*2*2*2*2*2*2*2*2 = 29 = 512;
Аналогично во второй строке таблицы получим еще 512 вариантов.
Итого в сумме 1024 решения.
Объем данной статьи не позволяет подробно разобрать решения всех приведенных задач. В своей работе мы опираемся на материалы популярного сайта К.Ю. Полякова[6], сайта distan-school.ru, а также на рекомендации по выбору оптимальных способов выполнения заданий ЕГЭ Чупина Н.А. [3]. Назовем лишь некоторые приемы и методы решения систем логических уравнений:
Метод рассуждений;
Метод независимой замены переменных;
Упрощение логических выражений;
Метод отображения;
Метод битовых цепочек.
Заключение и выводы
Данная методика в течение 2013-14 г., 2014-15, 2015 16 уч.г.г. была апробирована в классах физико-математического профиля МБОУ «Гимназия №96» Вахитовского района города Казани Республики Татарстан. Ее эффективность подтверждают следующие данные:
повысилось качество знаний по изучаемой теме (с 71% до 86%);
средний балл ЕГЭ в 2014 г. составил 74 балла;
Методика проведения практикумов-интенсивов по решению задач ЕГЭ демонстрировалась на мастер-классах для слушателей курсов повышения квалификации учителей информатики и заслужила положительные отзывы учителей-практиков. Данные мастер-классы проводились в рамках инновационной деятельности автора по теме «Применение современных педагогических технологий на уроках информатики по решению задач повышенной сложности» в рамках республиканской инновационной площадки «Актуальные проблемы реализации ФГОС общего образования» на базе Приволжского межрегионального центра повышения квалификации и профессиональной подготовки работников образования Казанского (Приволжского) Федерального университета.

Список источников и литературы
В.Р. Лещинер Методические рекомендации по некоторым аспектам совершенствования преподавания информатики и ИКТ (www.fipi.ru/sites/default/files/document/1410157306/informatika_i_ikt.pdf)
В.Р. Лещинер, М.А. Ройтберг Методические рекомендации для учителей, подготовленные на основе анализа типичных ошибок участников ЕГЭ 2015 года по ИНФОРМАТИКЕ и ИКТ, М, 2015 (http://fipi.ru/ege-i-gve-11/analiticheskie-i-metodicheskie-materialy )
Чупин Н.А. Подготовка к ЕГЭ по информатике: оптимальные способы выполнения заданий/ Н.А. Чупин. – Ростов н/Д: Феникс, 2013. – 105 [1] с.: ил. – (Абитуриент).
Бергер П.Г. Методика проведения практикума-интенсива по решению задач ЕГЭ по разделу «Основы информатики», сетевое издание «Образование: эффективность, качество, инновации», №»3, 2015 г. effektiko.ru/journal?p=7579
Материалы сайта http://distan-school.ruМатериалы сайта http://kpolyakov.spb.ru
Приложение 1: ОПОРНЫЙ КОНСПЕКТ ПО ТЕМЕ «АЛГЕБРА ЛОГИКИ»
Название логической операции Логическая связка Логический элемент Логическая функция Таблица истинности Диаграммы
Эйлера-Венна
ОТРИЦАНИЕ
(ИНВЕРСИЯ) НЕ Инвертор
21844062865
570865927100570865130810037465130810
607060-63500Z = X = X X Z=X
0 1
1 0
156845172720100330127635x
00x

ЛОГИЧЕСКОЕ СЛОЖЕНИЕ
(ДИЗЪЮНКЦИЯ) ИЛИ Дизъюнктор
2184405143500
412756159500593725137795001
450855715000
Z = X V Y X Y Z = X V Y
0 0 0
0 1 1
1 0 1
1 1 1

ЛОГИЧЕСКОЕ УМНОЖЕНИЕ
(КОНЪЮНКЦИЯ) И Конъюнктор
21844030480
5746757048500450851543050041275381000&
Z = X & Y =
= X Y X Y Z = X&Y
0 0 0
0 1 0
1 0 0
1 1 1

СЛЕДОВАНИЕ
(ИМПЛИКАЦИЯ) Если - то - Z = XY X Y Z = XY
0 0 1
0 1 1
1 0 0
1 1 1
709930280670y
00y
290830280670x
00x

РАВНОСИЛЬНОСТЬ
(ЭКВИВАЛЕНЦИЯ) Тогда и только тогда, когда - Z = X Y=
X Y=
=X~Y X Y Z=X Y
0 0 1
0 1 0
1 0 0
1 1 1
725170336550y
00y
260985341630x
00x

СЛОЖЕНИЕ ПО МОДУЛЮ 2
(ИСКЛЮЧАЮЩЕЕ ИЛИ) Либо-либо - Z= XY X Y Z= XY
0 0 0
0 1 1
1 0 1
1 1 0
260487306052x
00x
710927300426y
00y

логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)
логическое следование (импликация) А→В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно
эквивалентность АB равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1
ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ
Закон Для И Для ИЛИ
ДВОЙНОГО ОТРИЦАНИЯ

ЗАКОН ПРОТИВОРЕЧИЯ
ИСКЛЮЧЕНИЯ ТРЕТЬЕГО
ИСКЛЮЧЕНИЯ КОНСТАНТ A · 1 = A; A · 0 = 0 A + 0 = A; A + 1 = 1
ПОВТОРЕНИЯ A · A = A A + A = A
ПОГЛОЩЕНИЯ A · (A + B) = A A + A · B = A
ПЕРЕМЕСТИТЕЛЬНЫЙ A · B = B · A A + B = B + A
СОЧЕТАТЕЛЬНЫЙ A · (B · C) = (A · B) · C A + (B + C) = (A + B) + C
РАСПРЕДЕЛИТЕЛЬНЫЙ A + B · C = (A + B) · (A + C) A · (B + C) = A · B + A · C
ДЕ МОРГАНА
348043563500Законы склеивания:
Закон контрапозиции: (A B) = (B A).
Формула для исключения импликации: A B = А V B
Формула для исключения эквиваленции:A B = A & B V A & B = (A V B) & (A V B)
Формула для исключения сложения по модулю 2: A B = A & B V A & B = (A V B) & (A V B)
ПОСТРОЕНИЕ ТАБЛИЦ ИСТИННОСТИ
Приоритет логических операций в сложном логическом выражении:
инверсия;
конъюнкция;
дизъюнкция;
импликация;
эквивалентность.
Для изменения указанного порядка выполнения операций используются скобки.
Алгоритм построения таблиц истинности для сложных выражений:
Определить количество строк:КОЛИЧЕСТВО СТРОК = 2N + СТРОКА ДЛЯ ЗАГОЛОВКА, где N - количество простых высказываний.
Определить количество столбцов:КОЛИЧЕСТВО СТОЛБЦОВ = КОЛ-ВО ПЕРЕМЕННЫХ + КОЛ-ВО ЛОГИЧЕСКИХ ОПЕРАЦИЙ;
Определить количество переменных (простых выражений);
Определить количество логических операций и последовательность их выполнения.
Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
Количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти 2 8-6=22=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся).
-43815260985Логика
Алгебра логики
Высказывание
ИСТИНА
ЛОЖЬ
Логические связки
Дизъюнкция
Импликация
Конъюнкция
Эквиваленция
Исключающее ИЛИ
Таблица истинности
Логические операции
00Логика
Алгебра логики
Высказывание
ИСТИНА
ЛОЖЬ
Логические связки
Дизъюнкция
Импликация
Конъюнкция
Эквиваленция
Исключающее ИЛИ
Таблица истинности
Логические операции
Приложение 2: Облако понятий по разделу «Основы алгебры логики»
Приложение 3: Задания демо-версии ЕГЭ-2016 по разделу «Основы алгебры логики»
1. Тема «Составление таблицы истинности логической функции» (задание №2)

2. Тема «Поиск информации в Интернете» (задание №17)

3. Тема «Проверка истинности логического выражения» (задание №18)

4. Тема «Решение систем логических уравнений» (задание №23)

Ответы к заданиям демо-версии ЕГЭ-2016 г. по разделу «Основы алгебры логики»:
№ задания 2 17 18 23
Ответ zyx 85 8 1024
Приложение 4: Обучающий тест по теме «Основы алгебры логики»
I. Логические операции
а) Приведите в соответствие названия логических операций и логических связок:
№ Название логической операции Литера Логические связки
1 Отрицание (инверсия) А Либо … либо
2 Логическое сложение (дизъюнкция) Б И, А, НО
3 Логическое умножение (конъюнкция) В ИЛИ
4 Следование (импликация) Г Тогда и только тогда…, когда ...
5 Равносильность (эквиваленция) Д Если …, то …
6 Исключающее ИЛИ (сложение по модулю 2) Е НЕ
б) Свойства логических операций
Укажите название логической операции, для которой истинно утверждение и соответствующий ей знак:
1) Результат этой логической операции всегда равен нулю, кроме случая, когда все входные переменные истинны.
2) Результат этой логической операции всегда равен нулю, кроме случая, когда все входные переменные ложны.
3) Результат этой логической операции всегда равен единице, кроме случая, когда первый операнд равен единице, а второй равен нулю.
4) Результат этой одноместной логической операции всегда противоположен значению входной переменной.
5) Результат этой логической операции равен единице, если обе входные переменные имеют одинаковые значения.
6) Результат этой логической операции равен единице, если обе входные переменные имеют разные значения.
в) Расположите знаки логических операций через запятую в порядке уменьшения их приоритетаю
II. Таблицы истинности
а) Сколько строк (не считая заголовка) и столбцов будет в таблице истинности для логической функции?
F=(AB)V(AB)VC
б) Сколько единиц в результирующем столбце этой логической функции F?
в) Заполните таблицу истинности
A B A B AB AVB (AB) (AVB) AB BA AB AB
0 0 0 1 1 0 1 1 III. Законы алгебры логики
Заполните таблицу:
№ Название закона алгебры логики Формула
1 Закон двойного отрицания 2 Закон противоречия 3 Закон исключенного третьего 4 Переместительный закон 5 Сочетательный закон 6 Распределительный закон 7 Закон повторения (идемпотентности) 8 Законы исключения констант 9 Законы де Моргана 10 Законы поглощения 11 Законы склеивания 12 Закон контрапозиции 13 Формула исключения импликации 14 Формулы исключения эквивалентности 15 Формулы исключения сложения по модулю 2 IV. При каких значениях логических переменных K,L,M,N верно логическое равенство?
(KVM)(MVLVN)=0
V. Сколько различных решений имеет логическое уравнение?
((JJ)VKVL)M=1
VI. Системы логических уравнений
Определить количество решений системы логических уравнений и перечислите наборы логических переменных X1..X5:
(X1X2)=1
(X2X3)=1
……………
(X4X5)=1
Ответы к обучающему тесту:
I. Логические операции
а) Логические операции и логические связки
№ лог. операции 1 2 3 4 5 6
Литера Е В Б Д Г А
б) Свойства логических операций
1) Конъюнкция (&, , · )
2) Дизъюнкция (V, +)
3) Импликация ()
4) Инверсия ()
5) Эквиваленция (, , )
6) Исключающее ИЛИ ()
в) В порядке уменьшения приоритета
, , V, , ,
II. Таблица истинности
а) 8 и 10
б) 6
в)
A B A B AB AVB (AB) (AVB) AB BA AB AB
0 0 1 1 0 0 1 1 1 1 1 0
0 1 1 0 0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0 0 1 0 1
1 1 0 0 1 1 0 0 1 1 1 0
III. Законы алгебры логики
Название закона алгебры логики Формула
1 Закон двойного отрицания
2 Закон противоречия
3 Закон исключенного третьего
4 Переместительный закон A · B = B · A;A + B = B + A
5 Сочетательный закон A · (B · C) = (A · B) · C;A + (B + C) = (A + B) + C
6 Распределительный закон A + B · C = (A + B) · (A + C);A · (B + C) = A · B + A · C
7 Закон повторения (идемпотентности) A · A = A;A + A = A
8 Законы исключения констант A · 1 = A; A · 0 = 0; A + 0 = A; A + 1 = 1
9 Законы де Моргана ;
10 Законы поглощения A · (A + B) = A;A + A · B = A
11 Законы склеивания A · B + А · B = B;(A + B) · (А + B) = B
12 Закон контрапозиции (A B) = (B A).
13 Формула исключения импликации A B = A + B
14 Формулы исключения эквивалентности A B = A · B + A · B = (A + B) · (A + B)
15 Формулы исключения сложения по модулю 2 A B = A · B + A · B = (A + B) · (A + B)
IV. 1010
V. 6
VI. 6 решений: 00000, 00001, 00011, 00111, 01111, 11111.

Приложение 5: Проверочная работа по теме «Алгебра логики»
В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:
Запрос Количество страниц (тыс.)
Слобода 515
Пилигрим 175
Пилигрим & Равелин 105
Слобода & Равелин 70
Слобода & Пилигрим 0
Слобода | Равелин | Пилигрим 765
Сколько страниц (в тысячах) будет найдено по запросу
Равелин
Дан фрагмент таблицы истинности выражения F.
x1 x2 x3 x4 x5 x6 x7 F
0 1 0 1 1 1 1 1
1 0 1 0 1 1 0 0
0 1 0 1 1 0 1 1
Какое выражение соответствует F?
1) x1 ¬x2 x3 ¬x4 x5 x6 ¬x7
2) ¬x1 x2 ¬x3 x4 ¬x5 ¬x6 x7
3) ¬x1 x2 ¬x3 x4 x5 x6 x7
4) x1 ¬x2 x3 ¬x4 ¬x5 ¬x6 ¬x7
Дано логическое выражение, зависящее от 7 логических переменных:
X1 ¬X2 X3 ¬X4 ¬X5 ¬X6 ¬X7
Сколько существует различных наборов значений переменных, при которых выражение ложно?
1) 1 2) 23) 1274) 128
Дано логическое выражение, зависящее от 5 логических переменных:
(¬x1 ¬x2 ¬x3 x4 x5) (x1 x2 x3 ¬x4 ¬x5)
Сколько существует различных наборов значений переменных, при которых выражение истинно?
1) 02) 30 3) 31 4) 32
Сколько различных решений имеет уравнение
((K ∨ L) → (L ∧ M ∧ N)) = 0
6) Сколько существует различных наборов значений логических переменных x1, x2, ... x10, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∧ ¬x2) ∨ (¬x1 ∧ x2) ∨ (x3 ∧ x4) ∨ (¬x3 ∧ ¬x4) = 1
(x3 ∧ ¬x4) ∨ (¬x3 ∧ x4) ∨ (x5 ∧ x6) ∨ (¬x5 ∧ ¬x6) = 1
...
(x7 ∧ ¬x8) ∨ (¬x7 ∧ x8) ∨ (x9 ∧ x10) ∨ (¬x9 ∧ ¬x10) = 1
Ключи к проверочной работе:
№ 1 2 3 4 5 6
Ответ 250 2 1 2 10 192
Ключи к практической работе (см Приложение 6)
№ Вариант 1 № Вариант 2
1 YZX 1 YXZ
2 66 2 233
3 32 3 120
4 32 4 68
5 11 5 11
6 1849 6 231
7 162 7 730
Приложение 6. Практическая работа по решению задач по разделу «Основы алгебры логики»
Вариант 1 Вариант 2
1. Логическая функция F задаётся выражением (¬x y z) (¬x ¬z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
? ? ? F
0 0 0 1
1 0 0 1
1 1 0 1
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы. 1. Логическая функция F задаётся выражением (¬x z) (¬x ¬y ¬z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
? ? ? F
0 0 0 1
0 0 1 1
1 0 1 1
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы.
2. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:
Запрос Количество страниц (тыс.)
(макаки | павианы & гиббоны) & шимпанзе 154
шимпанзе & павианы & гиббоны 120
шимпанзе & макаки & павианы & гиббоны 32
Сколько страниц (в тысячах) будет найдено по запросу
макаки & шимпанзе 2. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:
Запрос Количество страниц (тыс.)
Англия & (Уэльс & Шотландия | Ирландия) 450
Англия & Ирландия 304
Англия & Уэльс & Шотландия & Ирландия 87
Сколько страниц (в тысячах) будет найдено по запросу
Англия & Уэльс & Шотландия?

3. Пусть P – множество всех 8-битовых цепочек, начинающихся с 11, Q – множество всех 8-битовых цепочек, оканчивающихся на 0, а A – некоторое множество произвольных 8-битовых цепочек. Сколько элементов содержит минимальное множество A, при котором для любой 8-битовой цепочки x истинно выражение
¬ (x A) (¬(x P) (x Q)) ? 3. Пусть P – множество всех 8-битовых цепочек, начинающихся с 1, Q – множество всех 8-битовых цепочек, оканчивающихся на 1011 , а A – некоторое множество произвольных 8-битовых цепочек. Сколько элементов содержит минимальное множество A, при котором для любой 8-битовой цепочки x истинно выражение
( (x P) ¬ (x Q)) (x A) ?
4. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение
(X & 35 0) ((X & 31 = 0) (X & A 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
4. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение
(X & 76 0) ((X & 10 = 0) (X & A 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
5. Сколько различных решений имеет система уравнений?
(x1 x2)(x2 x3)(x3 x4)(x4 x5) = 1
(у1 у2)(у2 у3)(у3 у4)(у4 у5) = 1
x1 у1 = 1 5. Сколько различных решений имеет система уравнений?
(x1 x2) (x2 x3) (x3 x4) (x4 x5)=1
(у1 у2) (у2 у3) (у3 у4) (у4 у5)=1
x5 у5 = 0
6. Сколько различных решений имеет система уравнений?
(((((x1x2)x3)x4)x5)x6)=1
(((((y1y2)y3)y4)y5)y6)=1 6. Сколько различных решений имеет система уравнений?
((((x1x2)x3)x4) x5) = 1
((((y1y2)y3)y4) y5) = 0
7. Сколько различных решений имеет система логических уравнений
(x1 y1) (x2 y2)
(x2 y2) (x3 y3)
...
(x7 y7) (x8 y8) 7. Сколько различных решений имеет система логических уравнений
(x1 y1) (x2 y2)
(x2 y2) (x3 y3)
...
(x5 y5) (x6 y6)

Приложенные файлы


Добавить комментарий