В предыдущих темах вы познакомились с устройством компьютера и узнали, что в процессе обработки двоичной информации процессор выполняет арифметические и логические операции. Поэтому для получения представлений об устройстве компьютера необходимо познакомиться с основными логическими элементами, лежащими в основе построения компьютера. Для понимания принципа работы таких элементов начнем это знакомство с основных начальных понятий формальной логики.
Воснове современной логики лежат учения, созданные еще древнегреческими мыслителями, хотя первые учения о формах и способах мышления возникли в Древнем Китае и Индии. Основоположником формальной логики является Аристотель, который впервые отделил логические формы мышления от его содержания.
Сам термин «логика» происходит от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон».
Логика— это наука о формах и способах мышления. Это учение о способах рассуждений и доказательств.
Законы мира, сущность предметов, общее в них мы познаем посредством абстрактного мышления. Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны.
Мышление всегда осуществляется через понятия, высказывания и умозаключения.
Понятие — это форма мышления, которая выделяет существенные признаки предмета или класса предметов, позволяющие отличать их от других.
ПримерПрямоугольник, проливной дождь, компьютер.
Логика использует ряд основных понятий и описывает действия над ними, подчиняющиеся законам логики. К этим основным понятиям логики относятся следующие.
Высказывание(суждение)— это формулировка своего понимания окружающего мира. Высказывание является повествовательным предложением, в котором что-либо утверждается или отрицается.
По поводу высказывания можно сказать, истинно оно или ложно. Истинным будет высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Ложным высказывание будет в том случае, когда оно противоречит реальной действительности.
Ложное высказывание: «Компьютер был изобретен в середине XIX века».
Заметим, что любое высказывание не может быть одновременно истинным и ложным, а принимает только одно из этих двух возможных логических значений: ИСТИНА или ЛОЖЬ. Эти значения называются логическими постоянными, или логическими константами.
Утверждение — суждение, которое требуется доказать или опровергнуть, например, сумма внутренних углов треугольника равна 180°.
Рассуждение — цепочка высказываний или утверждений, определенным образом связанных друг с другом, например, если хотите начать работать на компьютере, то необходимо сначала включить электропитание,
Умозаключение позволяет на основе известных фактов, выраженных в форме суждений, получать новое знание.
Умозаключение — это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение (знание или вывод).
Пример:
Дано высказывание: «Все углы равнобедренного треугольника равны».
Получить высказывание «Этот треугольник равносторонний» путем умозаключений.
Пусть основанием треугольника является сторона с. Тогда а=Ь. Так как в треугольнике все углы равны, следовательно, основанием может быть любая другая сторона, например а. Тогда Ь=с. Следовательно а=Ь=с. Треугольник равносторонний.
Выполните упражнение
Какие из предложений являются высказываниями? Определите их истинность.
1. Какой длины эта лента?
2. Прослушайте сообщение.
3. Делайте утреннюю зарядку!
4. Назовите устройство ввода информации.
5. Кто отсутствует?
6. Париж — столица Англии.
7. Число 11 является простым.
8. 4 + 5=10.
9. Без труда не вытащишь и рыбку из пруда.
10. Сложите числа 2 и 5.
11. Некоторые медведи живут на севере.
12. Все медведи - бурые.
13. Чему равно расстояние от Москвы до Сенкт-Петербурга.
Логические выражения и операции
Подобно тому, как для описания действий над переменными величинами был разработан раздел математики — алгебра, так и для обработки логических выражений в математической логике была создана алгебра высказываний, или алгебра логики. Поскольку основы такой алгебры были заложены в трудах английского математика Джорджа Буля (XIX век), то алгебра логики получила также название булевой алгебры. Вспомним, что ранее мы уже говорили о том, что решение любой задачи на компьютере сводится к выполнению процессором ряда арифметических и логических операций. Последние как раз и выполняются над логическими выражениями на основе законов и правил булевой алгебры. Таким образом, математический аппарат булевой алгебры позволил формализовать действия над логическими выражениям и явился базой для разработки логических элементов и, в целом, логических основ построения компьютеров.
Из сказанного становится ясно, что для лучшего понимания работы компьютера как инструмента обработки информации необходимо познакомиться с логическими выражениями, а также их преобразованием с помощью логических операций, определенных в булевой алгебре.
Алгебра — это наука об общих операциях, аналогичных сложению и умножению, которые выполняются не только над числами, но и над другими математическими объектами, в том числе и над высказываниями. Такая алгебра называется алгеброй логики.Алгебра логики отвлекается от смысловой содержательности высказываний и принимает во внимание только истинность или ложность высказывания.
Можно определить понятия логической переменной, логической функции и логической операции.
Логическая переменная— это простое высказывание, содержащее только одну мысль. Ее символическое обозначение - латинская буква (например, A,B,X,Y и т.д.). Значением логической переменной могут быть только константы ИСТИНАи ЛОЖЬ (1и 0).
Составное высказывание - логическая функция,которая содержит несколько простых мыслей, соединенных между собой с помощью логических операций. Ее символическое обозначение —F(A,B,...).
На основании простых высказываний могут быть построены составные высказывания.
Логические операции— логическое действие.
Рассмотрим три базовые логические операции - конъюнкцию, дизъюнкцию и отрицание и дополнительные - импликацию и эквивалентность. Предварительно заметим, что аргументами этих операций являются простые логические выражения, а их результат равен 1 или О (логические значения) и определяется по соответствующей таблице истинности.
Логическая операция КОНЪЮНКЦИЯ определяет соединение двух логических выражений (высказываний) с помощью союза И. Эта операция называется также логическим умножением и обозначается символами & или ^. Рассмотрим таблицу истинности, определяющую результат этой логической операции над двумя аргументами — простыми логическими выражениями А и В, каждое из которых может принимать логические значения 0 или 1.
А
В
А&В
В соответствии с таблицей истинности можно дать следующее определение: конъюнкцией называется логическая операция, ставящая в соответствие двум простым логическим выражениям новое — сложное логическое выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных (простых) логических выражения.
Логическая операция ДИЗЪЮНКЦИЯ определяет логическое соединение двух логических выражений (высказываний) с помощью союза ИЛИ. Эта операция называется также еще логическим сложением и обозначается значком v. Рассмотрим таблицу истинности, определяющую результат этой логической операции над двумя аргументами — простыми логическими выражениями А и В, каждое из которых может принимать логические значения 0 или 1.
А
В
AvB
В соответствии с таблицей истинности можно дать определение: дизъюнкцией называется логическая операция, ставящая в соответствие двум простым логическим выражениям новое — сложное логическое выражение, которое будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) логических выражений.
Логическая операция ОТРИЦАНИЕ, илиИНВЕРСИЯ, определяется над одним аргументом (простым или сложным логическим выражением) следующим образом: если исходное выражение истинно, то результат его отрицания будет ложным, и наоборот, если исходное выражение ложно, то его отрицание будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО. Операция ОТРИЦАНИЕ обозначается символом , а ее результат определяется следующей таблицей истинности:
А
а
Логическая операция ИМПЛИКАЦИЯ {логическое следование).
Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия. В разговорном языке эта операция выражается словами если... , то... Для ее обозначения в алгебре логики используется значок следования =>. Результат операции импликации для условия А (первое логическое выражение) и условия В (второе логическое выражение) определяется в соответствии со следующей таблицей истинности:
А
В
А=>В
По определению результатом импликации является ЛОЖЬ тогда и только тогда, когда условие (А) истинно, а следствие (В) ложно.
Логическая операция ЭКВИВАЛЕНТНОСТЬ (равнозначность) определяет результат сравнения двух простых логических выражений А и В, обозначается символом <=>. Результат этой операции — новое логическое выражение, которое является истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Это определение описывается следующей таблицей истинности:
А
В
А<=>В
Сложным логическим выражениемназывается логическое выражение, составленное из одного или нескольких простых (или сложных) логических выражений, связанных с помощью рассмотренных логических операций. Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение,значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА. При составлении логического выражения необходимо учитывать порядок выполнения логических операций.
Порядок выполнения логических операций в сложном логическом выражении:
1. инверсия — ;
2. конъюнкция — & (или ^);
3. дизъюнкция — v;
4. импликация — =>;
5. эквивалентность — <=>.
Для изменения указанного порядка выполнения логических операций используются круглые скобки.
Например, А, В и С — три простых логических выражения. Одним из примеров составленного из них сложного логического выражений будет:
D = (AvB&C)
Пример
Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку».
1. Проанализируем составное высказывание.
Оно состоит из следующих простых высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдет на рыбалку». Обозначим их через логические переменные:
A = Петя поедет в деревню;
В = Будет хорошая погода;
С = Он пойдет на рыбалку.
2. Запишем высказывание в виде логического выражения, учитывая по рядок действий. Если необходимо, расставим скобки:
F = A&(B=>С).
Выполните упражнение
I. Есть два простых высказывания: А - «Число 10 - четное»; В - «Волк - травоядное животное».
Составьте из них все возможные составные высказывания и определите их истинность.
II. Запишите следующие высказывания в виде логических выражений.
1. Число 17 нечетное и двузначное.
2. Неверно, что корова - хищное животное.
3. На уроке физики ученики выполняли лабораторную работу и сообщали результаты ис следований учителю.
4. Если число делится на 2, то оно - четное.
5.Переходи улицу только на зеленый свет.
6. На уроке информатики необходимо соблюдать особые правила поведения.
7. При замерзании воды выделяется тепло.
8. Если Маша - сестра Саши, то Саша - брат Маши.
9. Если компьютер включен, то можно на нем работать.
10. Водительские права можно получить тогда и только тогда, когда тебе исполнится 18 лет.
11. Компьютер выполняет вычисления, если он включен.
12. Ты можешь купить в магазине продукты, если у тебя есть деньги.
13. Тише едешь - дальше будешь.
III. Даны высказывания: А — «р делится на 5» и В — «р — нечетное число». Найти множество значений р, при которых результат
а) логического сложения и
б) логического умножения будет:
1)истинным;
2)ложным.
IV. Составьте и запишите истинные сложные высказывания из простых с использованием логических операций.
1. Неверно, что 10>Y≥5 и Z<0
2. Z является min(Z,Y).
3. А является max(A,B,C).
4. Любое из чисел X,Y,Z положительно.
5. Любое из чисел X,Y,Z отрицательно.
6. Хотя бы одно из чисел K,L,M не отрицательно.
7. Хотя бы одно из чисел X,Y,Z не меньше 12.
8. Все числа X,Y,Z равны 12.
9. Если X делится на 9, то X делиться и на 3.
10. Если X делится на 2, то оно четное.
V. Найдите значения логических выражений:
1. F = (0 v 0) v (l v l)
2. F = (l v l) v (l v 0)
3. F = (0 & 0) & (1 & 1)
4. F = 1 & (1 v 1) v (0 & 1)
5. F = (1 v 1) & (1 v1) & (1 v 0)
Таблицы истинности
Решение логических выражений принято записывать в виде таблиц истинности - таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.
Для составления таблицы необходимо:
1. Выяснить количество строк в таблице (вычисляется как 2П, где п - количество переменных).
2. Выяснить количество столбцов = количество переменных + количество логических операций.
3. Установить последовательность выполнения логических операций.
4. Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных.
5. Заполнить таблицу истинности по столбцам.
Пример 1
Построим таблицу истинности для выражения F = (A v B) & (A vB)..
Составьте таблицы истинности для следующих логических выражений:
1. F = (X & Y) v Z.
2. F= A ↔ B v A&C
3. F=A& (B↔C)
4. F = (X v Y) & (Y ↔ X).
5. F= A ↔ B v C
6. F=(AvB) → (AvC)
7. F= А ↔ (В v C)
8. F = A & B → C & D.
9. F= A ↔ B &C
10. F = (X v Y) & (Y v X).
11. F= A ↔ B &C
12. F = (A v B) & (B v A→ B).
13. F= A ↔ B v A &C
14. F= A → B v A&C
15. F = X & Y v X.
16. F = ((X v Y) & (Z → X)) & (Z v Y).
17. F= A → B v A &C
18. F= А →(В v C)
19. F= A ↔ B v C
20. F = ((X v Y) & (Z v X)) & (Z → Y).
21. F= (B & (A→C))
22. F= A → B v A&C
23. F= А ↔ (В v C)
24. F = ((X v Y) & (Z v X)) & (Z v Y).
25. F= A → B v A&C
26. F = A & B & C & D.
27. F= А ↔(В v C)
28. F=A& (B→C).
29. F= A ↔ B v A&C
30. F= А ↔ (В v C)
31. F= A → B v A &C
32. F = (A v B) & (B v A v B).
33. F= A v B v A &C
34. F= A & B v A&C
35. F = X & Y ↔ X.
36. F = ((X v Y) & (Z → X)) & (Z ↔ Y).
37. F= A → B &C
38. F = (X → Y) & (Y v X).
39. F= A → B &C
40. F = (A ↔ B) & (B v A &B).
41. F = (X & Y) v Z.
42. F= A & B v A&C
43. F=A& (BvC)
44. F = (X → Y) & (Y ↔ X).
45. F= A → B v A&C
46. F = A & B ↔ C & D.
47. F= А ↔(В v C)
48. F=(X & Y) v (Y & X).
49. Заполните пустые ячейки таблицы истинности:
А
В
С
C v A
(С v A) =>B
50. Заполните пустые ячейки таблицы истинности:
А
В
С
А
B v C
А & (В v С)
Логические схемы
Над возможностями применения логики в технике ученые и инженеры задумывались уже давно. Например, голландский физик Пауль Эренфест (1880 — 1933), кстати несколько лет работавший в России, писал еще в 1910 году: «...Пусть имеется проект схемы проводов автоматической телефонной станции. Надо определить: 1) будет ли она правильно функционировать при любой комбинации, могущей встретиться в ходе деятельности станции; 2) не содержит ли она излишних усложнений. Каждая такая комбинация является посылкой, каждый маленький коммутатор есть логическое «или-или», воплощенное в эбоните и латуни; все вместе - система чисто качественных... «посылок», ничего не оставляющая желать в отношении сложности и запутанности... правда ли, что, несмотря на существование алгебры логики своего рода «алгебра распределительных схем» должна считаться утопией?». Созданная позднее М.А.Гавриловым (1903 - 1979) теория релейно-контактных схем показала, что это вовсе не утопия.
Посмотрим на микросхему. На первый взгляд ничего того, что нас удивило бы, мы не видим. Но если рассматривать ее при сильном увеличении она поразит нас своей стройной архитектурой. Чтобы понять, как она работает, вспомним, что компьютер работает на электричестве, то есть любая информация представлена в компьютере в виде электрических импульсов. Поговорим о них.
С точки зрения логики электрический ток либо течет, либо не течет; электрический импульс есть или его нет; электрическое напряжение есть или его нет... В связи с этим поговорим о различных вариантах управления включением и выключением обыкновенной лампочки (лампочка также работает на электричестве). Для этого рассмотрим электрические контактные схемы, реализующие логические операции.
Как известно, любая информация при обработке на компьютере представляется в двоичной форме, то есть кодируется некоторой последовательностью 0 и 1. Поэтому упрощенно можно представить работу компьютера как некоторого устройства, производящего обработку двоичных сигналов, соответствующих 0 и 1. Такую обработку в любом компьютере выполняют так называемые логические элементы, из которых составляются логические схемы, выполняющие различные логические операции. Реализация любых логических операций над двоичными сигналами основана на использовании логических элементов трех типов: И, ИЛИ, НЕ.
Логический элемент — это электронное устройство, реализующее одну из логических функций. Рассмотрим указанные три простейших логических элемента. В зависимости от типа элемента на его вход подается один или несколько входных сигналов, а на выходе — снимается один выходной сигнал. Названия и условные обозначения этих логических элементов являются стандартными и используются при составлении и описании логических схем компьютеров.
А —
Логический элемент И (коньюнктор)
&
В —
А —
Логический элемент ИЛИ (дизьюнктор)
1
В —
А —
Логический элемент НЕ (инвертор)
Почему необходимо уметь строить логические схемы?
Дело в том, что из вентилей составляют более сложные схемы, которые позволяют выполнять арифметические операции и хранить информацию. Причем схему, выполняющую определенные функции, можно построить из различных по сочетанию и количеству вентилей. Поэтому значение формального представления логической схемы чрезвычайно велико. Оно необходимо для того, чтобы разработчик имел возможность выбрать наиболее подходящий ему вариант построения схемы из вентилей. Процесс разработки общей логической схемы устройства (в том числе и компьютера в целом) таким образом становится иерархическим, причем на каждом следующем уровне в качестве «кирпичиков» используются логические схемы, созданные на предыдущем этапе.
Алгебра логики дала в руки конструкторам мощное средство разработки, анализа и совершенствования логических схем. В самом деле, гораздо проще, быстрее и дешевле изучать свойства и доказывать правильность работы схемы с помощью выражающей ее формулы, чем создавать реальное техническое устройство. Именно в этом состоит смысл любого математического моделирования.
Логические схемы необходимо строить из минимально возможного количества элементов, что в свою очередь, обеспечивает большую скорость работы и увеличивает надежность устройства.