Математические и логические основы информатики — это раздел математики, называемый «алгебра логики» и изучающий высказывания, которые рассматриваются с точки зрения их истинности или ложности, а также логические операции над ними.
Алгебра логики
Алгеброй логики является раздел математики, который изучает высказывания с точки зрения их логических значений, то есть, истинны они или ложны, и логические операции над ними.
Логическим высказыванием считаются повествовательное предложение, про которое можно точно утверждать, что оно является истинным или ложным.
Истинное высказывание принято обозначать символом единица (1), а ложное высказывание принято обозначать символом ноль (0).
Примеры логических высказываний приведены в таблице ниже:
Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ
Математические и логические основы информатики
Используемые в повседневной речи слова и словосочетания «не», «и», «или», «если…,то», «тогда и только тогда» и другие дают возможность из стандартных высказываний формировать более сложные формы высказываний. Такого типа слова и их сочетания именуются логическими связками. Высказывания, которые были образованы при помощи логической связки, именуются составными высказываниями. Высказывания, которые не являются составными, считаются элементарными. Чтобы обозначить логическое высказывание, ему следует присвоить имя. К примеру, если А является высказыванием с текстом «В среду прошёл дождь», а высказывание В содержит утверждение «В субботу была солнечная погода», то в итоге можно записать это так: А и В.
В данном случае А, В являются логическими высказываниями, то есть могут иметь значения истинно или ложно. «И» является логической связкой. Все логические связки могут считаться операциями, выполняемыми с логическим высказыванием, и обладают своим названием и обозначением. В таблице ниже приведены возможные логические связки (операции):
Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ
Импликация может быть выражена при помощи дизъюнкции и отрицания:
A → B = ¬А v B
Логическое тождество может быть выражено при помощи отрицания, дизъюнкции и конъюнкции:
A B = (¬А v B) ^ (¬B v А)
Определение значения логического выражения выполняется слева направо согласно таблице истинности и приоритету осуществления логической операции. Ниже приведена таблица истинности:
Рисунок 3. Таблица истинности. Автор24 — интернет-биржа студенческих работ
Приоритет осуществления логической операции определяется согласно следующей таблице:
Рисунок 4. Таблица. Автор24 — интернет-биржа студенческих работ
Очерёдность осуществления логических операций может быть изменена при помощи круглых скобок.
Основные правила алгебры логики
Базовые правила алгебры логики, которые позволяют выполнять тождественные преобразования логических выражений, приведены в таблице ниже:
Рисунок 5. Таблица. Автор24 — интернет-биржа студенческих работ
Математический аппарат алгебры логики является очень удобным средством для описания работы аппаратного обеспечения компьютерного оборудования, так как там применяется двоичная система счисления, где есть только две цифры нуль и единица аналогично логическим постулатам. На этой основе можно сделать следующие выводы:
- Одни и те же компьютерные модули можно использовать для сохранения и переработки как числовых данных, которые представлены в двоичном формате, так и для переменных алгебры логики.
- При проектировании аппаратного обеспечения компьютеров методы алгебры логики дают возможность существенно упростить логические процедуры, которые описывают работу компьютерных схем. Это позволяет в разы сократить количество элементарных элементов логики, составляющих модули компьютера.
Формирование таблицы истинности
Как отмечалось выше, таблица истинности логического выражения отражает соответствие среди допустимых наборов значений переменных и значениями выражения (формулы). Если формула содержит только две переменные, то возможных наборов величин переменных будет четыре.
Когда в логическую формулу входят три переменные, то количество допустимых наборов значений переменных будет уже равно восьми.
Число наборов для выражений, имеющих четыре переменные, будет равняться шестнадцати и так далее. Для определения значений формулы, очень удобно использовать форму записи в виде таблицы, которая содержит помимо значений переменных и значений формулы ещё и значения промежуточных формул.
Рассмотрим пример решения конкретной задачи. Какое из приведённых ниже имён отвечает истинности следующего высказывания: «Первая из букв в имени является гласной, буква, стоящая в имени четвёртой, является согласной». Список имён следующий:
- Елена.
- Вадим.
- Антон.
- Фёдор.
Обозначим высказывания следующим образом:
A = «Гласная является первой буквой имени».
B = «В имени буква на четвёртом месте является согласной».
В таком случае исходное высказывание можно выразить так:
¬ (A → B).
Выполнив необходимые преобразования, можно определить, что условию задачи удовлетворяет только имя Антон.
