Логическое и функциональное программирование (стр. 4 из 16)

Функция F10 носит название функции равнозначности или эквивалентности и обозначается:

Функции F12 и F14 носят название импликации. Для их обозначения будем использовать:

Здесь следует отметить, что импликация соответствует высказыванию «Если А, то В». При этом возникает ситуация, что это высказывание с ложным А и истинным В истинно. Прежде всего, это соглашение, причем это соглашение ничему не противоречит. В повседневном языке утверждения с ложным А не употребляются.

Пример типа «Если бы я был космонавтом, я бы полетел на Луну» не опровергает наше утверждение. Здесь 1. Имеем дело не с «Если А, то В», а с «Если бы А, то бы В»; 2. Считать ложным такое утверждение не имеет смысла.

Возникает вопрос, можно ли бы было при ложном А, считать ложным высказывание «Если А, то В». В принципе можно, но математическая практика показывает, что выбранный нами вариант удобнее.

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

является также корнем уравнения

Это высказывание мы считаем верным, хотя исходное уравнение может вовсе не иметь корней. Ясно, что здесь мы использовали введенное соглашение.

Функция F15 носит название отрицание конъюнкции или штрих Шеффера. Для ее обозначения используется:

Оставшиеся функции F3 и F5 назовем отрицание импликации:

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

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

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

Функции F7, F9, F15, F5, F3 уже выражены через эти операции. Выразим функции F10, F12, F14.

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

Алгебраически перечисленные выше операции можно выразить следующим образом:

Отрицание (дополнение):

Конъюнкция:

Дизъюнкция:

Тогда:

Сумма по модулю 2:

Стрелка Пирса:

Эквивалентность:

Импликация:

Штрих Шеффера:

Отрицания импликации:

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

Законы булевой алгебры.

Для удобства разобьем законы на четыре группы.

Первая группа.

1.

(закон коммутативности для дизъюнкции).

2.

3.

(первый закон поглощения).

4.

(второй закон дистрибутивности).

5.

(закон идемпотентности для дизъюнкции).

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

1¢.

(закон коммутативности для конъюнкции).

2¢.

(закон ассоциативности для конъюнкции).

3¢.

(второй закон поглощения).

4¢.

(первый закон дистрибутивности)

5¢.

(закон идемпотентности для конъюнкции).

Каждый из законов 1¢ - 5¢ называется двойственным к соответствующему закону 1 – 5.

Вторая группа

1.

2.

3.

4.

5.

6.

Третья группа

1.

(закон двойного отрицания).

2.

3.

Четвертая группа

1.

2.

(закон контрапозиции).

3.

Сформулируем некоторые полезные следствия из приведенных законов.

С1. Выбрасывая из произвольной дизъюнкции дизъюнктивные элементы равные нулю, мы не изменим величину этой дизъюнкции.

С2. Если в дизъюнкции хотя бы один из элементов равен 1, то вся дизъюнкция равна 1.

С3. Выбрасывая из произвольной конъюнкции все сомножители равные 1, мы не изменим ее величины.

С4. Если в конъюнкции хотя бы один сомножитель равен 0, то все произведение равно 0.

С5. Дизъюнкция или произведение любого числа одинаковых элементов равняется А.

Эти следствия можно доказать по индукции.

С6. Если А(а1, . . ., ап) произвольное выражение булевой алгебры, построенное из выражений а1, . . ., ап с помощью операций отрицания, дизъюнкции и конъюнкции, то отрицание этого выражения равняется

, где В(а1,…,ап) получается из А с помощью замены всех умножений на дизъюнкции, а всех дизъюнкций на умножения, при условии сохранения всех имевшихся в А отрицаний.

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

Нормальные формы

Элементарной дизъюнкцией называется выражение,

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

В силу определения:

являются элементарными дизъюнкциями, а

не являются.

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

Неэлементарные произведения: Переменные и их отрицания называются первичными термами или литералами.