Презентация "Логические функции" – проект, доклад

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

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

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

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

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

Клод Шеннон (1916-2001). Его исследования позволили применить алгебру логики в вычислительной технике

Логика

Аристотель (384-322 до н.э.). Основоположник формальной логики (понятие, суждение, умозаключение).

Джордж Буль (1815-1864). Создал новую область науки - Математическую логику (Булеву алгебру или Алгебру высказываний).

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

Алгебра

Высказывание - это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.

В русском языке высказывания выражаются повествовательными предложениями: Земля вращается вокруг Солнца. Москва - столица.

Побудительные и вопросительные предложения высказываниями не являются. Без стука не входить! Откройте учебники. Ты выучил стихотворение?

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

Но не всякое повествовательное предложение является высказыванием: Это высказывание ложное.

Высказывание или нет?

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

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

Алгебра логики

Простые и сложные высказывания

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

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

A&B A&B A&B AvB AvB AvB

Юра делает физику и пойдет на дискотеку. Юра не делает физику и пойдет на дискотеку. Юра делает физику и не пойдет на дискотеку. Юра сделает физику или пойдет на дискотеку. Юра не сделает физику или пойдет на дискотеку. Юра сделает физику или не пойдет на дискотеку.

=1 =0

A&B AvB A&B

Неверно, что Юра сделает физику и пойдет на дискотеку. Неверно, что Юра сделает физику или пойдет на дискотеку. Неверно, что Юра не сделает физику и пойдет на дискотеку.

=(1&0) =(1v0)

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

Логические операции

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

Графическое представление

A B А&В

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

АVВ

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

Логические операции имеют следующий приоритет: инверсия, конъюнкция, дизъюнкция.

Ā

F =X & (Y v X)

F = Х v (Y v X)& X

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

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

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

Решаем задачу

5 000 000 – 7000 = 4 993 000 Web-страниц НЕ (А ИЛИ В)

A = 4800, B = 4500. 4800 + 4500 = 9300

4800 – 2300 = 2500 Web-страниц

Представим условие задачи графически:

На Web-страницах встречается слово "крейсер" И НЕ встречается слово "линкор".

5 000 000 7 000 НЕ (А ИЛИ В)

Сегмент Web-страниц

A&B

9300 – 7000 = 2300 Web-страниц A&B

И А ИЛИ В

Построение таблиц истинности для логических выражений

подсчитать n - число переменных в выражении

подсчитать общее число логических операций в выражении

установить последовательность выполнения логических операций

определить число столбцов в таблице

заполнить шапку таблицы, включив в неё переменные и операции

определить число строк в таблице без шапки: m =2n

выписать наборы входных переменных

провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью

А V A & B n = 2, m = 22 = 4. Приоритет операций: &, V

Пример построения таблицы истинности

Свойства логических операций

Законы алгебры-логики

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 & Ā = 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 v (B & C) = (A v B) & (A v C).

Доказательство закона

Умножаем В на С и выводим результат.

0 1

Складываем А и В и выводим результат.

Складываем А и (В&С) и выводим результат.

Складываем А и C и выводим результат.

Умножаем (АvB) на (AvC )и выводим результат.

Равенство выделенных столбцов доказывает распределительный закон.

Задача. Коля, Вася и Серёжа гостили летом у бабушки. Однажды один из мальчиков нечаянно разбил любимую бабушкину вазу.

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

На вопрос, кто разбил вазу, они дали такие ответы: Серёжа: 1) Я не разбивал. 2) Вася не разбивал. Вася: 3) Серёжа не разбивал. 4) Вазу разбил Коля. Коля: 5) Я не разбивал. 6) Вазу разбил Серёжа.

Бабушка знала, что один из её внуков (правдивый), оба раза сказал правду; второй (шутник) оба раза сказал неправду; третий (хитрец) один раз сказал правду, а другой раз - неправду. Назовите имена правдивого, шутника и хитреца. Кто из внуков разбил вазу?

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

Исходя из того, что знает о внуках бабушка, следует искать в таблице строки, содержащие в каком-либо порядке три комбинации значений: 00, 11, 01 (или 10). Вазу разбил Серёжа, он - хитрец. Шутником оказался Вася. Имя правдивого внука - Коля.

(X v Y)&X v Y

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

Последовательное соединение

Параллельное соединение

Логический элемент – устройство, которое после обработки двоичных сигналов выдаёт значение одной из логических операций.

Логические элементы

Какой сигнал должен быть на выходе при каждом возможном наборе сигналов на входах?

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

Решение. Все возможные комбинации сигналов на входах А и В внесём в таблицу истинности. Проследим преобразование каждой пары сигналов при прохождении их через логические элементы и запишем полученный результат в таблицу. Заполненная таблица истинности полностью описывает рассматриваемую электронную схему.

В инвертор поступает сигнал от входа В.

В конъюнктор поступают сигналы от входа А и от инвертора. Таким образом, F = A & B.

Тождество

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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