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

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

    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. проверка полученного решения по условию задачи.