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

Алгебра логики устанавливает законы мышления.
Основные формы мышления: понятие, суждение (высказывание), умозаключение.
Понятие выделяет существенные признаки объекта, которые отличают его от других объектов.
Высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать истинно оно или ложно.
Умозаключения позволяют на основе известных фактов, выраженных в форме суждений, получить заключение, т.е. вывести новое знание.
1. Понятие об алгебре логики

2. Этапы развития логики
Основоположник логики как науки - древнегреческий философ и ученый Аристотель (384-322 гг. до н. э.) . Он разработал теорию дедукции, то есть теорию логического вывода.

Демокрит
Платон
Евклид
Первый этап – формальная логика ( работы древнегреческих ученых: Аристотель, Платон, Демокрит).
1. Изучение законов мышления,
2. Высказывания на естественном языке.

Рене Декарт
Готфрид А. Лейбниц
Джордж Буль
Второй этап – математическая или символьная логика.
Основоположник - немецкий ученый Готфрид Лейбниц.
1. Введение логической символики.
2. Применение математических методов.
Джордж Буль – английский математик, создатель алгебры логики.

Клод Элвуд Шеннон
Американский математик и инженер.
Применил булеву алгебру к теории электрических цепей
«Отец» современной теории информации и связи.

Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ¬).
Высказывание ¬А истинно, когда А ложно, и ложно, когда А истинно.
3. Логические операции

Операция, выражаемая связкой «или» называется дизъюнкцией или логическим сложением и обозначается знаком ∨ или +. Высказывание А + В ложно тогда и только тогда, когда оба высказывания А и В ложны.
Операция, выражаемая связкой «и» называется конъюнкцией или логическим умножением и обозначается знаком ∧ или ∙ Высказывание А В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Операция, выражаемая связками «если…, то», «из…следует», «влечет…», называется импликацией и обозначается знаком →. Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.

Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «…равносильно…», называется эквиваленцией или двойной импликацией и обозначается знаком ~ или ↔.
Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают. Например, истинны высказывания: «24 делится на 6 тогда и только тогда, когда 24 делится на 3», «23 делится на 6 тогда и только тогда, когда 23 делится на 3».

Очень важными для вычислительной техники являются операции исключающее ИЛИ (неравнозначность, сложение по модулю два) и штрих Шеффера.
Сложение по модулю два обозначается символом ⊕,
штрих Шеффера символом \.

Основные логические операции отрицание, конъюнкция, дизъюнкция.
Таблица выражения операций через основные

Определение логической формулы.
1. Всякая логическая переменная и символы истина и ложь – формулы.
2. Если А и В – формулы, то А, A^B, А∨В, А→В, А↔В – формулы.
3. Никаких других формул в алгебре логики нет
В пункте 1 определены элементарные формулы, в пункте 2 даны правила образования из любых данных формул новых формул.
4. Логические формулы

Формула, которая при одних сочетаниях входящих в нее переменных является истинной, а при других – ложной, называется выполнимой.
Формула, которая имеет значение истина при любых значениях истинности входящих в нее переменных, называется тождественно-истинной формулой или тавтологией.
Например, формула А∨А.

Формула, которая ложна при любых значениях истинности входящих в нее переменных, называется тождественно-ложной или противоречивой.
Например, формула А^А всегда ложна
Формулы А и В имеющие одни и те же значения истинности при одинаковых наборах значений входящих в них переменных, называются равносильными.
Равносильность двух формул алгебры логики обозначается символом = или символом ≡.

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

6. Аксиомы и законы алгебры логики
Система аксиом алгебры логики
х=0, если х ≠ 1. х=1, если х ≠ 0.
1 ∨ 1 = 1 1 ^ 1 = 1
0 ∨ 0 = 0 0 ^ 0 = 0
0 ∨ 1 = 1 v 0 = 1 0 ^ 1 = 1 ^ 0 = 0
0 = 1 1 = 0

Тождества алгебры логики
х ∨ х = 1 х ^ х = 0
0 ∨ х = х 1 ^ х = х
1 ∨ х = 1 0 ^ х = 0
х ∨ х = х х ^ х = х

1. Закон исключения третьего.
Был известен уже в древности.
Содержательная трактовка: «Во время своих странствований Платон был в Египте ИЛИ не был Платон в Египте».
В такой трактовке это и любое другое выражение будут правильны (тогда говорили: истинно). Ничего другого быть не может: Платон либо был, либо не был в Египте – третьего не дано.

2. Закон непротиворечивости.
Если сказать: «Во время своих странствий Платон был в Египте И не был Платон в Египте, то очевидно, что любое высказывание, имеющее такую форму, всегда будет ложно.
3. Закон отрицания:
«Если НЕ верно, что Платон Не БЫЛ в Египте, то значит, Платон БЫЛ в Египте».

На принципиальных электрических схемах логические элементы изображаются прямоугольниками с обозначением входов и выходов.
7. Основные логические устройства ЭВМ

Сумматор

Одноразрядный сумматор

Полусумматор двоичных чисел
0 0 1 1
0 1 0 1
0 1 1 0
+
1
Перенос в старший разряд

Условное обозначение
Схема
RS- триггер