Основные понятия алгебры логики. Логические основы ЭВМ (для заочников)


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Министерство образования и науки Российской Федерации

Федеральное г
осударственное

бюджетное

образовательное учреждение

высшего профессионального образования


«
С
ибирский государственный индустриальный университет
»





Кафедра информатики






ОСНОВНЫЕ ПОНЯТИЯ АЛГ
ЕБРЫ ЛОГИКИ.

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

ЭВМ


Методические указания

к выполнению лабораторной работы

по дисциплине «Информатика»




















Новокузнецк

201
6
УДК 0
04
:510.6
(07)

О
-
852



Рецензент:

к
андидат технических наук,

доцент кафедры
прикладных информационных технологий

и
программирования

СибГИУ

Ю.А. Соловьева



О
-
852

Основные

понятия алгебры логики.

Логические основы ЭВМ
:

м
етод. указ. /
Сиб. гос. индустр. ун
-
т.;
с
ост.
:

Л.Д. Павлова
,

А.В.
Корн
ева
.


Новокузнецк
: Изд. центр СибГИУ
,
2
0
1
6
.



18

с.


Изложены
основные понятия
алгебры логики. Приведены
логические операции

и схемы для их изображения
.
Рассмотрены
примеры
по решению логических задач
.


Предназначен
ы

для студентов

всех
направлени
й

подготовки


и форм обучения
.


Печатается по решению Совета Института фундаментального
образования (протокол №5 от 27.01.2016 г
.
)
.

3

СОДЕРЖАНИЕ


ВВЕДЕНИЕ

................................
................................
..............................

4

ЦЕЛЬ РАБОТЫ

................................
................................
.......................

4

ОСНОВНЫЕ ПОНЯТИЯ АЛГ
ЕБРЫ ЛОГИКИ
................................
...

5

Логические операции над данными

................................
...............

5

Законы алгебры логики

................................
................................
.

10

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

................................
..........................

12

Логиче
ские элементы компьютера

................................
..............

12

Символические изображения стандартных вентилей

................

13

ЗАДАНИЕ ДЛЯ
К
ОНТРОЛЬ
НОЙ РАБОТЫ

................................
.....

16

ВОПРОСЫ ДЛЯ САМОКОНТ
РОЛЯ

................................
.................

17

СПИСОК ЛИТЕРАТУРЫ

................................
................................
....

17




4













ВВЕДЕНИЕ

Алгебра логики


это

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

Выск
а
зывание



это предложение, выражающее суждение.

Сужд
е
ние


эт
о

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

Виды суждений и отношения между
ними изучаются в философской логике. В математической логике
суждениям соответствуют
высказывания.

Если суждение, составляющее содержание (смысл) некоторого
высказывания, истинно, то о данном высказывании говорят, что оно
истинно.
Л
ожным называют такое высказывание, которое является
выражением ложного суждения.

Как правило,
предполагается
, что высказывания могут быть
только истинными или ложными, то есть используется
так

называемая
бинарная

или
двоичная

логика.

Логика высказываний послужила основным математическим
инструментом при создании компьютеров
, так как

о
на легко
преобразуется в
бит
овую

логику: истинность
или ложность
высказывания
обозначается одним битом (0



Л
ожь
, 1



И
стина)
.

ЦЕЛЬ РАБОТЫ

Изучить основные понятия

алгебры логики
, приобрести
практические навыки по

решению задач с

использованием

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

и
построению
логических
схем
.


5

ОСНОВНЫЕ ПОНЯТИЯ АЛГ
ЕБРЫ ЛОГИКИ

Логические операции над данными


Логическое выражение



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


Логическими константами

являются значения
«Истина»


(
T
rue
)



1


или «Ложь»

(
F
alse
)



0
.

Операнды могут принимать значения только одной из двух
логических констант.

В таблице
1

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


Таблица
1

-

Логические операции

Приоритет
операции

Название

операции

Обозначение

Выражение

1

Инверсия


(
отрицание,
дополнение
)

NOT


Н
E

¯



NOT

A


НЕ
A

Ā




А

2

Конъюнкция
(логическое
И
,
логическое умножение)

AND

И

&







A
AND

B


A
И

B

A

&

B

A



B

A



B


А



В

3

Дизъюнкция
(логическое
ИЛИ
,

логическое сложение)

OR

ИЛИ

+






A
OR

B

A
ИЛИ

B

А

+

В


A



B


А



В

3

Исключающее
ИЛИ

XOR

A

XOR

B

4

Импликация
(следствие)



A



B

5

Эквивалентность
(равносильность)



A



B


6

Логическая
операция

NOT

является
унарной
, так как действие
выполняется над одним операндом.

Логические операции AND, OR,
XOR
,

,


являются
бинарными
, так как действия выполняются над двумя операндами.

Инв
ерсия
(
отрицание
,
дополнение
)

обозначается
символами:
NOT
,
НЕ,
¯,

.

Результат
операции
всегда противоположен значению
аргумента.

Таблица истинности

имеет вид
:

А

Ā

0

1

1

0

Если А


«
И
сти
на»
, то Ā


«
Л
ож
ь»

и наоборот
, н
апример
:

NOT
(A) 1, если А 0.

Конъюнкция
(
логическое И,
логическое умножение)

обозначается
символами:
AND
,
И,
&,


,

,

.
Р
езультат
операции
«
И
стина» только в том случае,
когда

оба операнда принимают
значение «
И
стина». Во всех остальных случаях результат операции


«
Л
ожь».

Таблица
истинности

имеет вид
:

A

B

F

0

0

0

0

1

0

1

0

0

1

1

1

Если F A

B, то F
принимает значение
«
И
стина»
только когда
оба операнда
А
и В имеют значение

«
И
стина»
, н
апример
:


A
AND

B =

1, если A 1 и B 1.

Дизъюнкция
(
логическое ИЛИ
,
логическое сложение)

обозначается
символами:
OR
,
ИЛИ,
+
,

,

.
Р
езультат
операции
«
Ложь
»,
только в том случае,
когда

оба операнда принимают значение «Ложь».
Во всех остальных случаях результат операции


«Истина».

Таблица истинности

имеет вид
:

A

B

F

0

0

0

0

1

1

1

0

1

1

1

1


7

Если F A

B, то F
принимает значение

«
Л
ожь»
то
лько когда
оба
операнда
А
и В имеют значение

«
Л
ожь»
, н
апример
:


A
OR

B

=

0, если A 0 и В 0.

И
сключающее ИЛИ

обозначается
символ
ом

XOR
.
Р
езультат
операции
«
И
стина», если хотя бы один из операндов принимает

значение «
И
стина». Если оба операнда принимают одинаковые
значени
я
,

то
результат операции


«
Л
ожь».

Таблица истинности

имеет вид
:

A

B

F

0

0

0

0

1

1

1

0

1

1

1

0

Если F A
XOR

B, то F
принимает значение

«
Л
ожь»
когда
оба
операнда
А
и В имеют значение

«
Л
ожь»
или
«
И
стина»
, н
апример
:


A
XOR

B

=

0, если A 0 и В 0 или A 1 и В 1.

Импликация (следствие)

обозначается
символ
ом


.
Р
езультат
операции
«Л
ожь» только
когда

первый операнд принимает значение
«
И
стина», а второ
й операнд принимает значение «Л
ожь». Во
всех
остальных случаях

результат операции


«
И
стина».

Таблица истинности

имеет вид
:

A

B

F

0

0

1

0

1

1

1

0

0

1

1

1

Если F A



B, то F
принимает значение

«
Л
ожь»
только когда
операнд
А
имеет значение

«
И
стина»
, а
операнд
В



значение
«
Л
ожь»
,
н
апример
:

A


B

=

0, если A 1 и В 0.

Эквивалентность (равносильность)
обозначается
символ
ом


.
Р
езультат
операции
«
И
стина» только когда
оба операнда
одновременно
принимают значение «И
стин
а»

или
«Ложь»
.
Во всех
остальных случаях

результат операции


«
Л
ожь».

Таблица
истинности

имеет вид
:

A

B

F

0

0

1

0

1

0

1

0

0

1

1

1


8

Если F A



B, то F
принимает значение

«
И
стина»

когда

оба
операнда
А

и В

имеют значение

«
Л
ожь» и
ли

«
И
стина»
, н
апример
:

A


B

=

1, если A 0 и В 0 или A 1 и В 1.

Пример 1
.

Какое логическое выражение соответствует заданной
таблице истинности?

А

В

С

0

0

1

0

1

0

1

0

0

1

1

0

а
)


C

= NOT(
A

OR
B
)

б
)


C

=
A

AND
B

OR NOT
A

AND NOT
B

в
)


C

= NOT
A

AND NOT
B

AND
A

г
)


C

= NOT
A

OR NOT
B

OR
A

Решение:

Для каждого выражения нужно
построить таблицу
истинности.

С
трои
тся

таблиц
а

истинности

для выражения
а
)
.

А

В

А

OR

В

NOT(
A

OR
B
)

0

0

0

1

0

1

1

0

1

0

1

0

1

1

1

0

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

а
)
.

Пример 2
.

Какая таблица истинности соответствует

логическому
выражению
A

AND

(
A

OR

B
)?

а)

А

В

F

0

0

0

0

1

1

1

0

0

1

1

1


б)

А

В

F

0

0

0

0

1

0

1

0

1

1

1

1


в)

А

В

F

0

0

0

0

1

1

1

0

1

1

1

1


г)


А

В

F

0

0

0

0

1

0

1

0

0

1

1

1


Решение:

Строится таблица истинности

заданного выражения

А

В

А
OR

В

A

AND

(
A

OR

B
)

0

0

0

0

0

1

1

0

1

0

1

1

1

1

1

1


9

Заданно
му

логическому выражению
соответствует
таблица
истинности

б
)
.

Пример 3.
Выполнить подстановку логической операции

так,
чтобы равенство (
1

_____
1
)
OR

NOT

(
1

_____
0
) =
0

оказалось
верным.

Решение
:

Строится таблица истинности


1

___
1

NOT

(
1

___
0
)

(
1

___
1
)
OR

NOT

(
1

____
0
)


XOR

0

0

0

0

AND

1

1

1

1

OR

1

0

1

1

Необходимо подставить операцию исключающее ИЛИ.


Задание для самостоятельной работы


1.

Какое логическое выражение соответствует заданной таблице
истинности?

А

В

С

0

0

1

0

1

0

1

0

1

1

1

1

a)
C
=
A

AND (
B

OR
A
)

б
)
C
=NOT (
A

OR
B
)

в
)
C
=(
A

OR
B
) XOR NOT
A

г
)
C
=(
A

OR
B
) AND

NOT
B

2.

Какая таблица истинности
соответствует логическому
выражению NOT (
A

OR
B)?

а)

А

В

F

0

0

1

0

1

0

1

0

0

1

1

0


б)

А

В

F

0

0

0

0

1

0

1

0

0

1

1

1


в)

А

В

F

0

0

0

0

1

1

1

0

1

1

1

1


г)


А

В

F

0

0

0

0

1

1

1

0

0

1

1

1



3.
Какую логическую операцию следует
применить, чтобы

оказалось верным равенство (
0

____
1
) XOR (
1

AND
1
) =
1
?





10

Законы алгебры логики

Высказывание является

тождественно истинным
, если оно
истинно при любых значениях входящих в неё переменных.

Высказывание является

тождественно ложным
, если оно
ложно при любых значениях входящих в неё переменных.

В
таблице
2

приведены законы
алгебр
ы

логики,
которые
позволяю
т

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

(таблица
2
).


Таблица
2



Законы алгебры логики


Наименование
закона

Дизъюнкция

Конъюнкция

Переместительный

закон

(коммутативности)

А


В В


А

А


В В


А

Сочетательный

закон

(ассоциативности)

А





С)




В)


С

А





С)

=





В)


С

Распределительный

закон

(дистрибутивности)

А





С)


(
А


В
)



(
А


С
)

А





С)





В)





С)

Закон
де Моргана

(инверсии)

¬ ( А


В) ¬А


¬В

¬( А


В) ¬А


¬В

Закон
равносильности

демпотен
тности)

А


А А

А


А А

Закон

п
оглощени
я

А





В) А

А





В) А

Закон с
клеивани
я
(исключения)




В)


(¬А


В)

В




В)


(¬А


В)

=

В

Закон
противоречия

А


¬ А 1

А


¬ А 0

Закон исключения
констант

А


0 А;

А


1 = 1

А


0 = 0;

А


1 А

Закон д
войно
го

отрицани
я

¬ ¬ А А




11

Пример
4
.

Какое из приведенных
логических выражений

является тождественно истинным?

а
)

(
А




В
)



А



В

б
)

(
А



В)



А




В

в
)

(
А



В
)


(
А




В)



А

г
)

(
А



В)



(
А




В)

Решение:
Согласно
закону де Моргана

¬
А



¬
В

¬(
А



В
)
Тогда
выражение
б

можно записать следующим образом:

(
А



В)



(
А



В
)
.

Строится таблица истинности

А

В

А



В


(
А



В
)


(
А



В)



(
А



В)

0

0

0

1

1

0

1

0

1

1

1

0

0

1

1

1

1

1

0

1

Высказывание
б
)

является тождественно истинным.

Пример
5
.

При каких значениях выполняется равенство

(
NOT

A
)
XOR

B

=
C
?

а
)

A = 1, B = 1,
С

= 0

б
)

A = 1, B = 0, C = 1

в
)

A = 0, B = 1, C = 0

г)

A

= 0,
B

= 0,
C

= 0

Решение:

Строится таблица истинности

А

(
NOT

A
)


В

(
NOT

A
)
XOR

B


C

1

0

1

1

0

1

0

0

0

1

0

1

1

0

0

0

1

0

1

0

Равенство выполняется при
A

= 0,
B

= 1,
C

= 0
, что

соответствует
вариант
у

в).

Пример 6.

Если т
очка
X

не принадлежит ни одному из отрезков
[
A
;
B
], [
C
;
D
],
то
гда

к
акое логическое выражение

будет истинно
?

а
)

(XA OR -4 ;&#xOR -;X00;XB) OR (NOT XC AND NOT -7; ND ;&#x-4NO;&#xT-4 ;&#xX000; XD)

б
)

NOT (XA A -4 ; -4N; X0;ND XB) AND NOT (XC AND X -7; ND ;&#x-4X-;怀D)

в
)

(XA AND -6 ; ND-; X0; XB) OR (XC AND -4; ND-; X0; X
D)

г
)

(XA -4;&#xOR X;OR XB) AND (XC OR OR;&#x-9 -;X00;XD)

Решение:

Точка
X

не принадлежит отрезку [
A
;
B
] если
X

A

OR

X

B
.


12

Точка
X

не принадлежит отрезку [
C
;
D
] если
X

C

OR

X

D
.

Тогда выражение

г
)
:

(
X

A

OR

X

B
)
AND

(
X

C

OR

X

D
)
определяет точку
X
,

не принадлежащую ни одному из отрезков.


Задание для самостоятельной работы


4
.

Какое из приведенных высказываний является тождественно
ложным?

а) Р


Р

б) Р



Р

в) Р



Р

г) Р

Р

5
. Какое из приведенных логических выражений является
истинным при
X
1 и
Y
=1?

а) (


X



Y
)


(

X




Y
)

б)
(
X



Y
)


(

X




Y
)

в)
(

X




Y
)


(

X




Y
)

г)
(
X



Y
)


(

X




Y
)

6
.

Что можно утверждать в случае истинности логического
выражения (A> X AND B> X) AND (C< X AND X< D)?

a) Х не принадлежит ни
одному их отрезков [A; B] , [C; D]

б) Х не принадлежит ни одному их отрезков [A; B] , [C; D]

в) X принадлежит отрезку [C; D] и не принадлежит отрезку [A; B]

г) X принадлежит обоим отрезкам [A; B] и [C; D]



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

Логические элементы ком
пьютера

Любое устройство
компьютера
, выполняющее действия над
двоичными данными
,

можно представить как некоторый
функциональный преобразователь
, который значения входных
логических переменных (0 или 1) в результате выполнения некоторой
логической операции
преобразует в выходное логическое значение

0 или 1 (рисунок 1).




Рисунок 1


Ф
ункциональный преобразователь

х

у

F(x, y)


13

Логический вентиль



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

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

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

(1
-
2 В), чем логический ноль (
0
).

Символические изображения стандартных вентилей

Логической функции в компьютере соответствует логическая
схема из вентилей.
В таблице
3

представлены символические
изображения стандартных вентилей.


Таблица
3



Символическое изображение стандартных вентилей

Название схемы

Изображение вентиля

Схема НЕТ (
NOT
)


Схема И (
AND
)




Схема И
-
НЕ (
AND
-
NOT
)


Схема ИЛИ (
OR
)




Схема ИЛИ
-
НЕ (
OR
-
NOT
)


A


A


B



B

A


A + B

1

B


14

Название схемы

Изображение вентиля

Схема исключающее ИЛИ

OR
)




Схема исключающее
ИЛИ
-
НЕ (Х
OR
-
NOT
)




Пример
7
.

П
остроить
логическую
схему

для заданной
л
огической
функции

(
ܣ

ܤ

ܥ
)

(


̅




)
̅
̅
̅
̅
̅
̅
̅
̅
̅

(
ܣ

ܥ
)
̅
̅
̅
̅
̅
̅
̅
̅
̅
.

Решение:
Логическ
ая схема для заданной логической

функции
имеет вид
:


Пример 8.

Построить
таблиц
у

истинности
для заданной
логической схемы:


Решение:
Логическим выражением, соответствующим
за
данной
логической схеме, будет выражение вида
:


(
ܣ

ܤ
)




(
ܣ
̅



ܤ
)




Строится таблица истинности для полученного выражения:

А

В








(
ܣ

ܤ
)



(



)

0

0

1

0

0

0

1

1

1

1

1

0

0

0

1

1

1

0

0

1

A


A


B

=1

B

A


A


B

=1

B


15

Т
аблица истинности
для заданной логической схемы:

А

В

F

0

0

0

0

1

1

1

0

1

1

1

1

Пример 9.

Определить вид логической функции,
соответствующей следующей
логической
схеме:


Решение:

Представленной
логическ
ой схеме соответствует
логическая функция вида


(
ܣ

ܤ
)

ܣ

̅


(




ܤ
)



Задание для самостоятельной работы


7.
Построить
логическую
схему для логической функции:

(
ܣ

ܤ

ܥ
)

(





)




̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅
.

8.
Определить вид логической функции, которая соответствует
следующей
логической
схеме:


9.

Построить
таблицу истинности
, которая соответствует
следующей

логическ
ой

схем
е
:



16

ЗАДАНИЕ ДЛЯ
КОНТРОЛЬ
Н
ОЙ

РАБОТ
Ы


1.

Выполнить подстановку операции так, чтобы равенство

(
1

AND

0
) _____
1

=
0

оказалось верным.

2.

При каких значениях
A
,
B
,
C

выполняется равенство

(
A

AND

C
)
AND

(
B

OR

C
) =
1
?

3.

При каких значениях
A
,
B

выполняется равенство

(
NOT

B
)
AND

A

=
1
?

4.

Для какого значения X логическое выражение

¬ ((X > 2) → (X > 3)) будет истинно?

5.

Какое из приведенных высказываний является тождественно
истинным?

а
)
A


(A → B)

б
)
A → B

в
)
A →
(A


B)


A

г)
A


B → A

6.

При каких значениях переменных
K
,
L, M, N логическое
выражение
(¬(M


L)


K) →(
¬
(K


¬M)


N)
будет ложным?

7.

В случае истинности логического выражения

(
A
�=
X

AND

B
�=
X
)
OR

(
C
=
X

AND

X
=
D
) можно ли утверждать,
что
точка
X

принадлежит одному из отрезков [
A
;
B
], [
C
;
D
]?

8.

Построить
логическую
схему для функции:



(
ܣ

ܤ

ܥ
)

(





)
̅
̅
̅
̅
̅
̅
̅
̅
̅
̅

(
ܣ

ܥ
)
̅
̅
̅
̅
̅
̅
̅
̅
̅

9.

При какой комбинации входных параметров А, В, С
невозможно

получить значение
F

= 1

на выходе из представленной
логической схемы?



10. Определить вид логической функции, которая соответствует
следующей
логической

схеме:



17

ВОПРОСЫ ДЛЯ САМОКОНТ
РОЛЯ

1.

Какие существуют логические операции
?

2.

Каков приоритет выполнения логических операций?

3.

Какие существуют логические константы?

4.

Какая логическа
я операция является унарной?

5.

Какие логические операции являются бинарными?

6.

Чему равен результат
логической
операции Инверсия?

7.

Как определяется результат
логической
операции
Конъюнкция?

8.

Как определяется результат
логической
операции Дизъюнкция?

9.

Как определяется результат
логической
операции
Исключающее ИЛИ?

10.

Как определяется результат
логической
операции
Импликация?

11.

Как определяется результат
логической
операции
Эквивалентность?

12.

Какое высказывание является тождественно истинным?

13.

Какое высказывание

является тождественно ложным?

14.

Какие существуют законы алгебры логики для тождественных
преобразований логических выражений?

15.

Что называется функциональным преобразователем?

16.

Что такое логический вентиль?

17.

На каких операциях основана логика работы вентиля?

18.

Ка
кие существуют виды стандартных логических вентилей?

СПИСОК ЛИТЕРАТУРЫ

1.

Гуров В.В. Основы теории и организации ЭВМ : учебное
пособие / В.В. Гуров, В.О. Чуканов.


М. : Интернет
-
Университет
Информационных Технологий , 2010.


269 с.

2.

Ермаков А.П. Основы инфор
матики и вычислительной
техники: учебное пособие для вузов / А.П. Ермаков.


Старый Оскол :
ТНТ, 2010.


259 с.

3.

Информатика [Электронный ресурс] : электронный учебно
-
методический комплекс. Ч. 1 / Л. Д. Павлова, О. А. Кондратова, Н. В.
Балицкая, Д. Н. Клим
ова ; Сиб. гос. индустр. ун
-
т.


Электронные
данные.


Новокузнецк : СибГИУ, 2010.

4.

Степанов А.Н. Информатика. Базовый курс : учебное пособие
для вузов / А.Н. Степанов.


6
-
е изд.


СПб. : Питер, 2010.

Учебное

издание



Составител
и
:


Павлова Лариса Дмитриевна

Корнева

Анна Валерьевна




ОСНОВНЫЕ ПОНЯТИЯ АЛГ
ЕБРЫ ЛОГИКИ
.

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




Методические указания

к выполнению лабораторной работы

по дисциплине «Информатика»








Напечатано в полном
соответствии с авторским оригиналом









Подписано в печать
2
7
.
0
1
.
2
01
6

г.

Формат бумаги 60 х 84 1/16. Бумага писчая. Печать офсетная.

Усл. печ. л.
1,
0
5
. Уч.
-
изд. л.
1,
17
. Тираж 100 экз. Заказ

121


Сибирский государственный индустриальный университет

654007, г. Новокузнецк, ул. Кирова,

42.

Издательский центр
СибГИУ


Приложенные файлы

  • pdf 5634468
    Размер файла: 643 kB Загрузок: 0

Добавить комментарий