Слайд 1Основы алгебры логики
Кривко-Красько Сергей Васильевич
МОУ «Лицей № 26», г. Подольск
2014
Слайд 2Логические переменные
Логика – наука о «высказываниях».
Высказывание– это форма мышления, в которой
что-либо утверждается или отрицается об объектах, их свойствах или отношениях объектов. Высказывание может быть либо истинно, либо ложно.
Алгебра логики отвлекается от смысловой содержательности высказываний.
Ее интересует только: истинно или ложно высказывание.
Логическая переменная – символическое обозначение высказывания.
Истинность высказывания обозначается значением 1
Ложность высказывания обозначается значением 0
Слайд 3Булева алгебра
Двоичное кодирование – все виды информации кодируются с помощью 0
и 1.
Задача – разработать оптимальные правила обработки таких данных.
Джордж Буль разработал основы алгебры,
в которой используются только 0 и 1
(алгебра логики, булева алгебра).
Почему «логика»?
Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания.
Слайд 4Логические высказывания
Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно
сказать, истинно оно или ложно.
Высказывание или нет?
Сейчас идет дождь.
Жирафы летят на север.
История – интересный предмет.
У квадрата – 10 сторон и все разные.
Красиво!
В городе N живут 2 миллиона человек.
Который час?
Слайд 5Обозначение высказываний
A – Сейчас идет дождь.
B – Температура выше нуля.
простые высказывания
(элементарные)
Составные высказывания строятся из простых с помощью логических связок (операций) «и», «или», «не», «если … то», «тогда и только тогда» и др.
A и B
A или B
если A, то B
не A и B
Сейчас идет дождь и температура выше нуля.
Сейчас идет дождь или температура выше нуля.
Если сейчас идет дождь, то температура выше нуля.
Сейчас нет дождя и температура выше нуля.
Слайд 6Логические функции
Логическая функция (операция) – функция F(x1, x2,…xn),
значение которой и
значения аргументов являются логическими.
Логическая функция может быть задана или с помощью элементарных логических функций (операций), или путем перечисления ее значений для всех возможных наборов (сочетаний) аргументов.
Слайд 7Таблица истинности
Перечисление значений функции F(x1, x2,…xn) для всех вариантов задания аргументов
может быть задано с помощью специальной таблицы: «Таблицы истинности»
Всего в таблице 2N строк
Слайд 8Логические элементы
Описание преобразования двоичных сигналов в электрических схемах компьютера производится с
помощью логических схем, состоящих из логических элементов.
x2
xN
Работа логического элемента может быть описана логической функцией и таблицей истинности
Слайд 9ЭЛЕМЕНТАРНЫЕ
ЛОГИЧЕСКИЕ ФУНКЦИИ
(ОПЕРАЦИИ)
Слайд 10Логическое отрицание (инверсия)
Обозначение:
X, ¬X, not X.
Пример:
X – Идет снег
X -
Неверно, что идет снег
Таблица истинности
НЕ
НЕВЕРНО, ЧТО
Слайд 11
Элемент «НЕ»
Элемент НЕ (инвертор) – реализует операцию отрицания (выдает на выходе
сигнал, противоположный сигналу на входе).
0
0
1
1
Слайд 12Логическое умножение (конъюнкция)
Обозначения:
&, Λ, •, and
Пример:
X1 – Идет снег.
X2 –
Идет дождь.
X1•X2 - Идет дождь со снегом.
Таблица истинности:
И
Слайд 13
Элемент И (конъюнктор) – реализует конъюнкцию двух или более входных сигналов.
Слайд 14Логическое сложение (дизъюнкция)
Обозначения:
∨, +, or
Пример:
X1 – Идет снег.
X2 –
Идет дождь.
X1∨X2 - Идет дождь или снег.
Таблица истинности:
ИЛИ
Слайд 15
Элемент «ИЛИ»
Элемент ИЛИ (дизъюнктор) – реализует дизъюнкцию двух или более входных
Слайд 16Строгая дизъюнкция
Обозначения:
⊕, XOR
Пример:
X1 – Первый урок физика.
X2
– Первый урок химия.
X1 ⊕ X2- Первый урок либо физика, либо химия.
Таблица истинности:
ЛИБО, ЛИБО
Слайд 17Следование (импликация)
Обозначения: →
Пример:
X1 – Идет дождь.
X2 – Асфальт мокрый.
X1→X2 Если идет
дождь, то асфальт мокрый.
Таблица истинности:
Условная связь
ЕСЛИ, ТО
Слайд 18Равнозначность (эквиваленция)
Обозначения:
↔ ⇔ = ≡
Пример:
X1 – Небо голубое.
X2
–Светит солнце.
X1↔X2 – Небо голубое тогда и только тогда, когда светит солнце.
Таблица истинности:
Если и только если
Тогда и только тогда,
Слайд 19Отрицание логического умножения
Обозначения: |
Таблица истинности:
И-не (Штрих Шеффера)
Слайд 20Отрицание логического сложения
Обозначения: ↓
Таблица истинности:
ИЛИ-не (Стрелка Пирса)
Слайд 21Приоритет логических операций
Инверсия
Конъюнкция
Дизъюнкция и строгая дизъюнкция
Импликация и эквиваленция
¬
^
∨
⊕
→
⇔
Слайд 23Переместительный (коммутативный)закон
X·Y = Y·X
X∨Y = Y∨X
Сочетательный (ассоциативный)закон
(X·Y)·Z = Y·(X·Z)
(X∨Y)∨Z = Y∨(X∨Z)
Слайд 24Распределительный (дистрибутивный)закон
X·(Y∨Z) = X·Y∨X·Z
X∨Y·Z = (X∨Y)·(X∨Z)
Закон отрицания (де Моргана)
X·Y
= X∨Y
X∨Y = X·Y
Слайд 25Основные тождества
X·1 = Х
X∨1 = 1
X·0 = 0
X∨0 = Х
Правила исключения
констант
Слайд 26Основные тождества
X·Х = Х
X∨Х = Х
X·Х = 0
X∨Х = 1
X =
X
Правила равносильности
Закон непротиворечия
Закон исключенного третьего
Закон двойного отрицания
Слайд 27Правила упрощения выражений
Правило
поглощения
X∨Х·Y = Х
X∨Х·Y=X·1∨Х·Y=X·(1∨Y)=X·1=X
Правило
свертки
Правило
склеивания
Слайд 28Вычисление логических выражений
Порядок вычислений:
скобки
НЕ
И
ИЛИ, исключающее ИЛИ
импликация
эквивалентность
A
B
V
∙
V
B
C
∙
A
С
∙
1 4 2 5
3
Слайд 29Вычислите значение функции
При x1=0, x2=0, x3=1
При x1=1, x2=1, x3=1
1
0
Слайд 30Вычислите значение функции
При x1=1, x2=0, x3=0
При x1=0, x2=1, x3=0
1
0
Слайд 31Вычислите значение функции
При x1=1, x2=0, x3=0
При x1=0, x2=1, x3=0
1
1
Слайд 32Определите значение логического выражения
При X =1
1
1
При X =2
При X =3
При X
=4
0
1
Учебник, стр. 178, № 10
Слайд 33Составьте таблицу истинности для функции
Слайд 34Составьте таблицу истинности для функции
Слайд 35Составьте таблицу истинности для функции
Слайд 36Определите сигнал на выходе
X1
X2
X3
Y
При x1=0, x2=1, x3=1
При x1=1, x2=0, x3=1
Слайд 37Составьте таблицу истинности для логической схемы, запишите соответсвующую ей логическую функцию.
X1
X2
Y
0
1
1
0
Слайд 38Запишите логическую функцию, соответсвующую логической схеме
X1
X2
X3
Y
Слайд 39Запишите логическую функцию, соответсвующую логической схеме
X1
X2
X3
Y
Слайд 40ЕГЭ 2012 - А3
Дан фрагмент таблицы истинности выражения F:
Какое выражение
соответствует F?
1) X ∧Y∧ Z
2) ¬X ∨¬Y∨ Z
3) X ∨ Y ∨ Z
4) ¬X ∧ ¬Y∧¬Z
Слайд 41
Составить таблицу истинности для функций
Слайд 42Составьте таблицу истинности для функции
Слайд 43Составьте таблицу истинности для функции
Слайд 44Составьте таблицу истинности для функции
Слайд 45Составьте таблицу истинности для функции
Слайд 48ЕГЭ-2012 А10 Знание основных понятий и законов математической логики
1
2
3
4
Укажите, какое логическое
выражение равносильно выражению ¬A \/ ¬ (¬B \/ ¬C)
¬A \/ B \/ ¬C
¬ A \/ (B /\ C)
A \/ B \/ C
A \/ ¬B \/ ¬C
Слайд 49Задачи (упрощение)
Какое логическое выражение равносильно выражению
A ∧ ¬(¬B ∨ C)?
¬A ∨ ¬B ∨ ¬C
A ∧ ¬B ∧ ¬C
A ∧ B ∧ ¬C
A ∧ ¬B ∧ C
Слайд 50Запишите логическую функцию, соответствующую логической схеме и упростите
X1
X2
Y
X3
Слайд 51Синтез логических выражений
Y=F(x1, x2,…xn)
Слайд 52Совершенная дизъюнктивная нормальная форма
СДНФ – форма, в которой функция представлена в
виде логической суммы, каждое слагаемое является произведением всех переменных или их отрицаний.
Задана F(x1,x2,..xn)
Слайд 53
СДНФ функции
F(x1,x2, x3)=1 на 1, 2, 5, 6 наборах таблицы истинности
Записать
СДНФ этой функции
Слайд 54
СДНФ функции
F(x1,x2, x3)=1 на 1, 2, 5, 6 наборах таблицы истинности
Записать
СДНФ этой функции
Упростим функцию
Слайд 55СДНФ функции
F(x1,x2, x3)=1 на 1, 3, 6, 7 наборах таблицы истинности
Записать
СДНФ этой функции и упростить.
Слайд 56СДНФ функции
F(x1,x2, x3)=1 на 3, 5, 6, 7 наборах таблицы истинности
Записать
СДНФ этой функции и упростить.
Слайд 57СДНФ функции
F(x1,x2, x3)=1 на 1, 3, 5, 6, 7 наборах таблицы
истинности
Записать СДНФ этой функции и упростить.
Слайд 58СДНФ функции ДЗ
1) F(x1,x2, x3)=1 на 0, 2, 6, 7
наборах таблицы истинности
2) F(x1,x2, x3)=1 на 0, 1, 2, 3, 4 наборах таблицы истинности
Записать СДНФ этих функций и упростить.
Слайд 62ЕГЭ-2012 А10 Знание основных понятий и законов математической логики
1
2
3
4
Для какого имени
ложно высказывание: Первая буква имени согласная → Последняя буква имени гласная ?
Егор
Максим
Саша
Юля
Слайд 63ЕГЭ-2012 А10 Знание основных понятий и законов математической логики
1
2
3
4
(2012-демо) Какое из
приведенных имен удовлетворяет логическому условию:
(первая буква согласная → вторая буква согласная) ∧(предпоследняя буква гласная → последняя буква гласная)?
Кристина
Степан
Максим
Мария
Слайд 64Логические уравнения
Каково наибольшее целое число X, при котором истинно высказывание
(90
→ (X < (X -1))
Слайд 65Логические уравнения
3. Укажите значения логических переменных K, L, M, N, при
которых логическое выражение
(K ∨ M) → (M ∨ ¬L ∨ N) ложно.
К= L= M= N=
Слайд 66Логические уравнения
Сколько различных решений имеет уравнение
(¬K ∨¬ L ∨ ¬ M)
∧ (L ∨ ¬ M ∨ ¬ N)) = 0
К= L= M= N=
Слайд 67Логические уравнения
Найти все решения уравнения
((B \/ C)⋅ A)→(A
Слайд 68Логические уравнения
Найти все решения уравнения
A \/ B \/
(B→(C \/ D)= 0
A=0 B= 1 C=0 D=0
Слайд 69Использование алгебры логики
Следующие два высказывания истинны:
1. Неверно, что если корабль A
вышел в море, то корабль C – нет.
2. В море вышел корабль B или корабль C, но не оба вместе.
Определить, какие корабли вышли в море.
Слайд 70Использование алгебры логики
По обвинению в ограблении перед судом предстали три человека
- Иванов, Петров и Сидоров. Установлено следующее:
1) если Иванов невиновен, или Петров виновен, то Сидоров виновен;
2) если Иванов невиновен, то Сидоров невиновен.
Установить, виновен ли Иванов.
Слайд 71Использование алгебры логики
Четверо друзей Андрей, Борис, Сергей и Дмитрий решили пойти
на рыбалку. Но Дмитрий в последний момент отказался и высказал следующие предположения:
1) Если Андрей не пойдет на рыбалку, то Борис обязательно пойдет;
2) Не верно, что пойдут Андрей и Сергей;
3) Борис пойдет на рыбалку или пойдет Сергей;
4) Если пойдет Борис, то пойдет на рыбалку и Сергей.
Все предположения Дмитрия оказались истинными. Кто пошел на рыбалку?
Слайд 72Логические задачи
Три свидетеля дали показания о том, что преступники скрылись с
места преступления на:
- черном Ауди (1-ый свидетель),
- на синем Форде (2-ой свидетель),
на Рено, но машина не была черной (3-ий свидетель).
Оказалось, что каждый свидетель в одном своем утверждении был прав, а в одном ошибся. На какой машине скрылись преступники?
Слайд 73
Логические задачи
- черном Ауди (1-ый свидетель),
- на синем Форде (2-ой свидетель),
на
Рено, но машина не была черной (3-ий свидетель).
Слайд 74Логические задачи
- черном Ауди (1-ый свидетель),
- на синем Форде (2-ой свидетель),
на
Рено, но машина не была черной (3-ий свидетель).
Попробуем решить рассуждением.
Предполагаем, что верно одно из предположений и проанализируем последствия:
Ч
А
C
Ф
неЧ
Р
Ч
А
C
Ф
неЧ
Р
Слайд 75Логические задачи
Алеша, Боря и Володя нашли в море сосуд.
Алеша сказал:
«Это сосуд греческий, изготовлен в 5-ом веке до н.э.»
Боря сказал: «Это сосуд финикийский, 3-го века до н.э.».
Володя предположил: «Сосуд негреческий, изготовлен в 4-ом веке до н.э.».
Учитель осмотрел сосуд и сделал вывод, что каждый из ребят был прав только в чем-то одном. Определите, чей это сосуд, и в каком веке изготовлен.
Слайд 76Логические задачи
Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу
своих кумиров:
А) Макс победит, Билл – второй;
В) Билл – третий, Ник – первый;
С) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на турнире заняли Джон, Ник, Билл, Макс?
Слайд 77Логические задачи
Д, Даша и Маша остались дома одни. Кто-то из них
ел варенье. На вопрос мамы, кто это сделал, они сказали:
А) Петя: "Я не ел. Маша тоже не ела";
Б) Вася: "Маша действительно не ела. Это сделал Петя";
В) Маша: "Вася врет. Это он съел".
Выясните, кто ел варенье, если известно,
что двое оба раза сказали правду, а
третий один раз соврал, а один раз сказал правду.
Слайд 78Логические задачи
А) Петя: "Я не ел. Маша тоже не ела";
Б) Вася:
"Маша действительно не ела. Это сделал Петя";
В) Маша: "Вася врет. Это он съел".
двое оба раза сказали правду, а третий один раз соврал, а один раз сказал правду.
Слайд 79Логические задачи
Девять школьников, остававшихся в классе на перемене, были вызваны к
директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы:
Володя: «Это сделал Саша».
Аня: «Володя лжет!»
Егор: «Маша разбила».
Саша: «Аня говорит неправду!»
Рома: «Разбила либо Маша, либо Нина…»
Маша: «Это я разбила!»
Нина: «Маша не разбивала!»
Коля: «Ни Маша, ни Нина этого не делали».
Олег: «Нина не разбивала!»
Кто разбил окно, если известно, что из этих девяти высказываний истинны только три?
Слайд 80Логические задачи
(На одной улице стоят в ряд 4 дома, в которых
живут
4 человека: Алексей, Егор, Виктор и Михаил.
Известно, что каждый из них владеет ровно одной из следующих профессий:
Токарь, Столяр, Хирург и Окулист, но неизвестно, кто какой и неизвестно, кто в каком доме живет.
Однако, известно, что:
1) Токарь живет левее Столяра
2) Хирург живет правее Окулиста
3) Окулист живет рядом со Столяром
4) Токарь живет не рядом со Столяром
5) Виктор живет правее Окулиста
6) Михаил не Токарь
7) Егор живет рядом со Столяром
8) Виктор живет левее Егора
Выясните, кто какой профессии, и кто где живет.
Слайд 81Логические задачи
Аня, Вика и Сергей решили пойти в кино.
Учитель хорошо
знавший этих ребят, высказал следующие предположения:
Аня пойдет в кино только тогда, когда пойдут Вика и Сергей;
Аня и Сергей пойдут в кино вместе или же оба останутся дома;
чтобы Сергей пошел в кино, необходимо, чтобы пошла Вика.
Когда ребята пошли в кино, оказалось, что учитель немного ошибался, из трех его утверждений истинными оказались только два.
Кто из названных ребят пошел в кино?
Слайд 82
Диаграммы Вена (круги Эйлера)
A·B
A+B
A⊕B
A→B
A↔B
Слайд 83Диаграмма МХН (Е.М. Федосеев)
Хочу
Могу
Надо
1
2
3
4
5
6
7
8
Слайд 84Известно количество сайтов, которых находит поисковый сервер по следующим запросам :
Сколько
сайтов будет найдено по запросу
огурцы | помидоры
Задачи
Слайд 85Задачи
NA|B = NA+ NB
A
B
A
B
NA|B = NA+ NB – NA&B
огурцы | помидоры
50
огурцы
помидоры
100
200
огурцы & помидоры
250
Слайд 86Известно количество сайтов, которых находит поисковый сервер по следующим запросам :
Сколько
сайтов будет найдено по запросу
Динамо & Спартак & Рубин
Задачи
Слайд 87
Задачи
Динамо
Спартак
Рубин
1
2
3
Динамо & Рубин
= 1 + 2 = 320
Спартак
& Рубин
= 2 + 3 = 280
(Динамо | Спартак) & Рубин
= 1 + 2 + 3 = 430
Динамо & Спартак & Рубин
= 2
= (320 + 280) – 430 =
170
Слайд 88
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в
автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент:
Сколько сайтов будет найдено по запросу
(принтер | сканер) & монитор
если по трем следующим запросам найдено:
принтер | сканер – 450 сайтов,
принтер & монитор – 40 сайтов
сканер & монитор – 50 сайтов.
Задачи
Слайд 89
Задачи
А (сканер)
B (принтер)
NA|B = NA+ NB – NA&B
принтер | сканер
450
сканер
принтер
200
250
0
сканер
принтер
монитор
90
40
+ 50 =
принтер & монитор = 40
сканер & монитор = 50
50
40
(принтер | сканер) & монитор = ?
Слайд 90Сложная задача
Ниже приведены запросы и количество страниц, которые нашел поисковый сервер
по этим запросам в некотором сегменте Интернета:
мезозой 500
кроманьонец 600
неандерталец 700
мезозой | кроманьонец 800
мезозой | неандерталец 1000
неандерталец & (мезозой | кроманьонец) 200
Сколько страниц будет найдено по запросу
кроманьонец & (мезозой | неандерталец)
Слайд 92Предикаты
Предикат (логическая функция) – это утверждение, содержащее переменные.
Предикат-свойство – от одной
переменной:
P(N) = «В городе N живут более 2 млн человек»
P(Москва) = 1
P(Якутск) = 0
Простое(x) = «x – простое число»
Спит(x) = «x всегда спит на уроке»
Предикат-отношение – от нескольких переменных:
Больше(x, y) = «x > y»
Живет(x, y) = «x живет в городе y»
Любит(x, y) = «x любит y»
Слайд 93
Предикаты и кванторы
Предикаты задают множества:
Предикаты, которые всегда истинны:
для всех вещественных чисел
«Для
любого допустимого x утверждение P(x) истинно»:
высказывание
квантор
Квантор – знак, обозначающий количество.
А
(all – все)
E
(exists – существует)
Слайд 94Кванторы
Какой квантор использовать?
« … моря соленые».
« … кошки серые».
«
… числа чётные».
« … окуни – рыбы».
« … прямоугольники – квадраты».
« … квадраты – прямоугольники».
Истинно ли высказывание?
при
при
при
при
Слайд 95Кванторы
Дано:
A = «Все люди смертны» = 1.
B = «Сократ – человек»
= 1.
Доказать:
C = «Сократ смертен» = 1.
Доказательство:
P(x) = «x – человек» Q(x) = «x – смертен»
A = 1:
при «x =Сократ»
B = 1:
по свойствам импликации
Слайд 96Несколько кванторов
– предикат от переменной y
Квантор связывает одну переменную:
– предикат
от переменной x
Два квантора связывают две переменных:
– высказывание «для любого x существует y, при котором P(x,y)=1»
– высказывание «существует x, такой что при любом y верно P(x,y)=1»
Сравните два последних высказывания при:
Слайд 97Отрицание
НЕ «для любого x выполняется P(x)» ⇔
«существует x, при котором не
выполняется P(x)»
НЕ «существует x, при котором выполняется P(x)» ⇔
«для любого x не выполняется P(x)»
Слайд 99ЕГЭ -2016 -2
Задана лог. функция F = (¬z)∧x ∨ x∧y.
Определите,
какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
Слайд 100ЕГЭ -2015 -2
Александра заполняла таблицу истинности для выражения F. Она успела
заполнить лишь небольшой фрагмент таблицы:
Каким выражением может быть F?
1) x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7 /\ ¬x8
2) x1 \/ x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ ¬x6 \/ ¬x7 \/ ¬x8
3) ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ x7 /\ x8
4) x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ ¬x6 \/ ¬x7 \/ ¬x8
Слайд 101ЕГЭ -2016 -23
Сколько существует различных наборов значений логических переменных
x1, x2, ...
x9, y1, y2, ... y9, которые удовлетворяют всем перечисленным ниже условиям?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
…
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)