Алгебра логики (булева алгебра)

 

В

 

С

 

¬B

 

¬С

 

¬В&¬C

 

Bv(¬B&¬C)

 

A& (B v¬B&¬C)

 

0

 

0

 

0

 

1

 

1

 

1

 

1

 

0

 

0

 

0

 

1

 

1

 

0

 

0

 

0

 

0

 

0

 

1

 

0

 

0

 

1

 

0

 

1

 

0

 

0

 

1

 

1

 

0

 

0

 

0

 

1

 

0

 

1

 

0

 

0

 

1

 

1

 

1

 

1

 

1

 

1

 

0

 

1

 

1

 

0

 

0

 

0

 

0

 

1

 

1

 

0

 

0

 

1

 

0

 

1

 

1

 

1

 

1

 

1

 

0

 

0

 

0

 

1

 

1

 

Пример: Для формулы А & (B v ¬ B & ¬ C) построить таблицу истинности

 

Построить таблицы истинности  для следующих формул:

A v (B v ¬ B ) ¬C

Дом задание: A & (B & ¬ B ¬C)

Пример: Для формулы A v (B v ¬ B ) ¬C

 построить таблицу истинности

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

Определение логической формулы:

 

1. Всякая логическая переменная  и символы "истина" ("1") и "ложь" ("0") - формулы.

 

2. Если  А и В  - формулы,   то  А , А · В ,

А v В ,   А        B ,   А        В   - формулы.

 

3. Никаких других формул  в алгебре логики нет. 

 

 

Логические законы и  правила преобразования логических  выражений

 

• Закон двойного отрицания:

                                   А=А

2. Переместительный(коммутативный) закон:

• Для логического сложения: A v B = B v A
• для логического умножения: A & B = B & A

3. Сочетательный  (ассоциативный)закон:

-для логического сложения: (A  v B)  v C =A v ( B v  C)

-для логического умножения:  (A & B) & C = A &  (B & C)

 

 

4. Распределительный (дистрибутивный)  закон:

-для логического сложения: (A  v B)v C=(A & C) v (B &  C )

-для логического умножения:(A  & B)v C=(A v C) & (B v  C)

 

5.Закон общей инверсии  (законы де Моргана)

 

-для логического сложения: (A  v B)  = ¬ A & ¬B

 

-для логического умножения:  (A & B)  = ¬ A v ¬ B

 

6. Закон идемпотентности:

-для логического сложения: А  v A = A

 

-для логического умножения:A  & A = A

 

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

Логическими элементами  компьютеров являются электронные  схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие.

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

Единица на выходе схемы  И будет тогда и только тогда, когда на всех входах будут  единицы. Когда хотя бы на одном  входе будет ноль, на выходе  также будет ноль.

 

Таблица истинности схемы  И 

 

 

X

 

Y

 

X*Y

 

0

 

0

 

0

 

1

 

0

 

0

 

0

 

1

 

0

 

1

 

1

 

1

 

Схема И 

Схема И реализует конъюнкцию двух или более логических значений.

 

&

 

X

 

Y

 

F=X·Y

Таблица истинности схемы ИЛИ

 

x

 

y

 

x v y

 

0

 

0

 

0

 

0

 

1

 

1

 

1

 

0

 

1

 

1

 

1

 

1

 

Когда хотя бы на  одном входе схемы  ИЛИ  будет  единица, на её выходе также  будет единица.

 

Схема  ИЛИ  реализует  дизъюнкцию двух или более  логических значений.

 

X

 

Y

 

F=X+Y

 

1

Таблица истинности схемы НЕ

 

x

 

x

 

0

 

1

 

1

 

0

 

Если на входе схемы   0,  то на выходе  1.  Когда на входе  1,  на выходе  0. 

 

X

 

F=X

 

1

 

Схема   НЕ  (инвертор) реализует операцию отрицания.

С х е м а    И—НЕ

Схема И—НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом F и входами x и y схемы записывают следующим образом: F=x·y, где x·y  читается как   "инверсия x и y".  

 

X

 

F=X·Y

 

&

 

Y

Таблица истинности схемы  И—НЕ

 

x

 

y

 

X*Y

 

0

 

0

 

1

 

0

 

1

 

1

 

1

 

0

 

1

 

1

 

1

 

0

 

X

 

F=X·Y

 

&

 

Y

С х е м а    ИЛИ—НЕ

 

Схема ИЛИ—НЕ состоит из элемента ИЛИ и инвертора  и осуществляет отрицание результата схемы ИЛИ.     Связь между выходом  F и входами  x  и  y  схемы записывают следующим образом:F=x+y,          где    x+y ,  читается как  "инверсия  x или y ".

 

X

 

F=X+Y

 

1

 

Y

Таблица истинности схемы  ИЛИ—НЕ

 

x

 

y

 

X+Y

 

0

 

0

 

1

 

0

 

1

 

0

 

1

 

0

 

0

 

1

 

1

 

0

 

X

 

F=X+Y

 

1

 

Y

Элементы схемотехники. Логические  схемы 

 

Логический элемент (вентиль) И  – конъюнктор – реализует операцию логического умножения.

 

Логический элемент (вентиль) ИЛИ  – дизъюнктор – реализует операцию логического сложения.

 

Логический элемент (вентиль) НЕ  – инвентор – реализует операцию отрицания.

 

Логический элемент И – НЕ  реализует функцию штрих Шеффера.

 

Логический элемент ИЛИ –  НЕ реализует функцию стрелка Пирса.

 

&

 

A

 

B

 

1

 

A

 

B

 

A 

 

B

 

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

Электронная логическая схема, выполняющая суммирование двоичных  кодов, называется сумматором.

Открытые вопросы для самоконтроля

 

• Даны два высказывания: А = Число 5 – простое В = Луна – спутник Венеры. Очевидно, что А=1, В=0. Сформулируйте на русском языке высказывания, соответствующие следующим формулам:   а) Ā;  б) А&B; в) А↔В.  Какие из них истинны?
• Найдите значения выражений:

а)  (1v1) v (1v0);  б) ((1&A) v (Ā&0)) v 1;

• Постройте таблицы истинности для следующих формул:

а)  A v (B&A);  б) A & (B v ¬B &C).

• В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что: вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, , в банке не лимонад и не вода; стакан стоит между банкой и сосудом с молоком. В каком сосуде находится каждая жидкость?
• Cоставьте таблицу истинности для следующей логической функции:  F = X & ¬Y v ¬X & Y
• Найдите значение выходного сигнала в приведенной схеме, если:

a) А = 0 и В = 0;

b) А = 0 и В = 1;

c) А = 1 и В = 0;

d) А = 1 и В = 1.

 

Ответы на вопросы

 

• Истинных высказываний нет.
• а) 1;    б) 1.
• а)  F=(0 0 1 1);  б)  F=(0 0 0 0 0 1 1 1).
• Лимонад – в бутылке, вода – в стакане, молоко – в кувшине, квас – в банке.

 

 

 

X

 

Y

 

¬X

 

¬Y

 

X&¬Y

 

¬X&Y

 

F

 

0

 

0

 

1

 

1

 

0

 

0

 

0

 

0

 

1

 

1

 

0

 

0

 

1

 

1

 

1

 

0

 

0

 

1

 

1

 

0

 

1

 

1

 

1

 

0

 

0

 

0

 

0

 

0

 

5.

 

A

 

B

 

F

 

0

 

0

 

1

 

0

 

1

 

0

 

1

 

0

 

1

 

1

 

1

 

1

 

6.

 

Главная

 

Предыдущий  слайд

Триггер — это электронная схема, широко применяемая в регистрах компьютера для надёжного запоминания одного разряда двоичного кода. Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое — двоичному нулю.

 

Самый распространённый  тип триггера — так называемый RS-триггер (S и R, соответственно, от английских set — установка, и reset — сброс).

 

0

 

1

 

0

 

1

 

S

 

R

 

Q

 

Q

Сумматор — это электронная логическая схема, выполняющая суммирование двоичных чисел.

 

 

Сумматор служит, прежде  всего, центральным узлом арифметико-логического  устройства компьютера, однако он  находит применение также и  в других устройствах машины.

 

Многоразрядный двоичный  сумматор