Тема урока: «Основные логические: Логические выражения и формулы.

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

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

Логика Аристотель (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­странице  встречается  слово  "линкор"». В  некотором  сегменте  сети  Интернет  5  000  000  Web­ страниц. В нём высказывание  А истинно для  4800  страниц,  высказывание В ­ для 4500 страниц, а высказывание АVВ ­  для 7000 страниц.  Для какого количества Web­страниц в этом случае будут  истинны следующие выражения и высказывание? а) НЕ (А ИЛИ В); б) А & B; в)  На  Web­странице  встречается  слово  "крейсер"  И  НЕ  встречается слово "линкор".

Представим условие задачи графически: 5 000 000 000 A И B A A&B B 7 000  НЕ (А ИЛИ В)   4800 – 2300 =  2500 Web­страниц А ИЛИ В  Сегмент Web­страниц   A = 4800, B = 4500.  4800 + 4500 = 9300 5000000000 – 7000 = 4 993 000 Web­страниц НЕ (А ИЛИ В) На 2500 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).  Это  вторая  строка. Вазу  разбил  Серёжа,  он  ­  хитрец.  Шутником  оказался  Вася. Имя правдивого внука ­ Коля.