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




Скачать 155.05 Kb.
НазваниеТема : Основные понятия математической логики
Дата30.08.2012
Размер155.05 Kb.
ТипРешение

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

A15 (повышенный уровень, время – 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

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


Для какого из указанных значений 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. тогда исходное выражение можно переписать в виде ¬(AB)=1 или AB=0

  2. импликация AB ложна в одном единственном случае, когда 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 + 2X)(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 Огастес (Август) де Морганшотландский математик и логик.

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.

Похожие:

Тема : Основные понятия математической логики iconТема : Основные понятия математической логики
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Основные понятия математической логики iconТема : Основные понятия математической логики
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Основные понятия математической логики iconТема основы логики (первый этап отношений логики и языка) (6 часов)
История логики. Логика и язык. Миф о полной ограниченности и неприменимости логики в сфере языкознания. Миф о всесилии логики и семиотики...
Тема : Основные понятия математической логики iconПрограмма дисциплины по кафедре Прикладная математика
Охватывает круг вопросов, связанных с изучением формальных теорий, элементов теории множеств, логики высказываний и логики предикатов,...
Тема : Основные понятия математической логики iconЭлементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6
С 32 Элементарный курс математической логики. Логические функции: учеб пособие. Саратов: Сарат гос техн ун-т, 2011. 32 с
Тема : Основные понятия математической логики iconУрок 14 Тема: Основные понятия и определения
Цели урока: разобрать основные понятия и определения, научиться выбирать номенклатуру деталей для обработки на гпс
Тема : Основные понятия математической логики iconПреподаватель
Тема: «Наводнения. Основные понятия и их классификация. Основные понятия гидрологии. Классификация наводнений»
Тема : Основные понятия математической логики iconЛабораторная работа №1 По предмету: «Искусственный интеллект.»
Пролог (англ. Prolog) — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов...
Тема : Основные понятия математической логики iconКонспект урока «Основные понятия алгебры логики»
Вы зашли в темную комнату. В ней есть газовая и бензиновая лампа. Что вы зажжете в первую очередь?
Тема : Основные понятия математической логики iconЛаборатория математической логики

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница