Множества логических переменных

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

1. Аксиома двойного отрицания:

2. Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции):

3. Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):

4. Аксиомы одинаковых операндов:

5. Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения):

6. Аксиомы распределения операции (дизъюнкции относительно конъюнкции и наоборот):

7. Аксиомы де Моргана (перенесения бинарной операции на операнды):

8. Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):

9. Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем,

Из этих аксиом следует ряд полезных соотношений, например,

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

Итак, эти операции определяются совмещенной таблицей значений вида

Такая таблица всех значений некоторой логической функции называется таблицей истинности этой функции.

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

Всегда истинные формулы называют тавтологиями.

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

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

Логические функции позволяют эффективно решать так называемые инфологические (информационно-логические) задачи, доказывать утверждения.

Информационно-логическая (инфологическая) задача – это задача, в которой необходимо установить некоторые информационные или логические связи и сделать необходимые причинно-следственные логические выводы. Эти задачи возникают в различных областях и часто являются плохо формализованными и структурированными. Их нужно хорошо формализовать и структурировать. Насколько хорошо будет возможно это сделать – настолько хорошо и полно будет решена рассматриваемая проблема или задача. Рассмотрим пример информационно-логической задачи (например, решаемой следователем, знакомым с алгеброй предикатов).

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

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

Алгебра логики

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

1. Аксиома исключения третьего : либо имеет место высказывание, либо его отрицание.

2. Аксиома противоречия : высказывания и его отрицание не могут иметь места одновременно.

3. Аксиома двойного отрицания : двукратное отрицание какого-либо утверждения равносильно исходному утверждению.

4. Аксиома тождества : всякое высказывание тождественно самому себе.

Размещено на Allbest.ru

Источники

1. НОУ ИНТУИТ [Электронный ресурс]/Введение в информатику. История; Автор: Олег Спиридонов; Режим доступа: http://www.intuit.ru, свободный.

2. НОУ ИНТУИТ [Электронный ресурс]/Системы счисления и действия в них; Автор: Майя Головицына; Режим доступа: http://www.intuit.ru, свободный.

3. Slideshare [Электронный ресурс]/Арифметические действия в позиционных системах счисления; Режим доступа: http://www.slideshare.net, свободный.