Логические основы построения компьютера - презентация

1 1. Основные понятия алгебры логики Основные понятия алгебры логики 2. Логические выражения и логические операции Логические выражения и логические операции 3. Составление таблиц истинности по логической формуле Составление таблиц истинности по логической формуле 4. Некоторые законы булевой алгебры Некоторые законы булевой алгебры 5. Определение логического выражения по таблице истинности Определение логического выражения по таблице истинности 6. Логические элементы и основные логические устройства компьютера. Логические элементы и основные логические устройства компьютера

2 Алгебра логики – аппарат, который позволяет выполнять действия над высказываниями. Высказывание – это предложение, относительно которого имеет смысл говорить истинно оно или ложно: Все кошки серы(ложь) Париж-столица Франции(истина) 5*5=25(истина) H+O=H 2 O(ложь) Высказывания могут быть представлены с помощью математических, химических и прочих знаков.

3 Не все выражения можно назвать высказываниями: Программное обеспечение компьютера – это комплекс используемых в компьютере программ. Это выражение является определением термина «программное обеспечение». Определение не могут быть истинными или ложными, так как они лишь фиксируют принятое использование терминов 5 х+8=4В выражении не указано, для какого х определяется истинность или ложность этого выражения Она умнаВ выражении не указано, о каком конкретном человеке идет речь Существуют внеземные цивилизации. Истинность или ложность этого выражения еще не установлена На улице идет дождьВ выражении не определены название города, не указано время, Поэтому нельзя установить истинность или ложность выражения

4

5 Примеры: Высказывание «Земля вращается вокруг Солнца» истинно. Высказывание «Земля не вращается вокруг Солнца» ложно. Высказывание «4 – простое число» ложно. Высказывание «4 – не простое число» истинно. Условные обозначения: Ā, not А, ¬А. АĀ истина ложь истина АĀ или

6 Примеры: Знания или везение – залог сдачи экзаменов. Успешно сдать экзамен может тот, кто все знает, или тот, кому повезло (например, вытянул единственный выученный билет), или тот, кто все знает и при этом выбрал «хороший» билет. Условные обозначения: А\/ В. АBA\/ B

7 Примеры: Умение и настойчивость приводят к достижению цели. Достижение цели возможно только при одновременной истинности двух предпосылок – умения и настойчивости. Условные обозначения: А/\ В, А&В, А and В. АBA/\ B

8 Примеры: Добиться результатов в спорте можно тогда и только тогда, когда приложено максимум усилий. Условные обозначения: A ~ B АBA ~BA ~B

9 Примеры: Если идет дождь, то на улице сыро. Если не идет дождь и не сыро на улице, результат операции следования – истина. На улице может быть сыро и без дождя. Результат может быть ложен тогда, если дождь идет, а на улице не сыро. Условные обозначения: если A, то В; А влечет В; if A then B; А В АBA B Таблица истинности:

10 Задание: Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет погода хорошая, то он пойдет на рыбалку». 1. Проанализируем составное высказывание. Оно состоит из следующих простых высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдет на рыбалку». Обозначим их через логические переменные: А = Петя поедет в деревню В = Будет хорошая погода С = Он пойдет на рыбалку 2. Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки: F=A&(B C)

11 Задание: Есть два простых высказывания: А= «Число 10-четное»; В= «Волк – травоядное животное». Составьте из них все возможные составные высказывания и определите их истинность. A&BAvB¬A¬A¬B¬BA BA~B

12 Правила составления таблиц истинности: 1) Приоритет выполнения логических операций следующий: инверсия, конъюнкция, дизъюнкция. 2) Если среди слагаемых хотя бы одно истина(1), то результат истина(1). 3) Если среди сомножителей есть хотя бы один ложный(0), то результат ложь(0).

13 ПРИМЕР: Дано логическое выражение А ·. Требуется построить таблицу истинности. Выражение содержит две операции: отрицание и конъюнкцию. По правилам приоритетного выполнения операций сначала следует определить отрицание для всех возможных значений, которые может принимать В. Затем можно применять операцию конъюнкции для получения значений с высказыванием А. Построим таблицу истинности. АBВА·ВА·В

14 ПРИМЕР: Дано логическое выражение (А+В)·С. Требуется построить таблицу истинности. Выражение содержит три высказывания: А, В, С. Значит, таблица истинности будет содержать 2 3 =8 строк возможных сочетаний значений исходных высказываний (аргументов) А, В и С. Построим таблицу истинности. АBСВА+В(А+В) · С

15 ПРИМЕР: Запишите следующее высказывание в виде логических выражений: Число 17 нечетное и двузначное. (17-нечетное)& (17-двузначное) Неверно, что корова – хищное животное. Если Маша – сестра Саши, то Саша – брат Маши. (Маша – сестра Саши) (Саша – брат Маши)

16 ПРИМЕР: Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ». Запишите логические высказывания с помощью логических операций и определите их истинность: Андрей старше Светы. Наташа старше Светы. (Андрей старше Светы) И (Наташа старше Светы)

17 ПРИМЕР: Даны выражения: А=«21-четное число» В=«17

18 Основные законы булевой алгебры Закон ПояснениеДля дизъюнкции Для конъюнкции 1. Ассоциативность Независимость от порядка выполнения однотипных действий А+(В+С)=(А+В)+С= А+В+С А · (В · С)=(А · В) · С=А · В · С 2. Коммутативность Независимость от перестановки А+В=В+АА · В=В · А 3. Дистрибутивность Правила раскрытия скобок и вынесение за скобки А+(В · С)=(А+В) · (А+С) (А+В) · (В+С)=(А · С)+В (А+В) · С=А · С+В · С А · В+В · С=В · (А+С) 4. Идемпотентность Отсутствие степеней и коэффициентов А+А=АА ·А=А 5. Инволюция Двойная инверсия А=А 6. Действия с абсолютно- истинными высказываниями А+1=1А ·1=А

19 Продолжение Закон ПояснениеДля дизъюнкции Для конъюнкции 7. Действия с абсолютно-ложными высказываниями А+0=АА ·0 =0 8. Законы де Моргана Отрицание одновременной истинности Отрицание вариантов 9. Закон исключительного третьего и закон противоречия А+ Ā =1А ·Ā=0 10.ПоглощениеА+А ·В =АА ·(А+В)=А 11. Поглощение отрицания А+ Ā·В =А+ВА ·(Ā+В)=А·В

20 Приведена таблица истинности для аргументов А,В, по которой надо составить логическое выражение F(A,B). АВF(A,B) B A

21 Приведена таблица истинности для аргументов А,В, по которой надо составить логическое выражение F(A,B). АВF(A,B)

22 Алгоритм нахождения искомой формулы таков: АВF(A,B) Отмечаем Записываем ) Выделить в таблице истинности строки, в которых выражение истинно (1);

23 АВF(A,B) Отмечаем Записываем ) Соединить операцией И (умножением) содержимое столбцов аргументов для выбранных строк. При этом если в таблице «0», пишем входной сигнал с отрицанием, а если в таблице «1», то без отрицания:

24 3) Соединить операцией ИЛИ полученные выражения. 4) Упростим полученную формулу:

25 Приведена таблица истинности для аргументов А,В,С, по которой надо составить логическое выражение F(A,B,C). АВCF(A,B,C)Отмечае м Записы ваем

26 Приведена таблица истинности для аргументов А,В по которой надо составить логическое выражение F(A,B). АВF(A,B)Отмечаем Записыва ем

27 Логический элемент – это электронное устройство, выполняющее одну из основных логических операций: И, ИЛИ, НЕ. 1 1& A не A AA В В A или ВA и В

28 АВАиB & A В A и В

29 АВА или B A В A или В

30 Ане А Aне A

31 или и

32 Правило построения логических схем: 1)Определить число логических переменных; 2)Определить количество базовых логических операций и их порядок; 3)Изобразить для каждой логической операции соответствующий ей вентиль; 4)Соединить вентили в порядке выполнения логических операций. Пусть Х=1, Y=0. Составить логическую схему для следующего логического выражения: 1)Две переменные – X,Y. 2)Две логические операции – конъюнкция и дизъюнкция. 3)Строим схему: & 1 0 1

33

34