- •1.2 Теоретические основы информатики Представление информации в компьютере
- •1.2.1.1 Кодирование числовая информации
- •1.1.1.2 Операции с числовой информацией
- •1.2.1.3 Кодирование текстовой информации
- •Международная кодировка ascii
- •Международная кодировка unicode
- •1.2.1.4 Кодирование графической информации
- •Кодирование изображения
- •Цветовая модель hsb
- •Недостатки растрового изображения
- •1.2.1.5 Кодирование видеоинформация
- •1.2.1.6 Представление звуковой информации
- •1.2.3 Элементы алгебры логики
- •1.2.3.1 Основные понятия
- •1.2.3.2 Операции (высказывания) алгебры логики
- •1.2.3.3 Аксиомы алгебры логики
1.2.3 Элементы алгебры логики
1.2.3.1 Основные понятия
Алгебра логики или булева алгебра (ее разработчик – Дж. Буль) вытекает из логики, основу которой составили труды Аристотеля (384-322 гг до н. э.). Логика – наука о доказательных рассуждениях Правильность рассуждения определяется только его логической конструкцией (структурой), и не зависит конкретного содержания входящих в него рассуждений.
Математическая логика была создана во второй половине 19-го века, исчисления позволяют устранять неясности естественного языка. Математическая логика = Формальная логика + алгебраические операции.
Алгебра логики (булева алгебра) используется для описания логики функционирования аппаратных и программных средств вычислительной техники и представляет собой раздел математической логики, изучающий строение логических высказываний и способы установления их истинности с помощью алгебраических методов.
В алгебре логике все переменные и функции могут принимать только два значения 0 (Ложь, False) и 1 (истина, True).
Отношение между двумя высказываниями (или логическими функциями), когда для всех наборов значений аргументов значения функций на одинаковых наборах совпадают, называются эквивалентными. Логические выражения, истинные при любых значениях истинности входящих в них переменных, называют тавтологиями (от греч. “tauto” – то же самое и “logos” – слово).
Алгебра логики оперирует с высказываниями - грамматически правильными повествовательными предложениями, передающими смысл. Высказывание является истинным или ложным, простым или сложным, образованным из простых с помощью логических связок “и”, “или”, “не”, “если... , то” и т. п. Основные термины алгебры логики:
простое высказывание – повествовательное предложение, принимающее одно из двух возможных значений – истина или ложь;
предикат – высказывание с переменными, которое при одних значениях переменных может стать истинным высказыванием, при других – ложным;
рассуждение – цепочка взаимосвязанных фактов и умозаключений, вытекающих друг из друга;
составное высказывание – комбинация простых высказываний, соединенных логическими операциями.
1.2.3.2 Операции (высказывания) алгебры логики
Типы высказываний (основные операции алгебры логики):
Конъюнкция – логическое умножение (результат соединения высказываний с помощью связки “и”) дает сложное высказывание, истинное только тогда, когда истинны оба составляющие его высказывания обозначаются: xy или x & y или ху, читается “х и у”.
Обозначается Таблица истинности
на схемах & логического умножения
X |
Y |
Х Y |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
Дизъюнкция – логическое сложение (результат соединения высказываний с помощью связки ”или”) дает сложное высказывание, истинное, когда истинно хотя бы одно из составляющих его высказываний. Обозначается xy или x + y – дизъюнкция, читается “х или у”
Обозначается Таблица истинности
на схемах 1 логического сложения
X |
Y |
Х Y |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Строгая дизъюнкция (результат соединения высказываний с помощью связки “исключающее или”) дает сложное высказывание, истинное, когда истинно только одно из составляющих его высказываний (xy или xy - строгая дизъюнкция).
Таблица истинности
X |
Y |
Х Y |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Иначе эта операция называется “сложение по модулю 2”, т.к. при сложении четного количества единиц результат будет 0, а при сложении нечетного количества единиц – 1.
Инверсия - логическое отрицание (результат применения к высказыванию связки “не”) дает сложное высказывание, истинное, когда исходное высказывание ложно (x или - инверсия).
Обозначается инверсия Таблица истинности инверсии
Х | |
0 |
1 |
1 |
0 |
Импликация (следование) (результат соединения высказываний с помощью связки “если ... , то”) дает сложное высказывание, ложное, только когда первое из составляющих его высказываний истинно, а второе - ложно (xy - импликация).
Таблица истинности
импликации
-
Х
Y
XY
0
0
1
0
1
1
1
0
0
1
1
1
Эквиваленция (результат соединения высказываний с помощью связки “тогда и только тогда”) дает сложное высказывание, истинное, когда истинность составляющих его высказываний совпадает (X Y или X Y - эквиваленция).
Эта операция называется также “эквивалентность” или равнозначность. Ее таблица истинности
-
Х
Y
XY
0
0
1
0
1
0
1
0
0
1
1
1
Алгебра логики вводит аксиомы и основные законы, с помощью которых можно упростить схемную реализацию компьютерных устройств или алгоритмов обработки информации, тем самым повысить надежность и сократить затраты на обработку информации. Используются также логические операторы - кванторы общности (“для всех”) и существования (“существует”). Для сложных высказываний строятся таблицы истинности, например:
A |
B |
AB |
AB |
AB |
0 (ЛОЖЬ) |
0 (ЛОЖЬ) |
0 (ЛОЖЬ) |
0 (ЛОЖЬ) |
1 (ИСТИНА) |
0 (ЛОЖЬ) |
1 (ИСТИНА) |
0 (ЛОЖЬ) |
1 (ИСТИНА) |
1 (ИСТИНА) |
1 (ИСТИНА) |
0 (ЛОЖЬ) |
0 (ЛОЖЬ) |
1 (ИСТИНА) |
0 (ЛОЖЬ) |
1 (ИСТИНА) |
1 (ИСТИНА) |
1 (ИСТИНА) |
1 (ИСТИНА) |
1 (ИСТИНА) |