Презентация по информатике Алгебра логики. Построение таблиц истинности

АЛГЕБРА ЛОГИКИСоздателем алгебры логики является живший в XIX веке английский математик Джордж Буль, в честь которого она названа булевой алгеброй. Алгебра логики – это математический аппарат, с помощью которого записывают (кодируют), вычисляют, упрощают и преобразовывают логические высказывания.Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. Высказывания выступают в качестве логических переменных.Два высказывания называются эквивалентными, если значения их истинности одинаковы.Логическая переменная – это переменная, которая принимает только два значения true – истина и false –ложь.Для связи с двоичной системой счисления вводят обозначения: false (ложь) - 0 true (истина) - 1 Булева алгебра оперирует логическими переменными, которые могут принимать только два значения: «истина» или «ложь» соответственно «1» или «0» и имеет три основные операции И, ИЛИ, НЕ.Порядок выполнения операций:НЕИИЛИМатематический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства электронно-вычислительной машины (ЭВМ, компьютер), поскольку основной системой счисления в ЭВМ является двоичная система счисления, в которой используются цифры 1 и 0.Из этого следуют два вывода: 1) Одни и те же устройства ЭВМ могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных.2) На этапе конструирования аппаратных средств булева алгебра позволяет значительно упростить логические функции, описывающие функционирование схем ЭВМ, и, следовательно, уменьшить число элементарных логических элементов, из десятков тысяч которых строятся основные узлы ЭВМ. Основными базовыми элементами ЭВМ являются элементарные логические схемы И, ИЛИ, НЕ, называемые также вентилями, и триггер.С помощью этих схем можно реализовать любую логическую функцию, описывающую работу тех или иных устройств ЭВМ.Логический элемент – это небольшая часть электронной логической схемы, которая выполняет элементарную логическую функцию. Работу логических схем описывают при помощи таблиц истинности.Таблица истинности – это таблица, в которой перечислены все возможные сочетания значений истинности входных сигналов (операндов) и соответствующие им значения истинности выходных сигналов (результата операции) для каждого из набора входных сигналов. Рассмотрим сначала элементарные логические операции, соответствующие им логические элементы и таблицы истинности, а потом на их основе буде строить таблицы истинности для более сложных логических функций и рассчитывать более сложные электронные схемы. ИНВЕРСИЯ{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}НазваниеОбозначение в математикеВ языке программирования функцияВ материалах ЕГЭНЕ, Инверсия, Логическое отрицание̅NOT¬{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}X¬X0110Пусть X – это логическая переменная, тогда таблица истинности для инверсии (НЕ X) будет выглядеть следующим образом:Соответствующий логический элемент реализующий функцию называется ИНВЕРТОР и на электронной схеме обозначается следующим образом:1ПРОСТЕЙШИЙ ПРИМЕР:Ключ замкнут (1) - лампочка не горит (0), т.к. ток идёт по линии наименьшего сопротивления. Если ключ разомкнуть (0), то ток пойдёт по замкнутому контуру через лампочку, и лампочка будет гореть (1).Операция НЕ выполняется над одной логической переменной или одним логическим выражением. КОНЬЮНКЦИЯ{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}НазваниеОбозначение в математикеВ языке программирования функцияВ материалах ЕГЭИ, Коньюнкция, Логическое умножение&^.AND& ^Пусть X и У – это логические переменные, тогда таблица истинности для операции И будет выглядеть следующим образом:Соответствующий логический элемент реализующий функцию называется СХЕМОЙ СОВПАДЕНИЯ и на электронной схеме обозначается следующим образом:ПРОСТЕЙШИЙ ПРИМЕР:Лампочка будет гореть (1), если замкнут первый ключ (1) и замкнут второй ключ (1), т.е. все ключи замкнуты.Операция И выполняется над несколькими логическими переменными или логическими выражениями.{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}XYX^Y000010100111Единица в результате - тогда и только тогда, когда все входные значения равны единице.& ДИЗЪЮНКЦИЯ{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}НазваниеОбозначение в математикеВ языке программирования функцияВ материалах ЕГЭИЛИ, Дизъюнкция, Логическое сложениеVORVПусть X и У – это логические переменные, тогда таблица истинности для операции ИЛИ будет выглядеть следующим образом:Соответствующий логический элемент реализующий функцию называется СОБИРАТЕЛЬНОЙ СХЕМОЙ и на электронной схеме обозначается следующим образом:ПРОСТЕЙШИЙ ПРИМЕР:Лампочка будет гореть (1), если замкнут первый ключ (1) или замкнут второй ключ (1), т.е. хотя бы один ключ замкнут. Операция ИЛИ выполняется над несколькими логическими переменными или логическими выражениями.{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}XYX V Y000011101111Единица в результате - когда хотя бы одно входное значение равно единице.1 ДРУГИЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}XYX XOR Y000011101110XORИсключающее или{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}XYX → Y001011100111{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}XYX ~ Y001010100111~ Эквиваленция→ СледованиеРезультат истина (1), когда значения логических переменных совпадают (значения логических выражений совпадают при одинаковых наборах входных данных).Результат истина (1), когда истинны или одно, или другое входное значение, но не оба вместе.Результат ложь (0) только тогда, когда из истины (1) следует ложь (0).Из лжи может следовать что угодно. Логическое выражение – это выражение, результатом вычисления которого могут быть только два значения: истина или ложь.В составе логического выражения помимо переменных и констант обязательно присутствуют операции отношения: > больше< меньше= равно>< не равно>= больше равно<= меньше равноИ / ИЛИлогические операции:^, V, ¬, ~, →Операции выполняются в соответствии с их приоритетами. Операции одного уровня выполняются по порядку слева направо. Порядок вычисления операций можно изменить, расставив круглые скобки. Сначала вычисляется выражение в скобках, а потом производятся операции между скобками согласно приоритетам. Алгоритм построения таблицы истинности1)       Подсчитать количество переменных n в логическом выражении;  2)      Определить число строк в таблице, которое равно m = 2n+1; 3)       Подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций;  4)       Ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов;  5)       заполнить столбцы входных переменных наборами значений;  6)       провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в п.4 последовательностью. ЗАДАНИЕПостроить таблицы истинности для следующих логических выражений: XYZ¬YX^¬Y¬X¬X^Z¬(¬X^Z)x^Z¬(x^Z)(X^¬Y)^¬(¬X^Z)(X^¬Y)^¬(¬X^Z)V¬(X^Z)000101010101001101100101010001010101011001100101100110010111101110011011110000010101111000011000Количество переменных - 3 (X, Y, Z)Число строк 23+1=9 (Количество наборов входных значений плюс строка заголовка)Количество столбцов 9+3=11 ( 9 - количество операций, и 3 столбца для переменных)Заполняем столбцы таблицы в соответствии порядком вычисленияВ строку заголовка таблицы заполняются операции (или их номера). Для того, чтобы на сбиться при заполнении наборов данных принято поступать следующим образом: для первой переменной половина значений заполняются 0, вторая половина 1. Для второй переменной каждая из половин делится на две части и соответственно сначала заполняется 0, а потом 1 и т.д. для каждой из последующих переменных. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью. При выполнении элементарных операций используем их таблицы истинности. РАССЧИТАТЬ ЭЛЕКТРОННУЮ СХЕМУ Рассчитать электронную схему – это значит построить для неё таблицу истинности. Схема обрабатывается слева направо. В зависимости от значения на входе и типа элемента получаем значение на выходе и подаем его на следующий элемент .{073A0DAA-6AF3-43AB-8588-CEC1D06C72B9}XYZF0000010100111100101110111Работа электронной схемы описывается логической функцией от трёх переменных F(X,Y,Z). Значение на выходе из схемы при определённом наборе входных значений – есть соответствующее значение функции.FАналогично определяются выходные значения при других наборах данных. РАССЧИТАТЬ ЭЛЕКТРОННУЮ СХЕМУ(проверка)XYZ¬X¬Y¬Z¬Y^¬Z¬Y^¬ZvX¬Y^¬ZvXvY¬X^Z(¬Y^¬ZvXvY)^( ¬XvZ)0001111110000111000010010101001000111000011110001111100101010011001100010110011100001101F(X,Y,Z)= (¬Y^¬ZvXvY)^( ¬XvZ) Работа данной электронной схемы описывается соответствующей логической функцией