Лекция 4 . Информационно-логические основы вычислительной техники (продолжение)

Лекция 4. Информационно-логические основы вычислительной техники (продолжение)

 

Основные понятия и законы алгебры логики

 

4.1. Основные определения алгебры логики

 

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

Высказывание – утверждение, которое может быть истинным («да») или ложным («нет»). Одно и то же высказывание не может быть одновременно истинным и ложным. Поэтому в алгебре логики рассматриваются только 2 значения высказываний:

· истинное (ему ставится в соответствие значение 1);

· ложное (ему ставится в соответствие значение 0).

 

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

Логические переменные величины и функции от них, которые могут принимать только 2 значения – 0 и 1, называются логическими или булевскими переменными и функциями. Значение логической функции зависит от конкретного сочетания значений всех ее n аргументов - набора аргументов.

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

 

Законы и правила упрощения логических функций

 

Соотношения, законы и правила алгебры логики

 

В алгебре логики имеют место следующие соотношения и действуют следующие законы (слайд 15).

Соотношения

 

Законы отрицания (инверсии)

 

а) отрицание конъюнкции

Отрицание от конъюнкции равно дизъюнкции отрицаний.

 

б) отрицание дизъюнкции

Отрицание от дизъюнкции равно конъюнкции отрицаний.

Переместительный закон

 

Логические функции И и ИЛИ подчиняются переместительному закону:

 

Сочетательный закон

 

Логические функции И и ИЛИ подчиняются сочетательному закону:

 

 

Правило склеивания для ДНФ

 

а) (для 2 переменных)

 

.

 

б) (для 3 переменных)

 

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

 

Правило поглощения для ДНФ

 

а) (для 2 переменных)

 

XVXY = X.

 

б) (для 3 переменных)

 

XVX Λ YVX Λ Y Λ Z = X.

 

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

Из второй формы дистрибутивного закона вытекает правило свертки (слайд 18).

 

Правило свертки для ДНФ

a)

или

 

b)

 

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

Аналогичные формулы существуют для преобразования конъюнктивных нормальных форм (слайд 18).

 

Правило склеивания для КНФ

 

 

Правило поглощения для КНФ

 

 

Правило свертки для КНФ

Пример 5. Пусть логическая функция задана аналитически:

 

 

Требуется упростить функцию (получить ее минимальную форму) (слайды 19-20).

 

· Преобразуем член с инверсией:

 

 

· Раскроем скобки:

 

(конъюнкция )

· Преобразуем член с конъюнкцией:  

 

{ раскрываем скобки } =

 

· Подставляем преобразованные выражения в исходную формулу:  

 

Это нормальная дизъюнктивная форма. Применяя к ней правила склеивания и поглощения, можно ее упростить:

 

· к 1-му и 2-му членам применим правило склеивания:

 

 

· к 3-му и 5-му членам применим правило поглощения:

 

 

Получим:

 

 

Результат не подлежит дальнейшему преобразованию (упрощению). Следовательно, минимальная форма исходной функции:

 

Лекция 4. Информационно-логические основы вычислительной техники (продолжение)

 

Основные понятия и законы алгебры логики

 

4.1. Основные определения алгебры логики

 

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

Высказывание – утверждение, которое может быть истинным («да») или ложным («нет»). Одно и то же высказывание не может быть одновременно истинным и ложным. Поэтому в алгебре логики рассматриваются только 2 значения высказываний:

· истинное (ему ставится в соответствие значение 1);

· ложное (ему ставится в соответствие значение 0).

 

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

Логические переменные величины и функции от них, которые могут принимать только 2 значения – 0 и 1, называются логическими или булевскими переменными и функциями. Значение логической функции зависит от конкретного сочетания значений всех ее n аргументов - набора аргументов.

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