Элементы алгебры логики

ЭЛЕМЕНТЫ  АЛГЕБРЫ ЛОГИКИ МАТЕМАТИЧЕСКИЕ ОСНОВЫ  ИНФОРМАТИКИ

Ключевые слова • алгебра логики • высказывание • логическая операция • конъюнкция • дизъюнкция • отрицание • логическое выражение • таблица истинности • законы логики

Логика Аристотель (384­322 до н.э.).   Основоположник формальной логики  (понятие, суждение, умозаключение).  Джордж Буль (1815­1864). Создал новую  область науки ­ Математическую логику  (Булеву алгебру или Алгебру высказываний).  Клод Шеннон (1916­2001). Его  исследования позволили применить алгебру  логики в вычислительной технике

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

Высказывание Высказывание  ­  это  предложение  на  любом  языке,  содержание  которого  можно  однозначно  определить  как  истинное или ложное. В  русском  языке  высказывания  выражаются  повествовательными предложениями: Земля вращается вокруг Солнца. Москва ­ столица.  Но  не  всякое  повествовательное  предложение  является  высказыванием: Это высказывание ложное. Побудительные  и  вопросительные  предложения  высказываниями не являются. Без стука не входить! Откройте учебники. Ты выучил стихотворение?

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

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

Простые и сложные высказывания Высказывания бывают простые и сложные. Высказывание  называется  простым,  если  никакая  его  часть сама не является высказыванием.  Сложные (составные) высказывания строятся из простых с  помощью логических операций. Название логической операции Логическая связка Конъюнкция Дизъюнкция Инверсия  «и»; «а»; «но»; «хотя» «или» «не»; «неверно, что»

Логические операции Конъюнкция  ­  логическая  операция,  ставящая  в  соответствие  новое  высказывание,  являющееся  истинным  тогда  и  только  тогда,  когда оба исходных высказывания истинны. высказываниям  каждым  двум  Другое название: логическое умножение. Обозначения:  , , &, И.  Таблица истинности: Графическое представление А 0 0 1 1 В 0 1 0 1 А&В 0 0 0 1 A B А&В

Логические операции Дизъюнкция    ­  логическая  операция,  которая  каждым  новое  двум  высказывание,  являющееся  ложным  тогда  и  только  тогда,  когда оба исходных высказывания ложны. высказываниям  ставит  в  соответствие  Другое название: логическое сложение. Обозначения:  V, |,  ИЛИ, +.  Таблица истинности: Графическое представление А 0 0 1 1 В 0 1 0 1 АVВ 0 1 1 1 A B АVВ

Логические операции Инверсия  ­  логическая  операция,  которая  каждому  высказыванию  ставит  в  соответствие  новое  высказывание,  значение которого противоположно исходному. Другое название: логическое отрицание. Обозначения: НЕ,  ¬ , ˉ  .  Таблица истинности: Графическое представление А 0 1 Ā 1 0 A Ā Логические операции имеют следующий приоритет: инверсия, конъюнкция, дизъюнкция.

Решаем задачу Пусть  А  =  «На  Web­странице  встречается  слово  "крейсер"»,  В  =  «На  Web­странице  встречается  слово  "линкор"». В  некотором  сегменте  сети  Интернет  5000000  Web­ страниц. В нём высказывание  А истинно для  4800  страниц,  высказывание В ­ для 4500 страниц, а высказывание АVВ ­  для 7000 страниц.  Для какого количества Web­страниц в этом случае будут  истинны следующие выражения и высказывание? а) НЕ (А ИЛИ В); б) А & B; в)  На  Web­странице  встречается  слово  "крейсер"  И  НЕ  встречается слово "линкор".

Представим условие задачи графически: 5 000 000 A И B A A&B B 7 000  НЕ (А ИЛИ В)   4800 – 2300 =  2500 Web­страниц А ИЛИ В  Сегмент Web­страниц   A = 4800, B = 4500.  4800 + 4500 = 9300 На 2500 Web­страницах встречается слово "крейсер" И  5000000 – 7000 = 4 993 000 Web­страниц НЕ (А ИЛИ В) НЕ встречается слово "линкор".   9300 – 7000 = 2300 Web­страниц A&B

Построение таблиц истинности для логических выражений подсчитать n ­ число переменных в выражении подсчитать общее число логических операций в выражении установить последовательность выполнения логических операций определить число столбцов в таблице заполнить шапку таблицы, включив в неё переменные и операции определить число строк в таблице без шапки: m =2n выписать наборы входных переменных провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью

Пример построения таблицы истинности А V A & B n = 2, m = 22 = 4.  Приоритет операций: &, V   A 0 0 1 1 B 0 1 0 1 A&B AVA&B 0 0 0 1 0 0 1 1

Свойства логических операций Законы алгебры­логики Закон исключения Переместительный  третьего  Закон повторения Сочетательный  Законы операций Распределительный  с 0 и 1  Закон двойного Законы общей отрицания  инверсии A & B = B & A A & Ā = 0 A V B = B V A A V Ā = 1 (A & B) & C = A & ( B & C) A & A = A (A V B) V C =A V ( B V C) A V A = A A&(BVC)= (A&B) V (A&C) A & 0=0;   A &1 = A A V 0 = A;  A V 1 = 1 AV(B&C) = (AVB)&(AVC) A & B = Ā V B Ā = A A V B  = Ā & B  Законы алгебры­логикиA & B = B & AA V B = B V AA&(BVC)= (A&B) V (A&C)AV(B&C) = (AVB)&(AVC)(A & B) & C = A & ( B & C)(A V B) V C =A V ( B V C)Переместительный Сочетательный Распределительный Закон двойногоотрицания Ā = AA & Ā = 0A V Ā = 1A & 0=0;   A &1 = AA V 0 = A;  A V 1 = 1A & A = AA V A = AЗакон исключениятретьего Закон повторенияЗаконы операцийс 0 и 1 Законы общейинверсииA & B = Ā V BA V B  = Ā & B

Доказательство закона Распределительный закон для логического сложения:  A v (B & C) = (A v B) & (A v C). A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 B&C A v (B & C) A v B A v C (A v B) & (A v C) 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 Равенство  Складываем А и (В&С) и выводим результат. Умножаем (АvB) на (AvC )и выводим результат. столбцов  Умножаем В на С и выводим результат. Складываем А и В и выводим результат. Складываем А и C и выводим результат. распределительный закон. выделенных  доказывает

Решение логических задач Задача.  Коля,  Вася  и  Серёжа  гостили  летом  у  бабушки.  Однажды  один  из  мальчиков  нечаянно  разбил  любимую  бабушкину вазу. На вопрос, кто разбил вазу, они дали такие ответы: Серёжа: 1) Я не разбивал. 2) Вася не разбивал. Вася: 3) Серёжа не разбивал. 4) Вазу разбил Коля. Коля: 5) Я не разбивал. 6) Вазу разбил Серёжа. Бабушка  знала,  что  один  из  её  внуков  (правдивый),  оба  раза  сказал  правду;  второй  (шутник)  оба  раза  сказал неправду; третий (хитрец) один  раз  сказал  правду,  а  другой  раз  ­  неправду. Назовите имена правдивого,  шутника и хитреца.  Кто из внуков разбил вазу?

Решение. Пусть К =«Коля разбил вазу»,                             В =«Вася разбил вазу»,                              С =«Серёжа разбил вазу».  Представим в таблице истинности высказывания каждого  мальчика.  Так  как  ваза  разбита  одним  внуком,  составим  не  всю  таблицу,  а  только  её  фрагмент,  содержащий  наборы  входных переменных: 001, 010, 100.  K 0 0 1 B 0 1 0 C Утверждение  Утверждение  Утверждение  Серёжи С 0 1 1 В 1 0 1 Васи Коли С 0 1 1 K 0 0 1 К 1 1 0 C 1 0 0 1 0 0 Исходя  из  того,  что  знает  о  внуках  бабушка,  следует  искать в таблице строки, содержащие в каком­либо порядке  три  комбинации  значений:  00,  11,  01  (или  10).  Это  первая  строка. Вазу  разбил  Серёжа,  он  ­  хитрец.  Шутником  оказался  Вася. Имя правдивого внука ­ Коля.

Логические элементы Логический  элемент  –  устройство,  которое  после  обработки  двоичных  сигналов  выдаёт  значение  одной  из  логических операций. А В & А В 1 А И (конъюнктор) ИЛИ (дизъюнктор) НЕ (инвертор) И (конъюнктор)ИЛИ (дизъюнктор)НЕ (инвертор)

Анализ электронной внесём  в  схемы Решение. Все возможные комбинации сигналов на входах А  и  В  истинности.  Проследим  Какой сигнал должен быть на выходе при каждом  преобразование каждой пары сигналов при прохождении их  возможном наборе сигналов на входах? через  логические  элементы  и  запишем  полученный  результат  в  таблицу.  Заполненная  таблица  истинности  полностью описывает рассматриваемую электронную схему. таблицу  А  В  & F A 0 0 1 1 B 0 1 0 1 F 0 0 1 0 В инвертор поступает сигнал от входа В.  В  конъюнктор  поступают  сигналы  от  входа  А  и  от    инвертора. Таким образом, F = A & B.

Самое главное Основные  логические  операции,  определённые  над  Высказывание  —  это  предложение  на  любом  языке,  Таблицы истинности для основных логических операций: содержание  которого  можно  однозначно  определить  как  истинное или ложное. Ā 1 0 A&B AVB высказываниями: инверсия, конъюнкция, дизъюнкция. 0 1 1 1 0 Обозначение 0 0 1 А 0 1 операции Название логической  Логическая связка Инверсия Конъюнкция «не, «неверно, что» ¬, ─ & «и», «а», «но»,  «хотя» сначала  V «или» выполняются  действия  в  скобках.  Приоритет  выполнения  логических операций: ¬, &, V. вычислении  логических  выражений  При  Дизъюнкция A 0 0 1 1 B 0 1 0 1

Вопросы и задания Объясните,  почему  следующие  предложения  не   Постройте отрицания следующих высказываний. В  следующих  высказываниях  выделите  простые  высказывания,  обозначив  каждое  из  них  буквой.  Выясните,  какой  сигнал  должен  быть  на  выходе  являются высказываниями. Запишите с помощью букв и знаков логических операций  электронной схемы при каждом возможном наборе сигналов  Пусть  А  =  «Ане  нравятся  уроки  математики»,  а  В  =  1) Сегодня в театре идёт опера «Евгений Онегин». каждое составное высказывание. на  входах.  Составьте  таблицу  работы  схемы.    Каким  Приведите по одному примеру истинных и ложных  «Ане  нравятся  уроки  химии».  Выразите  следующие  логическим выражением описывается схема?  2) Каждый охотник желает знать, где сидит фазан. высказываний из биологии, географии, информатики,  1) Число 376 чётное и трёхзначное. формулы на обычном языке: 3) Число 1 есть простое число. истории, математики, литературы. 2) Зимой дети катаются на коньках или на лыжах. 4) Натуральные числа, оканчивающиеся цифрой 0, не  3)  Новый  год  мы  встретим  на  даче  или  на  Красной  являются простыми числами. 5) Неверно, что число 3 не является делителем числа  4) Неверно, что Солнце движется вокруг Земли. 198. 6) Коля решил все задания контрольной работы. 5)  Земля  имеет  форму  шара,  который  из  космоса  7) Во всякой школе некоторые ученики интересуются  спортом. 6) На уроке математики старшеклассники отвечали на  8) Некоторые млекопитающие не живут на суше. вопросы  учителя,  а  также  писали  самостоятельную  работу. 1) Какого цвета этот дом? 2) Число Х не превосходит единицы. 3) 4Х +3. 4) Посмотрите в окно. 5) Пейте томатный сок! 6) Эта тема скучна. 7) Рикки Мартин ­ самый популярный певец. 8) Вы были в театре? В  кажется голубым. площади. А  1  F

Вопросы и задания Алёша,  Боря  и  Гриша  нашли  в  земле  старинный  Разбирается  дело  Джона,  Брауна  и  Смита.  сосуд.  Рассматривая  удивительную  находку,  каждый  Известно,  что  один  из  них  нашёл  и  утаил  клад.  На  высказал по два предположения: следствии  каждый  из  подозреваемых  сделал  два  заявления: 1) Алеша: «Это сосуд греческий и изготовлен в V  Смит: «Я не делал этого. Браун сделал это». 2) Боря: «Это сосуд финикийский и изготовлен в III  Джон: «Браун не виновен. Смит сделал это». Браун: «Я не делал этого. Джон не делал этого». 3) Гриша: «Это сосуд не греческий и изготовлен в IV  Суд  установил,  что  один  из  них  дважды  солгал,  веке». другой дважды сказал правду, третий один раз солгал,  Учитель истории сказал ребятам, что каждый из них  один раз сказал правду. прав только в  одном из двух предположений. Где и в  каком веке изготовлен сосуд? Кто из подозреваемых должен быть оправдан? веке». веке».

Опорный конспект Высказывание – это предложение на любом языке, содержание которого  можно однозначно определить как истинное или ложное.  Основные логические операции Инверсия  Конъюнкция Дизъюнкция А 0 1 Ā 1 0 A 0 0 1 1 B 0 1 0 1 A&B 0 0 0 1 A 0 0 1 1 B AVB 0 1 0 1 0 1 1 1 Приоритет выполнения логических операций: ¬, &, V. Инверсия КонъюнкцияДизъюнкцияОсновные логическиеоперации

Электронные образовательные ресурсы 1. http://school­collection.edu.ru/catalog/res/9e997f40­f285­4369­aa7d­88b89 2beca45/?interface=catalog&class=51&subject=19  – Элементарные логические операции