Математическая логика и теория алгоритмов презентация

Таблица истинности для инверсии х ( ) :

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

Таблица истинности для конъюнкции:

Из определения операции дизъюнкции и отрицания ясно, что высказывание всегда истинно.

Таблица истинност для дизъюнкции:

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

Таблица истинности для эквиваленции:

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

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

Например: - ТИФ, - ТЛФ.

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

Эти соглашения следующие:

Рассмотрим эти аксиомы и законы, объединив их в несколько групп.

– законы
идемпотентности

– сочетательные
законы.

Пример:
Возьмем правую часть закона 8) и выполним логическое
перемножение скобок:

V. Закон двойственности.
Пусть формула содержит только операции конъюнкции, дизъюнкции и отрицания. Операцию конъюнкции называют двойственной операции дизъюнкции, и наоборот.

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

Например:

1. Операция импликации не обладает переместительным свойством (законом).

Действительно: Отсюда видим, что .

2. Операция импликации не обладает сочетательным свойством (законом).

Действительно: ,

, ,
.

4. Операция эквивалентности обладает сочетательным свойством.

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

Используя правило поглощения , получаем формулу:


Выполняя операцию с номером 5, будем иметь
Остается выполнить операцию отрицания. Выполнив её,
используя закон де Моргана, получим формулу

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

Если любую формулу алгебры логики можно свести к некоторой другой равносильной формуле, содержащей только определенную систему операций, то такая система операций называется функционально полной системой операций (ФПСО) или базисной. В алгебре логики такой ФПСО являются системы операций:

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

Правило склеивания для элементарных дизъюнкций:

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

Пример:

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

Правило поглощения для элементарных дизъюнкций:

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

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

НДФ – это дизъюнкция нескольких элементарных конъюнкций.

СНДФ – форма, все члены которой имеют высший ранг, являясь
конституентами единицы или нуля

Общая запись любой логической функции в СНДФ имеет вид:




Иначе говоря, значение определяет факт вхождения в .
При конституента входит в , а при – не входит.

В общем случае переход к СНДФ и СНКФ осуществляется за три
шага.

1. Путем многократного применения закона отрицания снимаются групповые и общие отрицания так, чтобы они оставались только у одиночных переменных.
2. С помощью распределительных законов производится переход к одной из нормальных форм функций:
а) для перехода к НДФ применяется распределительный закон первого
рода [раскрываются скобки, т.е. ];
б) для перехода к НКФ применяется распределительный закон второго
рода [вводятся скобки, т.е ;
3. С помощью правила развертывания производится преобразование членов НДФ или НКФ в соответствующие конституенты.

Переход от одной формы логической функции к другой можно осуществить, используя таблицу истинности. Для этого надо по заданной формуле построить таблицу истинности. Для в всех 1 в столбце функции составить КЕ, соединив их знаком . Для всех 0 в столбце функции составить КН, заключив их в скобки и поставив между ними знак .

1) расчетный метод – метод непосредственных логических
преобразований;

2) табличный метод – метод карт Карно или Вейча – Карно;

3) расчетно-табличный метод Квайна.

1. Переход от СНД(К)Ф к сокращенной сНД(К)Ф путем
выполнения всех возможных склеиваний друг с другом сначала
конституент, а затем всех членов сумм (произведений) более
низкого ранга до тех пор, пока склеивание возможно.

2. Переход от сНД(К)Ф к тупиковой нормальной
дизъюнктивной (конъюнктивной) форме (ТНД(К)Ф) путем
устранения избыточных импликант.

3. Переход от ТНД(К)Ф к минимальной форме (МНД(К)Ф) логической функции.

Карта Карно для 3 – х переменных:

Пример:

1.6.3. Расчётно-табличный метод минимизации (метод Квайна)

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

Будем считать, что каждая переменная в формуле алгебры логики соответствует одному входу в некоторой логической схеме. Над одной переменной x в алгебре логики, как мы знаем, может выполняться единственная операция отрицания. Для реализации операции отрицания логической схемой необходимо, чтобы эта схема имела один вход x и один выход , и в виде схемы это будет выглядеть так:

или

На вход логической схемы могут подаваться уже инвертированные сигналы. Тогда 3-входовые схемы И и ИЛИ будут соответственно такие:

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