Praktika_II_Logika
.pdfФедеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования
Уфимский государственный авиационный технический университет
ЛОГИЧЕСКИЕ ОСНОВЫ ОРГАНИЗАЦИИ ЭВМ
ПРАКТИКУМ по дисциплине «Информатика»
Часть II
Уфа 2007
Составители: М.П. Карчевская, О.Л. Рамбургер
УДК 004.4 (07)
ББК 32.973-018.2(я7)
Логические основы организации ЭВМ: Практикум по дисциплине «Информатика». Часть II / Уфимск. гос. авиац. техн. ун-т; Сост.: М.П. Карчевская, О.Л. Рамбургер – Уфа, 2007. – 24 с.
Излагаются рекомендации для проведения второго из пяти практических занятий по дисциплине «Информатика». Приводятся краткие теоретические сведения, примеры решения задач и задачи для самостоятельной работы, посвященные логическим основам ЭВМ: построение таблиц истинности, преобразование логических функций, построение логических выражений, составление логических схем.
Предназначен для студентов, обучающихся по направлению подготовки дипломированного специалиста 140100 – « Теплоэнергетика» специальности 140101 – « Тепловые электрические станции», направлению 160300 – « Двигатели летательных аппаратов» специальности 160304 – « Авиационная и ракетно-космическая теплотехника», направлению 220300 – « Автоматизированные технологии и производства» специальности 220301 – « Автоматизация технологических процессов и производств» и направлению подготовки бакалавра 220200 – « Автоматизация и управление» и одобрены научнометодическими советами специальностей.
Табл. 5. Библиогр.: 5 назв.
Рецензенты: канд. техн. наук доц. Каримов Р. Р. д-р техн. наук, проф. Кривошеев И. А.
© Уфимский государственный авиационный технический университет, 2007
|
СОДЕРЖАНИЕ |
|
1. |
ОСНОВЫ ЛОГИКИ ........................................................................................... |
4 |
2. |
ПОСТРОЕНИЕ ТАБЛИЦЫ ИСТИННОСТИ ДЛЯ ЗАДАННОЙ |
|
|
ЛОГИЧЕСКОЙ ФУНКЦИИ............................................................................. |
6 |
3. |
ПРЕОБРАЗОВАНИЕ ЛОГИЧЕСКИХ ФУНКЦИЙ..................................... |
8 |
4. |
ПОСТРОЕНИЕ ЛОГИЧЕСКОЙ ФУНКЦИИ ПО ЗАДАННОЙ |
|
|
ТАБЛИЦЕ ИСТИННОСТИ............................................................................ |
11 |
5. |
ПОСТРОЕНИЕ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ ПО УСЛОВИЯМ, |
|
|
ЗАДАННЫМ В ВИДЕ ТЕКСТА..................................................................... |
13 |
6. |
РЕШЕНИЕ ТЕКСТОВЫХ ЛОГИЧЕСКИХ ЗАДАЧ ................................. |
15 |
7. |
ЛОГИЧЕСКИЕ СХЕМЫ................................................................................. |
19 |
СПИСОК ЛИТЕРАТУРЫ ..................................................................................... |
24 |
3
1. ОСНОВЫ ЛОГИКИ
Высказывание в алгебре логики – это повествовательное предложение, в котором что-либо утверждается или отрицается. По поводу любого высказывания можно сказать истинно оно или ложно.
Логические величины – |
понятия, |
выражаемые словами |
|||
ИСТИНА, ЛОЖЬ. |
|
|
|
|
|
Логические константы – |
ИСТИНА или ЛОЖЬ. Принята сле- |
||||
дующая кодировка логических констант: |
|
|
|||
|
|
|
|
|
|
|
Значение логической константы |
|
Кодировка |
|
|
|
|
|
|
|
|
|
ЛОЖЬ |
|
|
0 |
|
|
ИСТИНА |
|
|
1 |
|
Логическая переменная – |
символически обозначенная логиче- |
ская величина, которая может принимать значения только ИСТИНА или ЛОЖЬ.
Простое высказывание – это повествовательное предложение или некоторое математическое соотношение, в котором что-либо утверждается или отрицается и в отношении которого можно сразу сказать, истинно оно или ложно. Простые высказывания в математике строятся с помощью знаков отношений (<, >, =, ¹ , ³ , £).
Сложное высказывание образуется из других высказываний с помощью логических операций.
Простому высказыванию ставят в соответствие логическую пе-
ременную, а сложному – логическую функцию Y = F ( X1, X 2 ,..., X N ) ,
где X1, X 2 ,..., X N – логические переменные, соответствующие простым высказываниям.
С помощью логических переменных и символов, обозначающих логические операции любое высказывание можно формализовать, т.е.
заменить логической формулой.
В табл. 1.1 приведено описание основных логических операций.
4
Таблица 1.1
|
№ |
|
|
Операция |
|
|
Обозна- |
|
|
Истолкование |
|
|||
|
|
|
|
|
|
чение |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
не А, |
|
|
|
операции |
|||
1 |
|
|
Инверсия |
|
ØА, |
|
Не А; |
|
||||||
|
|
|
|
|
|
|||||||||
|
|
(Отрицание) |
|
|
|
Неверно, что А |
|
|
||||||
|
|
|
` |
A |
|
|
|
|||||||
|
|
|
|
|
|
|
not A |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
А·В, |
|
|
А и В; |
|
логические |
||
|
|
|
|
|
|
|
А ´ В |
|
|
A, но B; |
|
|||
|
2 |
|
|
Конъюнкция |
|
|
А Ù В, |
|
|
A, a B; |
|
|
||
|
|
|
(логическое произведение) |
|
|
А и В, |
|
|
как А, так и В; |
|
|
|||
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
А and В, |
|
|
А вместе с В; |
|
|
||
|
|
|
|
|
|
|
А & В |
|
|
А в то время, как В |
|
Базовые |
||
3 |
|
|
(логическое сложение) |
|
А или В, |
|
А или В или оба |
|
||||||
|
|
|
|
|
|
|
А + В, |
|
|
|
|
|||
|
|
|
|
Дизъюнкция |
|
А Ú В, |
|
А или В; |
|
|
||||
|
|
|
|
|
|
|
А or В |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
А xor В, |
|
А либо В; |
|
||||
|
4 |
|
|
Исключающее ИЛИ |
|
|
А " В, |
|
А или В, но не оба |
|
||||
|
|
|
|
|
|
|
А Å В |
|
Только A или только B |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
Если А, то В; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Из A следует В; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В если А; |
|
|
5 |
|
|
Импликация |
|
А ® В |
|
В необходимо для А; |
|
||||||
|
|
|
|
А достаточно для В; |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
А только тогда, когда В; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В тогда, когда А; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
все А есть В |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
А « В, |
|
А эквивалентно В; |
|
||||
|
6 |
|
|
Эквиваленция |
|
|
А = В, |
|
А необходимо и достаточно для В; |
|||||
|
|
|
|
|
|
|
А ~ В |
|
А тогда и только тогда, когда В; |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Приоритеты выполнения логических операций в логических выражениях:
1.отрицание;
2.логическое произведение;
3.логическое сложение, исключающее или;
4.импликация, эквиваленция.
5
Скобки меняют порядок выполнения операций.
Для удобства и наглядности отражения сути логических операций производимых над логическими переменными принято использовать таблицы истинности. В таблицах истинности записываются все возможные сочетания значений логических переменных и соответствующие им значения логической функции.
В табл. 1.2 приведена сводная таблица истинности для описанных логических операций в табл. 1.1.
|
|
|
|
|
|
|
Таблица 1.2 |
|
|
|
|
|
|
|
|
|
|
А |
В |
Not A |
A and B |
A or B |
A xor B |
A → B |
|
A ↔ B |
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|
1 |
2.ПОСТРОЕНИЕ ТАБЛИЦЫ ИСТИННОСТИ ДЛЯ ЗАДАННОЙ ЛОГИЧЕСКОЙ ФУНКЦИИ
Для каждой логической функции Y = F ( X1, X 2 ,..., X N ) можно построить таблицу истинности. Количество строк в этой таблице будет равно числу возможных комбинаций значений логических переменных, т.е. 2N, где N – число логических переменных, входящих в логическое выражение. Количество столбцов в таблице истинности равно сумме количества логических переменных и количества логических операций в логическом выражении, т.е. N+M, где M – число логических операций.
Логические выражения называются тождественно истинными, если они имеют в таблице истинности значения 1 для всех наборов значений входных переменных.
Логические выражения называются тождественно ложными, если они имеют в таблице истинности значения 0 для всех наборов значений входных переменных.
Логические выражения называются равносильными или эквива- лентными, если они имеют одинаковые значения в таблице истинности для всех наборов значений входных переменных.
6
Пример 2.1. Составить таблицу истинности для логической функции
F ( A, B,C) = (B or C) and A.
Решение. Количество строк, в таблице истинности будет равно 8 (23), количество столбцов – 6 (3 + 3). Для каждой логической операции в порядке приоритета вычисляется значение согласно таблице 2.1, результат операции записывается в соответствующей колонке таблицы истинности при соответствующих значениях переменных. Последняя колонка полученной таблицы является ответом на поставленную задачу.
|
|
|
|
|
|
|
(B + C) × |
|
|
|
|
|
|
|
|
|
|
B+C |
|
A |
|
||
A |
B |
С |
|
A |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
|
0 |
0 |
|
|
|
||
0 |
0 |
1 |
1 |
|
1 |
1 |
|
|
|
||
0 |
1 |
0 |
1 |
|
1 |
1 |
|
|
|
||
0 |
1 |
1 |
1 |
|
1 |
1 |
|
|
|
||
1 |
0 |
0 |
0 |
|
0 |
0 |
|
|
|
||
1 |
0 |
1 |
0 |
|
1 |
0 |
|
|
|
||
1 |
1 |
0 |
0 |
|
1 |
0 |
|
|
|
||
1 |
1 |
1 |
0 |
|
1 |
0 |
|
|
|
Пример 2.2. Доказать, что функции f ( A, B,C) = ( A Ù B) Ú ( A Ù C) и g( A, B,C) = ( A Ù B) Ú ( A Ù C) Ú (B Ù C) являются эквивалентными.
Решение: Составим таблицу истинности для обеих функций:
|
A |
|
|
B |
|
|
C |
|
|
A × B |
|
|
|
|
|
|
×C |
|
A × B + |
|
×C |
B × C |
A × B + |
|
× C + B ×C |
|
|
|
|
|
|
|
|
|
|
A |
|
|
|
A |
|
A |
A |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
0 |
|
0 |
|
0 |
|
1 |
|
|
0 |
|
0 |
|
|
0 |
0 |
|||||||||
|
0 |
|
|
0 |
|
|
1 |
|
0 |
|
1 |
|
|
1 |
|
1 |
|
|
0 |
1 |
||||||
0 |
|
1 |
|
0 |
|
0 |
|
1 |
|
|
0 |
|
0 |
|
|
0 |
0 |
|||||||||
0 |
|
1 |
|
1 |
|
0 |
|
1 |
|
|
1 |
|
1 |
|
|
1 |
1 |
|||||||||
1 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
0 |
|
0 |
|
|
0 |
0 |
|||||||||
1 |
|
0 |
|
1 |
|
0 |
|
0 |
|
|
0 |
|
0 |
|
|
0 |
0 |
|||||||||
|
1 |
|
|
1 |
|
|
0 |
|
1 |
|
0 |
|
|
0 |
|
1 |
|
|
0 |
1 |
||||||
1 |
|
1 |
|
1 |
|
1 |
|
0 |
|
|
0 |
|
1 |
|
|
1 |
1 |
Ответ: Поскольку на всех наборах значений входных переменных значения функции f ( A, B,C) и g( A, B,C) в таблице истинности одинаковые, то они являются эквивалентными.
7
Задачи и упражнения
1.Определить при каких значениях переменных логическая функция
ABC ® ( A + B) принимает значение ИСТИНА.
2.Определить при каких значениях переменных логическая функция
( A º B) ×(B ® A) + C принимает значение ЛОЖЬ.
3.Определить является ли логическая функция ( AB ® B )( AB ® A )
тождественно истинной.
4. Определить какие из трех предложенных функций
(( A and not B or not A and B) and (B → A and B)) and B ;
( A ↔ B ) and (not A and B ↔ B) or not ( A or B) ; A and (( A → B) and (( A and B) → (not A and B)))
являются эквивалентными. |
|
|
|
|||
5. Составить |
таблицу |
истинности |
для |
функции |
||
F( A, B,C ) = A Ù B Ú |
|
Ù C . |
|
|
|
|
A |
|
|
|
3. ПРЕОБРАЗОВАНИЕ ЛОГИЧЕСКИХ ФУНКЦИЙ
Логические операции инверсии, конъюнкции и дизъюнкции называют базовыми. Любую функцию с помощью тождественных преобразований можно представить таким образом, чтобы она содержала только базовые логические операции. В табл. 3.1 приведены тождества, позволяющие заменить операции «исключающее ИЛИ», «импликации» и «эквиваленции» базовыми функциями.
Таблица 3.1
A Å B = A × B + A × B ;
A ® B = A + B ;
A « B = A × B + A × B ;
A« B = ( A + B) × ( A + B)
Втабл. 3.2 приведены основные законы алгебры логики, позволяющие производить тождественные преобразования логических выражений.
8
Таблица 3.2
Закон
Переместительный
Сочетательный
Распределительный
Правила де Моргана
Идемпотенции
Поглощения
Склеивания
Переменная и ее инверсия
Переменная и константа
Двойное отрицание
Для операции дизъюнкции |
Для операции конъюнкции |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A + B = B + A |
|
A × B = B × A |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( A + B) + C = A + (B + C) |
( A × B) × C = A × (B × C) |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A×(B + C) = A× B + A×C |
A + B ×C = ( A + B) ×( A + C) |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
|
|
× |
|
|
|
|
|
|
|
|
= |
|
|
|
+ |
|
|
|||||
|
A + B |
A |
B |
A × B |
A |
B |
||||||||||||||||||||||
|
|
|
|
|
= A × B |
|
|
|
|
= A + B |
||||||||||||||||||
|
|
+ |
|
|
|
|
× |
|
||||||||||||||||||||
|
A |
B |
A |
B |
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
A + A = A |
|
|
A × A = A |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
A + A × B = A |
A × ( A + B) = A |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
( A × B ) + ( |
|
|
× B ) = B |
( A + B )×( |
|
|
|
+ B ) = B |
||||||||||||||||||||
A |
A |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
A + |
|
|
= 1 |
|
|
|
|
A × |
|
|
= 0 |
|||||||||||||||
|
|
A |
|
|
A |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
A + 0 = A |
|
|
|
|
|
|
A +1 = 1 |
A ×1 = A A × 0 = 0 |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= A |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Форма представления логических функций, содержащая только три основные логические операции: логическое отрицание, логическое сложение и логическое умножение называется нормальной. Инверсия в нормальной форме представления должна быть только над переменными (не над выражениями!).
Выделяют две специальных нормальных формы представления логических функций:
-Конъюнктивно-нормальная форма (КНФ) – представление в виде произведений суммы элементарных высказываний и их отрицаний (дизъюнкции конъюнкций). Например:
F ( A, B,C) = ( A or not B) and (not A or not B) and (B or C or A)
или
F ( A, B, C) = ( A + B) × ( A + B) × (B + C + A)
9
-Дизъюнктивно-нормальная форма (ДНФ) – представление в виде суммы произведений элементарных высказываний и их отрицаний (конъюнкции дизъюнкций). Например:
F ( A, B,C) = ( A and not B and C) or (not A and B) or (not C and A)
или
F ( A, B,C) = A × B × C + A × B + C × A
Любая логическая функция приводится к КНФ или ДНФ с помощью следующего алгоритма:
-избавляются от импликации и эвиваленции;
-избавляются от отрицаний над сложными высказываниями;
-раскрывают скобки, применяя распределительный закон логики.
Пример 3.1. Привести логическое высказывание
(A ® C) and (B « C) к ДНФ.
Решение:
1. Избавимся от импликации и эвиваленции:
( A ® C) and (B « C) = ( A + C) × (B × C + B × C)
1. Раскрываем скобки:
( A + C) × (B × C + B × C) = A × B ×C + C × B + A × B × C + C × B × C
2. Преобразуем:
A × B ×C + C × B + A × B × C + C × B × C = B × C × ( A +1) + A × B × C = B × C + A × B ×C
Ответ: ( A ® C) and (B « C) = B × C + A × B × C
Задачи и упражнения
1.Упростите логическое выражение A Ú B ( A ® B) .
2.Укажите минимальное количество операций отрицания, конъ-
юнкции и дизъюнкции с помощью которых можно вычислить логическую функцию F( A,B,C ) = ( A ® B ) « BC .
3.Упростите логическое выражение ( A ® B) « (B ® A).
4.Упростите логическое выражение ( AB Ú A Ú B) Ú A Å B .
5.Докажите тождество
( A Ú B Ú C) Ù ( A Ú B Ú C) Ù ( A Ú B Ú C) Ù ( A Ú B Ú C) Ù ( A Ú B Ú C) = = A Ù B + B Ù C.
10