Тема "Алгебра логики" при подготовке к ОГЭ по информатике

Тема «Алгебра логики» в ОГЭ по информатике

Учитель информатики

Грунюшкина Ж. В.

МОУ СШ№32 «Эврика – развитие»

г. Волжского Волгоградской области

Знать:

УМЕТЬ:

• определение логики как науки,
• что такое высказывание (истинные и ложные высказывания),
• простые и сложные высказывания
• определение алгебры логики,
• что такое логическая операция
• виды основных логических операций, (конъюнкция, дизъюнкция, отрицание),
• приоритет логических операций логическое выражение,
• правила построения таблиц истинности сложных логических выражений,
• способы нахождения значений логических функций,
• преобразование логических выражений

• объяснять важность логики как науки,
• определять является ли утверждение высказыванием,
• уметь приводить примеры высказываний,
• различать простые и сложные высказывания,
• составлять простые и сложные высказывания,
• определять истинность или ложность простого и сложного высказывания
• определять значение логического выражения,
• строить таблицу истинности логического выражения. Решать задачи с логическими операциями:
• осуществлять поиск информации в готовой базе данных по сформулированному условию
• осуществить поиск информации в сети Интернет в виде запросов с логическими операциями.

Решите задачу:

Три подружки - Аня, Света и Настя - купили различные молочные коктейли в белом, голубом и зелёном стаканчиках. Ане достался не белый стаканчик, а Свете - не голубой. В белом стаканчике не банановый коктейль. В голубой стаканчик налит ванильный коктейль. Света не любит клубничный коктейль.

Требуется выяснить, какой коктейль и в каком стаканчике купила каждая из девочек.

Решение задачи о коктейлях

У Ани не белый стаканчик, а у Светы не голубой.

Света не любит клубничный коктейль, значит у неё не белый стаканчик, а зелёный.

Следовательно в зелёном стаканчике налит банановый коктейль, а в белом – клубничный.

Ванильный коктейль не белом стаканчике и не в зелёном.

Значит в голубом стаканчике не банановый и не клубничный коктейль.

В голубом стаканчике налит ванильный коктейль.

В белом стаканчике не банановый коктейль.

Создадим две таблицы:

Значит у Насти белый стаканчик, а у Ани – голубой.

Стаканчик

Девочка

Аня

Белый

Света

Голубой

Настя

Зелёный

0

0

1

0

0

1

0

1

0

Стаканчик

Коктейль

Белый

банановый

Голубой

ванильный

Зелёный

клубничный

1

0

0

1

0

0

0

0

1

Ответ: Аня купила ванильный коктейль в голубом стаканчике, Света - банановый коктейль в зелёном стаканчике, Настя - клубничный коктейль в белом стаканчике.

История появления и развития термина «логика»

Древнегреческий философ Аристотель (384-322 до н.э.) - основоположник формальной логики – науки о формах правильного мышления. Он ввёл термины : понятие, суждение, умозаключение.

История появления и развития термина «логика»

Английский математик Джордж Буль (1815-1864) создал новую область науки - Математическую логику (Булеву алгебру или Алгебру высказываний). Буль применил алгебраические методы для решения логических задач.

Основные понятия алгебры логики : логическая величина (высказывание), логическая операция, логическая формула.

Американский инженер Клод Шеннон (1916-2001). Его исследования позволили применить алгебру логики в вычислительной технике

Высказывание

Высказывание - это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное .

ПРИМЕРЫ высказываний:

Земля вращается вокруг Солнца .

Москва – столица России.

Но не всякое повествовательное предложение является высказыванием :

Выполните задание.

Побудительные и вопросительные предложения высказываниями не являются .

Без стука не входить!

Откройте учебники.

Ты выучил стихотворение?

Определите: перед вами

высказывание или нет?

Зимой идет дождь.

Снегири живут в Крыму.

Кто к нам пришел?

У треугольника 5 сторон.

Как пройти в библиотеку?

Переведите число в десятичную систему.

Запишите домашнее задание

• Зимой идет дождь. Снегири живут в Крыму. Кто к нам пришел? У треугольника 5 сторон. Как пройти в библиотеку? Переведите число в десятичную систему. Запишите домашнее задание

Определите по таблице с данными примерами из биологии, географии, истории, математики, информатики и литературы, в каком столбце истинные высказывания, а в каком высказывания ложные.

ЛОЖЬ

ИСТИНА

предмет

биология

Крокодилы летают.

математика

25*2=60

информатика

Кит -млекопитающее

география

Информация хранится в процессоре ПК

1+1=2

Амазонка – река в Египте

клавиатура – основное устройство ввода информации в ПК

история

Волга – великая русская река.

22 июня 1941 – начало второй мировой войны

литература

Автор «Капитанской дочки» - И. С. Тургенев

Пётр 1 – первый российский император

А. С. Пушкин – автор поэмы «Евгений Онегин»

АЛГЕБРА ЛОГИКИ

Алгебра логики определяет правила записи, вычисления значений, упрощения и преобразования высказываний.

В алгебре логики высказывания обозначают буквами и называют логическими величинами (переменными) .

Логические величины могут принимать всего два значения : «ИСТИНА» или «ЛОЖЬ»

Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей ( А = 1 ), а если ложно - нулём ( В = 0 ).

0 и 1 называются логическими значениями .

Простые и сложные высказывания

Высказывания бывают простые и сложные.

Высказывание называется простым , если никакая его часть сама не является высказыванием.

Сложные (составные) высказывания строятся из простых с помощью логических операций.

Название логической операции

Конъюнкция

Логическая связка

Пример сложного высказывания

«и»; «а»; «но»; «хотя»

Дизъюнкция

Мы купались в море И играли в мяч на берегу.

Инверсия

«или»

Летом мы будем отдыхать на море ИЛИ поедем на дачу.

«не»; «неверно, что»

Неверно, что Солнце вращается вокруг Земли.

№ 1 Число 376 чётное и трёхзначное

Высказывание А

Высказывание В

Составное высказывание

Число 376 чётное

Число 376 трёхзначное

А И B

№ 2 Зимой дети катаются на коньках или на лыжах

Высказывание А

Высказывание В

Составное высказывание

Зимой дети катаются на коньках

Зимой дети катаются на лыжах

А ИЛИ B

№ 3 Неверно, что Солнце вращается вокруг Земли

Высказывание А

Составное высказывание

Солнце вращается вокруг Земли

НЕ А

Высказывание – это предложение на любом языке,

содержание которого

можно однозначно определить как истинное или ложное.

Основные логические

операции

Инверсия

Конъюнкция

Дизъюнкция

Логические операции

Конъюнкция - логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.

Другое название: логическое умножение.

Обозначения:  ,  , & , И. пример:

Зимой холодно и идёт снег (А И В)

Таблица истинности:

А

0

В

А & В

0

0

0

1

1

1

0

0

1

0

1

Логические операции

Дизъюнкция - логическая операция, которая каждым двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.

Другое название: логическое сложение .

Обозначения: V , |, ИЛИ, +. Пример: (А ИЛИ В)

Я поеду отдыхать в Сочи или поеду отдыхать в Крым.

Таблица истинности:

А

0

В

А V В

0

0

0

1

1

1

0

1

1

1

1

Логические операции

Инверсия - логическая операция, которая каждому высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному.

Другое название: логическое отрицание.

Обозначения: НЕ, ¬ , ¯ .

Пример: Я не поеду в Сочи.(не А)

Таблица истинности:

А

0

Ā

1

1

0

Логические операции имеют следующий приоритет:

инверсия, конъюнкция, дизъюнкция .

Построение таблиц истинности для логических выражений

подсчитать n - число переменных в выражении

подсчитать общее число логических операций в выражении

установить последовательность выполнения логических операций

определить число столбцов в таблице

заполнить шапку таблицы, включив в неё переменные и операции

определить число строк в таблице без шапки: m =2 n

выписать наборы входных переменных

провести заполнение таблицы по столбцам, выполняя логические

операции в соответствии с установленной последовательностью

Пример построения таблицы истинности логического выражения

А V A & B

n = 2, m = 2 2 = 4 .

Приоритет операций: &, V

A

B

A&B

A V A&B

0

0

0

1

0

1

0

1

0

0

0

1

0

1

1

1

ВОПРОСЫ И ЗАДАНИЯ

Постройте таблицу истинности для формулы:

НЕ А ИЛИ В

n = 2, m = 2 2 = 4 .

Приоритет операций: НЕ, ИЛИ

А

В

НЕ А

НЕ А ИЛИ В

1

1

0

0

1

1

0

1

0

0

0

1

1

0

1

1

Типы логических задач в ОГЭ по информатике

Вычисление значения логического выражения

Задание №2

Поиск информации в Интернете

Задание №18

Поиск информации в таблице по сформулированному условию

Задание №12

25)? Решение способом рассуждения Логическое «И» истинно толь­ко тогда, когда истинны оба высказывания. За­пи­шем выражение в виде (число нечётное) И (число 25) =1 Найдём ближайшее к 25 целое нечётное число, превосходящее 25 ОТВЕТ: 27 " width="640"

Задание ОГЭ №3 Значение логического выражения

Найдите наименьшее целое число, для которого истинно высказывание:

НЕ (число чётное) И (число 25)?

Решение способом рассуждения

Логическое «И» истинно толь­ко тогда, когда истинны оба высказывания.

За­пи­шем выражение в виде

(число нечётное) И (число 25) =1

Найдём ближайшее к 25 целое нечётное число, превосходящее 25

ОТВЕТ: 27

25)? 1)17 2) 25 3) 31 4) 42 Решение через заполнение таблицы истинности для каждого варианта ответа Варианты ответов 17 Не (число чётное) Число 25 25 1 31 Не (число чётное) и (число 25) 0 1 42 1 0 0 1 0 0 1 1 0 Ответ: 3 " width="640"

Задание№2 Значение логического выражения

Для какого из приведённых чисел истинно высказывание:

НЕ (число чётное) И (число 25)?

1)17 2) 25 3) 31 4) 42

Решение через заполнение таблицы истинности для каждого варианта ответа

Варианты ответов

17

Не (число чётное)

Число 25

25

1

31

Не (число чётное) и (число 25)

0

1

42

1

0

0

1

0

0

1

1

0

Ответ: 3

Осуществление поиска информации в таблице по сформулированному условию

В таблице « Отправление по ­ ез ­ дов даль ­ не ­ го следования » найти

Сколько за ­ пи ­ сей в дан ­ ном фраг ­ мен ­ те удо ­ вле ­ тво ­ ря ­ ют усло ­ вию

(Категория по ­ ез ­ да = « скорый » )   ИЛИ   (Вокзал = « Ярославский » )?

В от ­ ве ­ те ука ­ жи ­ те одно число  —  искомое ко ­ ли ­ че ­ ство строк .

Пункт назначения

Адлер

Категория поезда

фирменный

Адлер

Время в пути

скорый

29:46

Адлер

Вокзал

Казанский

фирменный

Адлер

38:35

скорый

25:30

Курский

Алма-Ата

скорый

Казанский

39:13

Амстердам

Курский

102:22

скорый

Анапа

пассажирский

Павелецкий

Архангельск

36:40

скорый

Архангельск

Белорусский

35:37

пассажирский

Белорусский

20:46

Архангельск

Астана

Ярославский

скорый

46:30

скорый

Ярославский

Астрахань

21:25

скорый

Белорусский

58:00

Казанский

27:56

Павелецкий

РЕШЕНИЕ задачи№12

(Категория по ­ ез ­ да = « скорый » )  

ИЛИ   (Вокзал = « Ярославский » )=1

  Логическое «ИЛИ» ис­тин­но тогда, когда истиннo хотя бы одно высказывание.

Пункт назначения

Категория поезда

Адлер

фирменный

Время в пути

Адлер

Адлер

29:46

скорый

Вокзал

фирменный

Казанский

38:35

Адлер

Курский

25:30

скорый

Алма-Ата

Казанский

скорый

39:13

Амстердам

Анапа

скорый

Курский

102:22

пассажирский

Павелецкий

36:40

Архангельск

35:37

скорый

Архангельск

Белорусский

Белорусский

пассажирский

20:46

Архангельск

Астана

скорый

46:30

Ярославский

скорый

Ярославский

21:25

Астрахань

Белорусский

58:00

скорый

Казанский

27:56

Павелецкий

Ответ: 9

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

В таблице « Отправление по ­ ез ­ дов даль ­ не ­ го следования » найти

Сколько за ­ пи ­ сей в дан ­ ном фраг ­ мен ­ те удо ­ вле ­ тво ­ ря ­ ют усло ­ вию

(Категория по ­ ез ­ да = « скорый » )   И   (Вокзал = « Ярославский » )?

В от ­ ве ­ те ука ­ жи ­ те одно число  —  искомое ко ­ ли ­ че ­ ство строк .

Пункт назначения

Адлер

Категория поезда

фирменный

Адлер

Время в пути

скорый

29:46

Адлер

Вокзал

Казанский

фирменный

Адлер

38:35

скорый

25:30

Курский

Алма-Ата

скорый

Казанский

39:13

Амстердам

Курский

102:22

скорый

Анапа

пассажирский

Павелецкий

Архангельск

36:40

скорый

Архангельск

Белорусский

35:37

пассажирский

Белорусский

20:46

Архангельск

Астана

Ярославский

скорый

46:30

скорый

Ярославский

Астрахань

21:25

скорый

Белорусский

58:00

Казанский

27:56

Павелецкий

Решение задачи

(Категория по ­ ез ­ да = « скорый » )   И   (Вокзал = « Ярославский » )=1

Логическое «И» ис­тин­но тогда, когда истинны оба высказывания одновременно .

Пункт назначения

Адлер

Категория поезда

фирменный

Адлер

Время в пути

29:46

скорый

Адлер

Вокзал

Казанский

Адлер

фирменный

38:35

скорый

Алма-Ата

25:30

Курский

39:13

Казанский

скорый

Амстердам

102:22

Курский

скорый

Анапа

Павелецкий

пассажирский

36:40

Архангельск

скорый

Архангельск

Белорусский

35:37

пассажирский

Архангельск

20:46

Белорусский

Ярославский

46:30

скорый

Астана

скорый

Астрахань

21:25

Ярославский

скорый

58:00

Белорусский

27:56

Казанский

Павелецкий

Ответ: 1 (в ответ входит строка (желтый цвет), где встречаются «скорый» и «Ярославский» одновременно).

Поиск информации в Интернете

Всемирная паутина ( WWW ) - это сервис для получения доступа пользователей сети к информационным ресурсам, хранящимся на компьютерах в разных частях света.

Основой WWW являются Web-страницы и Web-сайты .

Задача. В таблице приведены запросы к поисковому серверу. Для обозначения логической операции ИЛИ в запросах используется символ |, а для логической операции И – символ &.

1

2

Франция | Испания | История

3

Франция & Карта & История

Франция | История

4

Франция & История

Расположите номера запросов в порядке убывания количества страниц .

Изобразим графически количество страниц, которые найдёт поисковый сервер по каждому запросу.

Решаем задачу :

1

2

Франция | Испания | История

3

Франция & Карта & История

4

Франция | История

Франция & История

Франция

Франция

Франция

Франция

Испания

Карта

История

История

История

История

4)

3)

2)

1)

Вывод: Чем боль­ше в за­про­се опе­ра­ций «ИЛИ», тем боль­ше ре­зуль­та­тов выдаёт по­ис­ко­вой сервер. Чем боль­ше в за­про­се опе­ра­ций «И», тем мень­ше ре­зуль­та­тов вы­даст по­ис­ко­вой сервер.

Ответ: 1 3 4 2