Реферат: Логическое и функциональное программирование

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

Функция F2 носит название конъюнкции или произведения или логического И. Для ее обозначения используется либо знак умножения, либо Ù. Отсюда:

Функция F7 носит название функции неравнозначности или суммы по модулю два. Для ее обозначения будем использовать:

Функция F8 носит название дизъюнкции или логическое ИЛИ. Для ее обозначения принято использовать знак Ú:

Функцию F9 будем называть отрицанием дизъюнкции или стрелкой Пирса, и обозначать через:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конъюнкция:

Дизъюнкция:

Тогда:

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

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

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

Импликация: