Логика Уроки

Логика – наука о законах и формах мышления. Слово «логика» произошло от древнегреческого logos, что означает «слово, мысль, понятие, рассуждение, закон». Основные формы мышления: понятие, высказывание, умозаключение. Понятие – это форма мышления, которая выделяет существенные признаки предмета или класса предметов, позволяющие отличать их от других («Вот стул на нем сидят, вот стол – за ним едят.»). Высказывание – это повествовательное предложение, о котором можно сказать, истинно оно или ложно. Земля – планета солнечной системы. 3+5=19 Умозаключение – это форма мышления, с помощью которой из одного или несколько суждений может быть получено новое суждение (вывод). ( Доказательство теорем в алгебре). Английский математик Джордж Буль ( ) изобрел своеобразную алгебру – систему обозначений и правил, применимую к всевозможным объектам, в частности к высказываниям. Эта алгебра называется его именем – алгебра Буля или булева алгебра. Логическая переменная – это простое высказывание (содержит одну мысль), значение которой 0 (ложь, false) или 1 (истина, true), обозначается латинскими буквами. Логическая функция – составное высказывание, полученное из простых высказываний, соединенных между собой с помощью логических операций.

Логические операции. Логические операции над высказываниями выполняются на основе законов и правил булевой алгебры. Логическое умножение КОНЪЮНКЦИЯ (,&) определяет соединение логических выражений с помощью союза И. Например: 1) А – Х>10; В – Х< 30; А и В - 10

Логические операции. Импликация (логическое следование) ( ) соответствует связке « если …, то …» Если А, то В, В необходимо для А, А достаточно для В, В тогда, когда А Импликация истинна всегда, за исключением случая, когда А истинно, а В ложно. Пример: Если идет дождь, то земля сухая. (ложь) А - х делится на 9 В - х делится на 3 А В - если число х делится на 9, то оно делится на 3 (истина) Эквивалентность(равнозначность) (, = ) соответствует связке «тогда и только тогда, когда..». А тогда и только тогда, когда В Результат эквивалентности будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Исключающая дизъюнкция «либо…, либо», (неэквивалентность) А В. Результат будет истинным, когда одно из исходных выражений истинно, а другое ложно. Пример: Пан или пропал.

Построение таблиц истинности. Таблица истинности – таблица, определяющая значение сложного высказывания при всех возможных значениях простых высказываниях. Для составления таблицы надо: 1. определить число переменных; 2. выяснить количество строк в таблице (вычисляется как 2 n, где n – количество переменных); 3. выяснить количество столбцов = количеств переменных + количество логических операций; 4. установить последовательность выполнения логических операций; 5. записать логические операции в таблицу истинности и определить для каждого значение; Порядок выполнения логических операций: 1. операция в скобках; 2. отрицание; 3. логическое умножение; 4. логическое сложение; 5. импликация; 6. эквивалентность.

Составьте по булевому выражению F=(A В) ¬ C таблицу истинности: _ _ _ Самостоятельно: 1) F=A (В C); 2) F=A (В C); 3) F=(A В) C. АВС ¬ С А В(A В) ¬ C

Законы алгебры логики. Если логическое выражение содержит большое число операций, то составлять для него таблицу истинности достаточно сложно. В таких случаях формулы надо привести к нормальной форме. Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации, двойного отрицания, знаки отрицания находятся только при логических переменных. Для приведения формулы к нормальной форме используют законы логики и правила преобразований. Тождества. А + 0 =АА&0 = 0 А + 1 = 1A&1 = A = A = A двойное отрицание А + А = АA&A = A _ А + А = 1 _ A&A = 0

Законы алгебры логики. Переместительный закон А + В = В + А А & В = В & А Сочетательный закон (А + В) + C =А + (В + C) (А& В)& С =А& (В&С) Распределительный закон (А + В)&C =А&С+ В&C) дистрибутивность конъюнкции относительно дизъюнкции – аналог раскрытия скобок в алгебре А& В +С =(А + С)& (В + С) дистрибутивность дизъюнкции относительно конъюнкции – «чудо» логики, в алгебре аналога нет. Закон де Моргана (закон отрицания) ____ _ ______ _ _ А + В = А& В А & В = А + В Доказать на уроке, используя таблицы истинности. __ __ А В = В А = А + В _ _ _ _ А В = А& В + А & В = ( А + В) &( А + В)

Задания: 1) Записать формулу, упростить: 1. А или (не А и В) 2. А и (не А или В) 3. (А или В) и (не В или А) и (не С или В) 4. (1 или (А или В)) или ((А или С) и 1) Решение: __ __ А + (А & B) = (А + А)&(А + В) = 1& (А + В) = А +В; __ __ А & (А + В) = А&А + А&В = 0 + А&В = А&В; __ __ __ __ __ (А + В)&( В + А)&(С + В) =(А&В +А&А +В&В + В&А)&(С +В) = __ __ __ __ __ (А&В + А В&А)& (С +В) = А&(В В)& (С +В) =А&(С +В); (1 + (А + В)) + (( А + С)&1) = 1 + (А + С) =1. 2) Доказать, используя таблицы истинности, второй распределительный закон А& В +С =(А + С)& (В + С).

Логические схемы. Над возможностями применения логики в технике ученые и инженеры задумывались давно. Американский логик Чарльз Сандерс Пирс первым осознал, что бинарная логика имеет сходства с работой электрических переключательных (контактных) схем. Компьютер работает на электричестве, любая информация представлена в компьютере в виде электрических импульсов. Рассмотрим реализацию логических элементов через электрические контактные схемы. Контакты обозначены латинскими буквами. Последовательное соединение контактов. Цепь с последовательным соединением соответствует логической операции И (конъюнкции). Параллельное соединение контактов Цепь с параллельным соединением соответствует логической операции ИЛИ (дизъюнкции). Логическая операция НЕ (инверсия) реализуется через контактную схему электромагнитного реле. АВ А В

Логические схемы – схемы, выполняющие операции преобразования: запоминания, пересылки двоичных битов информации в компьютере Логический элемент (вентиль) – часть электронной логической схемы, которая выполняет элементарную логическую операцию. К элементарным логическим операциям реализуемым на логических микросхемах относятся операции: и, или, не, и-или, и-не, или-не, и-или-не и др. Логический элемент И - конъюнктор.& Х Y Х&Y Логический элемент ИЛИ – дизъюнктор. X Y X Y Логический элемент НЕ – инвертор. Х _ Х & 1

Задания: Упростить логическое выражение. Построить таблицу истинности. Построить логическую схему. Показать. Что схема работает в соответствии с таблицей истинности. ___ ____ Выражение: F = A&B + B&C ___ ___ _ _ _ _ _ _ _ Ответ: F = A&B + B&C = A + B + B + C = A + B + C. А В С 1 1

Задание для самостоятельной работы: _________ _ ________ __ _____ __ 1) F = X&Y + Y&Z + Z&X =Y&(X + Z) +Z&X = Y + X + Y + Z&X = _ _ _ _ _ _ _ _ _ Y + X&Z + Z&X = Y + X&(Z + Z) = Y + X 2) F = A&B + D + ¬(A + ¬B) = A&B + D + ¬ A&B = B&(A + ¬ A) + D = B + D.

Упростить электрическую схему и построить электрическую и логическую схемы результата.

Решение

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

Сумматор – это электронная логическая схема, выполняющая суммирование двоичных чисел. В целях максимального упрощения работы компьютера все многообразие математических операций в процессоре сводится к сложению двоичных чисел. Поэтому главной частью процессора является сумматор, который обеспечивает такое сложение. При сложении двоичных чисел образуется сумма в данном разряде, при этом возможен перенос в старший разряд. Обозначим слагаемые А и В, сумму S и перенос Р. Построим таблицу сложения одноразрядных двоичных чисел с учетом переноса в старший разряд. ABSP Cоставим булево выражение по этой таблице: _ _ S = A&B + A&B; P = A&B Упростим формулу для S: _ _ A&B = A&A +A&B = A&(A + B), _ _ _ _ A&B = A&B +B&B = B&(A + B). _ _ _ _ S = A&B + A&B = A&(A + B) + B&(A + B) = _ _ ____ (A + B) &(A + B) = (A + B)&A&B.

Схема сумматора A B 1 & S & P 1& &

Триггер. Регистры. Триггер – устройство памяти компьютера для хранения одного бита информации. Это устройство позволяет запоминать, хранить и считывать информацию. Триггер может находиться в одном из двух устойчивых состояний, которые соответствуют логической»1» и логическому «0». Триггер способен почти мгновенно переходить из одного электрического состояния в другое и наоборот. Самый распространенный триггер – SR-триггер ( S и R от английских слов set – установка, reset – сброс). Он имеет два входа S и R, два выхода Q и ¬Q. На каждый из входов подаются входные сигналы в виде кратковременных импульсов «1», отсутствие импульса – «0». Для построения триггера достаточно двух логических элементов «ИЛИ» и двух элементов «НЕ».

SRQ _Q_Q Режим триггера 00 Последнее значение Хранение 1 бит 0101 Установка «0» 1010 Установка «1» 11 Запрещено При подаче сигнала на вход S триггер переходит в устойчивое единичное состояние. При подаче сигнала на вход R триггер сбрасывается в устойчивое нулевое состояние. При отсутствии входных сигналов триггер сохраняет тот сигнал, который был установлен входным импульсом. Если на два входа подан сигнал, то появляется неоднозначный результат, поэтому такая комбинация запрещена.

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