Имя материала: Методика преподавания информатики

Автор: М.П.ЛАПЧИК

8.4. язык логики и его место в базовом курсе

 

Подходы к раскрытию темы в учебной литературе

 

Логика — наука, изучающая методы установления истинности или ложности одних высказываний на основе истинности или ложности других высказываний. Основы логики как науки были заложены в IV в. до н.э. древнегреческим ученым Аристотелем. Правила вывода истинности высказываний, описанные Аристотелем (силлогизмы) оставались основным инструментом логики вплоть до второй половины XIX в., когда в трудах Дж. Буля, О. де Моргана и др. возникла математическая логика. Средствами этой новой науки все прежние достижения логики были переведены на точный язык математики. Развивается аппарат алгебры логики (булевой алгебры), исчисления высказываний, исчисления предикатов. Развитие математической логики имело большое значение для всей математической науки, повысив уровень ее строгости и доказательности.

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

• процедурно-алгоритмическом;

• в логическом программировании;

• схемотехническом.

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

Впервые в школьной информатике элементы логического программирования языка Пролог были включены в учебник [19]. Согласно авторской концепции одной из главных задач школьной информатики должно быть развитие логического мышления учащихся, умения рассуждать, доказывать, подбирать факты, аргументы и обосновывать предлагаемые решения. Как известно, парадигма логического программирования является альтернативной к процедурной парадигме. В механизме вывода Пролога используется аппарат исчисления предикатов.

В контексте моделирования знаний элементы логического программирования присутствуют в учебнике [9]. В первой части учебника рассказывается лишь об идее построения логической модели знаний. Реализация этой идеи на Прологе раскрывается во второй части, ориентированной на углубленное изучение базового курса.

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

Тема логических схем элементов ЭВМ присутствует в учебниках [17, 19]. Обширный материал по использованию математической логики в курсе информатики содержится в пособии для учителя [14]. Практический материал по теме «Логическая информация и основы логики» имеется в учебном пособии [10].

Методические рекомендации по изучению темы

Изучаемые вопросы:

ª Логические величины, операции, выражения.

ª Математическая логика в базах данных.

ª Математическая логика в электронных таблицах.

ª Математическая логика в программировании.

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

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

Высказывание (суждение) — это повествовательное предложение, в котором что-либо утверждается или отрицается. По поводу любого высказывания можно сказать, истинно оно или ложно. Например:

«Лед — твердое состояние воды» — истинное высказывание.

«Треугольник, это геометрическая фигура» — истинное высказывание.

«Париж — столица Китая» — ложное высказывание.

6 < 5 — ложное высказывание.

Логические величины: понятия, выражаемые словами: ИСТИНА, ЛОЖЬ (true, false). Следовательно, истинность высказываний выражается через логические величины.

Логическая константа: ИСТИНА или ЛОЖЬ.

Логическая переменная: символически обозначенная логическая величина. Следовательно, если известно, что А, В, X, У и пр. — переменные логические величины, то это значит, что они могут принимать значения только ИСТИНА или ЛОЖЬ.

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

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

Конъюнкция (логическое умножение). В русском языке она выражается союзом И. В математической логике используются знаки & или Ù. Конъюнкция — двухместная операция; записывается в виде: А Ù В. Значение такого выражения будет ЛОЖЬ, если значение хотя бы одного из операндов ложно.

Дизъюнкция (логическое сложение). В русском языке этой связке соответствуют союз ИЛИ. В математической логике она обозначается знаком Ú. Дизъюнкция — двухместная операция; записывается в виде: A Ú В. Значение такого выражения будет ИСТИНА, если значение хотя бы одного из операндов истинно.

Отрицание. В русском языке этой связке соответствует частица НЕ (в некоторых высказываниях применяется оборот «неверно, что...»). Отрицание — унарная (одноместная) операция; записывается в виде: ØА или А̅.

Логическая формула (логическое выражение) — формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА или ЛОЖЬ.

 

Пример 1. Рассмотрим сложное высказывание: «Число 6 делится на 2, и число 6 делится на 3». Представить данное высказывание в виде логической формулы.

Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда соответствующая логическая формула имеет вид: А & В. Очевидно, ее значение — ИСТИНА.

 

Пример 2. Рассмотрим сложное высказывание: «Летом я поеду в деревню или в туристическую поездку».

Обозначим через А простое высказывание «летом я поеду в деревню», а через В — простое высказывание «летом я поеду в туристическую поездку». Тогда логическая форма сложного высказывания имеет вид A Ú В.

 

Пример 3. Рассмотрим высказывание: «Неверно, что 4 делится на 3».

Обозначим через А простое высказывание «4 делится на 3». Тогда логическая форма отрицания этого высказывания имеет вид ØА.

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

Таблица 8.2

 

 

А

В

Ø

А&В

AÚ В

1

и

и

л

и

и

2

и

л

л

л

и

3

л

и

и

л

и

4

л

л

и

л

л

 

Последовательность выполнения операций в логических формулах определяется старшинством операций. В порядке убывания старшинства логические операции расположены так: отрицание, конъюнкция, дизъюнкция. Кроме того, на порядок операции влияют скобки, которые можно использовать в логических формулах. Например: (А и Б) или (не А и В) или (не А и не Б)

 

Пример 4. Вычислить значение логической формулы:

не X и Y  или Х и Z,

если логические переменные имеют следующие значения: X = = ЛОЖЬ, Y = ИСТИНА, Z = ИСТИНА.

Отметим цифрами сверху порядок выполнения операций в выражении:

1243 не X и Y или X и Z.

Используя таблицу истинности, вычислим формулу по шагам:

1) не ЛОЖЬ = ИСТИНА;

2) ИСТИНА и ИСТИНА = ИСТИНА;

3) ЛОЖЬ и ИСТИНА = ЛОЖЬ;

4) ИСТИНА или ЛОЖЬ = ИСТИНА. Ответ: ИСТИНА.

 

Приложения математической логики в базовом курсе

 

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

Первое понятие о логической величине можно дать как ответ на альтернативный вопрос. Например: «Имеется ли данная книга в библиотеке?» или «Поступил ли абитуриент в университет», или «На улице идет дождь?» и т.п. Ответами на такие вопросы могут быть только «да» или «нет». Синонимами являются «истина», «ложь»; «true», «false». Если поле таблицы будет принимать только такие значения, то ему назначается логический тип.

Например, реляционная база данных ФАКУЛЬТАТИВЫ содержит сведения о посещении учениками трех факультативов по геологии, цветоводству и танцам. На реляционном языке ее структура описывается так:

ФАКУЛЬТАТИВЫ (УЧЕНИК. ГЕОЛОГИЯ,

ЦВЕТОВОДСТВО, ТАНЦЫ)

Поля ГЕОЛОГИЯ, ЦВЕТОВОДСТВО и ТАНЦЫ будут иметь логический тип. Значение ИСТИНА для каждого поля обозначает, что ученик посещает данный факультатив, а ЛОЖЬ — не посещает.

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

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

Основная проблема — научить учеников формальному представлению условий поиска в виде логических выражений. Например, от фразы «найти все книги, лежащие выше пятой полки» нужно перейти к логическому выражению: ПОЛКА > 5; или условие «выбрать всех неуспевающих по физике» представить в виде: ФИЗИКА < 3; или «выбрать все дни, когда шел дождь»: ОСАДКИ = «дождь».

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

Сложные логические выражения содержат в себе логические операции. Рассматриваются три основные операции математической логики: конъюнкция (И), дизъюнкция (ИЛИ), отрицание (НЕ).

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

• А и В истинно только в том случае, если истинны оба операнда;

• А или В ложно только в том случае, если ложны оба операнда;

• не А меняет значение логической величины на противоположное: не истина — ложь; не ложь — истина.

Эти правила отражены в таблице истинности.

При переходе к составлению условий поиска в базах данных ученики нередко попадают в «ловушки естественного смысла». Например, рассматривается база данных БИБЛИОТЕКА со сведениями о книгах в личной библиотеке, которая имеет следующую структуру:

 

БИБЛИОТЕКА (НОМЕР. АВТОР, НАЗВАНИЕ, ГОД, ПОЛКА)

Требуется получить сведения обо всех книгах Толстого и Тургенева. Абсолютное большинство учеников записывают это условие следующим образом:

АВТОР = «Толстой» и АВТОР = «Тургенев»

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

АВТОР = «Толстой» или АВТОР = «Тургенев»

Тогда будет получена искомая выборка книг обоих авторов.

Операция ИЛИ объединяет в одну выборку записи, удовлетворяющие каждому из условий. Операция И работает иначе: сначала выбираются все записи, удовлетворяющие первому условию, затем из отобранных записей выбираются те, которые удовлетворяют второму условию.

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

Таблица 8.3

 

 

Записи

Поля

А

В

С

R1

1

1

3

R2

1

3

1

R3

2

2

2

R4

3

3

3

R5

3

2

3

 

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

Условие:                                                                               Ответ

1) А = 1 и В = 2                                                     :R1

2) А = 1 или А = 3                                                :R1, R2, R4, R5

3) А = 1 или В = 2                                                :R1, R2, R3, R5

4) Л = 1 или В = 2 или С = 3                               :R1, R2, R3, R4, R5

5)А = 1и В = 2 и С=3                                           :R1

6) не А = 1                                                                             :R1, R4, R5

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

7) А = 1 и В = 1 или С = 3                   :R1, R4, R5

8) А = 1 или В = 2 и С = 3                   :R1, R2, R5

9) не А = 1 или В = 2 и С = 3                              :R1, R3, R4, RS

10) (Л = 1 или В = 2) и С = 3                               :R1, R5

После решения таких формальных задач следует снова вернуться к содержательным задачам. Теперь ученики будут гораздо успешнее формализовывать сложные условия поиска в логические выражения. Например, требуется выбрать все книги Беляева и Толстого, расположенные от 2-й до 5-й полки. Логическое выражение запишется так:

(АВТОР = «Толстой Л.Н.» или АВТОР = «Беляев А.Р.») и ПОЛКА >= 2 и ПОЛКА <= 5

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

Если в клетку заносится условная функция, то на экране отображается результат ее вычисления, т.е. то или иное значение в зависимости от условия, заданного логическим выражением. Обычно условная функция имеет такую структуру:

IF(условие, действие1, действие2).

Здесь «условие» — логическое выражение. Если условие истинно, то выполняется действие1, иначе — действие2. Простое логическое выражение представляет собой отношение (в том же смысле, в котором это понятие используется в базах данных). Сложное логическое выражение содержит логические операции.

Особенность логических выражений для электронных таблиц заключается в том, что логические операции используются как функции: сначала записывается имя логической операции: И, ИЛИ, НЕ (AND, OR, NOT), а затем в круглых скобках перечисляются логические операнды. Например, логическое выражение

AND (А1 > 0, А1 < 1)

соответствует математической системе неравенств: 0 < А1 < 1.

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

                               

В ячейке таблицы соответствующая условная функция запишется так:

IF (AND (A1 > -1, А1 < 1), ABS (А1), 1).

Логические формулы могут размещаться в ячейках ЭТ сами по себе, без использования условной функции. В таком случае в данной ячейке будет отражаться логическое значение ИСТИНА или ЛОЖЬ. Например, если в ячейке С6 хранится сумма баллов, набранная абитуриентом на вступительных экзаменах, а проходной балл в институт равен 14, то, поместив в ячейку D6 формулу: С6>= 14, получим в этой ячейке значение ИСТИНА, в случае если абитуриент поступил в институт, и ЛОЖЬ — если нет.

Математическая логика в программировании. В большинстве современных процедурных языков программирования высокого уровня (ЯПВУ) имеется логический тип данных, реализованы основные логические операции. Использование этих средств позволяет решать на ЭВМ сложные логические задачи, моделировать логику человеческого мышления в программных системах искусственного интеллекта. В программах решения задач с математическим содержанием логические выражения чаще всего применяются для описания систем неравенств (отношений). Решая задачи такого типа, ученики прежде всего должны проявить знания математики, а затем уже — умение переложить математические отношения на язык логики и оформить решение задачи на языке программирования.

 

Пример. Составить программу на Паскале, по которой выведется значение true, если точка с заданными координатами (х, у) лежит внутри заштрихованной области (рис. 8.1), и false — в противном случае.

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

1-я часть: x £ 0; x2 + y2 £ 9;  y ³ - x - 3

2-я часть: х > 0; х2 + у2 < 25.

Точка с координатами (х, у) лежит в заштрихованной области, если она принадлежит 1-й или 2-й части.

                       

 

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

Program Point;

var X,Y: real; L: boolean;

begin

write('Введите X:'); readln(X);

write('Введите Y:'); readln(Y);

L: = (X <= 0) and (Sqr(X)+ Sqr(Y) <= 9) and(Y >= -X-3)

or (X >= 0) and (Sqr(X) + Sqr(Y)<= 25)

writeln('Точка лежит в заданной области?', L)

end.

 

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

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 |