Логические основы ЭВМ. Теоретическая часть
Логика изучает внутреннюю структуру процесса мышления, который реализуется в таких естественно сложившихся формах как понятие, суждение, умозаключение и доказательство.
Высказывание. Высказывание (суждение) - это форма мышления, выраженная с помощью понятий, посредством которой что-либо утверждают или отрицают о предметах, их свойствах и отношениях между ними.
Высказывание называется простым, если никакая его часть сама не является высказыванием. Высказывание, состоящее из простых высказываний, называются составным (сложным).
Алгебра высказываний
Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться над различными математическими объектами (алгебра переменных и функций, алгебра векторов, алгебра множеств и т.д.). Объектами алгебры логики являются высказывания.
Алгебра логики отвлекается от смысловой содержательности высказываний. Ее интересует только один факт — истинно или ложно данное высказывание, что дает возможность определять истинность или ложность составных высказываний алгебраическими методами.
Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
А = {Аристотель - основоположник логики}
В = {На яблонях растут бананы}.
Истинному высказыванию ставится в соответствие 1, ложному — 0. Таким образом, А = 1, В = 0.
Составные высказывания на естественном языке образуются с помощью союзов, которые в алгебре высказываний заменяются на логические операции. Логические операции задаются таблицами истинности и могут быть графически проиллюстрированы с помощью диаграмм Эйлера-Венна.
Логическая операция КОНЪЮНКЦИЯ (логическое умножение):
в естественном языке соответствует союзу и;
в алгебре высказываний обозначение &;
в языках программирования обозначение And.
Конъюнкция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.
В алгебре множеств конъюнкции соответствует операция пересечения множеств, т.е. множеству получившемуся в результате умножения множеств А и В соответствует множество, состоящее из элементов, принадлежащих одновременно двум множествам.
Таблица истинности
|
Диаграмма Эйлера-Венна
| -
А
|
В
|
А&В
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
|
|
Логическая операция ДИЗЪЮНКЦИЯ (логическое сложение):
в естественном языке соответствует союзу или;
обозначение ;
в языках программирования обозначение Or.
Дизъюнкция - это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны и истинным, когда хотя бы одно из двух образующих его высказываний истинно.
В алгебре множеств дизъюнкции соответствует операция объединения множеств, т.е. множеству получившемуся в результате сложения множеств А и В соответствует множество, состоящее из элементов, принадлежащих либо множеству А, либо множеству В.
Таблица истинности
|
Диаграмма Эйлера-Венна
|
А
|
В
|
А В
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
|
Логическая операция ИНВЕРСИЯ (отрицание):
в естественном языке соответствует словам неверно, что... и частице не;
обозначение  ;
в языках программирования обозначение Not;
Отрицание - это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.
В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества, т.е. множеству получившемуся в результате отрицания множества А соответствует множество , дополняющее его до универсального множества.
Таблица истинности
|
Диаграмма Эйлера-Венна
|
A
|
|
0
|
1
|
1
|
0
|
|
|
Логическая операция ИМПЛИКАЦИЯ (логическое следование):
в естественном языке соответствует обороту если ..., то ...;
обозначение .
Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.
А
|
В
|
А В
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
Логическая операция ЭКВИВАЛЕНЦИЯ (равнозначность):
в естественном языке соответствует оборотам речи тогда и только тогда; в том и только в том случае;
обозначения , ~ .
Эквиваленция – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны. Таблица истинности эквиваленции:
А
|
В
|
А В
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
Логические операции имеют следующий приоритет: действия в скобках, инверсия, &, , , .
Логические основы компьютера
Дискретный преобразователь, который после обработки входных двоичных сигналов выдаёт на выходе сигнал, являющийся значением одной из логических операций, называется логическим элементом.
Ниже приведены условные обозначения (схемы) базовых логических элементов, реализующих логическое умножение (конъюнктор), логическое сложение (дизъюнктор) и отрицание (инвертор).
Алгоритм построения таблицы истинности:
1) подсчитать количество переменных n в логическом выражении;
2) определить число строк в таблице, которое равно m = 2n;
3) подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций;
4) ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов;
5) заполнить стобцы входных переменных наборами значений;
6) провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.
Наборы входных переменных, во избежание ошибок, рекомендуют перечислять следующим образом:
а) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;
б) разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами нулей и единиц , начиная с группы нулей;
в) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами нулей или единиц до тех пор, пока группы нулей и единиц не будут состоять из одного символа.
Пример. Для формулы A&(B  &  ) построить таблицу истинности алгебраически и с использованием электронных таблиц.
Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть 23 = 8.
Количество логических операций в формуле 5, следовательно количество столбцов в таблице истинности должно быть 3 + 5 = 8.
A
|
B
|
C
|
|
|
&
|
B ( & )
|
A&(B & )
|
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
|
Задание:
Построить таблицы истинности для следующих формул:
а) A (B   )
б) A (B )
в) A (B ) A (B )
Занятие 6. Алгебра логики. Основные законы преобразования алгебры логики. Теоретическая часть
Логические выражения называются равносильными, если их истинностные значения совпадают при любых значениях, входящих в них логических переменных.
В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.
1. Закон двойного отрицания:
А = .
Двойное отрицание исключает отрицание.
2. Переместительный (коммутативный) закон:
— для логического сложения:
А B = B A;
— для логического умножения:
A&B = B&A.
Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.
В обычной алгебре a + b = b + a, a b = b a.
3. Сочетательный (ассоциативный) закон:
— для логического сложения:
(A B) C = A (B C);
— для логического умножения:
(A&B)&C = A&(B&C).
При одинаковых знаках скобки можно ставить произвольно или вообще опускать.
В обычной алгебре:
(a + b) + c = a + (b + c) = a + b + c,
а (b c) = a (b c) = a b c.
4. Распределительный (дистрибутивный) закон:
— для логического сложения:
(A B)&C = (A&C) (B&C);
— для логического умножения:
(A&B) C = (A C)&(B C).
Определяет правило выноса общего высказывания за скобку.
В обычной алгебре:
(a + b) c = a c + b c.
5. Закон общей инверсии (законы де Моргана):
— для логического сложения
 =  & ;
— для логического умножения:
 =
6. Закон идемпотентности ( от латинских слов idem — тот же самый и potens —сильный; дословно — равносильный):
— для логического сложения:
A A = A;
— для логического умножения:
A&A = A.
Закон означает отсутствие показателей степени.
7. Законы исключения констант:
— для логического сложения:
A 1 = 1, A 0 = A;
— для логического умножения:
A&1 = A, A&0 = 0.
8. Закон противоречия:
A& = 0.
Невозможно, чтобы противоречащие высказывания были одновременно истинными.
9. Закон исключения третьего:
A = 1.
Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.
10. Закон поглощения:
— для логического сложения:
A (A&B) = A;
— для логического умножения:
A&(A B) = A.
11. Закон исключения (склеивания):
— для логического сложения:
(A&B) ( &B) = B;
— для логического умножения:
(A B)&( B) = B.
12. Закон контрапозиции (правило перевертывания):
(A Û B) = (BÛ A).
Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений А и В, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут.
Пример 3.11. Найдите X, если   = В.
Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:
(  & ) ( &A)
Согласно распределительному закону для логического сложения:
&( A)
Согласно закону исключения третьего и закона исключения констант:
&1 =
Полученную левую часть приравняем правой:
= В
Окончательно получим, что X = .
Пример 3.12. Упростите логическое выражение (A B C)& 
Правильность упрощения проверьте с помощью таблиц истинности для исходного и полученного логического выражения.
Согласно закону общей инверсии для логического сложения (первому закону Моргана) и закону двойного отрицания:
(A B C)&  = (A B C)&( &B& )
Согласно распределительному (дистрибутивному) закону для логического сложения:
(A B C)&( &B& ) = (A& ) (B& ) (C& ) (A&B) (B&B) (C&B) (A& ) (B& ) (C& )
Согласно закона противоречия:
(A& ) = 0; (C& ) = 0
Согласно закона идемпотентности
(B&B) = B
Подставляем значения и, используя переместительный (коммутативный) закон и группируя слагаемые, получаем:
0 (A&B) ( &B) B (C&B) ( &B) (C& ) (A& ) 0
Согласно закона исключения (склеивания)
(A&B) ( &B) = B
(C&B) ( &B) = B
Подставляем значения и получаем:
0 B B B (C& ) (A& ) 0
Согласно закона исключения констант для логического сложения и закона идемпотентности:
0 B 0 B B = B
Подставляем значения и получаем:
B (C& ) (A& )
Согласно распределительному (дистрибутивному) закону для логического умножения:
(C& ) (A& ) = (C A)&(C )&( A)&( )
Согласно закона исключения третьего:
(C ) = 1
( A) = 1
Подставляем значения и окончательно получаем:
B& & . |
