Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)
§8. Логика и компьютеры.
Что такое высказывание?
Ключевые слова:
• логика • формальная логика • логическое высказывание • алгебра логики • логические переменные • логическая операция • операция «НЕ» • операция «И» • операция «ИЛИ» • логическая функция
В быту мы часто используем слова «логика», «логично». Логика (наука о рассуждении) — это наука о том, как правильно рассуждать, делать выводы, доказывать утверждения.
В естественном языке рассуждения связаны с самыми разными предметами и понятиями, и поэтому изучать их достаточно сложно. Древнегреческий философ Аристотель начал изучать общие правила построения правильных выводов из известной информации, которая считается истинной. Такая логика называется формальной, она изучает истинность и ложность логических высказываний, отвлекаясь от их содержания.
Логическое высказывание — это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно.
Используя это определение, проверим, можно ли считать логическими высказываниями следующие предложения:
1) Сейчас идёт дождь.
2) Вчера жирафы улетели на север.
3) Беги сюда!
4) Который час?
5) В городе N живёт более 2 миллионов человек.
6) У квадрата 10 сторон, и все разные.
7) История — интересный предмет.
Здесь высказываниями являются только предложения 1, 2 и 6, остальные не подходят под определение. Предложения 3 и 4 не повествовательные (призыв к действию и вопрос). Предложение 5 станет высказыванием только в том случае, если N заменить на название конкретного города. Утверждение 7 кто-то считает истинным, а кто-то — ложным (нет однозначности), его можно более строго сформулировать в виде «По мнению N, история — интересный предмет». Для того чтобы оно стало высказыванием, нужно заменить N на имя человека.
Используя определение, проверьте, являются ли логическими высказываниями предложения:
1) Лошади едят сено.
2) Карету мне, карету!
3) Где расположен Канин Нос?
4) Восемью три — двенадцать.
5) Программировать очень просто.
Логика и компьютеры тесно связаны.
В классической формальной логике высказывание может быть истинно или ложно, третий вариант исключается 1). Если обозначить истинное значение единицей, а ложное — нулём, то получится, что формальная логика изучает правила выполнения операций с нулями и единицами, т. е. с двоичными кодами. Оказалось, что всю обработку двоичных данных можно свести к выполнению логических операций.
1) Существуют неклассические логические системы, например трёхзначная логика, где кроме «истинно» и «ложно» есть ещё состояние «не определено» (или «возможно»).
Важный шаг в этом направлении сделал английский математик Джордж Буль. Буль впервые ввёл в науку двоичные переменные, принимающие только два значения — «истина» и «ложь», — и три основные логические операции: НЕ, И, ИЛИ. Кроме того, он предложил применить для исследования логических высказываний методы алгебры. Позже этот раздел математики получил название алгебры логики, или алгебры высказываний. Ещё его называют булевой алгеброй (по имени Дж. Буля).
Алгебра логики — это математический аппарат, с помощью которого записывают, упрощают и преобразуют логические высказывания, вычисляют их значения.
Алгебра логики определяет правила выполнения операций с логическими значениями «ложь» и «истина». Если обозначить эти значения как 0 и 1, то получается, что с помощью алгебры логики можно описать алгоритмы работы с двоичными данными. Например, так можно построить запоминающие элементы и выполнять арифметические действия.
Используя дополнительные источники, выясните, как называлась основная научная работа Дж. Буля и в каком году она была написана. Сколько лет было тогда учёному?
Простые и сложные высказывания
Высказывания бывают простые и сложные (составные). Простые высказывания нельзя разделить на более мелкие высказывания, например: «Сейчас идёт дождь» или «Форточка открыта». Сложные (составные) высказывания строятся из простых с помощью логических связок — логических операций НЕ, И, ИЛИ.
В алгебре логики высказывания обычно обозначаются латинскими буквами. Таким образом, мы уходим от конкретного содержания высказываний, нас интересует только их истинность или ложность. Например, можно обозначить буквой А высказывание «Сейчас идёт дождь», а буквой В — высказывание «Форточка открыта».
Так как высказывания могут быть истинными или ложными, введённые символы А и В можно рассматривать как логические переменные, которые могут принимать два возможных значения: «ложь» (0) и «истина» (1). Из них строятся сложные высказывания:
не А = Неверно, что сейчас идёт дождь.
А и В = Сейчас идёт дождь и открыта форточка.
А или В = Сейчас идёт дождь или открыта форточка.
Если и другие логические операции, но НЕ, И и ИЛИ используются чаще всего. Оказывается, с их помощью можно выразить любую логическую операцию, поэтому эти три операции можно считать основными, базовыми, и говорят, что они составляют базис.
Различные устройства компьютера строятся на основе элементов, выполняющих логические операции НЕ, И, ИЛИ.
При введённых выше обозначениях А и В запишите на русском языке высказывания:
а) не В; б) (не А) и В; в) А или (не В).
При тех же обозначениях запишите в символьном виде высказывания:
а) «Неверно, что сейчас идёт дождь и открыта форточка».
б) «Неверно, что сейчас идёт дождь или закрыта форточка».
Операция НЕ
Операция НЕ часто называется отрицанием или инверсией. В алгебре логики всего два возможных значения (0 и 1), поэтому логическое отрицание — это переход от одного значения к другому: от 1 к 0 или наоборот. Если высказывание А истинно, то НЕ А ложно, и наоборот.
Используя дополнительные источники, переведите на русский язык слово inverse, от которого произошло слово «инверсия».
Операцию НЕ обозначают чертой сверху, например: А.
В школьном алгоритмическом языке 1) эта операция обозначается словом не, а в языке программирования Паскаль — английским словом not.
1) Вспомним, что мы договорились называть его просто «алгоритмический язык».
Используя дополнительные источники, найдите другие обозначения операции НЕ.
Операцию НЕ можно задать в виде таблицы (рис. 2.1).
Рис. 2.1
Эта таблица состоит из двух частей:
слева перечисляются все возможные значения исходной величины (их всего два — 0 и 1), а в последнем столбце записывают результат выполнения логической операции для каждого из этих вариантов. Такая таблица называется таблицей истинности логической операции. Таблица истинности задаёт логическую функцию.
Логическая функция — это правило преобразования входных логических значений в логическое значение-результат.
Используя таблицу истинности на рис. 2.1, определите, как можно упростить выражение не (не А). Рассмотрите оба варианта: когда А = 0 и когда А = 1. Сделайте вывод.
Операция И
Из двух простых высказываний А и В (например, А = Сейчас идёт дождь, В = Форточка открыта) можно составить сложное высказывание А и B. Высказывание А и B истинно в том и только в том случае, когда оба высказывания, А и B, истинны одновременно.
Для понимания операции И можно представить себе простую схему, в которой для включения лампочки используются два выключателя, соединённых последовательно (рис. 2.2).
Рис. 2.2
Чтобы лампочка загорелась, нужно обязательно включить оба выключателя. Вместе с тем, чтобы выключить лампочку, достаточно выключить любой из них.
Операция И (в отличие от НЕ) выполняется с двумя логическими значениями. В алгоритмическом языке системы КуМир операция И обозначается словом и, а в Паскале — словом and.
Используя дополнительные источники, найдите другие обозначения операции И.
В таблице истинности операции И будет уже не один столбец с исходными данными, а два, мы обозначим исходные данные как А и B. Число строк также выросло, с 2 до 4, поскольку с помощью 2 бит можно записать 4 разных комбинации значений двух переменных: 00, 01, 10 и 11. Как следует из определения операции И, в последнем столбце будет всего одна единица, для варианта А = B = 1 (оба высказывания, А и Б, истинны одновременно) — рис. 2.3.
Рис. 2.3
Из значений А и В в каждой строке этой таблицы составьте двоичное число и запишите его в десятичной системе счисления. Почему строки в таблице расположены именно так?
Легко проверить, что этот результат можно получить «обычным» умножением А на В, поэтому операцию И называют логическим умножением. Она часто обозначается знаком умножения (точкой): А • В.
С точки зрения обычной математики, эта операция выбирает наименьшее из исходных значений. Математики используют ещё одно название операции И — конъюнкция.
Используя дополнительные источники, выясните, от какого слова произошло слово «конъюнкция» и что оно обозначает.
С помощью таблицы истинности можно упрощать логические выражения. Например, рассмотрим выражение А и 1. По таблице истинности на рис. 2.3 получаем:
при А = 0: А и 1 = 0 и 1 = 0
при А = 1: А и 1 = 1 и 1 = 1.
Можно заметить, что в любом случае результат совпадает с А, поэтому А и 1 = А.
Используя таблицу истинности операции И, упростите выражения: а) А и 0; б) А и А; в) А и (не А).
Операция ИЛИ
Высказывание А или В (например, «Сейчас идет дождь или форточка открыта») истинно тогда, когда истинно хотя бы одно из входящих в него высказываний или оба одновременно.
В алгоритмическом языке операция ИЛИ обозначается словом или, а в языке Паскаль — английским словом or.
Используя дополнительные источники, найдите другие обозначения операции ИЛИ.
Для понимания операции ИЛИ можно представить себе схему с двумя выключателями, соединёнными параллельно (рис. 2.4).
Рис. 2.4
Чтобы лампочка загорелась, достаточно включить хотя бы один из выключателей. Чтобы выключить лампочку, необходимо обязательно выключить оба. В таблице истинности будет только один ноль — для варианта А = В = 0 (рис. 2.5).
Рис. 2.5
Операцию ИЛИ называют логическим сложением, потому что она похожа на обычное математическое сложение. Поэтому она часто обозначается знаком сложения: А+В. Единственное отличие — в последней строке таблицы истинности: в математике 1+1 равно 2, а в алгебре логики — единице.
Можно считать, что в результате применения операции ИЛИ из исходных значений выбирается наибольшее. Другое название этой операции — дизъюнкция.
Используя дополнительные источники, выясните, от какого слова произошло слово «дизъюнкция» и что оно обозначает.
Запишите в тетради ответы на следующие вопросы.
— Сколько строк в таблице истинности функции с двумя переменными?
— Сколько существует возможных вариантов распределения нулей и единиц в последнем столбце?
— Сколько можно придумать различных логических функций с двумя переменными?
Используя таблицу истинности операции И, упростите выражения:
а) А или 0; б) А или 1; в) А или А; г) А или (не А).
Выводы
• Логическое высказывание — это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно.
• Алгебра логики — это математический аппарат, с помощью которого записывают, упрощают и преобразуют логические высказывания, вычисляют их значения.
• Логическая функция — это правило преобразования входных логических значений в логическое значение-результат.
• Если высказывание А истинно, то не А ложно, и наоборот.
• Высказывание А и В истинно тогда и только тогда, когда оба высказывания, А и В, истинны одновременно.
• Высказывание А или В истинно тогда, когда истинно хотя бы одно из высказываний, А или Б, или оба они истинны одновременно.
• С помощью операций НЕ, И, ИЛИ можно выразить любую логическую операцию, поэтому говорят, что эти три операции составляют базис.
Нарисуйте в тетради интеллект-карту этого параграфа.
Вопросы и задания
1. Объясните значения слов «логика», «формальная логика», «алгебра логики».
2. Можно ли считать высказываниями эти предложения?
1) Не плачь, девчонка!
2) Почему я водовоз?
3) Купите слоника!
4) Клубника очень вкусная.
5) Сумма X и Y равна 36.
3. Как вы думаете, зачем в курсе информатики изучается логика?
4. Почему в таблице истинности для операции НЕ две строки, а для других изученных операций — четыре?
5. Сколько строк в таблице истинности выражения с тремя переменными? С четырьмя? С пятью?
6. В каком порядке обычно записываются значения переменных в таблице истинности? Зачем это нужно?
7. В чём различие арифметического и логического сложения?
8. Выполните по указанию учителя задания в рабочей тетради.
Подготовьте сообщение
а) «Информатика и логика»
б) «Логическая операция исключающее ИЛИ»
в) «Логическая операция импликация»
г) «Логическая операция эквиваленция»
§8. Логика и компьютеры.