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

Содержание

• 
  Слайд 1
  
• 
  Слайд 2
  
• 
  Слайд 3
  
• 
  Слайд 4
  
• 
  Слайд 5
  

  Формальная логика это наука о законах и формах мышления Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем, которые лежат в основе работы любого компьютера

• 
  Слайд 6
  

  Суждения в математической логике называют высказываниями или логическими выражениями Высказывание – это повествовательное предложение, о котором можно сказать, истинно оно или ложно. Примеры: Каждый ромб – параллелограмм (истинно) Каждый параллелограмм – ромб (ложно) Каждый треугольник – равнобедренный треугольник (ложно) Каждый равнобедренный треугольник – треугольник (истинно)

• 
  Слайд 7
  

  Сложное (составное) высказывание - получается из простых или сложных высказываний с использованием союзов «И», «ИЛИ» и частицы «НЕ» Простые ИЛИ сложные высказывания также называют логическими выражениями

• 
  Слайд 8
  

  Пример: Составить сложное высказывание с союзом И, ИЛИ Простое высказывание: «На улице светит солнце» Простое высказывание: «На улице пасмурная погода» Сложное высказывание с союзом «И»: «На улице светит солнце И на улице пасмурная погода» ЛОЖНО Сложное высказывание с союзом «ИЛИ»: «На улице светит солнце ИЛИ на улице пасмурная погода» ИСТИННО

• 
  Слайд 9
  

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

• 
  Слайд 10
  

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

• 
  Слайд 11
  

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

• 
  Слайд 12
  

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

• 
  Слайд 13
  

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

• 
  Слайд 14
  

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

• 
  Слайд 15
  

  Простые и сложные высказывания Высказывания бывают простые и сложные. Высказывание называется простым, если никакая его часть сама не является высказыванием. Сложные (составные) высказывания строятся из простых с помощью логических операций.

• 
  Слайд 16

  А={Юра делает физику.}B={Юра пойдет на дискотеку.}

  A&B A&B A&B AvB AvB AvB Юра делает физику и пойдет на дискотеку. Юра не делает физику и пойдет на дискотеку. Юра делает физику и не пойдет на дискотеку. Юра сделает физику или пойдет на дискотеку. Юра не сделает физику или пойдет на дискотеку. Юра сделает физику или не пойдет на дискотеку. =1 =0 =0 =0 =1 =1 =0 =1

• 
  Слайд 17
  

  A&B AvB A&B Неверно, что Юра сделает физику и пойдет на дискотеку. Неверно, что Юра сделает физику или пойдет на дискотеку. Неверно, что Юра не сделает физику и пойдет на дискотеку. =(1&0) =(1&0) =(1v0)

• 
  Слайд 18
  

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

• 
  Слайд 19
  

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

• 
  Слайд 20
  

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

• 
  Слайд 21

  F =X & (Y v X)

• 
  Слайд 22

  F = Х v (Y v X)& X

• 
  Слайд 23

  Заполнение таблиц истинности

  Определить число переменных n Определить порядок и количество действий (количество столбцов таблицы) Определить количество строк: m =2n Заполнить таблицу

• 
  Слайд 24
  

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

• 
  Слайд 25
  

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

• 
  Слайд 26
  

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

• 
  Слайд 27
  

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

• 
  Слайд 28
  

  Свойства логических операций Законы алгебры-логики A & B = B & A A V B = B V A A&(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) Переместительный Сочетательный Распределительный Закон двойного отрицания Ā = A A & Ā = 0 A V Ā = 1 A & 0=0; A &1 = A A V 0 = A; A V 1 = 1 A & A = A A V A = A Закон исключения третьего Закон повторения Законы операций с 0 и 1 Законы общей инверсии A & B = Ā VB A V B = Ā & B

• 
  Слайд 29
  

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

• 
  Слайд 30
  

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

• 
  Слайд 31
  

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

• 
  Слайд 32

  (X v Y)&X v Y

• 
  Слайд 33

  Переключательные схемы

  a F a b F Последовательное соединение Параллельное соединение

• 
  Слайд 34
  

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

• 
  Слайд 35

  Анализ электронной схемы

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

• 
  Слайд 36

  Тождество

  Две формулы алгебры логики Аи В называются равносильными, если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в них. Обозначают равносильности (тождества) с помощью знака =.

• 
  Слайд 37
  

  Формула А называется тождественно-истинной, или тавтологией, если она принимает значение «истинно» при всех значениях переменных, входящих в нее. Иными словами, тавтологией является функция, где все переменные фиктивны и хотя бы при одном наборе значений аргументов ее значение равно 1.

• 
  Слайд 38
  

  Формула называется тождественно-ложной, если она принимает значение нуль при всех значениях переменной, входящих в нее.

• 
  Слайд 39

  Булевы функции

  Булева функция от n переменных — это произвольное отображение вида f:{0,1}n{0,1} Гдеn – количество логических переменных Булева функция от n переменных может быть задана таблицей истинности, состоящей из n + 1 столбцов и 2n строк. В первых n столбцах перечисляются все наборы из множества {0,1} в лексикографическом (словарном) порядке, а в последнем, (n + 1)-м столбце — значения функций на этих наборах.

• 
  Слайд 40
  
• 
  Слайд 41
  

  Функция f7 = (0110), равная 0 только при совпадающих аргументах, называется суммой по модулю два. F(A,B) = AB Другое название — строгая дизъюнкция: значение функции равно 1, если либо первый, либо второй аргументы равны 1, но никак не оба.

• 
  Слайд 42
  

  Функция f9 = (1000), равная 1, только если оба аргумента равны 0, называется стрелкой Пирса. F(A,B) = AB Стрелка Пирса является отрицанием дизъюнкции.

• 
  Слайд 43
  

  Функция f15 = (1110), равная 0, только если оба аргумента равны 1, называется штрихом Шеффера. f(A, B) = A I B. Штрих Шеффера является отрицанием конъюнкции.

• 
  Слайд 44
  
• 
  Слайд 45
  
• 
  Слайд 46

  Решение логических задач

• 
  Слайд 47

  Задача 1(метод рассуждений, с помощью графа)

  При составлении расписания на понедельник преподаватели высказали просьбу завучу. Учитель математики: «Желаю иметь первый или второй урок». Учитель истории: «Желаю иметь первый или третий урок». Учитель литературы: «Желаю иметь второй или третий урок». Какое расписание будет составлено, если по каждому предмету может быть только один урок?

• 
  Слайд 48

  Решение логической задачи методом рассуждений

  Пусть в просьбе математика первое высказывание истинно, а второе – ложно. «Желаю иметь первый или второй урок». 1 0 Т.е. первым будет урок математики. Тогда в просьбе учителя истории первое высказывание ложно, а второе истинно, т.е. третьим будет урок истории. «Желаю иметь первый или третий урок». 0 1 Значит, в пожелании учителя литературы окажется истинной первая часть, т.е. урок литературы будет вторым. «Желаю иметь второй или третий урок». 1 0 Итак: I урок – математика, II урок – литература, III урок – история.

• 
  Слайд 49
  

  Предположим, что в высказывании учителя математики первое высказывание ложно, а второе истинно. «Желаю иметь второй или второй урок». 0 1 Т.е. вторым будет урок математики. Тогда в просьбе учителя литературы первое высказывание ложно, а второе истинно, т.е. третьим будет урок литературы. «Желаю иметь второй или третий урок». 0 1 А в пожелании учителя истории окажется истинной первая часть, т.е. урок истории будет первым. «Желаю иметь первый или третий урок». 1 0 Итак: I урок - история II урок - математика III урок – литература.

• 
  Слайд 50

  Решение с помощью графов

  Вершины графа – обозначения уроков и их порядковые номера в расписании. Рёбра графа – высказывания преподавателей: просьба учителя математики – красные линии (М1 и М2); просьба учителя истории – зелёные линии – (И1 и И3); просьба учителя литературы – синие линии (Л2 и Л3). М И Л 1 2 3

• 
  Слайд 51

  Задача 2. Решение средствами алгебры логики

  Три грибника, рассматривая найденный гриб, высказали свои предположения. Первый грибник сказал: «Не верно, что если это не опёнок, то этот гриб съедобный». Второй грибник сказал: «Не верно, что этот гриб или ядовитый, или опёнок, или не сыроежка». А третий добавил: «Это гриб не ядовитый, и я отрицаю, что если это сыроежка, то она съедобна». В итоге оказалось, что все три грибника были правы, и их суждения истинны. Какой гриб нашли грибники?

• 
  Слайд 52
  

  Обозначим: А – «Гриб опёнок», В – «Гриб сыроежка», С – «Гриб съедобный», D – «Гриб ядовитый». Тогда высказывание I грибника («Не верно, что если это не опёнок, то этот гриб съедобный») запишем как: Высказывание II грибника («Не верно, что этот гриб или ядовитый, или опёнок, или не сыроежка») запишем в виде: Высказывание третьего грибника: («Это гриб не ядовитый, и я отрицаю, что если это сыроежка, то она съедобна») запишем в виде: Т.к. высказывания всех грибников истинны, то итоговая функция равна их конъюнкции: F== Функция F принимаетединичное значение только при одном наборе значений аргументов, в котором А=0, В=1, С=0, D=0, т.е. найденный гриб – сыроежка.

• 
  Слайд 53

  Задача 3.Решение средствами алгебры логики)

  Следователь допросил трёх лиц- А, В и С, подозреваемых в совершении преступления. На допросе А сказал, что показания В неверны. В сказал, что показания С неверны. С сказал, что и А говорит неправду, и В говорит неправду. Может ли следователь на основании этих показаний установить, кто из допрошенных говорит неправду? За писав высказывания с помощью алгебры логики получим систему уравнений: Перемножив уравнения получим результат: . Следовательно, правду сказал подозреваемый ...

• 
  Слайд 54
  

  Задача 4. Следующие два высказывания истинны: «неверно, что если магазин А организует распродажу, то магазин С тоже»; «из двух магазинов В и С организует распродажу только один». Какие магазины организуют распродажу?

• 
  Слайд 55
  

  «Если магазин А организует распродажу, то магазин С тоже» A→C «Неверно, что если магазин А организует распродажу, то магазин С тоже» Из условия известно, что это высказывание истинно. Следовательно:

• 
  Слайд 56
  

  «Из двух магазинов В и С организует распродажу только один»

• 
  Слайд 57
  

  Это возможно только в одном случае, когда A=1, B=1, С=0. То есть, магазины A и Bпроводят распродажу, а магазинС – нет.

• 
  Слайд 58

  Минимизация булевых функций

• 
  Слайд 59
  

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

• 
  Слайд 60

  Элементарная конъюнкция (дизъюнкция)

  Элементарной конъюнкцией (дизъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделенных операциями конъюнкции (дизъюнкции)

• 
  Слайд 61

  Нормальная форма

  Дизъюнктивной (конъюнктивной) нормальной формой называется дизъюнкция (конъюнкция) конечного числа элементарных дизъюнкций (конъюнкций). Сокращенно они обозначаются ДНФ и КНФ соответственно.

• 
  Слайд 62
  
• 
  Слайд 63
  

  Процесс построения функциональных схем для разработки устройства ПК можно представить в виде алгоритма: Анализ функций Составление таблиц истинности по результатам п.1 Синтез логической функции по таблице истинности Минимизация полученной логической функции Построение логической схемы устройства по результатам п.4

• 
  Слайд 64
  

  Алгоритм синтеза логической функции: В заданной таблице истинности находятся наборы переменных (строки), в которых F(x1,…xn)=1 Для каждого набора записывается конъюнкция всех входных переменных, значение которых равно 0. Все полученные конъюнкции объединяются дизъюнкцией в логическую функцию и минимизируются