1.5.1. Логическая алгебра. Константы и утверждения
Логическая алгебра - это раздел математической логики, изучающий операции над логическими значениями, утверждениями, выражениями и особенности этих операций. Логическая алгебра по другому называется булевой алгеброй по имени учёного Дж. Буля, положившего начало формированию логики, как научной дисциплины.
Утверждением (условием) в логической алгебре является любое высказывание, относительно которого можно сказать, ложно оно или истинно. Каждое утверждение всегда имеет одно из двух логических значений - истина или ложь. Утверждения могут выражаться при помощи слов, математических и химических символов и т.д.Попробуйте сами привести несколько примеров.
Константа - это величина, имеющая постоянное значение "ложь" или "истина".
Кроме логических констант применяются логические переменные, которым даются произвольные имена. Например: А, В, Х. Логические переменные могут приобретать значения 0 или 1 (ложь и истина, True и False).
По определённым законам над логическими константами, переменными, утверждениями можно производить некоторые операции, манипулировать ими. Всё это является объектом изучения логической алгебры.
Логические действия двоичны по своей сути, поэтому логическая алгебра лежит в основе анализа и проектирования логических схем, применяемых в вычислительной технике, которые состоят из логических элементов, осуществляющих логические операции.
1.5.2. Логические выражения
Логическое выражение – это выражение, состоящее из логических переменных, логических констант, знаков логических операций и скобок.
С логическими переменными (или утверждениями) мы уже познакомились. С константами тоже. Что такое скобки вы знаете.
С логическими операциями вы познакомились при изучении оператора IF. Поэтому здесь лишь отметим, как они записываются в логике:
Название
В Паскале
Обозначение
Конъюнкция
A and B
A L B
Дизъюнкция
A or B
A V B
Отрицание
not A
`А
Если вы не помните, как выполняются эти операции, вернитесь к главе с оператором IF.
При вычислении логических выражений операции выполняются в следующей последовательности:
· сначала выполняются операции в скобках,
· потом выполняются операции отрицания,
· затем конъюнкция (L),
· затем дизъюнкция (V).
В остальных случаях операции выполняются по порядку записи.
Например:
2 1 4 3
A V B L C V D L E
Логическим выражением могут быть высказывания, например:
"Это двух- или трёхкомнатная квартира, но не первый и не последний этаж".
Давайте запишем в одну таблицу значения простейших логических выражений для всех возможных значений переменных.
A
B
A V B
A L B
`A
Таблица, в которой представлены все возможные комбинации логических переменных и указано значение некоторого логического выражения для каждой комбинации переменных, называется таблицей истинности.
Таблицу истинности можно составить для любого логического выражения.
Логические выражения, таблицы истинности которых совпадают, называют эквивалентными.
Рассмотрим логическое выражение: A V B L C. В это выражение входит 3 аргумента: A, B и C. Каждое из них может принимать одно из двух значений: либо 0, либо 1. Следовательно, для того чтобы построить таблицу истинности данного логического выражения, необходимо пересмотреть 23 различных комбинаций значений переменных A, B, C. В таблице истинности значение логического выражения проще считать по частям:
A
B
C
B L C
A V (B L C)
При вычислении значений выражения в последнем столбике используется результат B L C, вычисленный и записанный в предпоследнем столбике. Чтобы не допустить ошибку при составлении таблицы истинности, нужно составлять её по частям, как в последнем примере.
1.5.4. Законы логической алгебры
Знак равенства всюду означает, что выражения в левой и правой частях эквивалентны, т.е. они принимают одни и те же значения истинности при любых наборах значений входящих в них утверждений.
1. Коммутативность
a) конъюнкции: b) дизъюнкции:
A L B = B L A A v B = B v A
2. Ассоциативность
а) конъюнкции:
А L (В L С) = (А L В) L С = А L В L С
б) дизъюнкции:
А v (B v C) = (A v B) v C = A v B v C
3. Дистрибутивность
a) конъюнкции относительно дизъюнкции:
A L (B v C) = (A L B) v (A L C)=A L B v A L C
б) дизъюнкции относительно конъюнкции:
A v (B L C) = (A v B) L (A v C)
4. Закон двойного отрицания: не (не (А)) = А
5. Закон противоречия: A L (не A) = 0
6. Закон исключённого третьего: A v (не А) = 1
7. Закон де Моргана
а) отрицание конъюнкции: (не A) L (не B) = не (A v B)
б) отрицание дизъюнкции: (не A) v (не B) = не (A L B)
8. Закон поглощения:
а) А L 1 = А б) A v 1 = 1
А L 0 = 0 A v 0 = A
9. Идемпотентность:
A L A = A; A v A = A
Под системой счисления принято понимать совокупность приёмов обозначения (записи) чисел с помощью заданного набора специальных знаков, символов и правил выполнения арифметических операций. Существуют позиционные, непозиционные и смешанные системы счисления.
В непозиционной системе счисления значение каждого символа определено однозначно и не зависит от занимаемой им позиции в записи числа. В непозиционных системах счисления каждому числу соответствует свой знак и вне зависимости от занимаемой позиции в записи числа он всегда равен этому числу. Например, римская система счисления. Там: I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Для записи тысяч используется только буква M, когда в позиционной системе счисления единица может обозначать и одну тысячу, и одну единицу, и т.д.. В римской системе счисления приняты особые правила записи чисел, которые не вписываются в стандартные правила позиционных систем. Непозиционными были системы счисления у древних египтян, греков. Они были более - менее пригодны для выполнения операций сложения и вычитания, но совсем не удобны для умножения и деления.
Наиболее совершенными являются позиционные системы счисления, т.е. системы счисления, в которых значение каждого символа в записи числа, его "вес" определяется той позицией, которую занимает этот символ в записи числа, например: в десятичной системе счисления все символы "2" в записи числа 2222222 имеют разные значения.
В информатике чаще всего применяются двоичная, восьмеричная и шестнадцатеричная системы счисления. Название позиционной системы счисления определяется количеством различных символов, применяемых в данной системе счисления; напр., в десятичной системе счисления используется десять арабских цифр 0,1,...9, в двоичной - две цифры 0 и 1. Все используемые в данной системе счисления символы называются базисом.
Основанием позиционной системы счисления является число, определяемое названием данной системы счисления, например, основанием десятичной системы счисления является число 10, основанием двоичной системы счисления – число 2.
Любое число (Sn Sn-1...S1 S0) любой позиционной системы счисления можно записать в следующем виде.
Sn.gn + Sn-1.gn-1 + ... + S1.g1 + S0.g0 ,
где S с индексами - символы рассматриваемого числа (цифры), g - основание данной системы счисления.
Например, число 54637 (S4S3S2S1S0) восьмиричной системы счисления можно представить в виде:
