Получите профессию

Копирайтер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Инфоурок › Информатика ›Научные работы›ВКР "Раздел "Основы логики и логические основы компьютера" в ЕГЭ по информатике"

Раздел «Основы логики и логические основы компьютера» в ЕГЭ по информатике

Скачать материал

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ»

(ГОУ ВПО ДВГГУ)

 

Кафедра информатики и информационных технологий

 

 

Н.В. Ганжусь, студентка 254 гр.

 

 

РАЗДЕЛ «ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА»

В ЕГЭ ПО ИНФОРМАТИКЕ

 

выпускная квалификационная работа

по специальности 030100 – информатика

 

 

Оценка___________________                                    Научный руководитель:

Дата защиты___ __________2011 г.                           старший преподаватель    

Протокол № ______                                                     кафедры информатики и ИТ

Председатель ГАК ____________                               ________ Пишкова Н.Е.

 

 

Хабаровск 2011

ОГЛАВЛЕНИЕ

Введение........................................................................................................ 3

Глава 1. Основные сведения о ЕГЭ по информатике................................ 7

1.1. Инструкция (структура) экзаменационной работы по информатике....... 7

1.2. Содержание ЕГЭ по информатике........................................................... 9

1.3. Кодификатор по информатике................................................................. 15

Глава 2. Теоретические основы раздела «Основы логики и

логические основы компьютера» ............................................................... 19

2.1. Формы мышления................................................................................... 19

2.2. Алгебра логики........................................................................................ 23

2.2.1. Логические операции............................................................................ 23

2.2.2. Логические выражения и функции....................................................... 25

2.2.3. Логические законы................................................................................ 29

2.3. Логические основы устройства компьютера........................................... 31

2.3.1. Базовые логические элементы.............................................................. 31

2.3.2. Сумматор двоичных чисел.................................................................... 34

2.3.3. Триггер.................................................................................................. 38

Глава 3. Учебно-методические материалы для подготовки к ЕГЭ по

разделу «Основы логики и логические основы компьютера»................. 40

3.1. Анализ заданий ЕГЭ, представленных в различных учебно-методических пособиях, сборниках....................................................................................................... 40

3.2. Электронный образовательный ресурс «Способы решения логических задач» - как средство при подготовке к ЕГЭ...................................................................... 56

3.3. Разбор заданий ЕГЭ................................................................................. 58

Заключение................................................................................................... 84

Список литературы...................................................................................... 85

Приложения.................................................................................................. 87

 

 

ВВЕДЕНИЕ

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

Единый Государственный Экзамен (ЕГЭ) – основная форма государственной аттестации выпускников школ Российской Федерации.

Подготовка к ЕГЭ по информатике стала актуальной с введением этого предмета в перечень экзаменов по выбору, сдаваемых по окончанию средней общеобразовательной школы и необходимых при поступлении в некоторые ВУЗы, в том числе и гуманитарные.

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

Экзамен проверяет знания и умения выпускников на различных уровнях (базовый, профильный, высокий).

Содержание экзаменационного материала включает основные темы курса информатики и информационных технологий, объединенные в тематические блоки. Одним из них является раздел «Основы логики». Данному разделу и подготовке к ЕГЭ по нему посвящена выпускная квалификационная работа «Раздел «Основы логики и логические основы компьютера» в ЕГЭ по информатике».

Таким образом, становится актуальным  вопрос подготовки школьников выпускных классов к сдаче Единого Государственного Экзамена по информатике. Кроме того, разделу «Основы логики и логические основы компьютера» уделяется недостаточное внимание, хотя материал несет в себе большую методическую и познавательную нагрузку. Данный раздел неразрывно связан с такими разделами как «Алгоритмизация и программирование», «Моделирование и формализация», «Базы данных». Практические задания по разделу одни из сложных в курсе информатики, не все учащиеся их усваивают и понимают, что в дальнейшем приводит к проблемам при изучении других тем, а также при сдаче ЕГЭ по информатике.

Выполнение ЕГЭ по данному разделу требует от учащихся следующих знаний и умений:

· знать основные элементы математической логики;

· создавать и  преобразовывать логические выражения;

· формировать для логической функции таблицу истинности и логическую схему;

· решать логические задачи.

Объектом исследования является процесс подготовки к ЕГЭ по информатике по теме «Основы логики и  логические основы компьютера».

Предмет исследования – организация подбора учебно-методических материалов по теме «Основы логики и  логические основы компьютера», для подготовки к сдаче ЕГЭ.

Цель работы – комплексное, системное изучение заданий ЕГЭ по информатике по разделу «Основы логики и логические основы компьютера», а также анализ теоретического и учебно-методических материалов для подготовки к ЕГЭ с разбором заданий  по данному разделу в частях А, В, С.

 Исходя из цели,  поставлены следующие задачи исследования:

1)         изучить методическую, учебную и специальную литературу, источники Internet по теме исследования.

2)         проанализировать основные сведения (положения) о ЕГЭ по информатике.

3)         рассмотреть и провести теоретический анализ раздела «Основы логики и логические основы компьютера».

4)         рассмотреть и проанализировать различные типы заданий по разделу «Основы логики и логические основы компьютера», выносимые на ЕГЭ; выделить основные трудности при их решении; выполнить подборку за последние годы.

Структура работы представлена следующим образом: введение, три главы, заключение, список использованной литературы и источников Интернет, приложения.

Первая глава содержит в себе общие сведения о ЕГЭ по информатике (инструкция, содержание, кодификатор).

Вторая глава содержит теоретические основы раздела «Основы логики и логические основы компьютера», объединяющая три основные части: формы мышления, алгебра логики и логические основы устройства компьютера.

И наконец, в третьей главе представлены учебно-методические материалы для подготовки к ЕГЭ по разделу  «Основы логики и логические основы компьютера»: анализ заданий ЕГЭ в сборниках, учебно-методических материалах; способы решения логических задач; разбор заданий, вошедших в вопросы на ЕГЭ из раздела «Основы логики» в частях А, В, С.

Приложения включают в себя — описание материалов, представленных на CD-диске:

· ЭОР «Способы решения логических задач»;

· Презентация «Логика»;

· Электронный учебник «Логика в ЕГЭ» («Подготовка к ЕГЭ по логике»);

· Задачи ЕГЭ «Основы логики» (интерактивный задачник по книге Сафонова «Готовимся к ЕГЭ»);

· Задания по логике (представлены задания из сборника экзаменационных заданий ЕГЭ 2009г. П.А. Якушкин, в конце даны ответы);

· Логика (Logic: программа-тренажер для обучения основам математической логики);

· Логика в вопросах ЕГЭ (решение заданий, представленных в ЕГЭ, с представленными заданиями для тренировки).

Важным в выпускной квалификационной работе является самостоятельная разработка некоторых приложений (ЭОР «Способы решения логических задач»; Электронный учебник «Логика в ЕГЭ»; задания по логике) в электронном варианте.

ГЛАВА 1. ОСНОВНЫЕ СВЕДЕНИЯ О ЕГЭ ПО ИНФОРМАТИКЕ

В процессе написания дипломной работы, были рассмотрены документы, в которых определены общие сведения (положения) о ЕГЭ по информатике; они представлены в данной главе:

1.                      инструкция (структура) экзаменационной работы по информатике;

2.                      содержание ЕГЭ по информатике;

3.                      кодификатор по информатике.

 

1.1. Инструкция (структура) экзаменационной работы по информатике

С 2009 года Единый Государственный Экзамен (ЕГЭ) является основной формой итоговой государственной аттестации в школе для всех выпускников школ Российской Федерации.

Назначение ЕГЭ – оценить общеобразовательную подготовку по информатике и ИКТ выпускников XI классов общеобразовательных учреждений с целью проведения итоговой аттестации выпускников общеобразовательных учреждений и конкурсного отбора абитуриентов в учреждения среднего и высшего профессионального образования.

ЕГЭ проводится с использованием заданий стандартизированной  формы – контрольных измерительных материалов (КИМ). Для записи ответов используются специальные бланки, результаты выполнения заданий обрабатываются автоматизировано, с использованием компьютеров.

Содержание, формат и организация экзамена определяются утверждаемым ежегодно комплексом документов, важнейшим из которых является инструкция.

Инструкция (структура) экзаменационной работы

Общее число заданий в экзаменационной работе – 32.

Экзаменационная работа состоит из трёх частей.

Часть 1 (А) содержит 18 заданий базового, повышенного и высокого уровней сложности. В этой части собраны задания с выбором ответа, подразумевающие выбор одного правильного ответа из четырех предложенных. Часть 2 (В) содержит 10 заданий базового, повышенного и высокого уровней сложности. В этой части собраны задания с краткой формой ответа, подразумевающие самостоятельное формулирование и ввод ответа в виде последовательности символов.  Часть 3 (С) содержит 4 задания, первое из которых повышенного уровня сложности, остальные три задания – высокого уровня сложности.

На выполнение экзаменационной работы отводится 4 часа (240 минут). На выполнение заданий Части 1 (А) и Части 2 (В) рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий Части 3 (С) рекомендуется отводить 2,5 часа (150 минут).

В экзаменационных заданиях используются следующие соглашения по теме «Основы логики и логические основы компьютера»:

1. Обозначения для логических связок (операций): - отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬ А); - конъюнкция (логическое умножение, логическое И) обозначается /\, & (например, А /\ В, либо А & В);    - дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/, |

(например, А \/ В, либо А | В); - следование (импликация) обозначается → (например, А → В);

- символ 1 используется для обозначения истины (истинного высказывания); символ 0 — для обозначения лжи (ложного высказывания).

2. Два логических выражения, содержащих переменные, называются равносильными, если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны; а выражения А /\ В и А \/ В — нет (значения выражений разные, например, А=1, В=0).

3.                 Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), эквивалентность (равносильность).

1.2. СОДЕРЖАНИЕ ЕГЭ ПО ИНФОРМАТИКЕ

Содержание экзаменационной работы рассчитано на выпускников XI классов общеобразовательных учреждений, изучавших курс информатики и ИКТ, в соответствии с обязательным минимумом содержания среднего (полного) общего образования по информатике, по учебникам и учебно-методическим комплектам к ним, имеющим гриф Министерства образования и науки Российской Федерации.

Содержание заданий разработано по основным темам курса информатики и информационных технологий, объединенным в следующие тематические блоки: «Информация и её кодирование», «Алгоритмизация и программирование», «Основы логики», «Моделирование и компьютерный эксперимент», «Программные средства информационных и коммуникационных технологий», «Технология обработки графической и звуковой информации», «Технология обработки информации в электронных таблицах», «Технология хранения, поиска и сортировки информации в базах данных», «Телекоммуникационные технологии».

Часть 1 (A) экзаменационной работы содержит задания, большинство из которых относятся к базовому  и повышенному уровням сложности, и одно задание высокого уровня.

Часть 2 (B) содержит в основном задания повышенного уровня, а также по одному заданию базового и высокого уровней сложности.

Задания Части 3 (С) относятся к повышенному и высокому уровням.

Всего: базовый -17, повышенный -10, высокий -5.

Распределение заданий по частям экзаменационной работы представлено в таблице 1.

 Таблица 1. Распределение заданий по частям экзаменационной работы 

Части работы

Число заданий

Максимальный первичный балл

Процент максимального первичного балла за задания данной части от максимального первичного балла за всю работу (=40)

Тип заданий

Часть 1

18

18

45%

С выбором ответа

Часть 2

10

10

25%

С кратким ответом

Часть 3

4

12

30%

С развернутым ответом

Итого

32

40

100%

 

 Распределение заданий экзаменационной работы по содержанию и видам деятельности. Отбор содержания, подлежащего проверке в экзаменационных работах ЕГЭ 2009г., 2010г. осуществлялся на основе обязательного минимума содержания среднего (полного) общего образования федерального компонента государственного образовательного стандарта. Распределение заданий по разделам курса информатики и ИКТ представлено в таблице 2.

Таблица 2. Распределение заданий по разделам курса информатики и ИКТ

№ п/п

Название раздела

Вся работа

Часть 1

Часть 2

Часть 3

Количество заданий

1

Информация и ее кодирование

7

6

2

0

2

Алгоритмизация и программирование

9

5

2

2

3

Основы логики

5

3

2

0

4

Моделирование

1

1

0

0

5

Программные средства  ИКТ

1

1

0

0

6

Технология обработки графической и звуковой информации

1

1

0

0

7

Технология обработки информации в электронных таблицах

2

2

0

0

8

Технология хранения, поиска и сортировки информации в базах данных

1

1

0

0

9

Телекоммуникационные технологии

3

0

2

0

10

Технология программирования

2

0

0

2

 

Итого:

32

20

8

4

В КИМ по информатике и ИКТ не включены задания, требующие простого воспроизведения знания терминов, понятий, величин, правил (такие задания слишком просты для выполнения). При выполнении любого из заданий КИМ от экзаменуемого требуется решить какую-либо задачу: либо прямо использовать известное правило, алгоритм, умение, либо выбрать из общего количества изученных понятий и алгоритмов наиболее подходящее и применить его в известной либо новой ситуации.

По разделу «Основы логики» выполняются задания на базовом (часть А — 3 задания) и повышенном (часть В — 2 задания) уровнях.

Материал, проверяемый ЕГЭ

На уровне воспроизведения знаний (первая часть: 6 заданий) по разделу «Основы логики и логические основы компьютера» проверяется такой фундаментальный теоретический материал, как: основные элементы математической логики.

Материал на проверку сформированности умений применять свои знания в стандартной ситуации, входящий во все три части экзаменационной работы (17 заданий), включает: создавать и преобразовывать логические выражения; формировать для логической функции таблицу истинности и логическую схему.

Материал на проверку сформированности  умений применять свои знания в новой ситуации (9 заданий) входит во все три части экзаменационной работы. Это следующие сложные умения: решать логические задачи.

 

План экзаменационной работы ЕГЭ по информатике и ИКТ

Обозначение заданий в работе и бланке ответов: А – задания с выбором ответа, В – задания с кратким ответом, С – задания с развернутым ответом.

Уровни сложности задания: Б – базовый (примерный интервал выполнения задания – 60%-90%), П – повышенный (40%-60%), В – высокий (менее 40%).

 

 

Таблица 3. Порядок следования заданий в КИМ

Обозначение
задания в
работе

Проверяемые
элементы содержания

Коды содержания
по кодификатору

Уровень сложности задания

Макс. балл

А1

Кодирование текстовой информации. Кодировка ASCII. Основные кодировки кириллицы

1.1.8

Б

1

А2

Умение подсчитывать информационный объем сообщения

1.1.4

П

1

А3

Знания о системах счисления и двоичном представлении информации в памяти компьютера

1.1.7

Б

1

А4

Умения выполнять арифметические операции в двоичной, восьмеричной и шестнадцатеричной системах счисления

1.1.7

Б

1

А5

Использование переменных. Объявление переменной (тип, имя, значение). Локальные и глобальные переменные

1.2.3

Б

1

А6

Работа с массивами (заполнение, считывание, поиск, сортировка, массовые операции и др.)

1.2.4

П

1

А7

 Знание основных понятий и законов математической логики

1.3.1

П

1

А8

Умения строить и преобразовывать логические выражения

1.3.2

Б

1

А9

Умения строить таблицы истинности и логические схемы

1.3.3

Б

1

А10

Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)

1.4.2

Б

1

А11

Умение кодировать и декодировать информацию

1.1.5

Б

1

А12

 Формальное исполнение алгоритма, записанного на естественном языке

1.2.1

Б

1

А13

Знания о файловой системе организации данных

2.2.3

Б

1

А14

Знание технологии хранения, поиска и сортировки информации в базах данных

2.6.1 /

2.6.2 /

2.6.3 /

2.6.4

Б

1

А15

 Знание технологии обработки графической информации

2.4.1 /

2.4.2 /

2.4.3 /

П

1

А16

 Знание технологии обработки информации в электронных таблицах

2.5.1 /

2.5.2

Б

1

А17

 Знания о визуализации данных с помощью диаграмм и графиков

2.5.3

Б

1

А18

 Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд

1.2.1 /

1.2.2

В

1

В1

 Знания о методах измерения количества информации

1.1.3

Б

1

В2

 Знание и умение использовать основные алгоритмические конструкции: следование, ветвление, цикл

1.2.2

Б

1

В3

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

1.1.7

П

1

В4

 Умение строить и преобразовывать логические выражения

1.3.2

В

1

В5

 Умение исполнять алгоритм в среде формального исполнителя

1.2.2

Б

1

В6

 Умение строить и преобразовывать логические выражения

1.3.2

П

1

В7

 Умение определять скорость передачи информации при заданной пропускной способности канала

1.1.6

П

1

В8

 Умение исполнять алгоритм, записанный на естественном языке

1.2.1

П

1

В9

 Знание базовых принципов организации и функционирования компьютерных сетей, адресации в сети

2.7.1

Б

1

В10

 Умение осуществлять поиск информации в Интернет

2.7.3

П

1

С1

 Умение прочесть фрагмент программы на языке программирования и исправить допущенные ошибки

2.8.1 /

2.8.2

П

3

С2

 Умения написать короткую (10–15 строк) простую программу обработки массива на языке программирования или записать алгоритм на естественном языке

1.2.4 /

2.8.3

В

2

С3

 Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию (логическая задача)

1.2.1

В

3

С4

 Умения создавать собственные программы (30–50 строк) для решения задач средней сложности

2.8.3

В

4

1.3. КОДИФИКАТОР ПО ИНФОРМАТИКЕ

Кодификатор составлен на базе стандарта обязательного минимума содержания среднего (полного) общего образования по информатике и ИКТ (приказ Минобразования России № 1089 от 05.03.2004г.). В кодификаторе каждый контролируемый элемент содержания имеет свой порядковый номер.

В таблице 4 жирным шрифтом указаны крупные блоки содержания, которые ниже разбиты на более мелкие элементы. Каждому заданию присвоен номер того элемента содержания в кодификаторе, на проверку которого оно нацелено прежде всего. Если задание проверяет содержание всего крупного блока, указывается сокращенный номер элемента.

Таблица 4. Кодификатор по разделам информатики и ИКТ

Код блока

Код контролируемого элемента

Элементы содержания, проверяемые заданиями КИМ

 

1

ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ И СИСТЕМЫ

 

1.1

Информация и ее кодирование

 

 

1.1.1

Различные подходы к определению понятия «информация».

Виды информационных процессов. Информационный аспект в деятельности человека.

 

 

1.1.2

Язык как способ представления и передачи информации.

 

 

1.1.3

Методы измерения количества информации: вероятностный и алфавитный.

 

 

1.1.4

Единицы измерения количества информации. Числовые параметры объектов и процессов: объем памяти (хранение информации), скорость обработки информации.

 

 

1.1.5

Процесс передачи информации. Виды и свойства источников и приемников информации. Сигнал, кодирование и декодирование.

 

 

1.1.6

Скорость передачи информации и пропускная способность канала связи.

 

 

1.1.7

Представление числовой информации. Операции в разных системах счисления.

 

 

1.1.8

Кодирование текстовой информации. Кодировка ASCII.

 

1.2

Алгоритмизация и программирование

 

 

1.2.1

Алгоритмы, виды алгоритмов, описания алгоритмов. Формальное исполнение алгоритма.

 

 

1.2.2

Использование основных алгоритмических конструкций: следование, ветвление, цикл.

 

 

1.2.3

Использование переменных. Объявление переменной (тип, имя, значение). Локальные и глобальные переменные.

 

 

1.2.4

Работа с массивами (заполнение, считывание, поиск, и др.)

 

 

1.2.5

Структурирование задачи при ее решении для использования вспомогательного алгоритма. Вспомогательные алгоритмы: функции и процедуры.

 

1.3

Основы логики

 

 

1.3.1

Алгебра логики.

 

 

1.3.2

Логические выражения и их преобразование.

 

 

1.3.3

Построение таблиц истинности логических выражений.

 

1.4

Моделирование и компьютерный эксперимент

 

 

1.4.1

Общая структура деятельности по созданию компьютерных моделей.

 

 

1.4.2

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

 

 

1.4.3

Математические модели (графики, исследование функций).

 

 

1.4.4

Построение и использование информационных моделей реальных процессов (физических, химических, биологических, экономических).

 

1.5

Социальная информатика

 

 

1.5.1

История развития вычислительной техники.

 

 

1.5.2

Нормы информационной этики (почта, публикации в Интернете и др.).

 

 

1.5.3

Правовые нормы в области информатики.

 

2

ИКТ (ИНФОРМАЦИОННЫЕ И КОММУНИКАЦИОННЫЕ ТЕХНОЛОГИИ)

 

2.1

Основные устройства ИКТ

 

 

2.1.1

Типы компьютеров, их основные характеристики и области использования.

 

 

2.1.2

Основные периферийные устройства (ввода — вывода, для соединения компьютеров, и др.).

 

 

2.1.3

Обеспечение надежного функционирования средств ИКТ, устранение простейших неисправностей, требования техники безопасности, гигиены, и др. при работе со средствами ИКТ.

 

2.2

Программные средства ИКТ

 

 

2.2.1

ОС: назначение и функциональные возможности.

 

 

2.2.2

Графический интерфейс (основные типы элементов управления).

 

 

2.2.3

Файлы и файловая системы (архиваторы).

 

 

2.2.4

Оперирование информационными объектами с использованием знаний о возможностях ИКТ.

 

 

2.2.5

Технологии и средства защиты информации от несанкционированного доступа (антивирусные программы, и др.)

 

2.3

Технологии обработки текстовой информации

 

 

2.3.1

Ввод, редактирование и форматирование текста.

 

 

2.3.2

Внедрение в текстовый документ различных объектов (таблиц, диаграмм, рисунков, формул) и их форматирование.

 

 

2.3.3

Автоматизация процесса подготовки издания. Верстка документа. Проверка орфографии и грамматики.

 

2.4

Технология обработки графической и звуковой информации

 

 

2.4.1

Растровая графика. Графические объекты и операции над ними.

 

 

2.4.2

Векторная графика. Графические объекты и операции над ними.

 

 

2.4.3

Компьютерное черчение. Основные операции над чертежом.

 

 

2.4.4

Создание и редактирование цифровых звукозаписей.

 

 

2.4.5

Компьютерные презентации.

 

2.5

Технология обработки информации в электронных таблицах

 

 

2.5.1

Ввод и редактирование данных в электронных таблицах, операции над данными. Экспорт и импорт данных.

 

 

2.5.2

Типы и формат данных. Работа с формулами. Абсолютная и относительная ссылки. Использование функций.

 

 

2.5.3

Визуализация данных с помощью диаграмм и графиков. Построение графиков элементарных функций.

 

2.6

Технология хранения, поиска и сортировки информации в базах данных

 

2.6.1

Структура БД (записи и поля).

 

2.6.2

Табличное и картотечное представление БД.

 

2.6.3

Сортировка и отбор записей.

 

2.6.4

Использование различных способов формирования запросов к БД.

2.7

Телекоммуникационные технологии

 

2.7.1

Базовые принципы организации и функционирования компьютерных сетей. Локальные и глобальные сети. Адресация в сети.

 

2.7.2

Услуги компьютерных сетей: World Wide Web (WWW), электронная почта, файловые архивы, поисковые системы, и т.д.

 

2.7.3

Поиск информации в Интернете.

 

2.7.4

Методы и средства создания и сопровождения сайта (основы HTML).

2.8

Технологии программирования

 

2.8.1

Чтение короткой (30 - 50 строк) простой программы на алгоритмическом языке (языке программирования).

 

2.8.2

Поиск и исправление ошибок в небольшом фрагменте (10-20 строк) программы

 

2.8.3

Создание собственной программы (30-50 строк) для решения простых задач.

Примеры возможных задач: суммирование массива; проверка упорядоченности массива; слияние двух упорядоченных массивов; сортировка (например, вставками); умножение двух многочленов; разложение целого числа на множители (простейший алгоритм); поиск корня делением пополам; и т.д.

 

ГЛАВА 2. ТЕОРЕТИЧЕСКИЙ АНАЛИЗ РАЗДЕЛА

«ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА»

Для успешного выполнения заданий ЕГЭ по разделу «Основы логики и логические основы компьютеры», учащиеся должны твердо усвоить теоретические основы данной темы, которые представлены в данной главе, следующим образом: понятия форм мышления (понятие, суждение, умозаключение, алгебра высказываний); алгебра логики (логические операции: инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность). Кроме того, необходимо знать и уметь  применять при работе с логическими выражениями основные законы логики и правила преобразования логических выражений (правило построения таблицы истинности).

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

В  данной главе рассмотрены и проструктурированы теоретические основы, связанные с логикой. Для этого были изучены и проанализированы следующие пособия: Лыскова В.Ю., Ракитина Е.А. Логика в информатике — М.: Лаборатория Базовых Знаний, 2001; Угринович Н.Д.  Информатика и ИКТ. Профильный уровень: учебник для 10 класса —  М.: БИНОМ. Лаборатория знаний, 2008.


2.1. ФОРМЫ МЫШЛЕНИЯ

Формальной логикой принято называть античную логику, основанную Аристотелем. Это название происходит от основного принципа логики как науки, который гласит, что правильность рассуждения (умозаключения) определяется только его логической формой, или структурой, и не зависит от конкретного содержания входящих в него суждений [7].

Логика — наука о формах и способах мышления.

Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются: понятие, суждение (высказывание), умозаключение.

Понятие. Понятие — форма мышления, отражающая наиболее существенные свойства и признаки предмета, отличающие его от других предметов. Характеризуется содержанием и объемом. Содержание понятия — совокупность существенных признаков предмета. Чтобы раскрыть содержание понятия, следует выделить признаки, необходимые и достаточные для выделения данного объекта по отношению к другим объектам.  Например, понятие «компьютер» объединяет множество электронных устройств, которые предназначены для обработки информации и обладает монитором и клавиатурой.

Объем понятия — совокупность предметов, на которую понятие распространяется. Объем понятия «компьютер» выражает всю совокупность существовавших, существующих и могущих существовать в будущем компьютеров.

Объем и содержание понятия связаны между собой, и эта связь выражается следующим законом: чем больше объем понятия, тем меньше его объем. Например, понятие «карманный компьютер» охватывает меньший объем, чем понятие «компьютер», но обладает большим содержанием.

Для наглядной геометрической иллюстрации объемов понятий и соотношений между ними используются диаграммы Эйлера-Венна, как представлено на рисунке 1:

Рис.1. Представление объемов понятий с использованием диаграммы Эйлера-Венна

 

Если имеются какие-либо понятия А, В, С и т. д., то объем каждого понятия (множество) можно представить в виде круга, а отношения между этими объемами (множествами) — в виде пересекающихся кругов. Например, отобразим с помощью диаграммы соотношение между объемами понятий «натуральные числа» и «четные числа». Объем понятия «натуральные числа» включает в себя множество целых положительных чисел А, а объем понятия «четные числа» включают в себя множество отрицательных и положительных четных чисел В. Эти множества пересекаются, так как оба включают в себя множество положительных четных чисел С (рис.1).

Суждение. Суждение (высказывание) — форма мышления, выраженная с помощью понятий, посредством которой что-либо утверждают или отрицают о предметах, их свойствах и отношениях между ними. О предметах можно судить верно, или неверно, т. е. высказывание может быть истинным или ложным. Истинным будет высказывание, в котором связь понятий правильно отражает свойства и отношения, реальных вещей. Ложным высказывание будет в том случае, когда связь понятий искажает объективные отношения, не соответствует  реальной действительности.

Высказывания могут быть выражены не только с помощью естественных языков, но и с помощью формальных языков. Из двух числовых выражений можно составить высказывания, соединив их знаками равенства или неравенства. Например, высказывание на естественном языке имеет вид «Два умножить на два равно четырем», а на формальном, математическом языке оно записывается в виде «2 x 2 =4».

Высказывание называется простым, если никакая его часть сама не является высказыванием. Высказывание, состоящее из простых высказываний, называются составным (сложным).

Умозаключение. Умозаключение — форма мышления, в которой из одного или нескольких суждений (называемых посылками) по определенным правилам логического вывода получается новое знание о предметах реального мира (вывод, или заключение).

Умозаключения бывают дедуктивные, индуктивные и по аналогии.

В дедуктивных умозаключениях рассуждения ведутся от общего  к частному. Например, из двух суждений: «Все металлы электропроводны» и «Ртуть является металлом»  —  путем умозаключения можно сделать вывод: «Ртуть электропроводна».

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

Умозаключение по аналогии представляют собой движение мысли от общности одних свойств и отношений у сравниваемых предметов или процессов к общности других свойств и отношений. Например, химический состав Солнца и Земли сходен по многим показателям, поэтому, когда на Солнце обнаружили неизвестный еще на Земле химический элемент гелий, то по аналогии заключили: такой элемент есть и на Земле.

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

Примером умозаключений могут быть геометрические доказательства. Например, если мы имеем суждение «Все углы треугольника равны», то мы можем путем умозаключения доказать, что в этом случае справедливо суждение «Этот треугольник равносторонний» [12, с. 155].

 

2.2. АЛГЕБРА ЛОГИКИ

В своем развитии логика прошла ряд этапов. Современную логику называют математической. Алгебра высказываний (алгебра логики) - раздел математической логики [7].

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

Алгебра логики отвлекается от смысловой содержательности высказываний. Для нее важен только один факт — истинно или ложно данное высказывание, что дает возможность определять истинность или ложность составных высказываний алгебраическими методами.


2.2.1. ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Над высказываниями в алгебре логики определяются следующие основные логические операции, в результате которых получаются новые, составные высказывания:

Логическое отрицание (инверсия) — это логическая операция применяемая к одному высказыванию. Высказывание, Ā есть высказывание, которое ложно, когда А истинно, и истинно, когда А ложно. Высказывание называется отрицанием А.

Возможные обозначения отрицания: ¬А, not А, Ā, не А.

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

Возможные обозначения конъюнкции: А И В, А& В, А AND B, А·В, А\/В.

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

Возможные обозначения дизъюнкции: А ИЛИ В, А/\В, А OR В, А + В, А||В.

Дополнительными логическими операциями являются:

Логическое следование (импликация) — высказывание ложно тогда и только тогда, когда А истинно, а В ложно.

Возможные обозначения импликации: А→ В, А => В.

Эквивалентность — это высказывание истинно тогда и только тогда, когда А и В оба истинны или оба ложны.

Возможные обозначения эквивалентности: А ~ В, А <=> В, А≡В.

Значения логических операций задаются с помощью таблиц истинности. Таблица истинности показывает, какие значения дает логическая операция при всех возможных наборах ее аргументов (табл.5).

Таблица 5. Основные и дополнительные логические операции

Отрицание

 

Конъюнкция

 

Дизъюнкция

 

Следование

 

Эквивалентность

А

Ā

А

В

А&В

А

 

В

А\/В

А

В

А→В

А

В

А~ В

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

1

0

0

1

0

1

1

0

0

1

0

0

 

0

1

0

0

1

1

0

1

1

0

1

0

0

0

0

0

0

0

0

0

1

0

0

1

 

2.2.2. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ФУНКЦИИ

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

Исходные высказывания могут быть логическими константами (если имеют постоянное значение «истина» или «ложь») или логическими переменными.

Переменные высказывания — это такие переменные, значениями которых могут быть любые наперед заданные простые высказывания — константы.

Логические операции позволяют каждой формуле при заданных значениях входящих в нее высказываний приписать одно из двух значений: 0 или 1. Тем самым каждая формула может рассматриваться как некоторый способ задания или реализации функции алгебры логики.

Логическая функция — функция, определенная на множестве значений (истина, ложь) и принимающая значение из того же множества [7]. Например, F1=A&B, F2=A\/B.

Функцию можно задавать как в виде формулы, так и в виде таблицы, которая содержит все наборы значений переменных и значения функции на этих наборах. Такая таблица называется таблицей истинности.

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

При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий.

Правило построения таблицы истинности:

Построим таблицу истинности для логического выражения — (А\/В) & (¬А\/¬В).

Во-первых, необходимо определить количество строк в таблице истинности, которое равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение. Если количество логических переменных n, то: Количество строк = 2ⁿ.

В нашем случае логическое выражение (А\/В) & (¬А\/¬В) имеет две переменные и, следовательно, количество строк в таблице истинности должно быть равно:

Количество строк = 2ⁿ = 2² =4.

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

В нашем случае количество переменных равно двум, а количество логических операций равно пяти, т. е. количество столбцов  таблицы истинности равно:

Количество столбцов = 2 + 5 = 7.

В-третьих, необходимо построить таблицу истинности с указанным количеством строк и столбцов, обозначить столбцы и ввести все возможные наборы значений логических переменных. Наборы входных переменных, во избежание ошибок, рекомендуют вводить следующим образом:

1)         разделить столбец значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;

2)         разделить столбец значений второй переменной на четыре части и заполнить четверти чередующимися группами нулей и единиц, начиная с группы нулей;

3)         продолжать деление столбцов значений последующих переменных на 8, 16, и т. д. частей  и заполнение их группами нулей или единиц до тех пор, пока группа нулей (единиц) не будет состоять из одного символа.

В-четвертых,  необходимо заполнить таблицу истинности по столбцам, выполняя базовые логические операции в необходимой последовательности (инверсия, конъюнкция, дизъюнкция, следование, эквивалентность) и в соответствии с их таблицами истинности.

Построим таблицу истинности для рассмотренного логического выражения (табл.6).

Таблица 6. Таблица истинности логического выражения 

(А\/В) & (¬А\/¬В)

А

В

¬А

¬В

А \/ В

¬А \/ ¬В

(А\/В) & (¬А\/¬В)

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1

1

1

0

0

1

0

0

Рассмотрим логическое выражение А&(В\/¬В&¬С) с тремя логическими переменными, то количество строк в таблице истинности должно быть:

Количество строк = 2ⁿ =2³ =8

Количество логических операций равно пяти, следовательно, количество столбцов в таблице истинности:

Количество столбцов = 3+5=8

Построим таблицу истинности:

Таблица 7. Таблица истинности логического выражения

А&(В\/¬В&¬С)

А

В

С

¬В

¬С

¬В & ¬С

В \/ (¬В&¬С)

А&(В\/¬В&¬С)

0

0

0

1

1

1

1

0

0

0

1

1

0

0

0

0

0

1

0

0

1

0

1

0

0

1

1

0

0

0

1

0

1

0

0

1

1

1

1

1

1

0

1

1

0

0

0

0

1

1

0

0

1

0

1

1

1

1

1

0

0

0

1

1

Логические выражения и их преобразование

Будем называть две функции F1 и F2 равносильными, или тождественными, если при любых значениях всех переменных, входящих в F1 и F2, эти функции принимают одинаковые значения. Равносильность обозначается знаком равенства (=). Например: А ~ В = (А\/¬B) & (¬А\/В)

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

В итоге, исходя из выше изложенного следует, что любое логическое выражение можно рассматривать как логическую функцию  F(X1, X2, … , Xn),  аргументами которой являются логические переменные  X1, X2, … , Xn. Сама функция и аргументы могут принимать только два значения: «истина» (1) и «ложь» (0).

Каждая логическая функция двух аргументов имеет четыре возможных значения. Каждая функция несет 4 бита информации и тогда количество различных логических функций двух аргументов может существовать:

N=2ⁿ (где n=4) =16

Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается собственной таблицей истинности (табл.8).

Таблица 8. Таблицы истинности логических функций

двух аргументов

Аргументы

Логические функции

А

В

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

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

F2 – функция логического умножения; F8 – функция логического сложения; F10 – функция эквивалентности; F14 — функция импликации.

2.2.3. ЛОГИЧЕСКИЕ ЗАКОНЫ

В алгебре логики законы логики записываются в виде формул, которые позволяют проводить равносильные преобразования логических выражений [12, с.174 -с. 176].

А & Ā = 0
 
Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:

А \/ Ā = 1
 
Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина:

Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:

¬ (¬А) = А
 
 


       Законы де Моргана (законы общей инверсии для логического сложения (1) и логического умножения (2).

¬ (А \/ В) = ¬А & ¬В
 
1) Отрицание дизъюнкции переменных равно конъюнкции отрицаний переменных:

¬ (А & В) = ¬А \/ ¬В
 
2) Отрицание конъюнкции переменных равно дизъюнкции отрицаний переменных:

Законы поглощения:

А \/ (А & В) = А
 
1) для логического сложения:

А & (А \/ В) = А
 
 2) для логического умножения:

 

Закон исключения (склеивания):

(А&В) \/ (¬А & В) = В
 
1) для логического сложения:

(А\/В) & (¬А\/В) = В
 
2) для логического умножения:

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

Правило коммутативности (переместительности). В алгебре переменных и функций слагаемые и множители можно менять местами. В алгебре логики можно менять местами логические переменные при операциях логического умножения и логического сложения.

 А & В = В & А
 
1) для логического умножения:

 А \/ В = В \/ А
 
2) для логического сложения:

Правило ассоциативности (сочетательности). Если в логическом выражении используется только операция логического умножения или только операция логического сложения, то скобки можно расставлять произвольно.

(А & В) & С = А & (В & С)
 
1) для логического умножения:

(А \/ В)\/С = А\/ (В \/ С)
 
2) для логического сложения:

Правило дистрибутивности (распределительности).  В отличие от алгебры переменных и функций, где за скобки можно выносить только общие множители, в алгебре логики за скобки можно выносить как общие множители, так и общие слагаемые:

1)  дистрибутивность умножения относительно сложения:

(А&В) \/ (А&С) = А& (В \/ С)
 
 


2) дистрибутивность сложения относительно умножения:

(А\/В) & (А \/ С) = А \/ (В&С)
 
 


Правила равносильности. Это правила отсутствия показателей степени у

результатов логического сложения и умножения переменных.

А \/ А = А
 
1) для  логического сложения:

А & А = А
 
2) для логического умножения:

 

Правила исключения констант.

А \/ 1 = 1
 

А \/ 0 = А
 
1) для логического сложения:

А & 1 = А
 

А & 0 = 0
 
2) для логического умножения:

 

2.3. ЛОГИЧЕСКИЕ ОСНОВЫ УСТРОЙСТВА КОМПЬЮТЕРА

Работа компьютера состоит в операциях над двоичными кодами и пересылке этой информации по линиям связи. Средством обработки двоичных сигналов в компьютере являются логические элементы.

Логический элемент — электронная схема с одним или несколькими входами и одним выходом, через которые проходят электрические сигналы, представляющие цифры 1 и 0; на выходе логический элемент выдает значение логического произведения, логической суммы или отрицания. Для реализации любых логических операций над двоичными сигналами достаточно элементов трех типов, реализующих три основные логические операции — И, ИЛИ, НЕ.


2.3.1. БАЗОВЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

Базовые логические элементы реализуют три базовые логические операции [12, c. 180- c. 182]:

1) логический элемент «И» (конъюнктор) — логическое умножение;

2) логический элемент «ИЛИ» (дизъюнктор) — логическое сложение;

3) логический элемент «НЕ» (инвертор) — логическая инверсия.

Любая логическая операция может быть представлена в виде комбинации трех базовых, поэтому любые устройства компьютера, производящее обработку или хранение информации (сумматоры в процессоре, ячейки памяти в оперативной памяти и др.), могут быть собраны из базовых логических элементов.

Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс — логическое значение сигнала 1, нет импульса — значение 0. На вход логического элемента поступают сигналы-элементы, на выходе появляется сигнал-функция.

Преобразование сигнала логическим элементом задается таблицей состояния, которая является  таблицей истинности, соответствующей логической функции.

Логический элемент «И». На входы А и В логического элемента последовательно подаются 4 пары сигналов, а на выходе получается последовательность из 4-х сигналов, значения которых определяются в соответствии с таблицей истинности операции логического умножения. На рисунке 2 изображена логическая схема элемента «И»:

 

 

Рис.2. Логический элемент «И»

Простейшей моделью логического элемента «И» может быть электрическая схема, состоящая из источника тока, лампочки и двух выключателей. Данная схема представлена на рисунке 3:

 

 

 

Рис.3. Электрическая схема модели логического элемента «И»

Из схемы видно, что если оба выключателя замкнуты (на обоих входах 1), по цепи идет ток и лампочка горит (на выходе 1). Если хотя бы один выключатель разомкнут (на одном из выходов 0), то тока нет, и лампочка не горит (на выходе 0).

Логический элемент «ИЛИ» (рис.4). На входы А и В логического элемента последовательно подаются 4 пары сигналов, а на выходе получается последовательность из 4-х сигналов, значения которых определяются в соответствии с таблицей истинности операции логического сложения.

 

 

Рис.4. Логический элемент «ИЛИ»

Простейшей моделью логического элемента «ИЛИ» может быть электрическая схема, которую можно собрать из реальных электрических элементов (рис.5).

 

 

 

Рис.5. Электрическая схема модели логического элемента «ИЛИ»

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

Логический элемент «НЕ» (рис.6). На вход А логического элемента последовательно подаются 2 сигнала, на выходе получается последовательность из 2-х сигналов, значения которых определяются в соответствии с таблицей истинности логической инверсии.

 

 

Рис.6. Логический элемент «НЕ»

Простейшей моделью логического элемента «НЕ» может быть электрическая схема — инвертор,  которую можно собрать из реальных электрических элементов (рис.7).

 

 

 

 

 

Рис.7. Электрическая схема модели логического элемента «НЕ»

В схеме инвертора один вход и один выход. Когда переключатель не замкнут (на входе 0), лампочка горит (на выходе 1); если кнопку переключателя замыкают (на входе 1), лампочка гаснет (на выходе 0).

2.3.2. СУММАТОР ДВОИЧНЫХ ЧИСЕЛ

В целях максимального упрощения работы компьютера все многообразие математических операций в процессоре сводится к сложению двоичных чисел. Поэтому главной частью процессора является сумматор, который обеспечивает такое сложение [12, c. 183- c.187].

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

По числу входов различают полусумматоры, одноразрядные сумматоры (ОС) и многоразрядные сумматоры.

Полусумматор.  Полусумматор — вычислительная схема, которая реализует суммирование одноразрядных двоичных чисел без учета переноса из младшего разряда.

Вспомним, что при сложении двоичных чисел образуется сумма в данном разряде, при этом возможен перенос в старший разряд. Обозначим слагаемые А и В, перенос Р и сумму S. Таблица сложения 1-разрядных двоичных чисел с учетом переноса в старший разряд выглядит следующим образом (табл.9).

Таблица 9. Таблица сложения одноразрядных двоичных чисел

Слагаемые

Перенос

Сумма

А

В

Р

S

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

Из этой таблицы сразу видно, что перенос можно реализовать с помощью операции логического умножения: Р = А & В.

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

Для определения суммы можно применить следующее логическое выражение:   S = (А \/ В) & (¬(А &В)).

Построим таблицу истинности для данного логического выражения (табл.10) и убедимся в правильности предположения.

Таблица 10. Таблица истинности логической функции

S = (А \/ В) & (¬(А &В))

А

В

А \/ В

А & В

¬ (А & В)

 (А \/ В) & (¬(А &В))

0

0

0

0

1

0

0

1

1

0

1

1

1

0

1

0

1

1

1

1

1

1

0

0

Теперь, на основе полученных логических выражений, можно построить  из базовых логических элементов схему полусумматора.

По логической формуле переноса легко определить, что для получения переноса необходимо использовать логический элемент «И».

Анализ логической формулы для суммы показывает, что на выходе должен стоять элемент логического умножения «И» который имеет два входа. На один из входов подается результат логического сложения исходных величин А \/ В, т. е. на него должен подаваться сигнал с элемента логического сложения «ИЛИ».

На второй вход требуется подать результат инвертированного логического умножения исходных сигналов ¬ (А & В), т. е. на второй вход подается сигнал с элемента «НЕ», на вход которого поступает сигнал с элемента логического умножения «И» (рис.8).

 

 

 

 

Рис.8. Полусумматор двоичных чисел

Полный одноразрядный сумматор.

Полный одноразрядный сумматор — устройство с тремя входами (А, В — слагаемые и ¬P -  перенос из младшего разряда ) и двумя выходами (сумма S и перенос P).

Таблица сложения в этом случае будет иметь следующий вид (табл.11).

Таблица 11. Таблица сложения 1-разрядных двоичных чисел с учетом переноса из младшего разряда

Слагаемые

Перенос из младшего разряда

Перенос

Сумма

А

В

¬P

P

S

0

0

0

0

0

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

0

0

1

0

1

0

1

1

1

0

1

0

1

1

0

1

1

1

1

1

Из таблицы сложения видно, что перенос P принимает значение 1 тогда, когда хотя бы две входные логические переменные одновременно принимают значение 1. Таким образом, перенос реализуется путем логического сложения результатов попарно логического умножения входных переменных А, В, ¬P. Формула переноса имеет следующий вид: P = (А & В) \/ (А & ¬P) \/ (В & ¬P).

Для получения значения суммы S, необходимо результат логического сложения входных переменных А, В, ¬P умножить на инвертированный перенос

¬ P: S = (А \/ В \/ ¬P) & ¬Р.

Для получения правильного значения суммы (S должна принимать значение 1) необходимо сложить полученное выше выражение для суммы с результатом логического умножения входных переменных А, В, ¬P. В результате логическое выражение для вычисления суммы в полном сумматоре принимает следующий вид: S = (А \/ В \/ ¬P) & ¬Р \/ (А & В & P).

Логическая схема полного одноразрядного сумматора (рис.9).

 

 

 

 

 

 

 

Рис.9. Сумматор двоичных чисел

 

Многоразрядный сумматор процессора состоит из полных одноразрядных сумматоров. На каждый разряд ставится одноразрядный сумматор, причем выход (перенос) сумматора младшего разряда подключен к входу сумматора старшего разряда.

 

2.3.3. ТРИГГЕР

Важнейшей структурной единицей оперативной памяти компьютера, а также внутренних регистров процессора является триггер. Триггер может находиться в одном из устойчивых состояний, что позволяет запомнить, хранить и считывать 1 бит информации [12, c.188].

Триггер можно построить из двух логических элементов «ИЛИ» и двух элементов «НЕ». При этом выход первого элемента «НЕ»  соединен с входом второго элемента «ИЛИ», а выход второго элемента «НЕ» соединен с входом первого элемента «ИЛИ». Триггер имеет установочный вход S («Set» - установка) и вход сброса R («Reset» - сброс), а также выход Q (рис.10).

 

 

 

 

 

Рис.10. Триггер

Для записи 1 бита на вход S (установочный) подается сигнал 1. Последовательно рассмотрев по логической схеме прохождение сигнала, видим, что на выходе триггера Q устанавливается 1. Триггер переходит в это состояние и будет находиться в нем и после того, как сигнал на входе S исчезнет. Таким образом, триггер будет устойчиво хранить 1 бит.

Для того чтобы сбросить бит данных и подготовиться к приему нового бита, подается сигнал 1 на вход  R (сброс), после чего триггер возвратится к исходному «нулевому» состоянию.

Подача на оба входа S и R логической единицы может привести к неоднозначному результату, поэтому такая комбинация входных сигналов запрещена (табл.12).

 

Таблица 12. Таблица состояний входов и выходов триггера

Входы

Состояние Q

S

R

0

0

Q

Хранение

1

0

1

Установка 1

0

1

0

Установка 0

1

1

Недопустимо

Запрещенная комбинация

 

 

Регистр. Триггер запоминает один разряд двоичного числа. Для запоминания n-разрядного двоичного числа необходимо  n соединенных между собой триггеров. Получаем n-разрядный регистр.

ГЛАВА 3. Учебно-методические материалы для подготовки к ЕГЭ по разделу «Основы логики и логические основы компьютера»

При подготовке выпускной квалификационной работы были изучены и  проанализированы различные учебно-методические материалы (журнальные статьи, сборники материалов ЕГЭ, методические пособия, и т.д.); рассмотрены тренировочные тестовые задания по разделу «Основы логики и логические основы компьютера», проведены обобщения и структуризация материала.

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

 

3.1. Анализ заданий ЕГЭ, представленных в различных учебно-методических пособиях, сборниках

1. Тематические задания для подготовки к ЕГЭ по информатике. Журнал «Информатика в школе» №5-2010. Задания для подготовки к итоговой аттестации по информатике в IX и XI классах — М.: Образование и информатика, 2010.

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

Наряду с представленными заданиями по темам: «Аппаратное и ПО компьютера»; «Технология кодирования, создания и обработки графической и мультимедийной информации»; «Технология кодирования, создания и обработки текстовой информации»; «Технология кодирования, создания и обработки числовой информации в ЭТ»; «Технология создания, хранения поиска и сортировки информации в БД»; «Информационные модели и системы»; «Телекоммуникационные технологии», в итоговом тесте по информатике рассмотрены задания ЕГЭ (части А, В, С), связанные с разделом «Основы логики и логические основы компьютера».

Приведем примеры таких заданий, их решения и методические рекомендации по выполнению.

Часть А

А9. Для какого из указанных значений числа X истинно выражение

 (X<3) & ¬(X<2)?

1)  1     2) 2     3) 3     4) 4

Решение. Возможна подстановка предложенных значений X в выражение, однако целесообразнее упростить выражение (X<3) & ¬(X<2), после чего составить таблицу истинности для полученного выражения.

(X<3) & ¬(X<2)= (X<3) & (X≥2).

Таблица 13. Таблица истинности (X<3) & (X≥2)

X

X<3

X≥2

(X<3) & (X≥2)

1

1

0

0

2

1

1

1

3

0

1

0

4

0

1

0

Из таблицы истинности видно, что выражение (X<3) & ¬(X<2) истинно при X=2.

Номер ответа: 2.

А10. Укажите, какое логическое выражение равносильно выражению

¬ (¬ А /\ В).

1)   А \/ ¬В     2) ¬А \/ В     3) В /\ ¬А     4) А /\ ¬В

Решение. Для того, чтобы выяснить какое логическое выражение равносильно данному ¬ (¬А /\ В), упростим выражение ¬ (¬ А /\ В)=А \/ ¬В (по законам  де Моргана). Следовательно видно, что логическое выражение А \/ ¬В  равносильно выражению ¬ (¬А /\ В), т.е. ответ 1.

Номер ответа: 1.

X

Y

Z

F

0

0

0

0

1

1

0

1

1

0

0

1

А11. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

1)    ¬X Ú ¬Y Ú ¬Z             2) X Ù ¬Y Ù ¬Z

3) X Ú Y Ú Z                    4)  X Ù Y Ù Z

Решение. Составим таблицы истинности для данных выражений (табл.14).

Таблица 14. Таблицы истинности от логических выражений

X

Y

Z

¬X

¬Y

¬Z

F

¬X Ú ¬Y Ú ¬Z

1
 

0
 

0
 
  

X Ù ¬Y Ù ¬Z

 

X Ú Y Ú Z   

X Ù Y Ù Z

0

0

0

1

1

1

0

1

0

0

0

1

1

0

0

0

1

1

1

0

1

0

1

0

0

0

1

1

1

1

1

1

0

Из таблицы истинности видно, что для F соответствует выражение

 X Ú Y Ú Z, т.е. ответ 3.

Номер ответа: 3.

 

 Часть В

В2. Сколько различных решений имеет уравнение

(K/\L/\M)\/(¬L/\¬M/\N) = 1, где K, L, M, N - логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение. Построим таблицу для логического выражения

X =(K/\L/\M)\/(¬L/\¬M/\N) = 1 и посчитаем, сколько в ней единиц, это и будет ответ. Наше выражение зависит от четырех переменных, поэтому в таблице 15 будет 24= 16 строчек (16 возможных комбинация четырех логических значений).

 

Таблица 15. Таблица истинности выражения

X =(K/\L/\M)\/(¬L/\¬M/\N) = 1  

K

L

M

N

¬L

¬M

K/\L/\M

¬L/\¬M/\N

X

1

1

1

1

0

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

0

1

0

1

0

0

0

1

1

0

0

0

1

0

0

0

1

0

1

1

1

0

0

0

0

1

0

1

0

1

0

0

0

0

1

0

0

1

1

1

0

1

1

1

0

0

0

1

1

0

0

0

0

1

1

1

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

1

0

1

0

1

0

0

0

0

1

0

0

0

1

0

0

0

0

0

1

1

1

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

0

1

1

1

0

1

1

0

0

0

0

1

1

0

0

0

Из таблицы истинности видно, что уравнение вида (K/\L/\M)\/(¬L/\¬M/\N) = 1имеет 4 решения.

Ответ: 4.

В4. Три ученика, Саша, Коля и Вова, прогуляли информатику. Когда их спросили, кому пришла в голову эта идея, они ответили следующее:

  Саша: «Я никогда не призывал к прогулу, это была идея Коли».

  Коля: «Я никогда не предложил бы это первым, во всем виноват Вова».

  Вова: «Эта идея пришла в голову Коле. Я просто пошел за компанию».

Внутренним чутьем учитель почувствовал, что двое учеников говорят правду наполовину, а один – лжет. Кто из учеников был инициатором прогула? Ответ дайте в виде первой буквы имени.

Решение.

1)                     У каждого мальчика два высказывания, запишем их в более формальном виде:

Саша:           1. Это не Саша.   2. Это Коля.

Коля:             1. Это не Коля.      2. Это Вова.

Вова:            1. Это Коля.          2. Это не Вова.

2)                     Теперь предположим, что зачинщик – Саша; составим таблицу, где отметим истинность каждого высказывания единицей, а ложность – нулем:

                                                                                Таблица 16

 

если это Саша

если это Коля

если это Вова

Саша

0  0

 

 

Коля

1  0

 

 

Вова

0  1

 

 

3)                     этот вариант уже подходит, потому что Саша оба раза солгал, а остальные сказали один раз правду, а второй – нет;

4)                     на всякий случай проверяем остальные варианты:

                                                                                  Таблица 17

 

если это Саша

если это Коля

если это Вова

Саша

0  0

1  1

1  0

Коля

1  0

0  0

1  1

Вова

0  1

1  1

0  0

5)                     таким образом, Саша первым предложил прогулять урок, ответ – С.

2. ЕГЭ 2009. Информатика. Сборник экзаменационных заданий. Федеральный банк экзаменационных материалов/ ФИПИ. П.А.Якушкин, С.С.Крылов и др.  – М.: Эксмо, 2009.

В сборнике представлено более 500 экзаменационных заданий частей А, В, С. Все они сгруппированы по темам, соответствующим кодификатору ЕГЭ  (табл.3), к некоторым из них приведены ответы и критерии оценивания. Рассмотрим задания, относящиеся к разделу «Основы логики».

Комментарии и решение: Поочередно подставляем значения X в высказывание:

1)    ¬((1>3) → (1>4)) = ¬ (ложь → ложь) = ¬ (истина) = ложь;

2)    ¬((2>3) → (2>4)) = ¬ (ложь → ложь) = ¬ (истина) = ложь;

3)    ¬((3>3) → (3>4)) = ¬ (ложь → ложь) = ¬ (истина) = ложь;

4)    ¬((4>3) → (4>4)) = ¬ (истина → ложь) = ¬ (ложь) = истина.

Ответ: 4.

Комментарии и решение: Применим отрицание к выражению в скобках в соответствии с законом де Моргана: ¬ (A /\ В) /\ ¬С = (¬А \/ ¬В) /\ ¬С

Ответ: 2.

Комментарии и решение: Последовательно подставим первую строку таблицы истинности во все варианты ответов:

1)                     ¬0 \/ 1 \/ ¬0=1, по условию F=0. Первый ответ не подходит;

2)                     0 /\ ¬1 /\ ¬0 =0, по условию F=0. Второй ответ не подходит;

3)                     ¬0 /\ 1 /\ 0=0, по условию F=0. Третий подходит;

4)                      0 \/ ¬1 \/ 0 =0, по условию F=0. Четвертый не подходит.

Ответ: 3.

Решение (табличный метод):

1)                     заметим, что по условию высказывание Миши («Это кто-то с улицы») заведомо ложно, поскольку окно разбил кто-то из перечисленных детей, поэтому его можно вообще не учитывать;

2)                     проще всего решить эту задачу с помощью таблицы; в первом столбце запишем все высказывания, а в остальных будем отмечать, истинно высказывание или ложно (1 или 0), если окно разбил ученик, имя которого записано в заголовке столбца;

          Таблица 18

Егор

Разбил Андрей

0

Разбила Вика

0

Разбила Света

0

Оля права = Разбила Света

0

Разбила Вика или Света

0

Это не Вика и не Света

1

Это не Андрей

1

3)    например, если предположить что окно разбил Егор, получается так:

 

 

 

 

 

 

 

 

4)                     видим, что истинны только два высказывания, а не три (как нужно по условию); следовательно, это не Егор;

5)                     строим таблицу 19 для случаев, предполагая, что окно разбила Света, затем – Оля и т.д.:

      Таблица 19

Егор

Света

Оля

Миша

Надя

Коля

Андрей

Вика

Разбил Андрей

0

0

0

0

0

0

1

0

Разбила Вика

0

0

0

0

0

0

0

1

Разбила Света

0

1

0

0

0

0

0

0

Оля права = Разбила Света

0

1

0

0

0

0

0

0

Разбила Вика или Света

0

1

0

0

0

0

0

1

Это не Вика и не Света

1

0

1

1

1

1

1

0

Это не Андрей

1

1

1

1

1

1

0

1

6)                     только в последнем столбце ровно три единицы (три высказывания истинны), поэтому окно разбила Вика

7)                     таким образом, ответ – В.

3.                      Информатика и ИКТ. Подготовка к ЕГЭ /Под ред. проф. Н.В. Макаровой – СПб: Питер, 2007.

 В учебном пособии представлены тестовые задания по базовому курсу информатики и ИКТ с ориентацией на принятый в 2004г. ГОС для базового уровня. Все задания пособия позволяют проверить знания и умения выпускника школы по информатике в объеме обязательного минимума содержания основной образовательной программы базового уровня.

Раздел «Основы логики и логические основы компьютера» представлен в главе 3 «Задания по теме «Компьютер как средство автоматизации информационных процессов»» [4, с.109 - с. 119] пункт 3.4. «Логические основы ЭВМ». В конце раздела даны ответы на некоторые из них.

Задания части А

1)          Какое из следующих предложений является высказыванием?

1.     Ура, скоро Новый Год!

2.     Светает.

3.     3+4*56.

4.     Первый зимний месяц – декабрь.

Пояснения и решения: Предложения 1, 2, 3 не являются высказываниями, так как 1-е: восклицательное предложение, а относительно 2-го и 3-го нельзя сказать, истинны они или ложны. Значит, 4-е предложение является высказыванием.

2)         Из нижеприведенных фраз выберите ту, которая является истинным высказыванием.

1.     Все кошки серы.

2.     Познай самого себя.

3.     Талант всегда пробьет себе дорогу.

4.     Число 7 – простое.

Пояснения и решения: 1-е предложение является ложным высказыванием, 2-е предложение – побудительное, 3-е высказывание не всегда истинно. Следовательно, 4 – истинное высказывание.

Задания части В

3.84.          Имеются две логические переменные: А и В. Составьте и упростите логическое выражение F, соответствующее следующей таблице истинности:

A

B

F

0

0

1

0

1

1

1

0

0

1

1

0

 

 

 

 

Результат записать в виде F = _ _ _

Решение: Как видно из таблицы истинности для F соответствует логическое значение ¬ А.

4.                      Казиев В.М. Готовимся к ЕГЭ по информатике. Информатика в школе: Приложение к журналу «Информатика и образование». №2 – 2006. –М.: Образование и Информатика, 2006.

В данном сборнике приведены правила тестирования, тестовые задания и задачи по основополагающим разделам базового курса информатики и новых ИТ для подготовки ЕГЭ.

Сборник содержит «Обучающие и тренировочные тестовые задания уровня сложности  А, В, С»;  «Указания к выбору ответа для заданий группы А, В, С по десяти темам: «Информация и сообщения»; «Системы счисления»; «Высказывания, предикаты, логические функции» [5, с. 34 - с. 36;  с. 54 - с. 55; с. 59;  с. 64; с. 73; с. 82 — с.83]; «Алгоритмы и исполнители»; «Данные к алгоритмам и исполнители алгоритмов»; «Программные системы»;  «Компьютер, компьютерные системы и сети»; «Новые ИТ»; «Математическое и компьютерное моделирование»; «Программирование на языке Паскаль».

Рассмотрим Обучающие и тренировочные тестовые задания уровня сложности А по теме 3 «Высказывания, предикаты, логические функции».

1.     В списке выражений вида:

1)    2-2=0;          4) 2+2>2+2;

2)    2+3=6;         5) 2-0=3-0;

3)    3+12;           6) 56=50+6

приведено всего истинных и ложных высказываний соответственно:

          а) 2, 3                 г) 3, 3

          б) 2, 2                 д) 1, 4

          в) 3, 2

2. Выражение ¬(x \/ y) \/ ¬x после применения аксиом алгебры предикатов и высказываний запишется наиболее коротко в виде:

а) x    б) y    в) ¬x     г) ¬у   д) 0

Задачи уровня сложности В

1.     Упростите максимально и наиболее коротким способом выражение .

Задачи уровня сложности С

1. Из указанных ниже логических функций отметьте (с обоснованием рассуждений) эквивалентные между собой логические функции (если такие есть):

 

Составить их таблицы истинности.

Указания к выбору ответа для заданий группы А

1. Выражение, не являющееся повествовательным утверждением, не может быть высказыванием.

2. Применив аксиому поглощения, получите (x \/ x ) = x. Ответ: х.

Указания к решению задач группы В

1. В первой из перемножаемых скобок оба слагаемых равны по аксиоме де Моргана. Вторую скобку можно раскрыть последовательно, используя соответствующие аксиомы. Следовательно, ответ: (x \/ y).

Указания к решению задач группы С

1. Упростите выражение «а» с помощью аксиомы поглощения (применительно к выражению под знаком отрицания в скобке  и к следующим за скобкой двум слагаемым). В выражении «б» замените оба отрицания в скобке общим отрицанием по аксиоме де Моргана, а затем примените аксиому де Моргана и аксиому поглощения. К выражениям «в», «г», «д» примените аксиому поглощения.

Ответ:

5. Сафронов И.К. Готовимся к ЕГЭ. Информатика – СПб.: БХВ-Петербург, 2007.

В пособии рассматриваются некоторые варианты ЕГЭ последних лет с подробным разбором всех заданий. Пособие проструктурировано следующим образом: даны требования к знаниям выпускника по информатике и краткие теоретические пояснения к основным разделам учебного курса.

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

Раздел «Основы логики и логические основы компьютера» представлен таким образом:

Часть 1. Задания с выбором ответа

1.4 Алгебра логики или булева алгебра [11, с.42-с.55]

Требования

Учащиеся должны владеть понятиями элементарного высказывания значений TRUE (Истина) и FALSE (Ложь), знать, что такое инверсия (Логическое НЕ, отрицание), конъюнкция (Логическое И, умножение), дизъюнкция (Логическое ИЛИ, сложение), импликация (следование), таблицы их истинности, порядок логических действий, вычисление простых логических выражений, простейшие законы логики.

Замечание

В официальных заданиях ЕГЭ логическое отрицание НЕ обозначается символом «¬», например, ¬А, ¬(А&В).

Рассмотрим задания из демо-версий ЕГЭ по информатике 2006 года.

А9. Для какого из указанных значений числа X истинно высказывание: (X>4) \/ ((X>1) → (X>4))?

1) 1     2) 2     3) 3     4) 4

Решение задачи А9

Зная приоритет логических операций: инверсия, конъюнкция, дизъюнкция.

Решим задачу методом последовательной подстановки.

1) X=1, тогда (1>4) \/ ((1>1) → (1>4))=0 \/ (0→0)=0 \/ 1 =1;

2) X=2, тогда (2>4) \/ ((2>1) → (2>4))=0 \/ (1→0)=0 \/ 0 =0;

3) X=3, тогда (3>4) \/ ((3>1) → (3>4))=0 \/ (1→0)=0 \/ 0 =0;

4) X=4, тогда (4>4) \/ ((4>1) → (4>4))=0 \/ (1→0)=0 \/ 0 =0.

Из всех данных значений X, только при X=1 высказывание оказалось истинным. Следовательно, правильный ответ №1.

А10. Какое логическое выражение равносильно выражению ?

1)      2)        3)        4)

Решение задачи А10

Построим таблицу истинности для заданного выражения:

                                                                  Таблица 20

А

В

С

0

0

0

1

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

0

Теперь для выражений ответов:

                                                                 Таблица 21

А

В

С

0

0

0

1

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

0

В общем, видно, что совпали, поэтому ответ №1.

X

Y

Z

F

0

0

0

0

1

1

0

1

1

0

0

1

А11. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения  F:

1) ¬X Ú ¬Y Ú ¬Z             2) X Ù ¬Y Ù ¬Z

3) X Ú Y Ú Z                    4)  X Ù Y Ù Z

Решение задачи А11

Составим таблицы истинности для данных выражений:

                                                                                                  Таблица 22

X

Y

Z

¬X

¬Y

¬Z

F

¬X Ú ¬Y Ú ¬Z

1
 

0
 

0
 
  

X Ù ¬Y Ù ¬Z

 

X Ú Y Ú Z   

X Ù Y Ù Z

0

0

0

1

1

1

0

1

0

0

0

1

1

0

0

0

1

1

1

0

1

0

1

0

0

0

1

1

1

1

1

1

0

Из таблицы истинности видно, что для F соответствует выражение

 X Ú Y Ú Z, т.е. ответ №3.

После разбора официальных заданий предлагаются задания для самостоятельной работы и приводятся их решения.

Часть 2. Ответ как набор символов

2.1. Системы счисления и логическая алгебра [11, с.79-с.84]

В2. Укажите значения логических переменных K, L, M, N, при которых логическое выражение: (K \/ M) → (M \/ ¬L \/ N) –ложно. Ответ запишите в виде строки из четырех символов: значений переменных  K, L, M и N (в указанном порядке). Так, например, строка 0100 соответствует тому, что K=0, L=1, M=0, N=1.

Решение задачи В2

Из понятия импликация и таблицы истинности логических операций (табл.4) следует, что импликация будет ложной ↔, когда левое от знака импликации высказывание истинно, а правое от знака импликации высказывание – ложно. Для истинности высказывания K \/ M достаточно истинности K или M. Так как K в левой части выражения, то K=1, тогда M=0. То, что M=0 следует и при первом же рассмотрении правой части импликации, где видим три высказывания, связанные между собой дизъюнкцией, а так как правая часть должна быть ложна, то ВСЕ входящие в первую очередь  высказывания должны быть ложны. Из условия отсюда следует, что ¬ L=0 (так как L=1); M=0, N=0.

Правильный ответ: 1010.

2.3. Логические задачи [11, с.87-с.93]

В4. Три школьника, Миша (М), Коля (К) и Сергей (С), остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:

Миша: «Я не бил окно, и Коля тоже…»

Коля: «Миша не разбивал окно, это Сергей разбил футбольным мячом!»

Сергей: «Я не делал этого, стекло разбил Миша».

Стало известно, что один из ребят сказал чистую правду, второй в одной части заявления соврал, а другое его высказывание истинно, а третий оба факта исказил. Зная это, директор смог докопаться до истины.

Кто разбил стекло в классе? В ответе запишите только первую букву имени.

 

Решение задачи В4

Решим данную задачу с помощью логических рассуждений.

Начнем с того, что Миша не может быть неправ в обоих своих высказываниях, потому что в этом случае получится, что стекло разбили одновременно и Миша, и Коля. Значит, Миша говорит правду или полуправду. Если Миша говорит правду, то стекло однозначно разбил Сергей. Тогда остается два варианта – лжет либо Коля, либо Сергей.  Допустим, лжет Коля. Тогда из его высказываний следует, что стекло разбил Миша. Допустим, лжет Сергей. Тогда из его высказываний следует, что стекло разбил он, а Миша не бил. Проверим тогда высказывание Коли, который, получается, говорил полуправду.

Допустим, Коля лжет в своем первом утверждении, тогда стекло разбил Миша, а не Сергей; если Коля лжет в своем втором утверждении, но тогда стекло разбил сам Коля. Отсюда следует, что не лжет и не говорит правды Миша, значит он прав только наполовину. Допустим, на первую, тогда стекло разбил Коля.

Остался последний вариант: Миша говорит правду только во втором своем высказывании. Из этого следует, что стекло разбил собственно он, т.е. Коля лжет, а Сергей говорит правду.

Правильный ответ: стекло разбил Миша.

Часть 3. Самостоятельные задания

3.3. Разработка правильной стратегии [11, с.107-с.111]

С3. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня  какой-то кучу. Выигрывает игрок, после хода, которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Ответ обоснуйте.

Предполагаемое решение задачи С3

Выигрывает первый игрок. Своим первым ходом он должен удвоить количество камней во второй куче. Для доказательства рассмотрим неполное дерево игры после этого хода первого игрока (табл.23).

                                                                                                       Таблица 23

Позиция после

 1 хода

1-й ход

второго игрока

Выигрывающий ход первого игрока

Пояснение

 

10,6

10,10

Первый игрок выигрывает после любого ответа второго игрока, удвоив число камней в самой большой куче

5,6

9,6

9,10

Первый игрок выигрывает после любого ответа второго игрока, удвоив число камней в самой большой куче

 

5,10

9,10 или 10,10

Первый игрок выигрывает после любого ответа второго игрока, удвоив число камней в самой большой куче

 

5,12

5,24

Выигрыш первого игрока

Из таблицы видно, что при первом ходе (5,3) → (5,6) первый игрок выигрывает не позже, чем на третьем ходу при любом ответе второго игрока.

3.2. Электронный образовательный ресурс «Способы решения логических задач» - как средство  при подготовке к ЕГЭ

Тема «Основы логики и логические основы компьютера» изучается чаще всего в XI классе. В это время актуальным является повторение всего курса информатики, подготовка учащихся к экзаменам по курсу «Информатика и ИКТ» (тестирование, по билетам; ЕГЭ). Решение логических задач позволяет на профильном курсе (в ЕГЭ задание В4) повторить следующие темы [9, c.3]:

1.          Логика (таблицы истинности, законы логики, преобразование логических выражений, построение таблиц истинности, способы решения логических задач).

2.          Этапы решения задач на ЭВМ (для решения логических задач с помощью табличного процессора MS Excel и языка программирования).

3.          Алгоритмизация и программирование (составление алгоритма и программы на языке программирования решения логической задачи).

4.          Технология обработки текстовой информации (оформление решения логической задачи в текстовом процессоре).

5.          Технология обработки графической информации (построение графического дерева, графа с помощью графического редактора).

6.          Технология обработки числовой информации (решение логической задачи с помощью табличного процессора).

7.          Моделирование и формализация (моделирование логических задач).

Логические задачи в литературе по информатике публикуются в небольшом количестве. Поэтому, используя материал приложения к журналу «Информатика и образование» №6-2005: Логические задачи как форма контроля знаний,  в данной работе была предпринята попытка сбора, систематизации и оформления логических задач в Электронный Образовательный Ресурс.

Рис.11. ЭОР Способы решения логических задач

В приложении (СD-диск) содержится папка ЭОР «Способы решения логических задач», который предназначен для учителей информатики, методистов, а также для учащихся и всех тех, кто хочет в совершенстве овладеть разделом «Основы логики» и научиться самостоятельно решать логические задачи:

 

 

 

 

 

 

Рис.12. Содержание ресурса

Наглядно данные способы можно представить в виде схемы (рис.13).

 

 

 

 

 

 

 

 

 

 

 

Рис.13. Способы решения логических задач

 

 

3.3. РАЗБОР ЗАДАНИЙ ЕГЭ

Анализ выполнения заданий этой темы.

По разделу «Основы логики» в экзаменационной работе содержится 5 заданий: 3 с выбором ответа и 2 с кратким ответом. Часть А – 3 задания, часть В – 2 задания.  А также к данному разделу можно отнести и задание из части С.

 Таблица 24. Темы, вошедшие в вопросы на ЕГЭ из раздела

«Основы логики»

№

Название раздела курса

Порядковый номер задания

Уровень задания

«Основы логики»

1

Знание основных понятий и законов математической логики

А9

повышенный

2

Умения строить и преобразовывать логические выражения

А10

базовый

3

Умения строить таблицы истинности и логические схемы

А11

базовый

4

Умения строить и преобразовывать логические выражения

В2

высокий

5

Умения строить и преобразовывать логические выражения

В4

повышенный

6

Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию – игровая  логическая задача (стратегия)

С3

высокий

Рассмотрим данные задания более подробно в каждой части экзаменационной работы.

3.3.1. ЗАДАНИЯ С ВЫБОРОМ ОТВЕТА

Часть А

А9 (повышенный уровень, время – 3 мин). Тема:  «Основные понятия математической логики».

Что нужно знать:

·   условные обозначения логических операций

¬ A,                  не A (отрицание, инверсия)

A Ù B, A и B (логическое умножение, конъюнкция)

A Ú B,           A или B (логическое сложение, дизъюнкция)

A → B                  импликация (следование)

·   таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация» (см. презентацию «Логика»)

·   операцию «импликация» можно выразить  через «ИЛИ» и «НЕ»:

A → B = ¬ A Ú B или в других обозначениях  A → B =

·   если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем  – «ИЛИ», и самая последняя – «импликация»

·   иногда полезны формулы де Моргана:

¬ (A Ù B) = ¬ A Ú ¬ B            

¬ (A Ú B) = ¬ A Ù ¬ B            

Пример задания:

Для какого из указанных значений X истинно высказывание   

 ¬((X > 2)→(X > 3))?

 1)  1                   2) 2             3) 3             4) 4

Решение (вариант 1, прямая подстановка):

1)                     определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках

2)                     выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); сначала определяем результаты сравнения в двух внутренних  скобках:

Таблица 25

X

X > 2

X > 3

 (X > 2)→(X > 3)

¬((X > 2)→(X > 3))

1

0

0

 

 

2

0

0

 

 

3

1

0

 

 

4

1

1

 

 

3)                     по таблице истинности операции «импликация» находим третий столбец (значение выражения в больших скобках), применив операцию «импликация» к значениям второго и третьего столбцов (в каждой строке):

Таблица 26

X

X > 2

X > 3

 (X > 2)→(X > 3)

¬((X > 2)→(X > 3))

1

0

0

1

 

2

0

0

1

 

3

1

0

0

 

4

1

1

1

 

4)                     значение выражения равно инверсии третьего столбца (меняем 1 на 0 и наоборот):

Таблица 27

X

X > 2

X > 3

 (X > 2)→(X > 3)

¬((X > 2)→(X > 3))

1

0

0

1

0

2

0

0

1

0

3

1

0

0

1

4

1

1

1

0

5)    таким образом, ответ – 3.

Возможные проблемы:

·можно перепутать порядок операций (скобки, «НЕ», «И», «ИЛИ», «импликация»)

·нужно помнить таблицу истинности операции «импликация», которую очень любят составители тестов

·этот метод проверяет только заданные числа и не дает общего решения, то есть не определяет все множество значений X, при которых выражение истинно

Решение (вариант 2, упрощение выражения):

1)    обозначим простые высказывания буквами:

A = X > 2,   B = X > 3

2)    тогда можно записать все выражение в виде

      ¬(A → B)    или     

3)    выразим импликацию через «ИЛИ» и «НЕ» (см. выше):

¬(A → B)= ¬(¬A Ú B) или 

4)    раскрывая по формуле де Моргана операцию «НЕ» для всего выражения, получаем

¬(¬A Ú B)= A Ù ¬B   или  

5)    таким образом, данное выражение истинно только тогда, когда A истинно (X > 2), а B – ложно (X ≤ 3), то есть для всех X, таких что 2 < X ≤ 3

6)    из приведенных чисел только 3 удовлетворяет этому условию,

7)    таким образом, ответ – 3.

Возможные проблемы:

·   нужно помнить законы логики (например, формулы де Моргана)

·   при использовании формул де Моргана нужно не забыть заменить «И» на «ИЛИ» и наоборот

·   нужно не забыть, что инверсией (отрицанием) для выражения  X > 3 является X ≤ 3, а не X < 3

 

А10 (базовый уровень, время – 1 мин). Тема: «Преобразование логических выражений. Формулы де Моргана».

Что нужно знать:

·   условные обозначения логических операций

¬ A,                  не A (отрицание, инверсия)

A Ù B,           A и B (логическое умножение, конъюнкция)

A Ú B,           A или B (логическое сложение, дизъюнкция)

A → B                           импликация (следование)

·   операцию «импликация» можно выразить  через «ИЛИ» и «НЕ»:

A → B = ¬ A Ú B или в других обозначениях  A → B =

·   если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем  – «ИЛИ», и самая последняя – «импликация»

·   правила преобразования логических выражений (слайд из презентации «Логика»):

·   фактически это задание на применение законов де Моргана (хотя об этом нигде не говорится):

¬ (A Ù B) = ¬ A Ú ¬ B            

¬ (A Ú B) = ¬ A Ù ¬ B            

Пример задания:

Укажите, какое логическое выражение равносильно выражению                  A Ù ¬(¬B Ú C).

1)  ¬A Ú ¬B Ú ¬C  2) A Ú ¬B Ú ¬C           3) A Ù B Ù ¬C    4) A Ù ¬B Ù C

Решение (вариант 1, использование законов де Моргана):

1)    перепишем заданное выражение и ответы в других обозначениях:
заданное выражение
ответы: 1)      2)          3)     4)

2)    «посмотрев на заданное выражение, видим инверсию (операцию

«НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана,

а затем используем закон двойного отрицания по которому :

3)    таким образом, правильный ответ – 3 .

Возможные проблемы:

·   серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений с «закорючками», поэтому рекомендуется сначала внимательно перевести их в «удобоваримый» вид; при этом сразу становится понятно, что ответы 1 и 2 заведомо неверные

·   при использовании законов де Моргана часто забывают, что нужно заменить «И» на «ИЛИ» и «ИЛИ» на «И» (возможный неверный ответ )

·   расчет на то, что при использовании законов де Моргана инверсия сложного выражения по ошибке «просто пропадет», и все сведется к замене «ИЛИ» на «И» (неверный ответ )

·   иногда для решения нужно упростить не только исходное выражение, но и заданные ответы, если они содержат импликацию или инверсию сложных выражений

Решение (вариант 2, через таблицы истинности, если забыли формулы де Моргана):

1)    перепишем заданное выражение в других обозначениях:
заданное выражение
ответы: 1)      2)         3)     4)

2)    для доказательства равносильности двух логических выражений достаточно показать, что они принимают равные значения при всех возможных комбинациях исходных данных; поэтому можно составить таблицы истинности для исходного выражения и всех ответов и сравнить их

3)    здесь 3 переменных, каждая из которых принимает два возможных  значения (всего 8 вариантов, которые в таблице истинности записывают по возрастанию двоичных кодов – см. презентацию «Логика»)

4)    исходное выражение  истинно только тогда, когда  и , то есть только при . (в таблице истинности одна единица, остальные – нули)

5)    выражение  истинно, если хотя бы одна из переменных равна нулю, то есть, оно будет ложно только при  (в таблице истинности один нуль, остальные – единицы)

6)    аналогично выражение  ложно только при , а в остальных случаях – истинно

7)    выражение  истинно только при , а в остальных случаях – ложно

8)    выражение  истинно только при , а в остальных случаях – ложно

9)    объединяя все эти результаты в таблицу, получаем:

Таблица 28

A

B

C

0

0

0

0

1

1

0

0

0

0

1

0

1

1

0

0

0

1

0

0

1

1

0

0

0

1

1

0

1

0

0

0

1

0

0

0

1

1

0

0

1

0

1

0

1

1

0

1

1

1

0

1

1

1

1

0

1

1

1

0

0

1

0

0

 

10)              видим, что таблицы истинности исходного выражения и  совпали во всех строчках

11)              таким образом, правильный ответ – 3 .

Возможные проблемы:

·   сравнительно большой объем работы

Выводы:

1)    очевидно, что проще использовать первый вариант решения (упрощение исходного выражения и, если нужно, ответов), но для этого нужно помнить формулы

2)    если формулы забыты, всегда есть простой (хотя и более трудоемкий) вариант решения через таблицы истинности.

А11 (базовый уровень, время – 2 мин). Тема:  «Построение таблиц истинности логических выражений».

Что нужно знать:

·   условные обозначения логических операций

¬ A,                  не A (отрицание, инверсия)

A Ù B,           A и B (логическое умножение, конъюнкция)

A Ú B,           A или B (логическое сложение, дизъюнкция)

A → B                           импликация (следование)

·   операцию «импликация» можно выразить  через «ИЛИ» и «НЕ»:

A → B = ¬ A Ú B или в других обозначениях  A → B =

·   иногда для упрощения выражений полезны формулы де Моргана:

¬ (A Ù B) = ¬ A Ú ¬ B            

¬ (A Ú B) = ¬ A Ù ¬ B            

·   если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем  – «ИЛИ», и самая последняя – «импликация»

·   таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных

·   если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);

·   количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где  – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти    28-6=22=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)

·   логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)

·логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)

Пример задания:

Надпись: X Y Z F 1 0 0 1 0 0 0 1 1 1 1 0 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

1)  ¬X Ù ¬Y Ù ¬Z  2) X Ù Y Ù Z       3) X Ú Y Ú Z             4) ¬X Ú ¬Y Ú ¬Z

Решение (основной вариант):

1)    нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных

2)    если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F

3)    перепишем ответы в других обозначениях:
             1)           2)        3)            4)

4)    первое выражение, , равно 1 только при , поэтому это неверный ответ (первая строка таблицы не подходит)

5)    второе выражение, , равно 1 только при , поэтому это неверный ответ (первая и вторая строки таблицы не подходят)

6)    третье выражение,, равно нулю при , поэтому это неверный ответ (вторая строка таблицы не подходит)

7)    наконец, четвертое выражение,  равно нулю только тогда, когда , а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности

8)    таким образом, правильный ответ – 4 ; частичная  таблица истинности для всех выражений имеет следующий вид:

Таблица 29

X

Y

Z

F

1

0

0

1

   0 ×

   0 ×

1

1

0

0

0

1

–

–

0 ×

1

1

1

1

0

–

–

–

0

(красный крестик показывает, что значение функции не совпадает с F, а знак «–»  означает, что вычислять оставшиеся значения не обязательно).

Возможные проблемы:

·   серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений с «закорючками», поэтому рекомендуется, сначала внимательно перевести их в «удобоваримый» вид;

·   расчет на то, что ученик перепутает значки Ù и Ú (неверный ответ 1)

 

 

 

3.3.2. ОТВЕТ КАК НАБОР СИМВОЛОВ

Часть В

В2 (высокий уровень, время – 8 мин). Тема:  «Построение и преобразование логических выражений».

Что нужно знать:

·   условные обозначения логических операций

¬ A,                  не A (отрицание, инверсия)

A Ù B,           A и B (логическое умножение, конъюнкция)

A Ú B,           A или B (логическое сложение, дизъюнкция)

A → B                           импликация (следование)

A ↔ B                  эквиваленция (эквивалентность, равносильность)

·   таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция» (см. презентацию «Логика»)

·   операцию «импликация» можно выразить  через «ИЛИ» и «НЕ»:

A → B = ¬ A Ú B или в других обозначениях  A → B =

·   операцию «эквиваленция» также можно выразить  через «ИЛИ» и «НЕ»:

A ↔ B = ¬ A Ù ¬ B Ú A Ù B или в других обозначениях  A ↔ B =

·   если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем  – «ИЛИ», и самая последняя – «импликация»

·   логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)

·   логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

·   правила преобразования логических выражений (слайд 21 из презентации «Логика»)

 

Пример задания:

Каково наибольшее целое число X, при котором истинно высказывание

(50 < X·X) → (50 > (X+1)·(X+1))

Решение (вариант 1):

1)    это операция импликации между двумя отношениями   и

2)    попробуем сначала решить неравенства

,         

3)    обозначим эти области на оси X (рис.14):

Рис.14

На рисунке 14 черные зоны обозначают область, где истинно выражение , белая зона – это область, где истинно

4)    вспомним таблицу истинности операции «импликация»:

Таблица 30

A

B

A → B

0

0

1

0

1

1

1

0

0

1

1

1

5)    согласно таблице, заданное выражение истинно везде, кроме областей, где  и ; область истинности выделена зеленым цветом

6)    поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее , то есть, 7

7)    таким образом, верный ответ – 7 .

Возможные проблемы:

·   в этом примере потребовалось применить знания не только (и не столько) из курса информатики, но и умение решать неравенства

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

Еще пример задания:

Сколько различных решений имеет уравнение

((K Ú L) → (L Ù M Ù N)) = 0

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение (вариант 1, разделение на части):

1)                     перепишем уравнение, используя более простые обозначения операций:

((K + L) → (L · M · N)) = 0

2)                     из таблицы истинности операции «импликация» (см. первую задачу) следует, что это равенство верно тогда и только тогда, когда одновременно

K + L = 1      и     L · M · N = 0

3)                     из первого уравнения следует, что хотя бы одна из переменных, K или L, равна 1 (или обе вместе); поэтому рассмотрим три случая

4)                     если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения

5)                      если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

6)                     если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

7)                     таким образом, всего получаем 4 + 3 + 3 = 10 решений.

Совет:

·лучше начинать с того уравнения, где меньше переменных

 

Возможные проблемы:

·есть риск потерять какие-то решения при переборе вариантов

Решение (вариант 2, через таблицы истинности):

1)    перепишем уравнение, используя более простые обозначения операций:

((K + L) → (L · M · N)) = 0

2)    построим таблицу для логического выражения

X = ((K + L) → (L · M · N))

и подсчитаем, сколько в ней нулей, это и будет ответ

3)    наше выражение зависит от четырех переменных, поэтому в таблице будет 24 = 16 строчек (16 возможных комбинация четырех логических значений)

4)    подставляем различные комбинации в формулу для X; несмотря на большое количество вариантов, таблица строится легко: достаточно вспомнить, что выражение K + L ложно только при  K = L = 0, а выражение L·M·N истинно только при L = M = N = 1.

 

Таблица 31

K

L

M

N

K+L

L·M·N

X

0

0

0

0

0

0

1

0

0

0

1

0

0

1

0

0

1

0

0

0

1

0

0

1

1

0

0

1

0

1

0

0

1

0

0

0

1

0

1

1

0

0

0

1

1

0

1

0

0

0

1

1

1

1

1

1

1

0

0

0

1

0

0

1

0

0

1

1

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

0

1

1

0

0

1

0

0

1

1

0

1

1

0

0

1

1

1

0

1

0

0

1

1

1

1

1

1

1

5)    в последнем столбце 10 нулей; это значит, что есть 10 разных комбинаций, при которых выражение X равно нулю, то есть исходное уравнение имеет 10 решений

6)    таким образом, всего 10 решений.

В4 (повышенный уровень, время – 8 мин). Тема: «Решение логических задач методом рассуждений».

Что нужно знать:

·   таблицы истинности логических операций «И», «ИЛИ», «НЕ» (см. презентацию «Логика»)

·   логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)

·   логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

·   правила преобразования логических выражений (слайд из презентации «Логика»):

Пример задания:

Классный руководитель пожаловался директору, что у него в классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них правдив, а кто – нет. Однажды все трое прогуляли урок астрономии. Директор знает, что никогда раньше никто из них не прогуливал астрономию. Он вызвал всех троих в кабинет и поговорил с мальчиками. Коля сказал: «Я всегда прогуливаю астрономию. Не верьте тому, что скажет Саша». Саша сказал: «Это был мой первый прогул этого предмета». Миша сказал: «Все, что говорит Коля, – правда». Директор понял, кто из них кто. Расположите первые буквы имен мальчиков в порядке: «говорит всегда правду», «всегда лжет», «говорит правду через раз». (Пример: если бы имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ)

Решение (вариант 1, метод рассуждений):

1)                     во-первых, есть «точная» информация, которая не подвергается сомнению:

(*) все трое прогуляли урок астрономии в первый раз

2)                     запишем высказывания мальчиков:

Коля:            1. Я всегда прогуливаю астрономию.

                     2. Саша врет.

Саша:           1. Я в первый раз прогулял астрономию.

Миша:          1. Коля говорит правду.

3)                     известно, что один из них все время лжет, второй ­– говорит правду, а третий говорит правду через раз (то есть, из двух его высказываний одно истинно, а второе – ложно; если у нас есть только одно высказывание «полу-лжеца», оно может быть как истинным, так и ложным)

4)                     сопоставив первое высказывание Коли и высказывание Саши с «точной» информацией (*), сразу определяем, то тут Коля соврал, а Саша сказал правду; это значит, что второе высказывание Коли – тоже неверно, поэтому мальчик Коля всегда лжет

5)                     тогда один из оставшихся, Саша или Миша, говорит правду всегда, а второй – через раз

6)                     Мишино высказывание неверно, поскольку мы уже определили, что Коля лжет; это значит, что Миша не всегда говорит правду, он – «полу-лжец»

7)                     тогда получается, что Саша всегда правдив, и действительно, его высказывание верно

8)                     таким образом, верный ответ – СКМ  (Саша – правдив, Коля – лжец, Миша – «полу-лжец»).

Возможные проблемы:

·длинное запутанное условие, из которого нужно выделить действительно существенную информацию и формализовать ее

 

3.3.3. ЗАДАНИЯ ПОВЫШЕННОЙ СЛОЖНОСТИ

Часть С

C3 (высокий уровень, время – 30 мин). Тема:  «Дерево игры.  Поиск выигрышной стратегии».

Что нужно знать:

·в простых играх можно найти выигрышную стратегию, просто перебрав все возможные варианты ходов соперников

·для примера рассмотрим такую игру: сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку

·первый игрок может убрать одну спичку (в этом случае их останется 4), или сразу 2 (останется 3), эти два варианта можно показать на схеме:

Рис. 15

·если первый игрок оставил 4 спички, второй  может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:

Рис. 16

·если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:

Рис.17

·простроенная схема называется «деревом игры», она показывает все возможные варианты, начиная с некоторого начального положения (для того, чтобы не загромождать схему, мы не рисовали другие варианты, если из какого-то положения есть выигрышный ход)

·в любой ситуации у игрока есть два возможных хода, поэтому от каждого узла этого дерева отходят две «ветки», такое дерево называется двоичным (если из каждого положения есть три варианта продолжения, дерево будет троичным)

·проанализируем эту схему; если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока

·кто же выиграет при правильной игре? для этого нужно ответить на вопросы: 1) «Может ли первый игрок выиграть, независимо от действий второго?», и 2) «Может ли второй игрок выиграть, независимо от действий первого?»

·ответ на первый вопрос – «да»; действительно, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу

·ответ на второй вопрос – «нет», потому что если первый игрок сначала убрал одну спичку, второй всегда проиграет, если первый не ошибется

·таким образом, при правильной игре выиграет первый игрок; для этого ему достаточно первым ходом убрать всего одну спичку

·в некоторых играх, например, в рэндзю (крестики-нолики на бесконечном поле) нет выигрышной стратегии, то есть, при абсолютно правильной игре обоих противников игра бесконечна (или заканчивается ничьей); кто-то может выиграть только тогда, когда его соперник по невнимательности сделает ошибку

·полный перебор вариантов реально выполнить только для очень простых игр; например, в шахматах сделать это за приемлемое время не удается (дерево игры очень сильно разветвляется, порождая огромное количество вариантов)

·в демо-вариантах ЕГЭ рекомендуется записывать дерево в виде таблицы (фактически, повернув его «на бок»), так получается более компактно:

Таблица 32

 

1 игрок

2 игрок

1 игрок

5

4

3

1

2

1

3

1

 

Пример задания:

Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Решение (вариант 1, полное дерево игры, «поиск в ширину»):

1)                     из каждой ситуации в этой игре возможно три продолжения, поэтому дерево получается троичным

2)                     по теореме Пифагора расстояние L от точки с координатами (x,y) до начала координат – это квадратный корень из суммы квадратов координат: ; чтобы избавиться от вычисления квадратного корня, нужно перейти от заданного условия  к равносильному условию в целых числах:

3)    в начальный момент , условие не выполнено

4)                     первый игрок имеет три варианта хода, запишем их в таблицу 33, указывая для каждого положения координаты (в скобках) и значение (мелким шрифтом);

Таблица 33

 

I игрок

(5,2) 29

(8,2) 68

(5,5) 50

(5,6) 61

5)                     видим, что одним ходом первый игрок никак не может выиграть (для всех вариантов )

 

I игрок

II игрок

(5,2) 29

(8,2) 68

(11,2) 125

(8,5) 89

(8,6) 100

(5,5) 50

(8,5) 89

(5,8) 89

(5,9) 106

(5,6) 61

(8,6) 100

(5,9) 106

(5,10) 125

6)                     построим следующий столбец таблицы 34 (ход второго игрока):

       Таблица 34

 

 

 

7)                      второй игрок тут тоже никак не может                                                 выиграть (для всех вариантов );

8)                     обратите внимание на варианты, выделенные в таблице 34 серым фоном: они уже встречались выше в этом же столбце (хотя получены в результате другой последовательности ходов), поэтому дальше не стоит их рассматривать отдельно

9)                     строим таблицу 35 для третьего хода (I-й игрок); для сокращения записи не будем выписывать все возможные ходы, если мы нашли выигрышный ход из этой позиции (выделен, синим фоном):

 

Таблица 35

 

I игрок

II игрок

I игрок

(5,2) 29

(8,2) 68

(11,2) 125

(14,2) 200

(8,5) 89

(11,5) 146

(8,8) 128

(8,9) 145

(8,6) 100

(11,6) 157

(8,9) 145

(8,10) 164

(5,5) 50

(8,5) 89

 

(5,8) 89

(5,12) 169

(5,9) 106

(5,12) 169

(5,6) 61

(8,6) 100

 

(5,9) 106

 

(5,10) 125

(5,13) 196

10)           видим, что в некоторых случаях первый игрок может выиграть уже на втором ходу, однако это не гарантируется, значит, нельзя утверждать, что первый игрок всегда выиграет

11)           легко проверить, что во всех оставшихся позициях (если первый не выиграл) второй игрок выигрывает своим следующим ходом:

Таблица 36

 

I игрок

II игрок

I игрок

II игрок

(5,2) 29

(8,2) 68

(11,2) 125

(14,2) 200

 

(8,5) 89

(11,5) 146

(14,5) 221

(8,8) 128

(11,8) 185

(8,9) 145

(11,9) 202

(8,6) 100

(11,6) 157

(14,6) 232

(8,9) 145

 

(8,10) 164

(11,10) 221

(5,5) 50

(8,5) 89

 

 

(5,8) 89

(5,12) 169

 

(5,9) 106

(5,12) 169

 

(5,6) 61

(8,6) 100

 

 

(5,9) 106

 

 

(5,10) 125

(5,13) 196

 

12)                теперь осталось выполнить самое главное – сделать анализ этой таблицы и определить, кто же выиграет, если оба играют лучшим для себя образом

13)                из таблицы следует, что второй игрок выигрывает (своим вторым ходом), если ему удастся свести ситуацию к положению (8,5) или (8,6)

14)                далее замечаем, что при любом ходе первого игрока второй может добиться нужной ему позиции (показаны варианты в зависимости от первого хода):

(8,2)→(8,5)

(8,2)→(8,6)

или

(5,5)→(8,5)

или

(5,6)→(8,6)

и выиграть вторым ходом

15)                таким образом, при правильной игре выиграет второй игрок, для этого при любом ходе первого игрока ему достаточно свести ситуацию к положению (8,5) или (8,6); такая возможность у него есть.

Возможные проблемы:

·   нужно уметь правильно считать, часто в работах встречаются арифметические ошибки, которые приводят к неверному решению

·   таблица получается довольно громоздкой, чтобы не запутаться, лучше оставлять в ней только те данные, которые действительно влияют на решение (как мы делали выше)

·   необходимо проверить, при любом ли ходе первого игрока второй игрок (в нашей задаче) может получить нужную для себя ситуацию; например, мог быть вариант, когда для первого хода (5,5) при любом ходе второго игрока выигрывал первый, это означало бы, что при правильной игре первый всегда победит

 

Как правильно оформить решение:

·   нужно обязательно написать ответ СЛОВАМИ, например, «Выиграет игрок, который делает второй ход»

·   нужно обязательно привести ВСЕ варианты ходов первого игрока и доказать, что во всех случаях у второго (в данной задаче!) есть выигрышный ход

·   в решении должна быть СЛОВАМИ описана стратегия игры второго игрока «как он должен играть, чтобы выиграть)

·   рекомендуется записывать ходы в таблицу, точно совпадающую с той, которая приводится в официальном решении демо-варианта; для эксперта этот вариант будет гарантированно понятен и привычен

Итак, у нас получилось, что выигрывает второй игрок. В ответе на каждом ходу нужно привести все возможные ходы первого игрока, и на каждый из этих ходов дать выигрышный ответ второго.  В первом столбце стандартной таблицы записываем начальную позицию. Из этого положения у I-ого игрока есть 3 варианта хода, записываем их во второй  столбец:

Таблица 37

 

1-й ход

2-й ход

3-й ход

4-й ход

стартовая позиция

I-й игрок (все варианты хода)

II-ой игрок, выигрышный ход

I-й игрок (все варианты хода)

II-ой игрок, выигрышный ход

(5,2) 29

(8,2) 68

 

 

 

(5,5) 50

 

 

 

(5,6) 61

 

 

 

Обратите внимание, что мы перечислили все возможные ходы I-ого игрока, как и требуется.

Теперь на каждый возможный ход I-ого игрока во втором столбце записываем выигрышный ответ II-ого, то есть, такой ответ, который приводит второго к выигрышу, и подчеркиваем его (или как-то выделяем по-другому, чтобы показать, что это выигрышный ход):

Таблица 38

 

1-й ход

2-й ход

3-й ход

4-й ход

стартовая позиция

I-й игрок (все варианты хода)

II-ой игрок, выигрышный ход

I-й игрок (все варианты хода)

II-ой игрок, выигрышный ход

(5,2) 29

(8,2) 68

(8,5) 89

 

 

(5,5) 50

(8,5) 89

 

 

(5,6) 61

 (8,6) 100

 

 

В четвертом столбце нужно перечислить все варианты (обязательно все!) второго хода I-ого игрока в ответ на указанный выигрышный ход второго:

Таблица 39

 

1-й ход

2-й ход

3-й ход

4-й ход

стартовая позиция

I-й игрок (все варианты хода)

II-ой игрок, выигрышный ход

I-й игрок (все варианты хода)

II-ой игрок, выигрышный ход

(5,2) 29

(8,2) 68

(8,5) 89

(11,5) 146

 

(8,8) 128

 

(8,9) 145

 

(5,5) 50

(8,5) 89

(11,5) 146

 

(8,8) 128

 

(8,9) 145

 

(5,6) 61

 (8,6) 100

(11,6) 157

 

(8,9) 145

 

(8,10) 164

 

Остается добавить в последний столбец (один!) выигрышный ход II-ого игрока. Обратите внимание, что для выигрывающего игрока,  достаточно указать только один выигрышный ход, а для проигравшего нужно рассмотреть все ходы на каждом шаге.

Таблица 40

 

1-й ход

2-й ход

3-й ход

4-й ход

стартовая позиция

I-й игрок (все варианты хода)

II-ой игрок, выигрышный ход

I-й игрок (все варианты хода)

II-ой игрок, выигрышный ход

(5,2) 29

(8,2) 68

(8,5) 89

(11,5) 146

(14,5) 221

(8,8) 128

(11,8) 185

(8,9) 145

(11,9) 202

(5,5) 50

(8,5) 89

(11,5) 146

(14,5) 221

(8,8) 128

(11,8) 185

(8,9) 145

(11,9) 202

(5,6) 61

 (8,6) 100

(11,6) 157

(14,6) 232

(8,9) 145

(11,9) 202

(8,10) 164

(11,10) 221

После таблицы обязательно опишите стратегию игры словами:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 «Основы логики и логические основы компьютера» – один из разделов, изучаемых в рамках школьного курса  «Информатика и ИКТ» на базовом и  профильном уровнях.

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

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

При подготовке к ЕГЭ по информатике необходимо совершенствовать методику подготовки к ЕГЭ по разделу «Основы логики и логические основы компьютера», так как анализ результатов ЕГЭ за предыдущие годы выявляет определенные трудности, которые возникают перед учащимися.

В работе представлен разбор заданий ЕГЭ (приложения) по разделу «Основы логики», взятые из демо-версий ЕГЭ по информатике последних лет (2004 -2009 гг.).

Таким образом, в результате проделанной работы была достигнута цель и решены поставленные задачи.

 

СПИСОК ЛИТЕРАТУРЫ

1.                 Босова Л.Л. Арифметические и логические основы ЭВМ. Серия «Информатика в школе» — М.: Информатика и образование, 2000.

2.                 Дергачева Л.М., и др. Тематические задания для подготовки к ЕГЭ по информатике. Журнал «Информатика в школе» №5-2010. Задания для подготовки к итоговой аттестации по информатике в IX и XI классах — М.: Образование и информатика, 2010.

3.                 ЕГЭ 2009. Информатика. Сборник экзаменационных заданий. /П.А. Якушкин, С.С. Крылов — М.: Эксмо, 2009.

4.                 Информатика и ИКТ. Подготовка к ЕГЭ. / Под ред. проф. Н.В. Макаровой

— Спб: Питер, 2007.

5.                 Казиев В.М. Готовимся к ЕГЭ по информатике. Информатика в школе. Приложение к журналу «Информатика и образование» №2-2006 — М.: Образование и информатика, 2010.

6.                 Кошелев М.В. Итоговые тесты по информатике: 10-11 классы: к учебникам Н.Д. Угриновича «Информатика и информационные технологии: 10-11 класс» и А.Г. Гейна, и др. «Информатика: 10-11 классы» — М.: Издательство «Экзамен», 2006.

7.                 Лыскова В.Ю., Ракитина Е.А. Логика в информатике — М.: Лаборатория Базовых Знаний, 2001.

8.                 Лыскова В.Ю., Ракитина Е.А. Логика в информатике. Серия «Информатика в школе». — М.: Информатика и образование, 1999.

9.                 Пустоваченко Н.Н. Решение логических задач. Информатика в школе: Приложение к журналу «Информатика и образование» №6-2005 — М.: Образование и информатика, 2005.

10.              Н.Н. Самылкина, и др. Материалы для подготовки к экзамену по информатике — М.: БИНОМ, Лаборатория знаний, 2006.

11.              Сафронов И.К. Готовимся к ЕГЭ. Информатика — Спб: БХВ-Петербург, 2007.

12.              Угринович Н.Д.  Информатика и ИКТ. Профильный уровень: учебник для 10 класса —  М.: БИНОМ. Лаборатория знаний, 2008.

13.              Хан А.К. Способы решения логических задач — Информатика и образование, №5-2003.

14.              Шауцукова Л.З. Информатика: учебное пособие для 10-11 класса общеобр. учреждений — М.: Просвещение, 2000.

15.              Шевченко Н.Е. Некоторые способы решения логических задач — Киев: Выща школа, Головное изд-во, 1979.

Ресурсы в Интернете

16.              Федеральный институт педагогических измерений http://www.fipi.ru/

17.              Сайт информационной поддержки ЕГЭ http://www.ege.ru/

18.              Задачи для подготовки к ЕГЭ http://www.aktanish.ru/edu/school/aktsh3/info/ege.htm

19.              Вики-учебник для подготовки к ЕГЭ/Информатика/Основы логики

http://letopisi.ru/index.php/Викиучебник_для_подготовки_к_ЕГЭ/Информатика /Основы_логики

20.              Электронный учебник «Подготовка к ЕГЭ по логике».

http://pedsovet.su/load/51-1-0-1454

21.              Публикация материалов для подготовки к ЕГЭ по информатике http://kpolyakov.narod.ru/ege.htm

22.              Лопатина Н.С. Вопросы по основам логики в ЕГЭ.

http://www.it-n.ru/board.aspx?cat_no=73740&tmpl

23.              Презентация «Логика» http://kpolyakov.narod.ru/ppt.html

24.              Логика (программа-тренажер для обучения матлогики) http://kpolyakov.narod.ru/prog/logic.htm

 

 

ПРИЛОЖЕНИЯ

Приложения включают в себя — описание материалов, представленных на CD-диске:

· ЭОР «Способы решения логических задач»;

· Презентация «Логика»;

· Электронный учебник «Логика в ЕГЭ» («Подготовка к ЕГЭ по логике»);

· Задачи ЕГЭ «Основы логики» (интерактивный задачник по книге Сафонова «Готовимся к ЕГЭ»);

· Задания по логике (представлены задания из сборника экзаменационных заданий ЕГЭ 2009г. П.А. Якушкин, в конце даны ответы);

· Логика (Logic: программа-тренажер для обучения основам математической логики);

· Логика в вопросах ЕГЭ (решение заданий, представленных в ЕГЭ, с представленными заданиями для тренировки).

 

1.               ЭОР «Способы решения логических задач».  В связи с тем, что логические задачи в литературе по информатике публикуются в небольшом количестве (исходя из анализа). Поэтому, используя материал приложения к журналу «Информатика и образование» №6-2005: Логические задачи как форма контроля знаний,  в данной работе была предпринята попытка сбора, систематизации и оформления логических задач в Электронный Образовательный Ресурс.

Данный ЭОР по теме «Способы решения логических задач» предназначен для учащихся и всех тех, кто хочет в совершенстве овладеть разделом «Основы логики» и научиться самостоятельно решать логические задачи. ЭОР содержит задачи и рассмотрены различные способы их решения.

Содержание: РЛЗ с помощью логических рассуждений; РЛЗ табличным способом; РЛЗ графическим методами; РЛЗ средствами алгебры логики; Другие типы ЛЗ.

2.               Презентация «Логика». Презентация, с сайта http://kpolyakov.narod.ru/ppt.html, в которой рассмотрены следующие основные темы: «Логические выражения и операции»; «Диаграммы»; «Преобразование логических выражений»; «Синтез логических выражений»; «Логические элементы компьютера»; «Логические задачи».

 

 

 

 

 

 

 

 

 

 

 

 

Рис.18.  Вид первого слайда презентации

3.               Электронный учебник «Логика в ЕГЭ» («Подготовка к ЕГЭ по логике»). В электронном учебнике «Подготовка к ЕГЭ по логике» разбираются задания по логике, встречающиеся в ЕГЭ с 2004-2009гг. В данном материале предлагаются аналогичные задания для части А и В с подробными решениями и ответами, а также предложены задачи для тренировки, которые требуется решить самостоятельно, затем проверить.

Для решения задач приведена таблица законов логики; представлен флеш-ролик для демонстрации решения задачи табличным способом.

Рис.19.  ЭУ_Логика в ЕГЭ

 

 

 

 

 

 

 

 

4.               Задания по логике: представлены задания из сборника экзаменационных заданий ЕГЭ 2009г. П.А. Якушкин, в конце даны ответы.

5.               Задачи ЕГЭ «Основы логики» (интерактивный задачник по книге Сафонова «Готовимся к ЕГЭ»). Предлагаемое пособие (ресурс) включает задания из демо-версий ЕГЭ 2004-2009 г.г., в котором включены более 50 задач по теме «Основы логики». Интерактивный ролик оформлен так, что учитель может использовать как в классе на уроке, предъявляя постановку задачи на большом экране (интерактивной доске через проектор), обсуждая ее решение со всей группой учащихся, так и на рабочем месте ученика (самостоятельный выбор задачи для ее решения). Учитель сам может продиктовать набор задач для контроля освоения темы по цветовым индикаторам (ресурса) решенных задач, выставить оценку за работу на уроке, указав заранее критерий количественного оценивания.

Интерфейс тест - программы с пояснениями на рисунке, расположенном на рисунке 20.

6.               Логика в вопросах ЕГЭ: решение заданий, представленных в ЕГЭ (с сайта http://kpolyakov.narod.ru/ege.htm) по теме «Основы логики»:

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

Рис.20

Интерфейс

тест - программы

7.               Логика: программа-тренажер для обучения основам математической логики.  Тренажер «Логика» предназначен для проведения практических занятий по теме «Математическая логика» в игровой форме. Программа работает под управлением операционных систем Windows 95/98/NT/2000/XP/2003 на любых современных компьютерах. Программа является бесплатной для некоммерческого использования. Исходные тексты программы не распространяются. Программа содержит конструктор, позволяющий создавать новые схемы и подключать их в качестве уровней. Здесь можно скачать готовые схемы всех уровней, а также схемы триггеров на элементах «И-НЕ» и «ИЛИ-НЕ».

Достоинства

·игровая форма закрепления учебного материала;

· программа имеет встроенный набор логических схем (задач) для каждого из 10 уровней;

· существует возможность составлять новые схемы и проверять их работу, не выходя из программы;                                                              Рис.21. Вид программы

· с каждым уровнем можно связать свою схему; список нестандартных схем хранится в файле инициализации LOGIC.INI; таким образом, можно составить несколько ini-файлов с разнотипными заданиями;

· кроме стандартного набора логических элементов (И, ИЛИ, НЕ) в схемах можно использовать включенные (непонятно почему) в школьную программу элементы «импликация», «эквивалентность», а также полусумматор, сумматор и RS-триггер.

 

Правила игры

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

Для управления механизмами используют выключатели в левой части поля. Их состояние изменяется щелчком мыши. Если выключатель включен, по цепи идет ток и поступает на логические схемы, включенные в эту цепь (средняя часть поля). Логические схемы преобразуют входные сигналы по следующим правилам:

·схема НЕ: на выходе будет ток (сигнал 1), если на входе тока нет (сигнал 0), и наоборот;

·схема И: на выходе будет 1, если на обоих входах 1;

·схема ИЛИ: на выходе будет 1, если хотя бы на одном входе 1;

·схема XOR (исключающее ИЛИ): на выходе будет 1, если только на одном входе 1;

·схема импликация (1→2): на выходе будет 0, если на первом входе 1, а на втором — 0; иначе на выходе 1;

·схема эквивалентность (↔): на выходе будет 1, если оба входа равны; иначе на выходе 0.

 Кристалл нельзя передавать сразу через несколько «пролетов» — в этом случае он разбивается и приходится начинать уровень заново. Кроме того, у вас есть только 5 кристаллов на всю игру, если вы разобьете их все, задание считается невыполненным.

 

Просмотрено: 0%
поделиться в vk поделиться в одноклассниках поделиться в майлру
Просмотрено: 0%
Скачать материал
поделиться в vk поделиться в одноклассниках поделиться в майлру
Скачать материал "ВКР "Раздел "Основы логики и логические основы компьютера" в ЕГЭ по информатике""
Как учитель может зарабатывать на Инфоуроке?

Методические разработки к Вашему уроку:

Получите новую специальность за 2 месяца

Копирайтер

Получите профессию

Фитнес-тренер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 656 262 материала в базе

Найти материалы
Скачать материал

Другие материалы

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 14.09.2021 1488
    • DOCX 2.3 мбайт
    • 15 скачиваний
    • Оцените материал:

  • Настоящий материал опубликован пользователем Яранцева Наталья Владимировна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

    Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

    Удалить материал

  • Автор материала

    Яранцева Наталья Владимировна
    Яранцева Наталья Владимировна
    • На сайте: 8 лет и 11 месяцев
    • Подписчики: 1
    • Всего просмотров: 83724
    • Всего материалов: 53

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой

Курс профессиональной переподготовки

HR-менеджер

Специалист по управлению персоналом (HR- менеджер)

500/1000 ч.

Подать заявку О курсе

Курс повышения квалификации

Применение компьютерных моделей при обучении математике и информатике в рамках ФГОС ООО

72 ч. — 180 ч.

от 2200 руб. от 1100 руб.
Подать заявку О курсе
  • Сейчас обучается 50 человек из 29 регионов
  • Этот курс уже прошли 177 человек

Курс профессиональной переподготовки

Теория и методика обучения информатике в начальной школе

Учитель информатики в начальной школе

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 95 человек из 34 регионов
  • Этот курс уже прошли 222 человека

Курс повышения квалификации

Особенности подготовки к сдаче ЕГЭ по информатике и ИКТ в условиях реализации ФГОС СОО

36 ч. — 180 ч.

от 1700 руб. от 850 руб.
Подать заявку О курсе
  • Сейчас обучается 106 человек из 42 регионов
  • Этот курс уже прошли 576 человек

Мини-курс

Современные направления в архитектуре

6 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Практические аспекты работы логопеда: методы и приемы в логоритмике

2 ч.

780 руб. 390 руб.
Подать заявку О курсе
  • Сейчас обучается 22 человека из 13 регионов
  • Этот курс уже прошли 18 человек

Мини-курс

Управление проектами: концепции, практика и финансы

6 ч.

780 руб. 390 руб.
Подать заявку О курсе