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

Введение

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

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

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

    Предмет исследования – методы подготовки к ЕГЭ по информатике по теме «Основы логики».

    Объект  исследования – раздел «Основы логики» школьного курса информатики.

    Цель: комплексное, системное изучение методики подготовки к ЕГЭ по информатике по теме «Основы логики».

    Достижение  поставленной цели требует постановки и решения следующих задач:

1. провести теоретический анализ раздела «Основы логики»;
2. рассмотреть возможные трудности при решении задач данной темы.

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

§1. Формы мышления. Алгебра высказываний.

    Логика  — наука о способах и формах мышления,  которая возникла в  Древнем Китае и Индии. 

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

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

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

      В алгебре высказываний простым  высказываниям или  суждениям соответствуют логические переменные.   Истинному высказыванию соответствует значение логической  переменной 1, а ложному — значение 0. Над высказываниями  можно производить определенные логические операции,  в результате которых получаются новые, составные  высказывания[14, 98 c.].

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

    Конъюнкция. Операцию логического умножения  (конъюнкцию) принято обозначать значком  «&» либо «/\»:

F = А  /\В.

    Функция логического умножения F может принимать  лишь два значения «истина» (1) и «ложь» (0). Значение логической функции определяется с помощью таблицы  истинности:

    Дизъюнкция. Операцию логического сложения  обозначают «v» либо «+».

F = A\/B

    Таблица истинности:

    Инверсия. Операцию логического отрицания обозначают F = ¬A.

    Таблица истинности логического отрицания:

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

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

    А –> В.

    Таблица истинности:

    Логическое  равенство (эквивалентность) — это логическая функция, которую можно описать помощью оборота «тогда и только тогда, когда ...» и обозначается А<–>В.

    Таблица истинности:

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

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

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

F = (A\/B) /\ (A\/B)

Таблицу истинности можно построить для каждого  логического выражения. Она определяет его значение при всех возможных комбинациях значений логических переменных [14, 99 c.].

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

1. Количество строк N в таблице истинности равно количеству возможных комбинаций значений логических переменных n и определяется по формуле: N = 2".
2. Количество столбцов в таблице истинности равно количеству логических переменных плюс количество логических операций.
3. Построить таблицу истинности с необходимым количеством строк и столбцов и записать значения исходных логических переменных.
4. Заполнить таблицу истинности по столбцам, в соответствии с таблицами истинности.

§3. Логические законы

    Закон тождества. Всякое высказывание тождественно  самому себе:

    А = А.

    Закон непротиворечия. Высказывание не может  быть  одновременно истинным и ложным:

    А /\ ¬А = 0.

   Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным:

    A \/ ¬A = 1.

    Закон двойного отрицания. Двойное отрицание дает в итоге исходное высказывание:

    ¬¬А = А

    Законы  де Моргана:

    ¬(A \/ B) = ¬A /\ ¬B

    ¬(A /\ B) = ¬A \/ ¬B

    Закон коммутативности.

    А /\ В = В /\ А

    A \/ B = B \/ A

    Закон ассоциативности:

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

    (A \/ B) \/ C = A \/ (B \/ C)

    Закон дистрибутивности. Отличается от подобного закона в алгебре — за скобки можно выносить не только общие множители, но и общие слагаемые:

    (A /\ B) \/ (A /\ C)=A /\ (B \/ C)

    (A \/ B) /\ (A \/ C) = A \/ (B /\ C)  

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

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

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

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

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

    Из  тысяч и миллионов таких элементов  строится ЭВМ [14, 103 c.].

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

    0 + 0 = 00

    0 + 1 = 01

    1 + 0 = 01

    1 + 1 = 10

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

Глава 2. Методика подготовки к ЕГЭ по теме «Основы логики»

§1. Кодификатор

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

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

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

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

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

§2. Разбор заданий

    По  теме «Основы логики» в экзаменационной  работе содержалось пять заданий: три  с выбором ответа и два с  кратким ответом (что составляет 12,5% от максимального первичного балла за всю работу). Эти задания включали в себя проверку умения строить таблицы истинности и логические схемы, преобразовывать логические выражения, решение логического уравнения. Уровень сложности, максимальный первичный балл и время выполнения определяется по спецификации. Обозначения: Б – базовый уровень, сложности, П – повышенный уровень сложности, В – высокий уровень сложности.

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

    1. Обозначения для логических связок (операций):

1. отрицание (инверсия) обозначается ¬ (например, ¬А);
2. конъюнкция (логическое умножение, логическое И) обозначается /\ (например, А /\ В);
3. дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/ (например, A \/ В);
4. следование (импликация) обозначается –> (например, А –> В);
5. символ 1 используется для обозначения истины (истинного высказывания); символ 0 — для обозначения лжи (ложного высказывания).

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

    3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), эквивалентность (равносильность). Таким образом, ¬А /\ В \/ С /\ D совпадает с ((¬А) /\ В) \/ (С /\ D). Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С.  

§3. Основные трудности при решении заданий

    Задание А7 повышенного уровня на проверку знания основных понятий и законов математической логики. Задание А8 базового уровня на преобразование логических выражений, задания А9 и В4 проверяют сформированность умений применять свои знания в новой ситуации. Это умение преобразовывать сложные логические высказывания.

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

А7.

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

Уровень сложности задания: повышенный.

Максимальный  балл за задание: 1.

Примерное время выполнения: 2 мин.

Типичные  ошибки:

• можно «забыть» отрицание (помните, что правильный ответ – всего один!);
• можно перепутать порядок операций (скобки, «НЕ», «И», «ИЛИ», «импликация»);
• нужно помнить таблицу истинности операции «импликация», которую очень любят составители тестов;
• этот метод проверяет только заданные числа и не дает общего решения, то есть не определяет все множество значений X, при которых выражение истинно;
• нужно помнить законы логики (например, формулы де Моргана);
• при использовании формул де Моргана нужно не забыть заменить «И» на «ИЛИ» и наоборот.

А8.

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

Уровень сложности задания: базовый.

Максимальный  балл за задание: 1.

Примерное время выполнения: 2 мин.

Типичные  ошибки:

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

А9.

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

Уровень сложности задания: повышенный.

Максимальный  балл за задание: 1.

Примерное время выполнения: 4 мин.

Типичные  ошибки:

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

В4.

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

Уровень сложности задания: высокий.

Максимальный  балл за задание: 1.

Примерное время выполнения: 10 мин.

Типичные  ошибки:

• Плохое знание таблиц истинности;
• Ошибки из-за невнимательности к значкам, которыми в выражениях обозначают логические операции. Это происходит от того, что в разных учебниках эти значки отличаются по написанию;
• нужно помнить правила преобразования логических выражений и хорошо владеть этой техникой;
• легко запутаться в многочисленных столбцах с однородными данными (нулями и единицами).

В6.

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

Уровень сложности задания: повышенный.

Максимальный  балл за задание: 1.

Примерное время выполнения: 8 мин.

Типичные  ошибки:

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

    Последовательность  решения логической задачи:

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