Алгебра логики. Операции алгебры логики

ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

В ЭВМ информация подвергается не только арифмети­ческой, но и логической обработке. В основе работы логиче­ских схем и устройств ЭВМ лежит алгебра логики.

Алгебра логики – это раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Значения всех элементов алгебры логики определены в двухэлементном множестве 0 и 1.

Логическое высказывание – это любое повествова­тельное предложение, относительно которого можно одно­значно сказать, истинно оно или ложно. Если высказывание истинно, то считают, что его значение равно единице; если вы­сказывание ложно, то считают, что его значение равно нулю.

Пример: «Лед – твердое состояние воды» - истинное высказывание; «Все рыбы умеют плавать» - общее высказыва­ние (истинное); «Париж – столица Китая» - ложное высказы­вание.

Логическая константа – ИСТИНА (1) или ЛОЖЬ (0).

Логическая переменная – символически обозначенная логическая величина, которая может принимать только значе­ния ИСТИНА (1) или ЛОЖЬ (0).

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

Пример: Пусть А – Петров врач, В – Петров – шахма­тист. Тогда можно (например при помощи связки «и») соста­вить составное высказывание: Петров – врач И шахматист (мы это поймем как «Петров – врач, умеющий играть в шахматы), А при помощи введенных обозначений мы получим: А И В.

Для К логических переменных существует 2^К логиче­ских комбинаций 0 и 1.

Пример: К=2 (высказывания А и В) следовательно раз­личных комбинаций – 4 (00, 01, 10, 11); К=3 (А, В, С) следова­тельно комбинаций 2³=8 (000, 001, 010, 011, 100, 101, 110, 111)

Основными операциями алгебры логики являются опе­рации конъюнкции, дизъюнкции и инверсии.

В то же время всякое устройство ЭВМ, выполняющее преобразование информации на комбинационные схемы тех­нически реализуется с использованием логических элементов.

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

Конъюнкция – логическое умножение, логическое И. Логическое умножение: операция, связывающая 2 и более вы­сказывания с помощью союза «И». Обозначается: И, Ù, ×,&

ЗАКОН: Конъюнкция истинна тогда и только тогда, ко­гда истинны ВСЕ входящие в нее высказывания.

Логический элемент «И» (конъюнктор) выдает на вы­ходе значение логического произведения входных сигналов.

Таблица истинности для конъюнкции и графическое изображение логического элемента имеет вид:

x	y	xÙy	Условное обозначение

Дизъюнкция – логическое сложение, логическое ИЛИ. Логическое сложение: операция, связывающая два и более вы­сказывания с помощью союза «ИЛИ». Обозначается: ИЛИ, V, +

ЗАКОН: Дизъюнкция истинна тогда и только тогда, ко­гда истинно ХОТЯ БЫ ОДНО из входящих в нее высказыва­ний.

Логический элемент «ИЛИ» (дизъюнктор) выдает на выходе значение логической суммы входных сигналов.

Таблица истинности для дизъюнкции и графическое изображение логического элемента имеет вид:

x	y	x v y	Условное обозначение

Инверсия – логическое отрицание, логическое НЕ. Ло­гическое отрицание – это присоединение частицы «НЕ» к ска­зуемому высказывания. (Петров – врач. Петров – не врач). Обозначается: НЕ, , Х.

ЗАКОН: Если высказывание Х – истинно, то НЕ Х – ложно.

Логический элемент «НЕ» (инвертор) выдает на выходе сигнал, противоположный сигналу на входе.

Таблица истинности для инверсии и графическое изо­бражение логического элемента имеет вид:

x		Условное обозначение

На основе использования основных логических схем строятся еще две логические схемы: Схема И-НЕ (элемент Шеффера) и схема ИЛИ-НЕ (элемент Пирса).

Схема И-НЕ состоит из элемента «И» и инвертора и осуществляет отрицание результата схемы «И». Связь между выходом z и входами x и y схемы записывают следующим об­разом: , где читается как «инверсия x и y».

x	y		Условное обозначение

Схема ИЛИ-НЕ состоит из элемента ИЛИ и инвер­тора и осуществляет отрицание результата схемы «ИЛИ». Связь между выходом z и входами x и y схемы записывают следующим образом: , где , читается как «инвер­сия x или y».

x	y		Условное обозначение

Соединяя выходы одних логических элементов со вхо­дами других логических элементов можно построить логиче­ские схемы.

Приоритет логических операций:

1) Инверсия

2) Конъюнкция

3) Дизъюнкция

Замечание: скобки могут менять приоритет операций

Пример: По заданному логическому выражению по­строить таблицу истинности и составить логическую схему.

а)

Решение: 1. Т.к. мы видим 2 логические переменные «х» и «у», то для них будет 4 различные логические комбина­ции 0 и 1: (0,0); (0,1); (1,0); (1,1). 2. Для построения таблицы истинности расставим сначала приоритет операций: 1) ; 2) ; 3) ; 4) ; 5) ; 6) ; 7)

Составим таблицу истинности. В ней будет 5 строк (первая – для обозначения переменных и действий, и 4 для возможных комбинаций входных данных) и столько столбцов, сколько мы выделили отдельных операций (расставляя при­оритеты) плюс количество исходных переменных:

x	y

Теперь изобразим логическую схему.

Пример: По заданной логической схеме составить логи­ческое выражение и заполнить для него таблицу истинности

Решение: Во-первых, определяем, сколько входов име­ется. Их в данной схеме три. Обозначаем их символами, на­пример: x, y, z. Во-вторых, смотрим, какие логические эле­менты составляют схему и аккуратно изображаем эти эле­менты в виде формул. Получаем следующее логическое выра­жение: .

Составляем таблицу истинности. Т.к. имеется три входа, то будет 2³=8 различных логических комбинаций 1 и 0.

(Заметим, что необходимо не забывать об инвертировании вы­ражений)

x	y	z

Задачи:

1. По заданному логическому выражению построить таблицу истинности и составить логическую схему.

а)

б)

в)

г)

д)

е)

ж)

2. По заданной логической схеме составить логическое выра­жение и заполнить для него таблицу истинности.

а)	б)
в)	г)
д)	е)

Дата добавления: 2014-11-20