Теоретическая информатика. Алгебра логики. Титоров Даниил Юрьевич. - презентация

1 Теоретическая информатика. Алгебра логики. Титоров Даниил Юрьевич

2 Реле состоит из: катушки, двух источников тока, двух переключателей и лампочки. принцип работы: При переключении ключа (1), в катушке идет ток и появляется электромагнитное поле (2). Под действием поля металлический ключ (3) притягивается к катушке, замыкая вторую цепь. Под действием электрического тока лампочка начинает светиться. Реле было изобретено в 1831 году, использовалось для работы телеграфа и позже телефонной связи. Создатели не подозревали, что с помощью реле можно создать компьютер. Реле

3 Краткая схема реле В дальнейших схемах будут использоваться краткие схемы реле, некоторые элементы на схеме опущены, но принцип действия остается тем же самым.

4 Объединение нескольких реле позволяет получить логические вентили: 1.логический вентиль «И» 2.логический вентиль «Или» 3.логический вентиль «Не» проанализируйте каждый из предложенных схем что произойдет если замкнуть каждый из ключей? Почему логические вентили получили такие названия? Набор из нескольких реле мы будем далее использовать как единые логические вентили. Логические вентили

5 Логический вентиль «И» два входа один выход; на выходе ток есть только если на оба входа подан ток. Логический вентиль «И» два входа один выход; на выходе ток есть если хотя бы на один вход подан ток. Логический вентиль «Не» один вход один выход; на выходе ток есть если на входе его нет (это не противоречие, смотри схему вентиля). Логические вентили

6 Можно изобразить в таблице все возможные состояния каждого логического вентиля. Такие таблицы называются таблицы истинности. В таблице показаны все возможные входящие значения от 00 до 11 (порядок значений имеет значение) и что мы имеем на выходе для каждого набора. Таблицы истинности

7 Соединяя логические схемы в определенной последовательности можно получить логическую схему. Например, на схеме, представленной на рисунке два вентиля «И», два вентиля «Не» и один вентиль «Или». Подставляя значения на входе, можно проследить какое значение будет на выходе логической схемы. Для того чтобы проанализировать все значения могут быть на выходе нужно построить таблицу истинности для данной логической схемы. Логические схемы

8 Можно построить в электронных таблицах модель логической схемы, написать логическая функции, которые соответствуют каждому вентилю и получить все возможные значения, которые может принять схема. формула в ячейках: C2 =И(A2;B2) D2 =НЕ(A2) E2 =НЕ(B2) F2 ==И(D2;E2) G2 =ИЛИ(C2;F2) H2 =ЕСЛИ(G2;1;0) Логические схемы в MS Excel

9 У некоторых схем есть особые названия, например, у полусумматора. Он называется так, потому что имитирует сложение двух младших разрядов у двоичных чисел. В самом деле = 1 (первая строка истинности) = 1 (вторая строка истинности) и т.д. Возможно складывать числа используя только механические реле! Попробуйте построить модель полусумматора в MS Excel. Полусумматоры

10 Сложение чисел во втором и большем разрядах по сути является сложением трех чисел (двух чисел в каждом разряде, и еще одного бита переноса, что пришел из младшего разряда). Для выполнения такой операции необходим сумматор, который состоит из двух полусумматоров и одного логического вентиля или. Объединение сумматоров в группу для сложения многоразрядных двоичных чисел образуют каскад сумматоров. Попробуйте построить модель сумматора каскада сумматоров в MS Excel. Сумматор

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

12 Из всего бесконечного количества логических схем с двумя входящими сигналами можно сделать не более шестнадцати различных наборов выходящих значений. Следовательно существует шестнадцать логических функций двух аргументов F 1..F 16. На рисунке представлены все шестнадцать функций. Это число легко вычислить: Для функций из 2-х элементов 4 набора входных значений от 00 до 11. Одна функция принимает значения от 0000 до 1111 всего вариантов 16. Для n входных значений существует 2 2 n различных функций. Логические функции

13 Среди шестнадцати функций есть несколько знакомых. Например, F 9 = A and BF 15 = A or B Легко заметить, что каждая функция имеет себе противоположную. Например, F 2 = not F 15 Функция F 16 называется тождественно истинной (она принимает значение равное 1 при любом входном значении). Функция F 1 называется тождественно ложной (она принимает значение равное 0 при любом входном значении). Логические функции

14 Любую логическую функцию легко записать. Для этого достаточно построить ее область определения, описать ее значение на языке множеств с помощью кругов Эйлера. Рассмотрим, например, функцию F 6. На двух пересекающихся кругах закрасим области, в которых F=1: когда и А и В = 0 (т.е. точки не принадлежат ни А и не В) когда и А = 1 и В = 0 (т.е. точки принадлежат А, но не принадлежат В) Из рисунка видно что F 6 = не В. Но т.к. у функции два аргумента вернее записать так: F 6 = (не А и не B) или (А и не В) Круги Эйлера

15 Логические выражения из таблицы видно, что F = (не A и не B и C) или (не A и B и не C) или (A и не B и не C) или (A и не B и C) или (A и B и не C) с помощью кругов Эйлера можно упростить: F = (A или B или C) и не (B и C)

16 Логические законы Для упрощения логических функций (схем) можно использовать круги Эйлера, а также формальные законы, которые помогут упростить сложное выражение. Законов много, но многие очевидны, и все их можно легко доказать, например, законы де Моргана.

17 Спасибо за внимание