Операция «импликация»

a	b	ab
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	1	0	1

Импликация читается так: из a следует b (a  b). Из табл. 2.2 видно, что справедливо выражение

, (3.1)

которое будет широко использоваться в предикатах первого порядка.

Существуют следующие правила для Булевой алгебры:

1) aa = a,

2) aa = a

3)  ,

4)  ,

5) a1 = 1,

6) a1 = a,

7) a0 = a,

8) a0 = 0.

Законы Де Моргана

,

.

Доказательство равнозначности может иметь разновидности:

1) поэлементное сравнение (семантическое преобразование),

2) синтаксическое преобразование (построение правильно построенных форм в соответствии с правилами алгебры логики).

Первая разновидность показана в табл. 2.2.

При синтаксическом преобразовании ведется построение так называемых правильно построенных (по определенным правилам) форм и возможны три варианта:

1) прямое преобразование левой части в правую;

2) нахождение равных промежуточных значений;

3) доказательство истинности или ложности.

Приведем пример для второго варианта.

.

Преобразуем левую часть

.

Преобразуем правую часть

.

Обе части равны и исходное равенство справедливо.

Покажем доказательство либо истинности, либо ложности.

Результирующее выражение истинно и исходное выражение справедливо.

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

Булева алгебра отличается однозначностью. Однако она не может оперировать множествами и подмножествами, а использует операции только с отдельными элементами. Иными словами, в ней отсутствует понятие «квантор».

К моменту поиска аппарата для МЛВ появилась необходимость описывать не только дискретные, но и непрерывные процессы, для чего необходимо использовать непрерывные функции.

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

Алгебра логики не дает ответа на этот вопрос. Названные причины привели к тому, что Булева алгебра не может быть использована для МЛВ.

3.3. Предикаты первого порядка

Пусть имеется n исходных множеств X, что запишем как Xⁿ.

Если осуществляется преобразование: Xⁿ  X, то говорят об алгебре.

Если осуществляется преобразование: Xⁿ  {0, 1}, то говорят об отношениях.

Исчисление – совокупность правил оперирование с каким-либо символом (предикатами).

Предикат (сказуемое) – отношение между множествами элементов, соответствующих аргументов. Например: Q (a₁, a₂, … a_n), где a_n – аргументы, Q – предикат.

Предикаты первого порядка «наследуют» кванторы от традиционной логики и строгую логику алгебры логики. Предикат является предикатом первого порядка, если квантор не входит в сам предикат. Предикаты первого порядка охватывают большую часть отношений. Доказано, что в ряде частных случаев предикаты более высокого порядка могут быть сведены к предикатам первого порядка. Хотя предикаты первого порядка не позволяют [12] описывать возможность и необходимость, убеждения, намерения, цели, метазнания (знания о знаниях), они охватывают широкий спектр возможностей и получили широкое распространение в построении ЭС.

Выделяют 3 вида аргументов предиката: абстрактные Q(X, Y) или отец (X, Y), конкретные Q(a, b) или отец (Иван, Петр), анонимные Q(-, b), где _ ставится в случае, когда конкретная величина аргумента не имеет значения.

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