Лекция 11. Понятия алгебры логики. Логические операции.
План:
1. Основы логики.
2. Таблицы истинности.
3. Логические схемы.
Основы логики
Формы мышления.
В основе современной логики лежат учения, созданные еще древнегреческими мыслителями, хотя первые учения о формах и способах мышления возникли в Древнем Китае и Индии. Основоположником формальной логики является Аристотель, который впервые отделил логические формы мышления от его содержания.
Логика — это наука о формах и способах мышления. Это учение о способах рассуждений и доказательств.
Законы мира, сущность предметов, общее в них мы познаем посредством абстрактного мышления. Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны.
Мышление всегда осуществляется через понятия, высказывания и умозаключения.
Понятие — это форма мышления, которая выделяет существенные признаки предмета или класса предметов, позволяющие отличать их от других. Например: Прямоугольник, проливной дождь, компьютер.
Высказывание — это формулировка своего понимания окружающего мира, высказывание является повествовательным предложением, в котором что-либо утверждается или отрицается. Высказывания могут быть истинны или ложны. Истинным будет высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Ложным высказывание будет в том случае, когда оно противоречит реальной действительности. Например: Истинное высказывание: «Буква «а» — гласная». Ложное высказывание: «Компьютер был изобретен в середине XIX века».
Умозаключение — это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение (знание или вывод). Например: Дано высказывание: «Все углы равнобедренного треугольника равны». Получить высказывание «Этот треугольник равносторонний» путем умозаключений. Пусть основанием треугольника является сторона с. Тогда а = b. Так как в треугольнике все углы равны, следовательно, основанием может быть любая другая сторона, например а. Тогда b = с. Следовательно а = b = с. Треугольник равносторонний.
Логические выражения и операции
Алгебра — это наука об общих операциях, аналогичных сложению и умножению, которые выполняются не только над числами, но и над другими математическими объектами, в том числе и над высказываниями. Такая алгебра называется алгеброй логики. Алгебра логики отвлекается от смысловой содержательности высказываний и принимает во внимание только истинность или ложность высказывания.
Логическая переменная — это простое высказывание, содержащее только одну мысль. Ее символическое обозначение — латинская буква (например А, В, Х, Y и т.д.). Значением логической переменной могут быть только константы ИСТИНА и ЛОЖЬ (1 и 0).
Логическая функция - составное высказывание, которое содержит несколько простых мыслей, соединенных между собой с помощью логических операций. Ее символическое обозначение — F(A,B,...).
Логические операции — логическое действие.
Рассмотрим три базовые логические операции — конъюнкцию, дизъюнкцию и инверсия и дополнительные — импликацию и эквивалентность (табл. 1).
Таблица 1 – Логические операции
| Название | Операция | Обозначение |
| Конъюнкция – логическое умножение | И (AND) | A&B, AÙB |
| Дизъюнкция – логическое сложение | ИЛИ (OR) | AÚB |
| Инверсия – логическое отрицание | НЕ (NOT) | Ā, Ø |
| Импликация – логическое следование | Если А, то В | А→В А – условие, В - следствие |
| Эквивалентность – логическое равенство | А тогда и только тогда, когда В | А≡В, А↔В |
Аксиомы (постулаты алгебры логики
• Конъюнкция двух переменных равна 0, если хотя бы одна переменная равна 0.
| А | В | A&B |
• Дизъюнкция двух переменных равна 1, если хотя бы одна переменная равна 1.
| А | В | AÚB |
• Инверсия одного значения переменной совпадает с ее другим значением.
| А | Ā |
• Импликация: результат будет ложным тогда и только тогда, когда из истинного основания (А) следует ложное следствие (В).
| А | В | А→В |
• Эквивалентность: результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны
| А | В | А≡В |
Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение, значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА.
При составлении логического выражения необходимо учитывать порядок выполнения логических операций, а именно:
1. действия в скобках;
2. инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.
Например: Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку».
1. Проанализируем составное высказывание.
Оно состоит из следующих простых высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдет на рыбалку». Обозначим их через логические переменные:
А = Петя поедет в деревню;
В = Будет хорошая погода;
С = Он пойдет на рыбалку.
2. Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки:
F = A&(B→С).
Таблицы истинности
Решение логических выражений принято записывать в виде таблиц истинности — таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.
Алгоритм составления таблицы истинности:
1. Определить количество строк в таблице по формуле m = 2n + 1 (заголовки столбцов), где n – количество переменных.
2. Определить количество столбцов, которое равно количеству переменных + количество логических операций.
3. Установить последовательность выполнения логических операций.
4. Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных.
5. Заполнить таблицу истинности по столбцам.
Построим таблицу истинности для выражения F = (A v B)&(Ā v 
).
Количество строк = 22 (2 переменных) + 1 (заголовки столбцов) = 5.
Количество столбцов = 2 логические переменные (А, В) + 5 логических операций = 7.
Расставим порядок выполнения операций: 
Построим таблицу истинности
| А | В | AvB | Ā |
| Āv
| (AvB)&(Āv )
|
Задание для самостоятельной работы студентов на уроке.
Построить таблицу истинности для выражения F = Х v Y& 
Количество строк = 23 (3 переменных) + 1 (заголовки столбцов) = 9.
Количество столбцов = 3 логические переменные (X, Y, Z) + 3 логических операций = 6.
Расставим порядок выполнения операций: 
Построим таблицу истинности
| X | Y | Z |
| Y&
| Х v Y&
|
Логические схемы
Над возможностями применения логики в технике ученые и инженеры задумывались уже давно. Например, голландский физик Пауль Эренфест (1880 - 1933), кстати несколько лет работавший в России, писал еще в 1910 году: «...Пусть имеется проект схемы проводов автоматической телефонной станции. Надо определить: 1) будет ли она правильно функционировать при любой комбинации, могущей встретиться в ходе деятельности станции; 2) не содержит ли она излишних усложнений. Каждая такая комбинация является посылкой, каждый маленький коммутатор есть логическое «или-или», воплощенное в эбоните и латуни; все вместе — система чисто качественных... «посылок», ничего не оставляющая желать в отношении сложности и запутанности... правда ли, что, несмотря на существование алгебры логики, своего рода «алгебра распределительных схем» должна считаться утопией?». Созданная позднее М.А. Гавриловым (1903 - 1979) теория релейно-контактных схем показала, что это вовсе не утопия.
С точки зрения логики электрический ток либо течет, либо не течет; электрический импульс есть или его нет; электрическое напряжение есть или его нет... В связи с этим поговорим о различных вариантах управления включением и выключением обыкновенной лампочки (лампочка также работает на электричестве). Для этого рассмотрим электрические контактные схемы, реализующие логические операции (рисунок 1).
| 
| 
|
Рисунок 1 - Электрические контактные схемы
На рисунках контакты обозначены латинскими буквами А и В. Введем обозначения: 1 - контакт замкнут, 0 - контакт разомкнут. Цепь на схеме 1 с последовательным соединением контактов соответствует логической операции «И». Цепь на схеме 2 с параллельным соединением контактов соответствует логической операции «ИЛИ». Цепь на схеме 3 (электромагнитное реле) соответствует логической операции «НЕ».
Недостатками контактных схем являлись их низкая надежность и быстродействие, большие размеры и потребление энергии. Поэтому попытка использовать такие схемы в ЭВМ не оправдала себя. Появление вакуумных и полупроводниковых приборов позволило создавать логические элементы с быстродействием от 1 миллиона переключений в секунду. Именно такие электронные схемы нашли свое применение в качестве элементной базы ЭВМ. Вся теория, изложенная для контактных схем, была перенесена на электронные схемы. Элементы, реализующие базовые логические операции, назвали базовыми логическими элементами или вентилями и характеризуются они не состоянием контактов, а наличием сигналов на входе и выходе элемента. Их названия и условные обозначения являются стандартными и используются при составлении и описании логических схем компьютера.
Почему необходимо уметь строить логические схемы?
Дело в том, что из вентилей составляют более сложные схемы, которые позволяют выполнять арифметические операции и хранить информацию. Причем схему, выполняющую определенные функции, можно построить, из различных по сочетанию и количеству вентилей. Поэтому значение формального представления логической схемы чрезвычайно велико. Оно необходимо для того, чтобы разработчик имел возможность выбрать наиболее подходящий ему вариант построения схемы из вентилей. Процесс разработки общей логической схемы устройства (в том числе и компьютера в целом) таким образом становится иерархическим, причем на каждом следующем уровне в качестве «кирпичиков» используются логические схемы, созданные на предыдущем этапе.
Алгебра логики дала в руки конструкторам мощное средство разработки, анализа и совершенствования логических схем. В самом деле, гораздо проще, быстрее и дешевле изучать свойства и доказывать правильность работы схемы с помощью выражающей ее формулы, чем создавать реальное техническое устройство. Именно в этом состоит смысл любого математического моделирования.
Логические схемы необходимо строить из минимально возможного количества элементов, что в свою очередь, обеспечивает большую скорость работы и увеличивает надежность устройства.
Алгоритм построения логических схем:
1. Определить число логических переменных.
2. Определить количество базовых логических операций и их порядок.
3. Изобразить для каждой логической операции соответствующий ей вентиль.
4. Соединить вентили в порядке выполнения логических операций.
Рассмотрим пример. Постройте логическую схему для следующего логического выражения: F = Х v Y&X. X = 1, Y = 0
Количество логических переменных – 2 (X и Y).
Количество логических операций – 2 (конъюнкция и дизъюнкция).
Расставим порядок выполнения операций: 
Построим схему:
Задание для самостоятельной работы студентов на уроке.
Постройте логическую схему для следующего логического выражения: 
. X = 1, Y = 0
Количество логических переменных – 2 (X и Y).
Количество логических операций – 3 (конъюнкция, дизъюнкция и инверсия).
Расставим порядок выполнения операций: 
Построим схему:
Д/з.