Алгебра - наука об общих операциях,
аналогичных сложению и умножению,
которые могут выполняться над разнообразными математическими объектами –
числами, многочленами, векторами и др. Логика – это наука о формах и способах мышления. Алгебра логики
- раздел математической логики, в
котором изучаются логические операции над высказываниями.
Высказывание - это основной элемент логики, определяемый как повествовательное
предложение, относительно которого можно однозначно сказать, истинное или
ложное утверждение оно содержит. Вопросительное, побудительное и
восклицательное предложения не являются высказываниями, так как в них
ничего не утверждается и не отрицается.
Высказывания бывают простыми и сложными.
Высказывание называется простым (элементарным), если
никакая его часть сама не является высказыванием.
Примеры простых высказываний: Листва на деревьях опадает осенью. Земля
прямоугольная. Первое высказывание содержит истинную информацию, а второе -
ложную.
Высказывания могут быть и такими: 2>1, Н2О+SO3=H2SO4. Здесь
используются языки математических символов и химических формул.
Из простых высказываний можно получить сложные, объединив их с
помощью логических связок. Логические связки (операции) - слова, которые
подразумевают определённые логические связи между высказываниями. В
математической логике это “и”, “или”, “не”, “если ... то”, “либо ... либо” и
другие. Таким образом, сложные
(составные) высказывания строятся из простых с помощью логических операций.
Кроме того, высказывания бывают общими, частными и единичными.
Общее высказывание начинается со слов: всё, все, всякий, каждый, ни один.
Частное высказывание начинается со слов: некоторые, большинство и т.п. Во всех
других случаях высказывание является единичным.
Алгебра логики подразумевает, что каждая переменная может
принимать только два значения: истинно или ложно. Для обозначения
переменных принимают символы 0 и 1, которые по написанию
совпадают с обычными арифметическими единицей и нулём. Совпадение это только
внешнее, так как смысл они имеют совсем иной. Логическая 1 означает, что
какое-то событие истинно, а логический 0 означает, что
высказывание не соответствует истине, то есть ложно.
Высказывание заменяется на логическое выражение, которое
строится из логических переменных (А, В, Х, …) и логических операций
(связок).
В алгебре логики знаки операций
обозначают лишь три логические связки ИЛИ, И, НЕ.
Составные высказывания в алгебре логики записываются с
помощью логических выражений. Для любого логического выражения достаточно
просто построить таблицу истинности.
Таблицу, показывающую, какие значения принимает составное высказывание при всех
сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей
истинности логического высказывания.
В левой части этой таблицы перечисляются все возможные значения
аргументов функции (то есть входные величины), а в правой указывается
соответствующее им значение логической функции.
1. Для логической операции ИЛИ таблица
истинности имеет вид:
Операцию ИЛИ называют также логическим сложением, и
потому её можно обозначать знаком «+». Другое обозначение: АvВ
Рассмотрим сложное единичное высказывание: «Летом я поеду в деревню или
в туристическую поездку». Обозначим через А простое высказывание «Летом я поеду
в деревню», а через В - простое высказывание «Летом я поеду в туристическую поездку».
Тогда логическое выражение сложного высказывания имеет вид А+В, и оно будет
ложным только, если ни одно из простых высказываний не будет истинным.
2. Для логической операции И таблица
истинности имеет вид:
Из таблицы истинности следует, что операция И
- это логическое умножение, которое ничем не отличается от умножения в
обычной алгебре. Операцию И можно обозначить знаком по-разному:
В формальной логике операции логического умножения соответствуют связкам
«и», «а», «но», «хотя».
3. Логическая
операция НЕ - эта
операция является специфичной для алгебры логики и не имеет аналога в обычной
алгебре. Она обозначается чертой над значением переменной, либо знаком
приставки перед значением переменной:
Читается
в обоих случаях одинаково «Не А». Таблица истинности для этой функции
имеет вид:
Данная операция соответствует в формальной логике связкам «не»; «неверно,
что».
В
вычислительной технике операцию НЕ называют отрицанием или инверсией,
операцию ИЛИ - дизъюнкцией, операцию И - конъюнкцией.
Логические операции имеют следующий приоритет:
действия в скобках, инверсия, & (конъюнкция), v (дизъюнкция).
Алгоритм
построения таблицы истинности:
1. подсчитать
количество переменных n в логическом выражении;
2. подсчитать
количество логических операций в выражении;
3. установить последовательность выполнения
логических операций с учётом скобок и приоритетов;
4. определить
количество столбцов в таблице: число
переменных плюс число операций;
5. заполнить шапку таблицы, включив в неё
переменные и операции;
6. определить
число строк в таблице (без шапки) m = 2n;
7. выписать
наборы входных переменных с учётом
того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2n-1;
8. провести заполнение таблицы по столбцам, выполняя логические операции в
соответствии с установленной последовательностью.
Наборы входных переменных, во избежание ошибок, рекомендуют перечислять следующим
образом:
а) определить количество наборов
входных переменных;
б) разделить колонку значений первой переменной пополам и заполнить верхнюю
часть колонки 0, а нижнюю - 1;
в) разделить колонку значений второй переменной на четыре части и заполнить
каждую четверть чередующимися группами 0 или 1, начиная с группы 0;
г) продолжать деление колонок значений последующих переменных на 8, 16 и т.д.
частей и заполнение их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут
состоять из одного символа.
Комментариев нет:
Отправить комментарий