Логические основы построения компьютера. Содержание 1. Историческая справка. Историческая справка. Историческая справка. 2. Булева алгебра. Булева алгебра. - презентация

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

2 Содержание 1. Историческая справка. Историческая справка. Историческая справка. 2. Булева алгебра. Булева алгебра. Булева алгебра. 3. Логические выражения. Логические выражения. Логические выражения. a) Логическое отрицание. Логическое отрицание. Логическое отрицание. b) Логическое сложение. Логическое сложение. Логическое сложение. c) Логическое умножение. Логическое умножение. Логическое умножение. d) Логическое следование. Логическое следование. Логическое следование. e) Эквивалентность. Эквивалентность. 4. Порядок выполнения опреаций 4. Порядок выполнения опреаций. Порядок выполнения опреаций Порядок выполнения опреаций. 5. Построение таблиц. Построение таблиц Построение таблиц 6. Основные законы логики. Основные законы логики. Основные законы логики. 7. Список литературы. Список литературы. Список литературы.

3 Историческая справка Немецкий ученый Лейбниц первым (в 1666 году) попытался перевести законы мышления (формальную логику) из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются в виде математических соотношений. Немецкий ученый Лейбниц первым (в 1666 году) попытался перевести законы мышления (формальную логику) из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются в виде математических соотношений. Спустя более ста лет, в 1816 году, уже после смерти Лейбница среди ученых шел разговор о создании логического универсального языка, подчиняющегося строгим математическим законам. В 1847 году Буль написал важную статью на тему «Математический анализ логики», а в 1854 году развил свои идеи в работе «Исследование законов мышления». Спустя более ста лет, в 1816 году, уже после смерти Лейбница среди ученых шел разговор о создании логического универсального языка, подчиняющегося строгим математическим законам. В 1847 году Буль написал важную статью на тему «Математический анализ логики», а в 1854 году развил свои идеи в работе «Исследование законов мышления».

4 Буль изобрёл своеобразную алгебру – систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Его именем она теперь и называется: алгебра Буля, или булева алгебра. Буль изобрёл своеобразную алгебру – систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Его именем она теперь и называется: алгебра Буля, или булева алгебра.

5 Булева алгебра Булева алгебра состоит из компонентов: Логические объекты ( выражения) Логические объекты ( выражения) Операции над логическими объектами Операции над логическими объектами Аксиомы и теоремы, регламентирующие эти Аксиомы и теоремы, регламентирующие эти операции операции

6 Логические выражения 1. Логические 2. Предикаты утверждения утверждения

7 1. Логические утверждения – это конкретные частные утверждения, заведомо истинные или ложные, иначе говоря, это логические константы. Например: 2*2 = 4 ( истина) Волга впадает в Чёрное море. (ложь) Волга впадает в Чёрное море. (ложь)

8 2. Предикаты – это логические высказывания, значения которых могут меняться в зависимости от входящих в них переменных величин, иначе говоря, это логические переменые. Например: А +В >С (принимают значения Истина или Ложь в зависимости от значений А, В, С)

9 Логическое отрицание Логическое отрицание или Инверсия, определяется над одним аргументом (простым или сложным логическим выражением) следующим образом: если исходное выражение истинно, то результат его отрицания будет ложным, и наоборот. Логическое отрицание или Инверсия, определяется над одним аргументом (простым или сложным логическим выражением) следующим образом: если исходное выражение истинно, то результат его отрицания будет ложным, и наоборот. Операция означает, что к исходному логическому выражению добавляют частицу НЕ или слова НЕВЕРНО, ЧТО. Обозначается значком Операция означает, что к исходному логическому выражению добавляют частицу НЕ или слова НЕВЕРНО, ЧТО. Обозначается значком А А А 01 10

10 Логическое сложение Логическое сложение или Дизъюнкция, определяет логическое соединение двух логических выражений (высказываний) с помощью союза ИЛИ. Обозначается значком Логическое сложение или Дизъюнкция, определяет логическое соединение двух логических выражений (высказываний) с помощью союза ИЛИ. Обозначается значком Сложное логическое выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) логических выражений. Сложное логическое выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) логических выражений. ۷ АВ А۷ВА۷ВА۷ВА۷В запомни знак! Пример: для сдачи экзамена необходимы знания или везение.

11 Логическое умножение Логическое умножение или Конъюнкция, определяет соединение двух логических выражений (высказываний) с помощью союза И. Обозначается значком & или ٨. Логическое умножение или Конъюнкция, определяет соединение двух логических выражений (высказываний) с помощью союза И. Обозначается значком & или ٨. Эта операция ставит в соответствие двум простым логическим выражениям новое- сложное, которое будет истинным тогда и только тогда, когда истинны оба исходных (простых) логических выражения. Эта операция ставит в соответствие двум простым логическим выражениям новое- сложное, которое будет истинным тогда и только тогда, когда истинны оба исходных (простых) логических выражения. АВ А٨ВА٨ВА٨ВА٨В Запомни знак! Пример : Учитель должен быть умным и терпеливым (только одновременное наличие двух качеств, ума и терпения, делает выражение истинным).

12 Логическое следование Логическое следование или Импликация. Логическое следование или Импликация. Эта операция связывает два простых логических выражения, из которых первое является условием, а второе- следствием из этого условия. Выражается словами ЕСЛИ…, ТО… Обозначается значком Результатом импликации является ложь тогда и только тогда, когда (А) истинно, а следствие (В) ложно. Результатом импликации является ложь тогда и только тогда, когда (А) истинно, а следствие (В) ложно. АВ А В Например : Если выучишь материал, то сдашь зачет (высказывание ложно только тогда, когда материал выучен, а зачет не сдан, ведь сдать зачет можно и случайно, например если попался единственный знакомый вопрос или удалось воспользоваться шпаргалкой.

13 Эквивалентность Эквивалентность или Равнозначность. Эквивалентность или Равнозначность. Определяет результат сравнения двух простых логических выражений А и В, обозначается значком Результат – новое логическое выражение, которое является истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Результат – новое логическое выражение, которое является истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. АВ А В Пример: Когда в зимний день светит солнце и «кусает» мороз, это значит, что атмосферное давление высокое.

14 Порядок выполнения логических операций 1. Действия в скобках 2. Инверсия - 2. Инверсия - 3. Конъюнкция - & или ٨ 4. Дизъюнкция – ۷ 5. Импликация – 6. Эквивалентность – Например: D = ( A ۷ B ٨ C) 123

15 Построение таблиц Рассмотрим пример построения таблицы истинности для следующегося сложного (составного) логического выражения. D = A ٨ (B ۷ C) Рассмотрим пример построения таблицы истинности для следующегося сложного (составного) логического выражения. D = A ٨ (B ۷ C) Сначала нужно установить число строк и столбцов такой таблицы, то есть спланировать форму таблицы. При определении числа строк необходимо некоторым образом перебрать все возможные сочетания логических значений 0 и 1 исходных выражений А, В и С, из которых формируется заданное сложное логическое выражение. Сначала нужно установить число строк и столбцов такой таблицы, то есть спланировать форму таблицы. При определении числа строк необходимо некоторым образом перебрать все возможные сочетания логических значений 0 и 1 исходных выражений А, В и С, из которых формируется заданное сложное логическое выражение.

16 При добавлении третьего аргумента сначала запишем первые 4 строки таблицы, сочетания их со значением третьего аргумента, равным 0, а затем ещё раз запишем эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк (+ девятая строка – шапка таблицы), и при таком подходе легко проверить, что мы действительно не повторили и не пропустили ни одного возможного сочетания логических значений аргументов – исходных выражений А, В, С При добавлении третьего аргумента сначала запишем первые 4 строки таблицы, сочетания их со значением третьего аргумента, равным 0, а затем ещё раз запишем эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк (+ девятая строка – шапка таблицы), и при таком подходе легко проверить, что мы действительно не повторили и не пропустили ни одного возможного сочетания логических значений аргументов – исходных выражений А, В, С

17 Существует закономерность: для любого числа N аргументов сложного логического выражения таблица истинности содержит 2 n строк, а также строку заголовка (шапка таблицы). для любого числа N аргументов сложного логического выражения таблица истинности содержит 2 n строк, а также строку заголовка (шапка таблицы). Количество столбцов таблицы истинности для её построения выбирают равным М. Эти столбцы соответствуют значениям исходных выражений А, В, С, промежуточных результатов А, (В ۷ С), а также искомого окончательного результата- значения сложного арифметического выражения Количество столбцов таблицы истинности для её построения выбирают равным М. Эти столбцы соответствуют значениям исходных выражений А, В, С, промежуточных результатов А, (В ۷ С), а также искомого окончательного результата- значения сложного арифметического выражения А ٨ (В ۷ С) А ٨ (В ۷ С)

18 Построим таблицу сложного логического выражения Построим таблицу сложного логического выражения АВСА В ۷ С А ٨ (В ۷ С)

19 Основные законы логики 1.Отсутствие степеней и коэффициентов (идемпотентность): А ٨ А= А; А ۷ А= А 2.Двойное отрицание (инволюция): ¬(¬А) = А 3.Закон исключения третьего: А۷(¬ А)=1 (всегда истина) 4.Закон противоречия: А ٨ (¬ А)= 0 (всегда ложь) 5.Независимость от перестановки мест (коммутативность): А۷ В= В ۷ А; А ٨ В = В ٨ А 6. Независимость от порядка выполнения однотипных действий (ассоциативность): (А۷В) ۷ С = А ۷ (В۷С); (А٨В) ٨ С = А ٨ (В٨С). (А۷В) ۷ С = А ۷ (В۷С); (А٨В) ٨ С = А ٨ (В٨С).

20 7. Дистрибутивность (распределение): Умножения- (А۷В) ٨ С = (А٨С) ۷ (В٨С) и наоборот: (А٨В) ۷ (В٨С) = В ٨ (А۷С) Сложения- А۷В٨С = (А۷В) ٨ (А۷С) 8. Законы де Моргана: а) Отрицание одновременной истинности: ¬(А٨В)= (¬А)۷(¬В) б) Отрицание вариантов: ¬ (А۷В) = (¬А) ٨(¬В)

21 а) Отрицание одновременной истинности :¬(А٨В)= (¬А)۷(¬В) АВ ¬(А٨В) (¬А)۷(¬В) АВ ¬(А۷В) (¬А) ٨(¬В)

22 Используемая литература: 1.Макарова Н.В. /методическое пособие для учителей. 2.Макарова Н.В. /практикум по информационным технологиям.