Логика

Алгебра логики
Джордж Буль
Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля.
Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Что же такое логическое высказывание?
Логическое высказывание — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.
Так, например, предложение "6 — четное число" следует считать высказыванием, так как оно истинное. Предложение "Рим — столица Франции" тоже высказывание, так как оно ложное.

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

Bысказывания, образованные из других высказываний с помощью логических связок, называются составными. Высказывания, не являющиеся составными, называются элементарными.
Так, например, из элементарных высказываний "Петров — врач", "Петров — шахматист" при помощи связки "и" можно получить составное высказывание "Петров — врач и шахматист"

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание «2-четное число", а через В — высказывание «6- четное число". Тогда составное высказывание «2 и 6 четные числа" можно кратко записать как
А и В. Здесь "и" — логическая связка, А, В — логические переменные, которые мoгут принимать только два значения — "истина" или "ложь", "1" и "0".

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение: конъюнкция, дизъюнкция, отрицание, импликация, эквиваленция.

Конъюнкция
логическое умножение
Конъюнкцией высказываний А и В называется высказывание, которое истинно только тогда, когда A и B истинны.
Записывается: А∧В; А&В;А·В; Читается: И (AND)

Последовательное соединение
Элемент «И»

Дизъюнкция
Логическое сложение
Дизъюнкцией высказываний А и В называется высказывание, которое ложно тогда и только тогда, когда оба высказывания ложны.
Записывается: А∨В; А+В
Читается: ИЛИ (OR)

Параллельное соединение
Элемент «ИЛИ»

Инверсия-Отрицание
Отрицанием высказывания А называется высказывание , которое истинно, когда А ложно.
Записывается: ; А’
Читается: НЕ А (NOT)

Инвертор
Элемент «НЕ»

Импликация
Импликацией высказываний А и
В называется высказывание, которое ложно тогда и только тогда, когда
А истинно, В ложно.
А называется посылкой, а В заключением. Записывается А =>В
(из А следует В).
Операция, выражаемая связками "если ..., то",
"из ...следует","... влечет ..."
А =>В можно заменить на¬А V В

Импликация

Эквиваленция
Эквиваленцией высказываний А
и В называется высказывание, которое истинно тогда и только тогда, когда высказывания А и В имеют одинаковые значения истинности (А эквивалентно В).
Записывается: А <=> В
Операция, выражаемая связками "тогда и только тогда", "равносильно"
А <=> В можно заменить на (A & B)V(¬A & ¬B)

Эквиваленция

Последовательность выполне-
ния операций в сложных высказываниях задается
круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция
-отрицания ("не"), затем
-конъюнкция ("и"), после -дизъюнкция ("или") и затем -импликация.

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

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

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:
(0, 0), (0, 1), (1, 0), (1, 1).
Если формула содержит три переменные, то возможных наборов значений переменных восемь:
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Составим таблицу истинности для формулы

Если при всех наборах значений
переменных x и y формула
принимает значение 1, то
она является тождественно истинной;
Если значение 0, то тождественно ложной;
Если же в некоторых случаях функция принимает значение 1, а в некоторых — 0, то она является выполнимой.

Рассмотрим особенности
Записи целых чисел со знаком на
примере однобайтового формата,
при котором для знака
отводится один разряд, а для цифр
абсолютной величины – семь разрядов.
*

В компьютерной технике применяются три формы записи (кодирования) целых чисел
со знаком: прямой код, обратный код, дополнительный код.
Положительные числа в прямом, обратном и дополнительном кодах изображаются одинаково — двоичными кодами с цифрой 0 в знаковом разряде.
*

Например:

Прямой код. В знаковый разряд помещается цифра 1, а в разряды цифровой части числа — двоичный код его абсолютной величины.
*
Отрицательные числа в прямом,
обратном и дополнительном кодах
имеют разное изображение.

Например

*
Обратный код.
Получается инвертированием всех цифр двоичного кода абсолютной величины числа, включая разряд знака: нули заменяются единицами, а единицы — нулями.

Например: