3. Высказывания и предикаты

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

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

Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции).

Совокупность операций алгебры A называется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры.

Утверждение (высказывательная форма) – основная единица, неделимая с точки зрения отражения смысла информации (семантики).

Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь", "true" и "fаlse" или "1" и "0".

Переменная, значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.

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

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

Пример. Выражение "х = у" – предикат, "х > 5" – предикат, а "7 > 5" – высказывание.

Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.

Пример. Заданы предикаты вида р = "число х делится нацело на 3" и q = "у – день недели". Найдем множество истинности предикатов р и q, если x{1,4,6,16,20,24}, y{первый, второй, четверг, 1999, зима, выходной, праздник, воскресенье}. Получаем, что R(p) = {6, 24}; R(q) ={четверг, воскресенье}.

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

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

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

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

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

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

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

, .

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

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

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

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

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

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

0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

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

Пример. Составим таблицу истинности функции . Эта таблица имеет вид

0	0	1	0	0	1
0	1	1	1	0	1
1	0	0	0	0	1
1	1	0	0	0	1

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

.

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

1. Импликация – принимает значение “ложно”, тогда и только тогда, когда первое высказывание x (посылка, причина) “истина”, а второе у (заключение, следствие) – “ложно”. Формула перехода: . (!) Составьте самостоятельно таблицу истинности для .

2. Эквивалентность формул означает совпадение их значений истинности для всех возможных наборов входящих в них переменных. Формула перехода: . (!) Составьте самостоятель-но таблицу истинности для .

3. Тавтология – это формула, истинная при любой интерпретации входящих в нее переменных. (!) Составьте таблицу истинности для .

4. Противоречие – это формула, ложная при любой интерпретации входящих в нее переменных. (!) Составьте самостоятельно таблицу истинности для .

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

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

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

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

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

Пример. Упростим:

=(аксиома дистрибутивности)=

=(аксиома нейтральности)=

=(аксиома дистрибутивности)=

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

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

Левая часть равенства приведена к правой части, то есть данное равенство доказано полностью.

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

• правая часть равенства приводится к левой части;

• левая часть равенства приводится к правой части;

• обе части равенства приводятся к третьему выражению.

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

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

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

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

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

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

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

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

Если высказывания x и y связаны друг с другом отношением , то говорят, что высказывание y следует из высказывания x (или y – следствие x); если множество истинности Х высказывания х содержит множество истинности Y высказывания y, то высказывание x – условие, высказывание y – заключение, а само соотношение – вывод.

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

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

Контрольный тест №3:

1. Из заданных логических функций тождественно истинной является

   1. А и не А или не А

   2. А и не В или А

   3. А или не А или А

   4. А и не А или В

2. Из заданных логических функций тождественно истинной является

   1. А и не А или В

   2. А и не В или А

   3. А и не А или не А

   4. А или не В или не А

3. Из заданных логических функций эквивалентной А является

   1. А и не А или не А

   2. А и не В или А

   3. А и не А или В

   4. А и не В и А

4. Для простого высказывания В логическое отрицание обозначается

   3. & B

5. Высказыванию «А не является max (A,B,C) и не является min (A,B,C)» соответствует логическое выражение

   1. (A < B) или (A > C) и (A < C) или (A > B)

   2. (A > B) или (A > C)

   3. (A < B) и (A > C) или (A < C) и (A > B)

   4. (A < B) и (A < C)