Логические основы компьютера Логические основы компьютера Выполнила: Пронина Екатерина Руководитель: Паравина А. С. - презентация

1

2 Логические основы компьютера Логические основы компьютера Выполнила: Пронина Екатерина Руководитель: Паравина А. С.

3 Формы м мм мышления Логика- это наука о формах и способах мышления. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны. Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются понятие, высказывание, умозаключение. Это форма мышления, фиксирующая основные, существенные признаки объекта, которые отличают его от других объектов. Это форма мышления, в которой что-либо утверждается или отрицается о реальных предметах, их свойствах и отношениях между ними. Высказывание может быть либо истинно, либо ложно. Это форма мышления, с помощью которой из одного или нескольких суждений (посылок) может быть получено новое суждение (вывод).

4 Алгебра в вв высказываний Алгебра высказываний была разработана для того, чтобы можно было определять истинность или ложность составных высказываний, не вникая в их содержание. В алгебре высказываний суждениям (простым высказываниям) ставятся в соответствие логические переменные, обозначаемые заглавными буквами латинского алфавита. В алгебре высказываний высказывания обозначаются логическими переменными, которые могут принимать лишь два значения «истина» (1) и «ложь» (0). Для образования новых высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических элементов: логический элемент «И» - логическое умножение логический элемент «И» - логическое умножение логический элемент «ИЛИ» - логическое сложение логический элемент «ИЛИ» - логическое сложение логический элемент «НЕ» - инверсию логический элемент «НЕ» - инверсию

5 Логическое умножение ( конъюнкция ) Объединение двух (или нескольких) высказываний в одно с помощью союза «и» называется операцией логического умножения или конъюнкцией. Составное высказывание, образованное в результате операции логического умножения (конъюнкции), истинно тогда и только тогда, когда истинны входящие в него простые высказывания. Операцию логического умножения принято обозначать значками «&», « », либо знаком «*». Образуем составное высказывание F, которое получится в результате конъюнкции двух простых высказываний: F = A & B. Аргументами этой функции являются логические переменные A и B, которые могут принимать значения «истина» (1) и «ложь» (0). Сама функция логического умножения F также может принимать лишь два значения «истина» (1) и «ложь» (0). Значение логической функции можно определить с помощью таблицы истинности данной функции. A B F = A & B

6 Логическое с сс сложение (дизъюнкция) Объединение двух (или нескольких) высказываний с помощью союза «или» называется операцией логического сложения или дизъюнкцией. Составное высказывание, образованное в результате логического сложения (дизъюнкции), истинно тогда, когда хотя бы одно из входящих в него простых высказываний. Операцию логического сложения (дизъюнкцию) принято обозначать либо значком « v », либо знаком «+». Образуем составное высказывание F, которое получится в результате дизъюнкции двух простых высказываний: F = A v B Мы записали формулу функции логического сложения, аргументами которой являются логические переменные A и B. Значение логической функции можно определить с помощью таблицы истинности данной функции. По такой таблице легко определить истинность составного высказывания образованного с помощью операции логического сложения. A BF = A v B

7 Логическое отрицание(инверсия) Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией. Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное- истинным. Операцию логического отрицания (инверсию) над логическим высказыванием A принято обозначать A. Образуем высказывание F, являющееся логическим отрицанием A. F = A Истинность такого высказывания задается таблицей истинности функции логического отрицания. A F = A

8 Логические выражения и таблицы истинности Логические выражения. Каждое составное высказывание можно выразить в виде формулы (логического выражения), в которую войдут логические переменные, обозначающие высказывания, и знаки логических операций, обозначающие логические функции. Для записи составных высказываний в виде логических выражений на формальном языке ( языке алгебры логики) в составном высказывании нужно выделить простые высказывания и логические связи между ними. Запишем высказывание в форме логического выражения с учетом последовательности выполнения логических операций. При выполнении логических операций определен следующий порядок их выполнения: инверсия, конъюнкция и дизъюнкция. Для изменения указанного порядка могут использоваться скобки. F = (A v B) & (A v B) Истинность или ложность составных высказываний можно определять чисто формально, руководствуясь законами алгебры высказываний.

9 Таблицы истинности Таблица истинности логической функции F = (A v B) & (A v B) A BA v B A B (A v B) & (A v B)

10 Таблица истинности логического выражения A & B A B A BA & B Таблица истинности логического выражения A BA v B Таблицы истинности совпадают, следовательно, логические выражения равносильны A & B = A v B

11 Логические функции Логическое следование (импликация). Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…». Логическая операция импликации «если A то B», обозначается A B и выражается с помощью логической функции F 14, которая задается соответствующей таблицей истинности. A BF 14 =A B

12 Логические функции ABF1F1 F2F2 F3F3 F4F4 F5F5 F6F6 F7F7 F8F8 F9F9 F 10 F 11 F 12 F 13 F 14 F 15 F Аргу- менты Таблица истинности логических функций двух аргументов

13 Составное высказывание, образованное с помощью операции логического следования (импликации), ложна тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод ( второе высказывание). Например, высказывание «Если число делится на 10, то она делится на 5» истинно, т.к. истинны и первое высказывание (предпосылка), и второе высказывание(вывод). Высказывание «Если число делится на 10, то оно делится на 3» ложно, т.к. из истинной предпосылки делается ложный вывод. Докажем методом сравнения таблиц истинности, что операция импликации A B равносильна логическому выражению A v B. Таблица истинности логического выражения A v B A B A A v B Таблицы истинности совпадают, ч.т.д.

14 Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «..тогда и только тогда, когда…» Логическая операция эквивалентности «A эквивалентно B» обозначается A~B и выражается с помощью логической функции F 10, которая задается соответствующей таблицей истинности. A B F Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.

15 Логические законы и правила преобразования логических выражений. Законы логики отражают наиболее важные закономерности логического мышления. Закон тождества. Всякое высказывание тождественно самому себе: A = A Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание A – истинно, то его отрицание не A должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: A & A = 0 Закон исключительного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: A v A = 1

16 Закон двойного отрицания. Если дважды отрицать некоторое высказывания, то в результате мы получим исходное высказывание: A = A Закон Моргана. A v B = A & B A & B = A v B Правило коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения: Логическое умножение Логическое сложение A & B = B & A A v B = A v B Правило ассоциативности. Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять: Логическое умножение Логическое сложение (A & B)&C = A&(B&C) (A v B) v C= A v (B v C)

17 Правило дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые: Дистрибутивность умножения относительно сложения Дистрибутивность сложения относительно умножения (a x b) + (a x c) = a x (b+c) (A & B) v ( A & C) = A & ( B v C) ( A v B ) & ( A v C ) = A v ( B & C ) Например, нам необходимо упростить логическое выражение: ( A & B ) v ( A & B ) Воспользуемся правилом дистрибутивности и вынесем за скобки A: ( A & B ) v ( A & B ) = A & ( B v B). По закону исключительного третьего B v B = 1, следовательно: A & ( B v B ) = A & 1 = A

18 Решение задач Условие задачи. В школе- новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На аудиториях повесили шутливые таблички. На первой аудитории повесили табличку «По крайней мере, в одной из этих аудиторий размещается кабинет информатики», а на второй аудитории- табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу, известно только, что надписи на табличках или обе истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики.

19 Решение задачи. Переведем условие задачи на язык логики высказываний. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть: A – «В первой аудитории находится кабинет информатики», B – «Во второй аудитории находится кабинет информатики». Тогда отрицаниям этих высказываний будут соответствовать: A – «В первой аудитории находится кабинет физики», B – «Во второй аудитории находится кабинет физики». Высказывание, содержащее на табличке на первой аудитории, соответствует логическому выражению: X = A v B Высказывание, содержащее на табличке на второй аудитории, соответствует логическому выражению: Y = A Содержащееся в условии задачи утверждение о том, что надписи на табличках либо одновременно истинные, либо одновременно ложные, в соответствии с законом исключенного третьего записывается следующим образом: (X & Y) v (X & Y) = 1

20 Подставим вмеcто X и Y соответствующие формулы: (X & Y) v (X & Y) = ((A v B) & A) v (A v B) & A Упростим сначала первое слагаемое. В соответствии с правилом дистрибутивности умножения относительно сложения: ((A v B) & A = (A & A v B & A). В соответствии с законом непротиворечия: (A & A v B & A) = (0 v B & A) Упростим теперь второе слагаемое. В соответствии с первым законом Моргана и законом двойного отрицания: ((A v B) & A) = (A & B & A) = (A & A & B) В соответствии с законом непротиворечия: (A & A & B) = (0 & B) = 0 В результате получаем: (0 v B & A) v 0 = B & A Полученное логическое выражение оказалось простым и поэтому его можно проанализировать без построения таблицы истинности. Для того, чтобы выполнялось равенство B & A = 1, обе логические переменные должны быть равны 1, а соответствующие им высказывания истинны. Ответ: в первой аудитории- кабинет физики, а во второй- кабинет информатики.

21 Логические основы устройства компьютера Базовые логические элементы Базовые логические элементы реализуют три основные логические операции: логический элемент «И» - логическое умножение логический элемент «И» - логическое умножение логический элемент «ИЛИ» - логическое сложение логический элемент «ИЛИ» - логическое сложение логический элемент «НЕ» - инверсию логический элемент «НЕ» - инверсию Логические элементы компьютера оперируют с сигналами представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают сигналы- значения аргументов, на выходе появляется сигнал-значение функции. Преобразование сигнала логическим элементом задаётся таблицей состояния, которая фактически является таблицей истинности, соответствующей логической функции.

22 Логический элемент «И» И F(0,0,0,1) В(0,1,0,1) А(0,0,1,1) На входы A и B логического элемента подаются два сигнала (00,01,10,11). На выходе получается сигнал 0 или 1 в соответствии с таблицей истинности операции логического умножения

23 Логический элемент «ИЛИ» ИЛИ F(0,1,1,1) В(0,1,0,1) А(0,0,1,1) На входы A и В логического элемента подаются два сигнала (00,01,10,11). На выходе получается сигнал 0 или 1 в соответствии с таблицей истинности операции логического сложения

24 Логический элемент «НЕ» НЕ F(1,0) А(0,1) На вход А логического элемента подаётся сигнал 0 или 1. На выходе получается сигнал 0 или 1 в соответствии с таблицей истинности инверсии

25 Сумматор двоичных чисел В целях максимального упрощения работы компьютера всё многообразие математических операций в процессоре сводится к сложению двоичных чисел. Поэтому главной частью процессора являются сумматоры, которые как раз и обеспечивают такое сложение. Полусумматор. При сложении двоичных чисел в каждом разряде образуется сумма и при этом возможен перенос в старший разряд. Введём обозначения слагаемых (А,В), переноса (P) и суммы (S). Таблица сложения одноразрядных двоичных чисел с учётом переноса в старший разряд выглядит следующим образом:

26 Слагаемое Перенос Сумма ABPS Из этой таблицы сразу видно, что перенос можно реализовать с помощью операции логического умножения: P=A & B Для определения суммы можно применить следующее логическое выражение: S = (A v B) & (A & B)

27 Таблица истинности логической функции F = (A v B) & (A & B) ABA v BA & B (A v B) & (A & B)

28 Теперь на основе полученных логических выражений можно построить из базовых логических элементов схему сложения одноразрядных двоичных чисел: И ИЛИ НЕ И A B A & B A v B (A & B) & (A&B) Данная схема называется полусумматором, так как реализует суммирование одноразрядных двоичных чисел без учёта переноса из младшего разряда

29 Полный одноразрядный сумматор Полный одноразрядный сумматор должен иметь три входа: A, B – слагаемые и P 0 – перенос из младшего разряда и два выхода: сумму S и перенос P.

30 Таблица сложения в этом случае будет иметь следующий вид: Слагаемое Перенос из младшего разряда Перенос Сумма ABP0P0 PS

31 Идея построения полного сумматора точно такая же, как и полусумматора. Из таблицы сложения видно, что перенос (логическая переменная P) принимает значение 1. Таким образом, перенос реализуется путём логического сложения результатов попарного логического умножения входных переменных (A, B, P 0 ). Формула переноса получает следующий вид: P = (A & B) v (A & P 0 ) v ( B & P 0 ) Для получения значения суммы (логическая переменная S) необходима результат логического сложения входных переменных (A, B, P0) умножить на инвертированый перенос P: S = (A v B v P 0 ) & P Данное логическое выражение даёт правильное значение суммы во всех случаях, кроме одного, когда на все входные логические переменные принимают значение 1. Действительно: P = (1 & 1) v (1 & 1) v (1 & 1) = 1 S = (1 v 1 v 1) & P = 1 & 0 = 0 Для получения правильного значения суммы (для данного случая переменная S должна принимать значение 1) необходимо сложить полученные выше выражение для суммы с результатом логического умножения входных переменных (A, B, P 0 ). В результате логическое выражение для вычисления суммы в полном сумматоре принимает следующий вид: S = (A v B v P 0 ) & P 0 v (A & B & P 0 )

32 Многоразрядный сумматор Многоразрядный сумматор процессора состоит из полных одноразрядных сумматоров. На каждый разряд ставятся одноразрядный сумматор, причём выход (перенос) сумматора младшего разряда подключается ко входу сумматора старшего разряда.

33 Триггер Триггер – важнейшая структурная единица оперативной памяти компьютера, а также внутренних регистров процессора. Это устройство позволяет запоминать, хранить и считывать информацию. Триггер можно построить из двух логических элементов «ИЛИ» и двух элементов «НЕ» R ИЛИ НЕ S(1)

34 В обычном состоянии на входы триггера подан сигнал 0, и триггер хранит 0. Для записи 1 на вход S (установочный ) подаётся сигнал 1. Последовательно рассмотрев прохождение сигнала по схеме, видим, что триггер переходит в это состояние и будет устойчиво находится в нём и после того, как сигнал на входе S исчезнет. Триггер запомнил 1, то есть с выхода триггера Q можно считать 1. Для того чтобы сбросить информацию и подготовиться к приёму новой, подаётся сигнал 1 на вход R (сброс), после чего триггер возвратился к исходному «нулевому» состоянию.

35