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

Алгебра высказываний (логики) – это раздел математики, изучающий высказывания со стороны их логических значений (истинности или ложности) и логические операции над ними. Логическое высказывание – это любое повествовательное предложение, в отношении которого можно сказать истинно оно или ложно. Например: 6 – четное число -это истинное высказывание Рим – столица Франции -это ложное высказывание

Логические операции Над логическим высказыванием в компьютере выполняется та или иная логическая операция. Существует 5 основных логических операций: Инверсия; Конъюнкция; Дизъюнкция; Импликация; Эквиваленция.

Отрицание (выражается словом «не») или инверсия. Обозначается чертой над высказыванием. Функция, реализующая эту операцию, записывается в виде Эта функция истинна, если переменная (высказывание) ложна. Составим таблицу истинности для данной операции: Например, 2 +2 = 3 – ложь, значит ее отрицание - истинное высказывание. Устройство, реализующее эту операцию на схемах, называется инвертором и обозначается следующим образом

Конъюнкция (выражается словом «и») или логическое умножение. Обозначается *, ^, &(амперсанд). Функция, реализующая эту операцию, записывается в виде Эта функция истинна тогда и только тогда, когда все переменные (высказывания) истинны одновременно. Составим таблицу истинности для данной операции: Устройство, реализующее эту операцию на схемах, называется конъюнктором и обозначается следующим образом: Y = Х 1 * X 2 или Y = X 1 ^ X 2 или Y = X 1 & X 2.

Дизъюнкция (выражается словом «или») или логическое сложение. Обозначается +, v. Функция, реализующая эту операцию, записывается в виде Эта функция истинна тогда и только тогда, когда хотя бы одна переменная (высказывание) истинна или истинны обе переменные (высказывания) одновременно. Составим таблицу истинности для данной операции: Устройство, реализующее эту операцию на схемах, называется дизъюнктором и обозначается следующим образом: Y = Х 1 + X 2 или Y = X 1 v X 2.

Импликация ( «если…то», «из…следует») или логическое следование. Обозначается знаком. Функция, реализующая эту операцию, записывается в виде Функция ложна тогда и только тогда, когда Х 1 истинно, а Х 2 ложно. Составим таблицу истинности для данной операции: Y = X 1 X 2.

Эквиваленция ( «тогда и только тогда»), или двойная импликация. Обозначается знаком или. Функция, реализующая эту операцию, записывается в виде Функция истинна тогда и только тогда, когда значения Х 1 и Х 2 совпадают. Составим таблицу истинности для данной операции: Y = X 1 X 2.

Законы логики Закон Для операции ИЛИДля операции И 1. ПереместительныйX v Y = Y v XX & Y = Y & X 2. СочетательныйX v(Y v Z) = (X v Y) v ZX &(Y & Z) = (X & Y) & Z 3. РаспределительныйX &(Y v Z) = X & Y v X&ZX v(Y & Z) = (X v Y)&(X v Z) 4. Правила де Моргана 5. ИдемпотенцииX v X =XX & X = X 6. ПоглощенияX v X &Y =XX & (X v Y) =X 7. Склеивания 8. Инверсии 9. Операции с константами X v 0 = X X v 1 = 1X & 0 = 0 X & 1 = X 10. Двойное отрицание

Алгоритм построения логических схем 1. Определить число логических переменных. 2. Определить количество базовых логических операций и их порядок. 3. Изобразить для каждой логической операции соответствующий ей вентиль. 4. Соединить вентили в порядке выполнения логических операций.

Задание 1. Составить логическую схему для выражения: F=A v B & A. Две переменные – А и В. Две логические операции: 1-&, 2-v. Строим схему:

Задание 2 Составить таблицу истинности для формулы и построить логическую схему XYX v Y

Задание 3 Какие из формул являются тождественно –истинными, а какие являются тождественно – ложными

Домашнее задание 1. Построить таблицу истинности для логической формулы и упростить формулу, используя законы алгебры логики: __ __ _ _ __ A & D & (A v C & B v D) v A & C v A & B & C 2. Подготовиться к проверочной работе