Тема : Преобразование логических выражений. Формулы де Моргана icon

Тема : Преобразование логических выражений. Формулы де Моргана



НазваниеТема : Преобразование логических выражений. Формулы де Моргана
Дата конвертации08.10.2012
Размер171.75 Kb.
ТипДокументы

Вопрос 4


Тема: Преобразование логических выражений. Формулы де Моргана.

Про обозначения

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

Что нужно знать:

  • условные обозначения логических операций

¬ A, не A (отрицание, инверсия)

A  B, A и B (логическое умножение, конъюнкция)

A  B, A или B (логическое сложение, дизъюнкция)

AB импликация (следование)

  • операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

AB = ¬ A  B или в других обозначениях AB =

  • если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»

  • правила преобразования логических выражений (слайд из презентации «Логика»):



  • фактически это задание на применение законов де Моргана (хотя об этом нигде не говорится):

¬ (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. перепишем заданное выражение и ответы в других обозначениях:
    заданное выражение gif" name="object7" align=absmiddle width=73 height=21>
    ответы: 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  B  ¬A  ¬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.





Похожие:

Тема : Преобразование логических выражений. Формулы де Моргана iconПостроение таблиц истинности логических выражений Приоритет логических операций
При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:...
Тема : Преобразование логических выражений. Формулы де Моргана iconПроверочная работа «Преобразование логических выражений»
Выполнить вычисления по логической схеме и записать соответствующее логическое выражение
Тема : Преобразование логических выражений. Формулы де Моргана iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений. Формулы де Моргана iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений. Формулы де Моргана iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Преобразование логических выражений. Формулы де Моргана iconТема : Составление запросов для поисковых систем с использованием логических выражений
Тема: Составление запросов для поисковых систем с использованием логических выражений
Тема : Преобразование логических выражений. Формулы де Моргана iconТематическое планирование учебного материала по алгебре в 10-м классе
Тема № Преобразование тригонометрических выражений 13 ч. Контрольная работа №4
Тема : Преобразование логических выражений. Формулы де Моргана iconПриоритет логических операций
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных...
Тема : Преобразование логических выражений. Формулы де Моргана iconПриоритет логических операций
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных...
Тема : Преобразование логических выражений. Формулы де Моргана iconУрок путешествия: «Осенняя прогулка» Тема урока: «Преобразование рациональных выражений»
Оборудование: индивидуальные карточки ( в форме осенних листьев и цветов), тест, карточки для проведения рефлексии, компьютер
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов