Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Можно считать, что компьютеры состоят из последовательностных схем, указанных на рис. 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) не сравнимы).

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

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 ₂

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

x₁ ® x₂ = `x₁ + x₂ (5.1.10)

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

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

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

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