Презентация "Логические основы компьютеров"

Подписи к слайдам:
Тема урока: «Логические основы компьютеров».

Далее

ПЛАН ИЗУЧЕНИЯ ТЕМЫ «ЛОГИКА» ПЛАН ИЗУЧЕНИЯ ТЕМЫ «ЛОГИКА»
  • алгебра логики
  • высказывание
  • логическая операция
  • логическое выражение
  • таблица истинности
  • законы логики

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

Логика

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

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

Алгебра логики это наука о формах и способах мышления. Алгебра логики это наука о формах и способах мышления. Она оперирует логическими высказываниями. Высказывание - это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.
  • В русском языке высказывания выражаются повествовательными предложениями.
  • Побудительные и вопросительные предложения высказываниями не являются.

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

Простое высказывание - логическое высказывание, состоящее из одного утверждения.

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

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

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

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

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

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

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

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

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

Из следующих предложений выбрать те, которые являются высказываниями, объясните свой ответ:

  • Какой длины эта лента?
  • Прослушайте сообщение!
  • Делайте утреннюю зарядку!
  • Назовите устройства ввода/вывода информации.
  • Кто отсутствует?
  • Париж – столица Англии
  • Число 11 является простым
  • 4 + 5 = 10
  • Без труда не вытащишь и рыбку из пруда
  • Некоторые медведи живут на севере
  • Все медведи – бурые
  • Чему равно расстояние от Москвы до Питера?
  • Картины Пикассо слишком абстрактны.
  • Решение задачи – информационный процесс.

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

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

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

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

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

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

А

В

А&В

0

0

0

0

1

0

1

0

0

1

1

1

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

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

Графическое представление

A

B

А&В

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

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

Обозначения: V, |, ИЛИ, +.

А

В

АVВ

0

0

0

0

1

1

1

0

1

1

1

1

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

Графическое представление

A

B

АVВ

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

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

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

А

Ā

0

1

1

0

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

Импликация («если …, то …»)

Высказывание «A  B» истинно, если не исключено, что из А следует B.

A – «Работник хорошо работает».

B – «У работника хорошая зарплата».

A

B

А  B

0

0

1

0

1

1

1

0

0

1

1

1

Эквивалентность («тогда и только тогда, …»)

Высказывание «A  B» истинно тогда и только тогда, когда А и B равны.

A

B

А  B

0

0

1

0

1

0

1

0

0

1

1

1

Вычисление логических выражений

Порядок вычислений:

  • скобки
  • НЕ
  • И
  • ИЛИ,
  • импликация
  • эквивалентность
Задание Определите истинность составного высказывания, состоящего из простых высказываний: А = {Принтер – устройство вывода информации}, В = {Процессор – устройство хранения информации}, С = {Монитор – устройство вывода информации}, D = {Клавиатура – устройство обработки информации}. Решение
  • А = 1, В = 0, С = 1, D = 0
Задание 1.

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

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

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

Задание 2.

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

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

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

Задание 3.

Найти значения выражений для А=0 и В= 0

Задание 4.

Найдите значения логических выражений:

  • ((1V0)&(1&1))&(0V1);
  • ((1&0)V (1&0)) ≈1;
  • ((1V(0&0))

1;

Задание 5

Логические операции при формировании поисковых запросов

Список поисковых запросов

Запросы с операцией И будут располагаться в начале списка (по ним будет найдено мало сайтов)

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

возрастанию

Запросы с операцией ИЛИ будут располагаться в конце списка (по ним будет найдено много сайтов)

В середине списка – смешанные запросы (операции И и ИЛИ)

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

Потом идут запросы, где операция И стоит в скобках

Решение задач (выстроить запросы по возрастанию количества найденных сайтов)

A

чемпионы | (бег & плавание)

Б

чемпионы & плавание

В

чемпионы | бег | плавание

Г

чемпионы & Европа & бег & плавание

Запросы с операцией И располагаются в начале списка.

Чем больше операндов, тем ближе к началу

A

чемпионы | (бег & плавание)

Г

чемпионы & Европа & бег & плавание

Б

чемпионы & плавание

Смешанный запрос – в середине списка

Запрос с операцией ИЛИ располагается в конце списка.

В

чемпионы | бег | плавание

Ответ: ГБАВ

Решение задач (выстроить запросы по возрастанию количества найденных сайтов)

А

разведение & содержание & меченосцы & сомики

Б

содержание & меченосцы

В

(содержание & меченосцы) | сомики

Г

содержание & меченосцы & сомики

Запросы с операцией И располагаются в начале списка.

Чем больше операндов, тем ближе к началу

А

разведение & содержание & меченосцы & сомики

Г

содержание & меченосцы & сомики

Б

содержание & меченосцы

Так как запросов с операцией ИЛИ нет, смешанный запрос будет расположен в конце списка

В

(содержание & меченосцы) | сомики

Ответ: АГБВ

Решение задач (выстроить запросы по возрастанию количества найденных сайтов)

А

волейбол | баскетбол | подача

Б

волейбол | баскетбол | подача | блок

В

волейбол | баскетбол

Г

волейбол & баскетбол & подача

Запрос с операцией И располагается в начале списка

Г

волейбол & баскетбол & подача

Запросы с операцией ИЛИ располагаются в конце списка.

Чем больше операндов, тем ближе к концу

В

волейбол | баскетбол

А

волейбол | баскетбол | подача

Б

волейбол | баскетбол | подача | блок

Ответ: ГВАБ

Решение задач (выстроить запросы по возрастанию количества найденных сайтов)

А

физкультура

Б

физкультура & подтягивания & отжимания

В

физкультура & подтягивания

Г

физкультура | фитнес

Запросы с операцией И располагаются в начале списка.

Чем больше операндов, тем ближе к началу

Б

физкультура & подтягивания & отжимания

В

физкультура & подтягивания

Запрос из одного операнда можно считать запросом ИЛИ с наименьшим числом операндов. Тогда он в списке будет перед всеми запросами с ИЛИ

А

физкультура

Запрос с операцией ИЛИ располагается в конце списка

Г

физкультура | фитнес

Ответ: БВАГ

Решение задач на вычисление количества найденных сайтов

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос

Найдено страниц

(в тысячах)

Крейсер | Линкор

7000

Крейсер

4800

Линкор

4500

Какое количество страниц (в тысячах) будет найдено по запросу Крейсер & Линкор ?

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение задач на вычисление количества найденных сайтов

Решение:

Построим примерную диаграмму Венна.

крейсер

линкор

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

 +  +  = 7000;

- по запросу «крейсер | линкор»

 +  = 4800;

- по запросу «крейсер»

 +  = 4500.

- по запросу «линкор»

 - искомый запрос «крейсер & линкор»

Решение задач на вычисление количества найденных сайтов

Решение:

крейсер

линкор

Решаем систему уравнений:

 +  +  = 7000;

 +  = 4800;

 +  = 4500.

Ответ: по запросу «крейсер & линкор» будет найдено 2300 сайтов.

 = 7000 – 4800 = 2200

 = 4500 – 2200 = 2300.

Решение задач на вычисление количества найденных сайтов

Тренировочная работа №2. Вариант 1

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тысячах) будет найдено по запросу Торты ?

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Запрос

Найдено страниц (в тысячах)

Торты | Пироги

12000

Торты & Пироги

6500

Пироги

7700

Решение задач на вычисление количества найденных сайтов

Решение:

Построим примерную диаграмму Венна.

торты

пироги

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

 +  +  = 12000;

- по запросу «торты | пироги»

 = 6500;

- по запросу «торты & пироги»

 +  = 7700.

- по запросу «пироги»

 +  - искомый запрос «торты»

Решение задач на вычисление количества найденных сайтов

Решение:

торты

пироги

Решаем систему уравнений:

Ответ: по запросу «торты» будет найдено 10800 сайтов.

 +  +  = 12000;

 = 6500;

 +  = 7700.

 +  = 12000 – 6500 = 5500;

 = 7700 – 6500 = 1200;

 = 5500 – 1200 = 4300;

 +  = 4300 + 6500 = 10800

Решение задач на вычисление количества найденных сайтов

Тренировочная работа №2. Вариант 2

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тысячах) будет найдено по запросу Выпечка ?

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Запрос

Найдено страниц (в тысячах)

Пирожное & Выпечка

5100

Пирожное

9700

Пирожное | Выпечка

14200

Решение задач на вычисление количества найденных сайтов

Решение:

Построим примерную диаграмму Венна.

пирожное

выпечка

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

 +  +  = 14200.

- по запросу «пирожное & выпечка»

 = 5100;

- по запросу «пирожное»

 +  = 9700;

- по запросу «пирожное | выпечка»

 +  - искомый запрос «выпечка»

Решение задач на вычисление количества найденных сайтов

Решение:

Решаем систему уравнений:

пирожное

выпечка

 +  +  = 14200.

 = 5100;

 +  = 9700;

 = 5100 – 9700 = 4600;

 +  = 14200 – 4600 = 9600.

Ответ: по запросу «выпечка» будет найдено 9600 сайтов.

Определите какой операции соответствует каждая таблица истинности

А

В

А ? В

0

0

0

0

1

0

1

0

0

1

1

1

А

В

А ? В

0

0

0

0

1

1

1

0

1

1

1

1

А

В

А ? B

0

0

1

0

1

1

1

0

0

1

1

1

А

В

А ? B

0

0

1

0

1

0

1

0

0

1

1

1

Проверьте себя

А

В

АВ

0

0

0

0

1

0

1

0

0

1

1

1

А

В

АВ

0

0

0

0

1

1

1

0

1

1

1

1

А

В

АB

0

0

1

0

1

1

1

0

0

1

1

1

А

В

А  B

0

0

1

0

1

0

1

0

0

1

1

1

Подсчитайте устно: