Формальное решение логических задач.

1. Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.
2. Записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помощью логических операций.
3. Составить единое логическое выражение для всех требований задачи.
4. Используя законы алгебры логики, попытаться упростить полученное выражение и вычислить все его значения, либо построить таблицу истинности для рассматриваемого выражения.
5. Выбрать решение — набор значений простых высказываний, при котором построенное логическое выражение является истинным.
6. Проверить, удовлетворяет ли полученное решение условию задачи.

Билет №7 Алгебра логики. Основные законы алгебры логики. Алгебра переключательных схем.

Законы алгебры логики

Для логических величин обычно используются три операции:

•     Конъюнкция – логическое умножение (И) – and, &, ∧.

•     Дизъюнкция – логическое сложение (ИЛИ) – or, |, v.

•     Логическое отрицание (НЕ) – not, .

                     Логические выражения можно преобразовывать в соответствии с законами алгебры логики:

1.    Законырефлексивности:

a∨a = a

a∧a = a

2.    Законы коммутативности:

a ∨ b = b ∨ a

a ∧ b = b ∧ a

3.    Законы ассоциативности:

(a∧ b) ∧ c = a ∧ (b ∧ c)

(a∨ b) ∨ c = a ∨ (b ∨ c)

4.    Законы дистрибутивности:

a ∧ (b ∨ c) = a ∧ b ∨ a ∧ c

a ∨ b ∧ c = (a ∨ b) ∧ (a ∨ c)

5.    Закон отрицания отрицания:

( a) = a

6.    Законы де Моргана:

(a ∧ b) = a ∨ b

(a ∨ b) = a ∧ b

7.    Законыпоглощения:

a ∨ a ∧ b = a

a ∧ (a ∨ b) = a

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

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

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

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает

•     значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток;

•     если же переключатель разомкнут, то х равен нулю

Будем считать, что два переключателя Х и ⌐Х связаны таким образом, что когда Х замкнут, то ⌐Х разомкнут, и наоборот.

Всей переключательной схеме также можно поставить в соответствие логическую переменную, равную единице, если схема проводит ток, и равную нулю — если не проводит.

Эта переменная является функцией от переменных, соответствующих всем переключателям схемы, и называется функцией проводимости.

Билет №8. Булевы функции. Существование ограниченного числа функций от n переменных. Булевы функции двух переменных. Полные системы булевых функций. Возможность выражения любых булевых функций через полную систему.

Логической ( булевой ) функцией называют функцию f ( , ,......, ), аргументы которой , ,......, , (независимые переменные) и сама функция (зависимая переменная) принимают значения 0 и 1. Логические функции могут быть заданы табличным способом или аналитически - в виде соответствующих формул.

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

Для n = 2 существует 16 различных булевых функций.

Функции, выраженные с использованием одной логической операции, называются по имени этой логической операции. Например (x,y) = x&y - конъюкция. С увеличением часов аргументов количество логических функций резко возрастает. Для трех переменных существует 256 различных булевых функций. Для четырех переменных - уже 65 536 функций функций и т.д.

Множество функций алгебры логики называется полной системой, если замыкание(Замкнутый класс в теории булевых функций — такое множество P функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: [P]=P. Другими словами, любая функция, которую можно выразить формулой с использованием функций множества P, снова входит в это же множество) этого множества совпадает с множеством всех функций. (В частности, для двузначной логики .) Другими словами, должна быть возможность любую функцию алгебры логики выразить формулой с использованием функций множества .

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

Широко известны такие полные системы булевых функций:

• (конъюнкция, дизъюнкция, отрицание);
• (конъюнкция, сложение по модулю 2, константа 1);
• (конъюнкция, отрицание);
• (дизъюнкция, отрицание);
• (стрелка Пирса);
• (штрих Шеффера).

Билет №9.Канонические формы логических формул. Элементарная конъюнкция. Дизъюнктивная нормальная форма (ДНФ). Совершенная ДНФ (СДНФ). Теорема о существовании СДНФ.