Логические основы функционирования ЭВМ

Высказывание
Высказывание – повествовательное предложение, которое имеет определенное значение истинности: истина или ложь.
Каждое высказывание обозначается большой латинской буквой, а его истинность – 0 или 1.
Пример: А = 1. В = 0.

Логические операции
Операция Отрицание (инверсия) – заменяет высказывания на противоположные.

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

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

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

Логические операции
Операция Импликация -
истинна всегда, за исключением случая, когда первое высказывание истинно, а второе – ложно.

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

Формула алгебры логики
Формула алгебры логики – выражение, состоящее из простых высказываний А, В, …, знаков логических операций и скобок.
Скобки указывают последовательность выполнения операций.
При отсутствии скобок первой всегда выполняется операция отрицания, затем конъюнкция, дизъюнкция, затем импликация и эквиваленция.

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

Классификация формул
Две формулы называются равносильными, если их таблицы истинности совпадают при любой оценке переменных.
Две формулы называются совместимыми, если хотя бы при одной оценке переменных они одновременно являются истинными. В противном случае они несовместимые.
Две формулы называются противоположными, если при любой оценке переменных они принимают противоположное значения, и в этом случае каждая из формул является отрицанием другой.
Формула В называется логическим следствием формулы А, если при любых оценках переменных импликация А→В принимает только истинные значения

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

Нормальные формы
Существует два способа определения истинного значения формулы.
Первый – с помощью таблиц истинности, а второй – путем приведения формул к нормальной форме.
Формула имеет нормальную форму, если в ней отсутствуют знаки эквиваленции, импликации, исключающей дизъюнкции, двойного отрицания, при этом знаки отрицания находятся только при переменных.

Нормальные формы
Основная конъюнкция – это конъюнкция основных высказываний переменных или их отрицаний. Например, АВС.
Основная дизъюнкция – это дизъюнкция основных высказываний переменных или их отрицаний. Например, А+В+С+В.
Конъюнктивной нормальной формой (КНФ) данной формулы называется формула, равносильная данной и представленная в виде конъюнкции основных дизъюнкций. Например, (А+В)(А+В+С).
Дизъюнктивная нормальной формой (ДНФ) данной формулы называется формула, равносильная данной и представленная в виде дизъюнкции основных конъюнкции. Например, АВ+С+АВ.

Нормальные формы
Теорема 1.
Для того, чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы ее конъюнктивная нормальная форма содержала в каждой элементарной дизъюнкции некоторое высказывание и его отрицание.
Теорема 2.
Для того, чтобы формула алгебры высказываний была тождественно ложной, необходимо и достаточно, чтобы ее дизъюнктивная нормальная форма содержала в каждой элементарной дизъюнкции некоторое высказывание и его отрицание.

Основные формулы алгебры логики
Законы коммутативности:
А∨В=В∨А
А∧В=В∧А
Законы ассоциативности:
(А∨В)∨С=А∨(В∨С)
(А∧В)∧С=А∧(В∧С)

Основные формулы алгебры логики
Законы идемпотентности:
А∨А=А
А∧А=А
Законы поглощения:
А∧(А∨В)=A
А∨(А∧В)=A

Основные формулы алгебры логики
Законы дистрибутивности:
А∧(В∨С)=(А∧В)∨(А∧С)
А∨(В∧С)=(А∨В)∧(А∨С)
Закон поглощения 0 или 1:
А∨0=А
А∧1=А
А∨1=1
А∧0=0

Основные формулы алгебры логики
Закон противоречия:
Закон исключенного третьего
Законы де Моргана:
Закон двойного отрицания:

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

Базовые логические элементы
Схемы, реализующие операции НЕ, И, ИЛИ называют основными или базовыми логическими элементами.
Схема совпадения (элемент И)
Собирательная схема (элемент ИЛИ)
Схема отрицания (элемент НЕ)

Построение формул алгебры высказываний по заданной таблице истинности
Правило 1
Пусть F –двоичная функция от n переменных. Предположим, что F не равна тождественно нулю. Пусть Т1, Т2,…,Тк – все точки ее определения, в которых F=1. Можно доказать, что справедлива следующая формула:
F(x1, x2,…,xn)=f1+f2+…+fk, где fi=yi1*yi2*…*yin, i=1, 2, …k,
Yij=