Тема : Основные понятия математической логики icon

Тема : Основные понятия математической логики



НазваниеТема : Основные понятия математической логики
Дата конвертации24.06.2012
Размер145.71 Kb.
ТипДокументы

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

A10 (повышенный уровень, время – 2 мин)


Тема: Основные понятия математической логики.

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

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

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

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

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

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

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

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

  • таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация» (см. презентацию «Логика»)

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

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

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

  • иногда полезны формулы де Моргана1:

¬ (A  B) = ¬ A  ¬ B

¬ (A  B) = ¬ A  ¬ B gif" name="object6" align=absmiddle width=85 height=18>
^

Пример задания:


Какое из приведённых имен удовлетворяет логическому условию:
(первая буква согласная ? вторая буква согласная) /\ (предпоследняя буква гласная ? последняя буква гласная)?

1) КРИСТИНА 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ

Решение:

  1. два условия связаны с помощью операции /\ («И»), поэтому должны выполняться одновременно

  2. импликация ложна, если ее первая часть («посылка») истинна, а вторая («следствие») – ложна

  3. первое условие «первая буква согласная ? вторая буква согласная» ложно тогда, когда первая буква согласная, а вторая – гласная, то есть для ответов 2 и 4

  4. второе условие «предпоследняя буква гласная ? последняя буква гласная» ложно тогда, когда предпоследняя буква гласная, а последняя – согласная, то есть, для ответа 3

  5. таким образом, для варианта 1 (КРИСТИНА) оба промежуточных условия и исходное условие в целом истинны

  6. ответ: 1.
^

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


Для какого из указанных значений X истинно высказывание ¬((X > 2)?(X > 3))?

1) 1 2) 2 3) 3 4) 4

Решение (вариант 1, прямая подстановка):

  1. определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках

  2. выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); сначала определяем результаты сравнения в двух внутренних скобках:

    X

    X > 2

    X > 3

    (X > 2)?(X > 3)

    ¬((X > 2)?(X > 3))

    1

    0

    0







    2

    0

    0







    3

    1

    0







    4

    1

    1







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

    X

    X > 2

    X > 3

    (X > 2)?(X > 3)

    ¬((X > 2)?(X > 3))

    1

    0

    0

    1




    2

    0

    0

    1




    3

    1

    0

    0




    4

    1

    1

    1




  4. значение выражения равно инверсии третьего столбца (меняем 1 на 0 и наоборот):

    X

    X > 2

    X > 3

    (X > 2)?(X > 3)

    ¬((X > 2)?(X > 3))

    1

    0

    0

    1

    0

    2

    0

    0

    1

    0

    3

    1

    0

    0

    1

    4

    1

    1

    1

    0

  5. таким образом, ответ – 3.

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

    • можно «забыть» отрицание (помните, что правильный ответ – всего один!)

    • можно перепутать порядок операций (скобки, «НЕ», «И», «ИЛИ», «импликация»)

    • нужно помнить таблицу истинности операции «импликация», которую очень любят составители тестов2

    • этот метод проверяет только заданные числа и не дает общего решения, то есть не определяет все множество значений X, при которых выражение истинно

Решение (вариант 2, упрощение выражения):

  1. обозначим простые высказывания буквами:

A = X > 2, B = X > 3

  1. тогда можно записать все выражение в виде

¬(A ? B) или

  1. выразим импликацию через «ИЛИ» и «НЕ» (см. выше):

¬(A ? B)= ¬(¬A  B) или

  1. раскрывая по формуле де Моргана операцию «НЕ» для всего выражения, получаем

¬(¬A  B)= A  ¬B или

  1. таким образом, данное выражение истинно только тогда, когда A истинно (X > 2), а B – ложно (X ? 3), то есть для всех X, таких что 2 < X ? 3

  2. из приведенных чисел только 3 удовлетворяет этому условию,

  3. таким образом, ответ – 3.

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

    • нужно помнить законы логики (например, формулы де Моргана)

    • при использовании формул де Моргана нужно не забыть заменить «И» на «ИЛИ» и наоборот

    • нужно не забыть, что инверсией (отрицанием) для выражения X > 3 является X ? 3, а не X < 3


Решение (вариант 3, использование свойств импликации):

  1. обозначим простые высказывания буквами:

A = X > 2, B = X > 3

  1. тогда исходное выражение можно переписать в виде ¬(A?B)=1 или A?B=0

  2. импликация A?B ложна в одном единственном случае, когда A = 1 и B = 0; поэтому заданное выражение истинно для всех X, таких что X > 2 и X ? 3

  3. из приведенных чисел только 3 удовлетворяет этому условию,

  4. таким образом, ответ – 3.


Выводы:

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

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


^

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


  1. Для какого из указанных значений числа X истинно высказывание

((X < 5)?(X < 3))  ((X < 2)?(X < 1))

1) 1 2) 2 3) 3 4) 4

  1. Для какого числа X истинно высказывание ((X > 3)(X < 3)) ?(X < 1)

1) 1 2) 2 3) 3 4) 4

  1. Для какого числа X истинно высказывание X > 1  ((X < 5)?(X < 3))

1) 1 2) 2 3) 3 4) 4

  1. Для какого имени истинно высказывание:

¬ (Первая буква имени гласная ? Четвертая буква имени согласная)?

1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР

  1. Для какого символьного выражения неверно высказывание:

Первая буква гласная ? ¬ (Третья буква согласная)?

1)abedc 2)becde 3) babas 4) abcab

  1. Для какого числа X истинно высказывание (X > 2)(X > 5)?(X < 3)

1) 5 2) 2 3) 3 4) 4

  1. Для какого из значений числа Z высказывание ((Z > 2)(Z > 4)) ?(Z > 3) будет ложным?

1) 1 2) 2 3) 3 4) 4

  1. Для какого имени истинно высказывание:

¬ (Первая буква имени согласная ? Третья буква имени гласная)?

1) ЮЛИЯ 2) ПЕТР 3) АЛЕКСЕЙ 4) КСЕНИЯ



  1. Для какого из значений числа Y высказывание (Y < 5)  ((Y > 1) ? (Y > 5)) будет истинным?

1) 1 2) 2 3) 3 4) 4

  1. Для какого символьного выражения верно высказывание:

¬ (Первая буква согласная)  ¬ (Вторая буква гласная)?

1) abcde 2) bcade 3) babas 4) cabab

  1. Для какого имени истинно высказывание:

(^ Вторая буква гласная ? Первая буква гласная) Последняя буква согласная?

1) ИРИНА 2) МАКСИМ 3) МАРИЯ 4) СТЕПАН

  1. Для какого имени истинно высказывание:

¬ (Первая буква согласная ? Последняя буква гласная) Вторая буква согласная?

1) ИРИНА 2) СТЕПАН 3) МАРИНА 4) ИВАН

  1. Для какого имени истинно высказывание:

(^ Первая буква согласная ? Вторая буква согласная) Последняя буква гласная?

1) КСЕНИЯ 2) МАКСИМ 3) МАРИЯ 4) СТЕПАН

  1. Для какого имени истинно высказывание:

¬ (Вторая буква гласная ? Первая буква гласная) Последняя буква согласная?

1) ИРИНА 2) МАКСИМ 3) МАРИЯ 4) СТЕПАН

  1. Для какого имени истинно высказывание:

¬ (Первая буква согласная ? Последняя буква согласная) Вторая буква согласная?

1) ИРИНА 2) СТЕПАН 3) МАРИЯ 4) КСЕНИЯ

  1. Для какого имени истинно высказывание:

¬ (Первая буква гласная ? Вторая буква гласная) Последняя буква гласная?

1) ИРИНА 2) МАКСИМ 3) АРТЕМ 4) МАРИЯ

  1. Для какого названия животного ложно высказывание:

^ Заканчивается на согласную В слове 7 букв ? ¬(Третья буква согласная)?

1) Верблюд 2) Страус 3) Кенгуру 4) Леопард

  1. Для какого названия животного ложно высказывание:

^ В слове 4 гласных буквы  ¬ (Пятая буква гласная) В слове 5 согласных букв?

1) Шиншилла 2) Кенгуру 3) Антилопа 4) Крокодил

  1. Для какого названия животного ложно высказывание:

^ Четвертая буква гласная ? ¬ (Вторая буква согласная)?

1) Собака 2) Жираф 3) Верблюд 4) Страус

  1. Для какого слова ложно высказывание:

^ Первая буква слова согласная ? (Вторая буква имени гласная Последняя буква слова согласная)?

1) ЖАРА 2) ОРДА 3) ОГОРОД 4) ПАРАД

  1. Для какого числа X истинно высказывание (X(X-16) > -64) ?(X > 8)

1) 5 2) 6 3) 7 4) 8

  1. Для какого числа X истинно высказывание (X(X-8) > -25 + 2X) ?(X > 7)

1) 4 2) 5 3) 6 4) 7

  1. Для какого символьного набора истинно высказывание:

Вторая буква согласная (В слове 3 гласных буквы Первая буква согласная)?

1) УББОШТ 2) ТУИОШШ 3) ШУБВОИ 4) ИТТРАО

  1. Для какого имени ложно высказывание:

(^ Первая буква гласная Последняя буква согласная) ? ¬(Третья буква согласная)?

1) ДМИТРИЙ 2) АНТОН 3) ЕКАТЕРИНА 4) АНАТОЛИЙ

  1. Для какого имени истинно высказывание:

^ Первая буква гласная Четвертая буква согласная В слове четыре буквы?

1) Сергей 2) Вадим 3) Антон 4) Илья

  1. Для какого числа X истинно высказывание
    ((X < 4) ?(X < 3))  ((X < 3) ?(X < 1))

1) 1 2) 2 3) 3 4) 4

  1. Для какого имени истинно высказывание:

¬ (Первая буква согласная ? Вторая буква согласная) Последняя буква согласная?

1) ИРИНА 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ

  1. Для какого имени истинно высказывание:

¬ (Первая буква согласная ? Последняя буква согласная) Вторая буква согласная?

1) ИРИНА 2) СТЕПАН 3) КСЕНИЯ 4) МАРИЯ

  1. Для какого имени истинно высказывание:

(^ Первая буква согласная ? Вторая буква согласная) Последняя буква гласная?

1) КСЕНИЯ 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ

  1. Для какого имени истинно высказывание:

¬ (Последняя буква гласная ? Первая буква согласная) Вторая буква согласная?

1) ИРИНА 2) АРТЁМ 3) СТЕПАН 4) МАРИЯ

  1. Для какого слова истинно высказывание:

¬ (Первая буква согласная ? (Вторая буква согласная Последняя буква гласная))?

1) ГОРЕ 2) ПРИВЕТ 3) КРЕСЛО 4) ЗАКОН

  1. Для какого имени истинно высказывание:

(^ Первая буква согласная ? Вторая буква гласная) Последняя буква согласная?

1) АЛИСА 2) МАКСИМ 3) СТЕПАН 4) ЕЛЕНА

  1. Для какого имени истинно высказывание:

(^ Вторая буква гласная ? Первая буква гласная) Последняя буква согласная?

1) АЛИСА 2) МАКСИМ 3) СТЕПАН 4) ЕЛЕНА

  1. Для какого названия реки ложно высказывание:

(^ Вторая буква гласная ? Предпоследняя буква согласная) Первая буква стоит в
алфавите раньше третьей
?

1) ДУНАЙ 2) МОСКВА 3) ДВИНА 4) ВОЛГА

  1. Для каких значений X и Y истинно высказывание:

(Y+1 > X)  (Y+X < 0)  (X > 1)?

1) X = 0,5; Y = -1,1 2) X = 1,1; Y = -4
3) X = -1; Y = -4 4) X = -1/10; Y = -1,1

  1. Для какого слова истинно высказывание:

(Вторая буква согласная Последняя буква гласная) ? Первая буква гласная?

1) ГОРЕ 2) ПРИВЕТ 3) КРЕСЛО 4) ЗАКОН

  1. Для какого имени истинно высказывание:

^ Первая буква согласная (¬ Вторая буква согласная ? Четвертая буква гласная)?

1) ИВАН 2) ПЕТР 3) ПАВЕЛ 4) ЕЛЕНА

  1. Для какого названия станции метро истинно высказывание:

(^ Первая буква согласная ? Вторая буква согласная) ~ Название содержит букву «л»)?

Знаком ~ обозначается операция эквивалентности (результат X ~ Y – истина, если значения X и Y совпадают).

1) Маяковская 2) Отрадное 3) Волжская 4) Комсомольская

  1. Для какого названия города истинно высказывание:

(^ Первая буква гласная Последняя буква гласная) ~ Название содержит букву «м»)?

Знаком ~ обозначается операция эквивалентности (результат X ~ Y – истина, если значения X и Y совпадают).

1) Москва 2) Дюссельдорф 3) Амстердам 4) Атланта

  1. Для какого имени истинно высказывание:

(^ Первая буква согласная Вторая буква гласная) ? В слове 4 буквы?

1) МИХАИЛ 2) ГРИГОРИЙ 3) ЕВГЕНИЙ 4) ИОЛАНТА

  1. Для какого числа X истинно высказывание ((X < 5) ? (X < 3))  ((X < 2) ? (X > 1))

1) 1 2) 2 3) 3 4) 4

1 ^ Огастес (Август) де Морган – шотландский математик и логик.

2 … но которая, к сожалению, почти не нужна на практике. 

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

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

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

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

  4. Крылов С.С., Ушаков Д.М. ЕГЭ 2010. Информатика. Тематическая рабочая тетрадь. — М.: Экзамен, 2010.

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

  6. М.Э. Абрамян, С.С. Михалкович, Я.М. Русанова, М.И. Чердынцева. Информатика. ЕГЭ шаг за шагом. – М.: НИИ школьных технологий, 2010.

  7. Самылкина Н.Н., Островская Е.М. ЕГЭ 2011. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2010.

  8. Крылов С.С., Лещинер В.Р., Якушкин П.А. ЕГЭ 2011. Информатика. Универсальные материалы для подготовки учащихся. — М.: Интеллект-центр, 2011.

  9. Чуркина Т.Е. ЕГЭ 2011. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2010.

  10. Тренировочные и диагностические работы МИОО 2010-2011 гг.




Похожие:

Тема : Основные понятия математической логики iconТема : Основные понятия математической логики
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Основные понятия математической логики iconТема : Основные понятия математической логики
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Основные понятия математической логики iconОсновные понятия математической логики
Рассуждение- это цепочка взаимосвязанных суждений, фактов, общих положений и умозаключений, получаемых из других суждений по определенным...
Тема : Основные понятия математической логики iconЛогика в информатике
Обучение школьников основам информатики, изучение ими такого важного понятия как «алгоритм», невозможно без развития у них логического...
Тема : Основные понятия математической логики iconАлгебра логики. Основные понятия. Область применения алгебры- логики. Логические функции. Таблицы истинности
Логика (гр logos — мысль, слово, речь, разум) — это наука о законах и формах мышления, направленная на познание объективного мира....
Тема : Основные понятия математической логики iconДокументы
...
Тема : Основные понятия математической логики iconОсновы исследовательской деятельности содержание Введение
Тема 1 Исследования и их роль в практической деятельности человека. Основные понятия и определения Тема 2 Оформление результатов...
Тема : Основные понятия математической логики iconТема урока: «Основы логики. Алгебра высказываний»
Цель урока: обучающая Познакомить учащихся с основными понятиями логики, алгебры высказываний, с основными законами логики при упрощении...
Тема : Основные понятия математической логики iconТема урока: «Основы логики. Алгебра высказываний»
Цель урока: обучающая Познакомить учащихся с основными понятиями логики, алгебры высказываний, с основными законами логики при упрощении...
Тема : Основные понятия математической логики iconПроверочная работа по теме «Основные понятия формальной логики» Что изучает наука логика? Что такое «высказывание»
Из набора слов «траву, летает, собака, прыгает, ест, слон, по небу» составьте истинное и ложное высказывания
Разместите кнопку на своём сайте:
Документы


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

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