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

Логика – одна из древнейших наук. Ее основателем считается древнегреческий мыслитель Аристотель (384 – 322гг. до н. э.), который первым систематизировал формы и правила мышления, обстоятельно исследовал категории понятие и суждение, подробно разработал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления. Он подвергал анализу человеческое мышление, его формы – понятие, суждение, умозаключение, и рассмотрел со стороны строения, структуры. Логика Аристотеля носит название формальной логики. Это название происходит из принципа: правильность рассуждения определяется только его логической формой или структурой и не зависит от конкретного содержания входящих в него высказываний.

Продолжение развития логики связано математической логикой. Основоположником математической логики считается великий математик и философ Готфрид Вильгельм Лейбниц (1646-1716). Он попытался построить первые логические исчисления: арифметические и буквенно-алгебраические. Но Лейбниц высказал только идею, а развил ее окончательно англичанин Джордж Буль (1815-1864). Он вывел для логических построений особую алгебру (алгебру логики). В отличии от обычной логики, в ней символами обозначаются не числа, а высказывания. Алгебра логики (булева алгебра) изучает высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.

Создание алгебры логики представляло собой попытку решать традиционные логические задачи алгебраическими методами. С появлением теории множеств (70-е гг. 19 в.), поглотившей часть первоначального предмета алгебры логики, и дальнейшим развитием математической логики (последняя четверть 19 в. – 1-я половина 20 в.) предмет алгебр логики значительно изменился. Основным предметом алгебры логики стали высказывания. Под высказыванием понимается имеющее смысл языковое выражение, относительно которого можно утверждать, что оно либо истинно, либо ложно.

Пример 1.

1. «5 есть простое число». Это высказыванием является истинным.
2. «4 + х = 6». Это уравнение не является высказыванием. Однако, придавая переменной х определенное числовое значение, будет высказывание.
3. «роза – цветок». Это высказывание является истинным.
4. «все углы – прямые». Это высказывание является ложным.
5. «3 + 5 = 9». Это высказывание является ложным.

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

Пример 2.

1. «Париж – столица Франции». Это высказывание простое.
2. «Неверно, что Париж – столица Англии». Это высказывание сложное.

Частные высказывания выражают конкретные факты. Общие высказывания характеризуют свойства групп объектов или явлений.

Пример 3.

1. «Луна - спутник Земли». Это частное высказывание.
2. «Всякий человек – млекопитающее». Это общее высказывание.

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

Пример 4.

3. «Если треугольник равносторонний, то у него все углы равны между собой».
4. «Если король под шахом и ему некуда ходить, то – мат».

Умозаключение – прием мышления, посредством которого из исходного знания получается новое знание; из одного или нескольких истинных высказываний, называемых предпосылками, по определенным правилам вывода можно получить заключение.

Пример 5. «Все металлы – простые вещества». «Литий – металл». Следовательно «Литий – простое вещество».

Любое правило вывода умозаключений состоит из двух высказываний (простых или сложных). Одно из них называется предпосылкой или условием, а второе – следствием, заключением или выводом.

Пример 6. «Если треугольник равносторонний, то у него все углы 60 градусов». Высказывание «У него все углы равны 60 градусов» – это заключение, а высказывание «Треугольник равносторонний» – это предпосылка.

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

Умозаключение по аналогии – это правило полученное из рассмотрения какого-либо объекта, переносимое на менее изученный, сходный по существенным свойствам и качествам объекта.

Пример 7. Из высказывания «Солнечная система – это планеты, вращающиеся по орбитам, в центре которых находится Солнце» можно получить умозаключение по аналогии: «Атом – это электроны, вращающиеся по орбитам, в центре которых находится ядро».

Индукция – это правило вывода умозаключений при переходе от частных высказываний к общим.

Пример 8. Высказывания: «кошки имеют хвост», «собаки имеют хвост», «обезьяны имеют хвост», «кошки, собаки, обезьяна – млекопитающие». Следовательно, «все млекопитающие имеют хвост». Это умозаключение ложно.

Индуктивный вывод умозаключений позволяет формулировать различные гипотезы, догадки, но иногда он может приводить и к ошибочным умозаключениям.

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

Пример 9. «Умные люди не делают ошибки». «Я – умный человек». Следовательно: «Я не делаю ошибок».

В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывания можно представить некоторой переменной величиной, значением которой может быть только «0» или «1». Если высказывание истинно, то его значение равно «1», если ложно, то равно «0».

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

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

Истинностные значения новых высказываний определяются при этом только истинностными значениями входящих в них высказываний. Построение из данных высказываний (или из данного высказывания) нового высказывания называется логической операцией. Знаки логических операций называются логическими связками. Логические связки могут быть: одноместными (унарными), двухместными (бинарные), трехместными (тернарными) и т.д.

Пример 10.

1. Из высказываний «х > 2», «х < 3» при помощи связки «и» можно получить высказывание «x > 2 и х < 3»;
2. из высказываний «у > 10», «х < 3» при помощи связки «или» можно получить высказывание «у > 10 или х < 3»;
3. из высказываний «х > 2», «у < 3» при помощи связки «если..., то...» можно получить высказывание «если x > 2, то у < 3».

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

В алгебре логики логические операции чаще всего описываются при помощи таблиц истинности. В таблице 1 представлена таблица истинности для операции «отрицание» («инверсия»).

Таблица истинности для операции «отрицания»

Таблица 1

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

Основные бинарные логические операции и связки

Таблица 2

Примечание: А1 и А2 являются высказываниями.

Связки и частица «не» рассматриваются в алгебре логики как операции над величинами, принимающими значения 0 (ложь/false) и 1(истина/true), и результатом применения этих операций также являются числа 0 или 1. В таблице 3 представлены все наборы значений переменных А1 и А2 и значения функций на этих наборах.

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

Таблица 3

1. Инверсия

Отрицание высказывания А (т.е. не А) обозначается , или , или  и часто читается: «отрицание А», «не А» или «А с чертой».

Пример 11. Высказывание А=<Киев-столица Франции>, тогда сложное высказывание НЕ А означает: не верно, что А, т.е. не верно, что <Киев-столица Франции>.

2. Конъюнкция

Результатом операции конъюнкции для высказывания А  В будет истинна только тогда, когда истинны одновременно оба высказывания.

Пример 12. Высказывания А= «Москва – столица России» и В= «Рим – столица Италии». Сложное высказывание А  В (А & В) истинно, так как истинны оба высказывания.

3. Дизъюнкция

Результатом операции дизъюнкции для высказывания А  В будет истинна тогда, когда истинно хотя бы одно высказывание, входящее в него.

Пример 13. Высказывания А = «2 + 3 = 5» и В = «3 + 3 = 5». Сложное высказывание: А  В (А + В) истинно, так как истинно высказывание А.

4. Эквиваленция (равнозначность)

Результатом операции эквиваленции для высказывания А ~ В будет истинна тогда, когда истинны или ложны одновременно оба высказывания. Отличие эквиваленции от конъюнкции состоит в том, что вне зависимости от смысла, равнозначными являются как истинные, так и ложные высказывания.

Пример 14. Высказывания А = «2 + 2 = 7» и В = «1 – 8 = 5». Сложное высказывание А  В (А ~ В) истинно, так как оба высказывания ложны.

5. Импликация

Результатом операции импликации для высказывания А  В будет ложь только тогда, когда первое высказывание (А) истинно, а второе (В) ложно. При этом А – предпосылка, а В – следствие.

Пример 15. Высказывания А = «2 + 2 = 4» и В = «1 – 8 = 5». Сложное высказывание А  В (А  В) ложно, так как высказывание А истинно, а В – ложно.

6. Антиконъюнкция

Результатом операции антиконъюнкции для высказывания А  В будет ложь только тогда, когда оба высказывания истинны.

Пример 16. Высказывания А= «Москва – столица России» и В= «Рим – столица Италии». Сложное высказывание А  В ложно, так как истинны оба высказывания.

7. Антидизъюнкция

Результатом операции антидизъюнкции для высказывания А  В будет истинна только тогда, когда оба высказывания ложны.

Пример 17. Высказывания А= «Рим – столица России» и В= «Москва – столица Италии». Сложное высказывание А  В истинно, так как ложны оба высказывания.

Основными символами алгебры логики являются:

1. пропозициональные переменные;
2. унарная связка  и бинарные связки , , , ~;
3. скобки ( ).

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

Далее индуктивно вводится понятие формулы, являющееся формализацией понятия «сложного» высказывания. К формуле алгебры логики относят:

1. выражение, состоящее только из пропозициональной переменной (А1, В, с);
2. выражения, состоящие из пропозициональных формул соединенных связками ( С, (А1  А2), (Н1  Н2)).

Правила сокращения записей в пропозициональных формулах:

1. вместо  А пишут ;
2. вместо А1  А2 пишут А1А2;
3. приоритет применения связок возрастает в следующем порядке

                                

1. внешние скобки опускаются.

Пример 18.

2. ;
3. .

Для преобразований формул в равные формулы важную роль в алгебре логики играют следующие равенства:

1.  (закон коммутативности).
2.  (закон ассоциативности).
3.          (закон поглощения).
4.          (закон дистрибутивности).
5.          (закон противоречия).
6.  (закон исключенного третьего);
7.  (закон снятия двойного отрицания);
8.  (закон склеивания);
9.  (закон де Моргана);
10.  (закон свертки).

Эти равенства позволяют существенно упростить запись формул освобождением от лишних скобок.

2. 2.2. Нормальные формы

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

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

1. Конъюнктивная нормальная форма

Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой, то есть КНФ.

Совершенной КНФ (СКНФ) называется КНФ, в которой нет равных элементарных дизъюнкций и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием).

2. Дизъюнктивная нормальная форма

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой, то есть ДНФ.

Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием).

1. 3. Применение средств алгебры логики для описания функционирования устройств компьютера

Для описания того, как функционируют аппаратные средства компьютера очень удобен математический аппарат алгебры логики, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры «1» и «0».

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

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

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

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

Логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-НЕ». С помощью этих схем можно реализовать любую логическую формулу, описывающую работу устройств компьютера.

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

Схема «И» реализует конъюнкцию двух или более логических значений. Условное обозначение структурной схемы «И» представлена на рис. 5.

Рис. 5. схема «И»

На выходе схемы «И» значение «1» будет тогда и только тогда, когда на всех входах будут «1». Когда хотя бы на одном входе будет «0», на выходе также будет «0».

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

Схема «ИЛИ» реализует дизъюнкцию двух или более логических значений. Условное обозначение схемы «ИЛИ» представлено на рис. 6.

Рис. 6. Схема «ИЛИ»

Значение дизъюнкции равно «1», если сумма значений операндов больше или равна «1». Когда хотя бы на одном входе схемы «ИЛИ» будет «1», на её выходе также будет «1».

Операция дизъюнкции на функциональных схемах обозначается знаком «1».

Схема «НЕ» (инвертор) реализует операцию отрицания. Условное обозначение схемы НЕ представлено на рис. 7.

Рис. 7. Схема «НЕ»

Если на входе схемы – «0», то на выходе будет «1». Когда на входе – «1», на выходе будет «0».

Схема «И-НЕ» состоит из элемента «И» и инвертора и осуществляет отрицание результата схемы «И». Условное обозначение схемы «И-НЕ» представлено на рисунке 8. Таблица истинности схемы «И-НЕ» – это таблица 5.

Рис. 8. Схема «И-НЕ»

Таблица истинности схемы «И-НЕ»

Таблица 5

Схема «ИЛИ-НЕ» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата схемы «ИЛИ». Условное обозначение схемы «ИЛИ-НЕ» представлено на рис. 9, а таблица истинности схемы ИЛИ-НЕ – это табл. 6.

Рис. 9. Схема «ИЛИ-НЕ»

Таблица истинности схемы «ИЛИ-НЕ»

Таблица 6

3. Логические схемы

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

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную Х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то Х равен нулю.

Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).

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

При рассмотрении переключательных схем возникают две основные задачи: синтез и анализ схемы.

СИНТЕЗ СХЕМЫ по заданным условиям ее работы сводится к следующим трём этапам:

1. составлению функции проводимости по таблице истинности, отражающей эти условия;
2. упрощению этой функции;
3. построению соответствующей схемы.

АНАЛИЗ СХЕМЫ сводится к:

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

4. Построение логических схем

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

F =BA + BA + CB.

Первый этап: выполняется логическое сложение, логическую операцию ИЛИ, считая входными переменными функцииB A, BA и CB:

Второй этап: к входам элемента ИЛИ подключаются логические элементы И, входными переменными которых являются уже A, B, C и их инверсии:

Третий этап: для получения инверсий A иB на соответствующих входах ставят инверторы:

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

2. 5. Практическая работа 1. Системы счисления

Цель работы: Рассмотреть систему представления чисел в памяти ЭВМ.

Задания к практической работе №1:

1. В приложении №1 выбрать свой вариант индивидуального задания.
2. Выполнить его, пользуясь данными методическими указаниями (глава 1. Системы счисления).
3. Оформить работу по образцу приложения № 4.
4. Результат работы предъявить преподавателю.
5. Ответить на вопросы для самоконтроля к практической работе №1.
6. Защитить выполненную работу у преподавателя.

1. Вопросы для самоконтроля

1. Что такое система счисления?
2. Чем характеризуется система счисления?
3. Виды систем счисления.
4. Десятичная система счисления. Основание. Представление чисел.
5. Двоичная система счисления. Основание.
6. Восьмеричная и шестнадцатеричная системы счисления.
7. Перевод чисел из любой системы счисления в десятичную.
8. Перевод чисел из десятичной в любую другую систему счисления.
9. Почему для машинной арифметики используется двоичная система счисления?
10. Для чего используется шестнадцатеричная система счисления?

3. 6. Практическая работа 2. Алгебра логики

Цель работы: Ознакомиться с основными арифметическими операциями, базовыми логическими элементами (И, И-НЕ, ИЛИ, ИЛИ-НЕ, исключающее ИЛИ) и изучить методы построения на их основе простейших логических схем.

Задания к практической работе № 2:

1. В приложении №2 выбрать свой вариант индивидуального задания.
2. Выполнить его, пользуясь данными методическими указаниями (глава 2. Алгебра логики.).
3. Оформить работу по образцу приложения № 4.
4. Результат работы предъявить преподавателю.
5. Ответить на вопросы для самоконтроля к практической работе №2.
6. Защитить выполненную работу у преподавателя.

1. Решение логических задач средствами алгебры логики

Задача: Составить таблицу истинности для данной формулы и написать для нее СДНФ и СКНФ: (x ~ z) | ((x y) ~ (y z)).

Решение: В таблицу истинности данной формулы полезно включить таблицы истинности промежуточных функций: