5.1.2. Точная логика

Можно считать, что компьютеры состоят из последовательностных схем, указанных на рис. 5.4.

Каждая из n входных переменных и каждая из m выходных переменных в некоторый момент времени имеют одно из двух значений: 0 или 1. Кроме того, эти переменные изменяются одновременно по базовому сигналу управления, называемому тактовым импульсом. Если отношение входов и выходов записать в виде функции, то получим:

y_j(t + 1) = f_j(x₁(t), x₂(t), ..., x_n(t), y₁(t), y₂(t), ..., y_m(t)), j = 1, ..., m. (5.1.5)

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

Рисунок 5.4. Последовательностная схема

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

y_j = f_j(x₁, x₂, ..., x_n), j = 1, ..., m. (5.1.6)

Здесь m выходных переменных, но их уже можно рассматривать по отдельности одну за другой, поэтому без ограничения общности можно считать число выходов равным 1. Другими словами, можно рассматривать n входов и один выход. При этом отношение входов и выхода можно обозначить как

f:{0, 1}ⁿ{0, 1},

 

(x₁, x₂, …, x_n)y = f(x₁, x₂, …, x_n). (5.1.7)

Такая функция f называется булевой функцией n переменных, а её конкретная реализация - комбинаторной системой.

Прежде всего, рассмотрим наиболее простой случай n = 1:

f:{0, 1}{0, 1}

 

x y = f(x). (5.1.8)

Как показано на рис. 5.5, б, в этом случае существуют четыре отношения входа и выхода. Среди них важна операция НЕ; элемент, реализующий эту операцию, носит название инвертора или вентиля НЕ (рис. 5.5, в). Кроме того, на рис. 5.5, г представлена диаграмма Хассе, задающая последовательность этих четырех операций: 0 и 1 сравниваются поразрядно, выше размещаются пары с большими значениями. Пары, которые можно сравнивать соединены линиями (в этом случае х их не соединены линией, поскольку (0, 1) и (1, 0) не сравнимы).

Вход Выход y=f(x)

x		x	x	I
0	0	0	1	1
1	0	1	0	1

I O

x y

 

{0,1} {0,1}

а б

I(1,1)

x x x(0,1) x(1,0)

НЕ (0,0)

в г

Рисунок 5.5

Далее рассмотрим случай двух входов:

f:{0, 1}²{0, 1}

 

(x₁, x₂)y = f(x₁, x₂). (5.1.9)

В этом случае существует 16 отношений входов и выхода (рис. 5.6, а). Среди них - самые важные операции И, ИЛИ, НЕ-И, НЕ-ИЛИ, исключающее ИЛИ - EXOR (рис. 5.6, в). Если подобным образом рассмотреть схемы для n = 3 и n = 4, то найдем 2²ⁿ комбинаторных схем с входами и одним выходом. Поэтому уже при n = 4 их число достигает 65536, т. е. происходит комбинаторный взрыв. Однако достаточно изучить схемы до n = 2. Дело в том, что справедливы следующие три равнозначных утверждения.

1. Любую булеву функцию f(x₁, x₂, ..., x_n) можно синтезировать путем применения к входным переменным x₁, x₂, ..., x_n операций НЕ, И, ИЛИ.

2. Любую булеву функцию f(x₁, x₂, ..., x_n) можно реализовать с помощью синтеза операций НЕ-И над входными переменными x₁, x₂, ..., x_n.

3. Любую булеву функцию f(x₁, x₂, ..., x_n) можно реализовать с помощью синтеза операций НЕ-ИЛИ над входными операциями x₁, x₂, ..., x_n.

x1	x2		x1x2	x1/x2	x1	x2/x1	x2	x1 x2	x1+x2			x2		x1			I
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

И Исключающее ИЛИ ИЛИ НЕ-ИЛИ НЕ-И

а

I О

x ₁

x₂ y

 

{0,1} {0,1}

б

И ИЛИ НЕ-И НЕ-ИЛИ Исключ. ИЛИ

в

Рисунок 5.6

Если представить эти утверждения в терминах аппаратных средств, получим:

а) любую комбинаторную схему можно построить только с помощью инверторов, вентилей И и ИЛИ;

б) любую комбинаторную схему можно построить только с помощью вентилей НЕ-И;

в) любую комбинаторную схему можно построить только с помощью вентилей НЕ-ИЛИ.

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

Однако в компьютерах искусственного интеллекта и прежде всего в компьютерах пятого поколения, в нечётких компьютерах, основанных на нечётких логических выводах (приближенных рассуждениях), удобно на первый план выдвинуть операции, отличные от этих базовых операций. Одна из них соответствует операции , приведённой на рис. 5.6, а. Она называется импликацией. Обычно эту операцию обозначают стрелкой: x₁x₂ и читают так: если x₁, то x₂. Здесь x₁ называют антецедентом, предпосылкой, условием, допущением, а x₂ - заключением, выводом, операцией. Если представить в виде таблицы истинности значения операции импликации, то получим табл. 5.1.

Таблица 5.1. Таблица истинности операции импликации x₁x₂

x1	x2	x1x2
0	0	1
0	1	1
1	0	0
1	1	1

Можно доказать, что операцию импликации можно реализовать с помощью полной системы НЕ, И, ИЛИ следующим образом:

x₁  x₂ = x₁ + x₂ (5.1.10)

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

x1x2

x2x3

x1x3

(5.1.11)

представляет собой вывод из утверждения "если птица, то летает”, “если летит, то направляется на остров" заключения "если птица, то направляется на остров". Формула

x1x2

x1

x2

(5.1.12)

представляет вывод из утверждения "если птица, то летает" и "это животное летает". Следующая формула

x1x2

x2

x1

(5.1.13)

представляет собой вывод из утверждений "если птица, то летает" и "это животное не летает", и заключения "это животное не птица" (при этом исключения мы не принимаем во внимание). При изучении нечётких выводов с расчётом на их применение важное значение имеет формула (5.1.12), называемая "модус поненс". Кроме того, вывод x₁x₂ типа "если птица, то летает" или знания типа "если - то ..." называют процедурными знаниями, а знания типа утверждения "это животное - птица” - декларативными знаниями.