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

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

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

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Пример. «3 – простое число» является высказыванием, поскольку оно истинно.

Не всякое предложение является логическим высказыванием.

Пример. Предложение «Давайте пойдём в кино» не является высказыванием. Вопросительные и побудительные предложения высказываниями не являются.

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

Пример. «x+2>5» – высказывательная форма, которая при x>3 является истинной, иначе ложной.

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

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

Пример. Высказывание «Число 6 делится на 2» – простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» – составное высказывание, образованное из двух простых с помощью логической связки «и».

Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний, из которых они состоят.

Чтобы обращаться к логическим высказываниям, им назначают имена.

Пример. Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».

1. Логическое умножение (конъюнкция)

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

Для обозначения операции логического умножения, или конъюнкции, используют символы Ʌ, &, . (точку, которую можно опускать), AND.

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

Следовательно, составное высказывание принимает значение “ложь”, когда ложно хотя бы одно из этих высказываний.

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

Логические основы работы ЭВМ 1

Основы логики и логические основы компьютера 3

1. Формы мышления 3

1.1. Логика — это наука о формах и способах мышления 3

1.2. Понятие 3

1.3. Высказывание 4

1.4. Умозаключение 5

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

2.1. Логическое умножение (конъюнкция) 7

2.2. Логическое сложение (дизъюнкция) 9

2.3. Логическое отрицание (инверсия) 10

2.4. Логическое следование (импликация) 11

2.5. Логическое тождество (эквиваленция) 11

2.6. Операция «ИСКЛЮЧАЮЩЕЕ ИЛИ» 12

3. Порядок выполнения логических операций в сложном логическом выражении 13

4. Логические выражения и таблицы истинности 14

4.1. Логические выражения 14

4.2. Таблицы истинности 15

4.3. Равносильные логические выражения 16

5. Построение таблиц истинности для сложных выражений 17

6. Логические функции 18

6.1. Логическое следование (импликация) 19

6.2. Логическое равенство (эквивалентность) 20

7. Логические законы и правила преобразования логических выражений 21

7.1. Закон тождества 21

7.2. Закон непротиворечия 21

7.3. Закон исключённого третьего 21

7.4. Закон двойного отрицания 22

7.5. Законы де Моргана (общей инверсии) 22

7.6. Закон коммутативности (переместительный) 22

7.7. Закон ассоциативности (сочетательный) 22

7.8. Закон дистрибутивности (распределительный) 23

8. Логические элементы 23

8.1. Простейший логический элемент НЕ (инвертор) 24

Базовый набор операций 25

8.2. Логический элемент И (конъюнктор) 25

8.3. Логический элемент ИЛИ (дизъюнктор) 26

8.4. Логический элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 26

9. Таблица 18 – Условные обозначения логических элементов компьютера 27

10. Вопросы для самопроверки 28

11. Решение логических задач 29

11.1. Примеры решения задач 29

11.2. Тесты 33

11.3. Задания 34

Библиографический список 36

Содержание 37

Перейдём теперь от записи высказываний на естественном языке к их записи на формальном языке алгебры высказываний (алгебры логики). Образуем составное высказывание F, которое получится в результате конъюнкции двух простых высказываний:

F = А & В либо (F = А Ʌ В)

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

Сама функция логического умножения F также может принимать лишь два значения «истина» (1) и «ложь» (0). Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах её аргументов (таблица 1).

Таблица 1 – Таблица истинности функции логического умножения (конъюнкции)

А	В	F = А & В F = А Ʌ В
0	0	0
0	1	0
1	0	0
1	1	1

По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического умножения. Рассмотрим, например, составное высказывание «2 • 2 = 4 и З • 3 = 10».

Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0); по таблице определяем, что логическая функция принимает значение “ложь” (F = 0), то есть данное составное высказывание ложно.