Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Инструкция'
3.   Дистанция3.1. Дистанция протяжённостью около 1800 метров имеет форму вытянутого прямоугольника. Каждый поворот обозначен двумя буями, которые оги...полностью>>
'Конкурс'
В конкурсе вокального мастерства могут принять участие детские коллективы, занимающиеся вокальным творчеством, ансамбли, коллективы эстрадной песни, с...полностью>>
'Документ'
ОЦЕНКА «5»: Общей отраслью специализации районов Центральной России является машиностроение....полностью>>
'Документ'
Очистные сооружения шахтных вод рудника №6, 2 и 4 ОАО «Приаргунское производственное горно-химическое объединение» (техническое сопровождение стадии «...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

© К. Поляков, 2009-2010

A10 (базовый уровень, время – 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. посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана,

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

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

Возможные ловушки и проблемы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы:

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

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

Еще пример задания1:

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

1) ¬B A 2) A B ¬B 3) A B ¬A 4) ¬A

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

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

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

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

  1. наконец, применяем распределительный закон для операции «И» и еще раз закон исключения третьего :

  1. дальше уже не упрощается…

  2. теперь замечаем, что такого ответа нет среди предложенных вариантов!

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

ответы: 2)
3)

  1. видим, что упрощенное выражение для ответа 3 совпало с упрощенным исходным выражением

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

  3. заметим, что этот пример можно также решать через таблицы истинности, но это более трудоемко.

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

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

законы де Моргана: ,

распределительный закон:

закон поглощения: ,

закон исключения третьего: ,

Задачи для тренировки2:

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

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

  1. Какое логическое выражение равносильно выражению ¬ (A B) ¬C ?

1) ¬A B ¬C 2)(¬A ¬B) ¬C 3)(¬A ¬B) C 4) ¬A ¬B ¬C

  1. Укажите, какое логическое выражение равносильно выражению ¬ (¬А B)?

1) A ¬B 2) ¬A B 3) B ¬A 4) A ¬B

  1. Какое логическое выражение равносильно выражению ¬(А ¬B) ?

1) A B 2) A B 3) ¬A ¬B 4) ¬A B

  1. Какое логическое выражение эквивалентно выражению ¬(¬A ¬B) C ?

1) (A ¬B) C 2) A B C 3) (A ¬B) C 4) ¬(A ¬B) C

  1. Какое логическое выражение эквивалентно выражению A ¬(¬B ¬C)?

1) A B C 2) A B ¬C 3) A (B C) 4) (A ¬B) ¬C

  1. Какое логическое выражение эквивалентно выражению ¬(A B) ¬C?

1) (A B) ¬C 2) (A B) C 3) (¬A ¬B) ¬C 4) (A B) C

  1. Какое логическое выражение эквивалентно выражению ¬(A ¬B) ¬C?

1) A B C 2) ¬(A B) C 3) ¬(A C) B 4) ¬(A C) B

  1. Какое логическое выражение эквивалентно выражению ¬(¬A B) ¬C?

1) (A B) ¬C 2) (A B) C 3) (A ¬B) ¬C 4) (A ¬B) ¬C

  1. Какое логическое выражение эквивалентно выражению ¬(A B) C?

1) ¬A B C 2) A B C 3) ¬(A B) C 4) ¬A ¬B ¬C

  1. Какое логическое выражение эквивалентно выражению ¬(¬ A ¬ B) C?

1) ¬ A B ¬ C 2) A ¬ B) ¬C 3) (A B) C 4) A B C

  1. Какое логическое выражение эквивалентно выражению A ¬(B ¬ C)?

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

  1. Какое логическое выражение эквивалентно выражению ¬(¬A B) C?

1) ¬A B ¬C 2) (A ¬B) C 3) (A B) C 4) A ¬B C

  1. Какое логическое выражение эквивалентно выражению ¬(A ¬B ¬C)?

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

  1. Какое логическое выражение эквивалентно выражению ¬(¬A ¬B) C?

1) ¬A B ¬C 2) A B C 3) (A B) C 4)( ¬A ¬B) ¬C

  1. Какое логическое выражение эквивалентно выражению ¬(¬A (¬B C))?

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

  1. Какое логическое выражение эквивалентно выражению ¬(A ¬B C)?

1) ¬A B ¬C 2) ¬A B ¬C 3) ¬A (B C) 4) ¬A B ¬A ¬C

  1. Какое логическое выражение эквивалентно выражению ¬A ¬(¬B ¬¬C) D?

1) ¬A ¬B C D 2) ¬A ¬B ¬C D

3) ¬A B ¬C D 4) ¬A B C D

  1. Какое логическое выражение эквивалентно выражению ¬(A ¬B) ¬C D?

1) A ¬B C ¬D 2) A ¬B C D

3) ¬A B ¬C D 4) ¬A B ¬C D

  1. Какое логическое выражение эквивалентно выражению ¬(¬B ¬C) ¬A?

1) ¬A (B C) 2) ¬A ¬B C 3) ¬A B ¬C 4) ¬A (B C)

  1. Какое логическое выражение эквивалентно выражению A B C)?

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

  1. Какое логическое выражение эквивалентно выражению ¬(¬A B ¬C)?

1) A ¬B C 2) A ¬B C 3) A (¬B C) 4) A C ¬B C

  1. Какое логическое выражение эквивалентно выражению ¬(¬¬A ¬B C)?

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

  1. Какое логическое выражение эквивалентно выражению ¬(A B) ¬C?

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

  1. Какое логическое выражение эквивалентно выражению A ¬(¬B ¬C)?

1) ¬A ¬B ¬C 2) A (B C) 3) A B C 4) A ¬B ¬C

1 Самылкина Н.Н., Островская Е.М. Информатика: тренировочные задания. – М.: Эксмо, 2009.

2 Источники заданий:

  1. Демонстрационные варианты ЕГЭ 2004-2009 гг.

  2. Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. — СПб: Тригон, 2009.

  3. Самылкина Н.Н., Островская Е.М. Информатика: тренировочные задания. – М.: Эксмо, 2009.

  4. Якушкин П.А., Лещинер В.Р., Кириенко Д.П. ЕГЭ 2010. Информатика. Типовые тестовые задания. — М.: Экзамен, 2010.

  5. Якушкин П.А., Ушаков Д.М. Самое полное издание типовых вариантов реальных заданий ЕГЭ 2010. Информатика. — М.: Астрель, 2009.

6



Похожие документы:

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

    Решение
    ... уровень, время – 1 мин) Тема: Преобразование логических выражений. Формулы де Моргана. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ ...
  2. Решение. Рассуждения, приводящие к правильному ответу

    Решение
    ... отводится 2 мин Тема задания «Преобразование логических выражений. Формулы де Моргана» Какое логическое выражение равносильного выражению ¬(А۸В)۸¬С? 1) ¬А۷В۷¬С 2) (¬А۷¬В)۸¬С 3) (¬А۷¬В)۸С 4) ¬А۸¬В۸¬С Решение Применим отрицание к выражению в скобках ...
  3. Тема : Преобразование логических выражений (1)

    Документ
    ... время – 10 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ ... импликацию по формуле : раскроем инверсию сложного выражения по формуле де Моргана : упростим выражение : мы получили ...
  4. Тема : Преобразование логических выражений (2)

    Документ
    ... время – 10 мин) Тема: Преобразование логических выражений. Про обозначения К сожалению, обозначения логических операций И, ИЛИ и НЕ ... импликацию по формуле : раскроем инверсию сложного выражения по формуле де Моргана : упростим выражение : мы получили ...
  5. Тема : Алгебра логики. Логические операции, формулы и их преобразования

    Документ
    ... Тема: Алгебра логики. Логические операции, формулы и их преобразования. Цель работы: Практическое изучение логических ... )(X1  X2) = X1 7. Правило де Моргана. ¬(X1  X2  X3) = ... схеме логического устройства составить логическое выражение и заполнить ...

Другие похожие документы..