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

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

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

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

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

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

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

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

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

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

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

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

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

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

Закон двойного отрицания. Если дважды отрицать некоторое высказывания, то в результате мы получим исходное высказывание: 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)

Правило дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые: Дистрибутивность умножения относительно сложения Дистрибутивность сложения относительно умножения (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

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

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

Подставим вме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, а соответствующие им высказывания истинны. Ответ: в первой аудитории- кабинет физики, а во второй- кабинет информатики.

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

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

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

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

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

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

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

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

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

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

Идея построения полного сумматора точно такая же, как и полусумматора. Из таблицы сложения видно, что перенос (логическая переменная 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 )

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

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

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