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

Логические основы информатики

Математическая логика

• Булева алгебра (алгебра логики) возникла в середине XIX века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

• Алгебра логики оперирует с ЛОГИЧЕСКИМИ ВЫСКАЗЫВАНИЯМИ.

ЛОГИЧЕСКОЕ ВЫСКАЗЫВАНИЕ

Логическое высказывание – повествовательное предложение, в отношении которого можно точно сказать, истинно оно или ложно. Логическое высказывание можно обозначить любой буквой латинского алфавита.

Логическое

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

НЕ логическое высказывание

• «6 – чётное число»
• «Река Волга впадает в Чёрное море»
• «Дважды два – пять»

• «Я прав»
• «Информатика – интересный предмет»
• «Кто там?»

Приведите свои примеры логических и нелогических высказываний

ЛОГИЧЕСКИЕ СВЯЗКИ

• Простые логические высказывания можно объединять в СОСТАВНЫЕ при помощи ЛОГИЧЕСКИХ СВЯЗОК .

ЛОГИЧЕСКИЕ СВЯЗКИ

НЕБАЗОВЫЕ:

Исключающее ИЛИ

Импликация

Эквиваленция

БАЗОВЫЕ:

ИЛИ

И

НЕ

БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Логическое отрицание, НЕ, инверсия

образуется из простого высказывания с помощью добавления частицы «НЕ» к сказуемому или использования оборота речи «неверно, что…».

Инверсия обозначается: НЕ А, NOT A , ¬ А,

Таблица истинности: Диаграмма Эйлера-Венна:

А

Базовые логические элементы

• Логический элемент компьютера – это часть электронной логической схемы, которая реализует элементарную логическую функцию.

• Базовую логическую функцию НЕ реализует ИНВЕРТОР.

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

Логическое состояние «1» означает уровень напряжения от 4,5 до 5 вольт, а «0» - от 0 до 0,5 вольт.

БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Логическое сложение, ИЛИ, нестрогая дизъюнкция

Образуется соединением двух (или более) высказываний в одно с помощью союза «или».

Она обозначается: А+В, А ИЛИ В, A OR B ,

Таблица истинности: Диаграмма Эйлера-Венна:

В

А

Базовые логические элементы

• Базовую логическую функцию ИЛИ реализует ДИЗЪЮНКТОР.

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

• Дизъюнктор имеет число входов, количество которых равно степени числа 2, например, 2,4,8 и т.д. и один выход.

БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Логическое умножение, И, конъюнкция

Образуется соединением двух (или более) высказываний в одно с помощью союза «и».

Она обозначается: А*В, А И В, А & В, A AND B ,

Таблица истинности: Диаграмма Эйлера-Венна:

В

А

Базовые логические элементы

• Базовую логическую функцию И реализует КОНЪЮНКТОР.

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

• Конъюнктор имеет число входов, количество которых равно степени числа 2, например, 2,4,8 и т.д. и один выход.

НЕБАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Исключающее ИЛИ, строгая дизъюнкция

Образуется соединением двух (или более) высказываний в одно с помощью союза «или», который используется в разделительном смысле.

Строгая дизъюнкция обозначается: А В, A Х OR B

Таблица истинности: Замена операции

исключающее ИЛИ через базовые:

НЕБАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Логическое следование, импликация

Образуется соединением двух высказываний в одно с помощью оборотов речи «если…, то…», «из …следует…», «из…вытекает…»

Импликация обозначается: А → В,

Таблица истинности: Замена операции

импликации через базовые:

Импликация ложна только тогда, когда А истинно, а В – ложно.

НЕБАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Логическое равенство, эквиваленция, двойная импликация

Образуется соединением двух высказываний в одно с помощью оборотов речи «…тогда и только тогда, когда…», «…равносильно…».

Эквиваленция обозначается: А ↔ В,

Таблица истинности: Замена операции

эквиваленции через базовые:

Проверь свои знания

Определите, какое из повествовательных предложений не является логическим высказыванием:

1. Все зебры полосаты.

2. Некоторые школьники – спортсмены.

3. На небе 28 триллионов звёзд.

4. Лев – травоядное животное.

Проверь свои знания

Определите, какая из формул отображает структуру следующего логического высказывания: «Ваш приезд не является ни необходимым, ни желанным».

1.

2.

3.

4.

Проверь свои знания

Определите, какое из повествовательных предложений соответствует логической формуле А →В :

1. Льёт ли тёплый дождь, падает ли снег -нужно идти на работу.

2. Вчера было пасмурно, а сегодня ярко светит солнце.

3. Поиски врага велись уже три часа, но безрезультатно.

4. И добродетель стать пороком может, когда её неправильно приложат.

Проверь свои знания

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

«Если птица – страус, то она не летает»

1. Истина

2. Ложь

Проверь свои знания

Какая из логических формул соответствует диаграмме Эйлера-Венна:

1.

2.

3.

4.

В

А

Проверь свои знания

Логическое высказывание «Если Винни-Пух съел мёд, то он сыт» эквивалентно фразе:

1. Если Винни-Пух не сыт, то мёда он не ел.

2. Если Винни-Пух сыт, то мёда он не ел.

3. Если Винни Пух не сыт, то он съел мёд.

4. Неизвестно, сыт ли Винни-Пух, хоть он и съел мёд.

Проверь свои знания

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

(( X  1) -  (X  2))  ((X  2)-  (X  4))

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

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

Какое логическое выражение равносильно

 (  А -  В)?

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

1) А V В 2) А  В 3)  А  В 4)  А V  В

Сколько различных решений имеет уравнение

( K  L  M ) V (  L  M  N ) = 1

где К, L , М, N - логические переменные?

Составление таблицы истинности для логической формулы

• Таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
• Правила построения таблиц истинности:

- посчитать количество переменных N в логической формуле. Количество строк в таблице истинности вычисляется по формуле: 2 N + 1 (для заголовка)

- подсчитать количество логических связок K в формуле. Количество столбцов в таблице истинности вычисляется по формуле: К + N .

Задание 1.

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

х

у

0

0

0

1

1

1

0

1

F

Задание 2 .

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

x

y

0

0

z

0

0

0

0

1

1

0

1

0

1

1

0

1

0

1

0

1

1

1

F

1

0

1

Задание 3 .

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X , Y , Z .

• Дан фрагмент таблицы истинности выражения F :

Чему равно F?

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

1) X  Y  Z

2)  X V Y V Z

3)  Х  Y  Z

4) X V Y V Z

x

0

y

0

z

0

F

0

0

0

1

0

1

1

0

0

1

1

1

0

Основные законы алгебры логики

Закон

Для ИЛИ

Переместительный

Для И

Сочетательный

Распределительный

Правила де Моргана

Идемпотенции

Поглощения

Склеивания

Операция переменной с её инверсией

Операция с константами

Двойного отрицания

Упрощение логических формул

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

Домашнее задание:

Литература

• Шауцукова Л.З. «Информатика 10-11»,Москва, Просвещение, 2000 г.
• Лыскова В., Ракитина Е. «Логика в информатике», Москва, Лаборатория Базовых Знаний, 2006 г.
• Богомолова О.Б. «Логические задачи»,Москва, БИНОМ. Лаборатория знаний, 2005 г.
• Угринович Н.Д., «Информатика и информационные технологии 10-11», Москва, БИНОМ, 2003 г.