ЛЕКЦИЯ 15. ОПИСАНИЕ ЗАДАЧ НА ЯЗЫКЕ ЛОГИКИ


 

Рассмотрим описание задач на языке логики. Такое описание потребует формализовать некоторые наиболее часто встречаемые условия.

Прежде всего, таким условием является

 

x1 + x2+ +xn =1, (15.1)

xiÎ{0,1}.

 

Это условие эквивалентно следующей системе логических формул:

 

x1 v x2 v v xn,

Øx1 v Øx2,

Øx1 v Øx3,

Øx1 v Øxn,

Øx2 v Øxn,

Øxn-1 v Øxn.

 

Количество всех дизъюнктов равно +1. Число дизъюнктов можно уменьшить, если использовать дополнительные переменные и провести следующие преобразования.

Обозначим через F следующую систему формул:

 

x1 + x2 + y1 =1,

x3 + x4 + y2 =1,

F

xn-1 + xn + yn/2 =1.

 

Замечание. Если n – нечетное, то последняя формула заменяется на xn + y(n+1)/2 =1.

В F yi - дополнительные переменные.

Теперь система (15.1) оказывается эквивалентной системе

 

 

G

 

В свою очередь формулу Øy1 + Øy2 + … + Øyn/2 = 1 можно заменить эквивалентной системой H:

 

H

 

Следовательно, система становится эквивалентной системе J с булевскими переменными

 

J= . (15.2)

Описанные преобразования по аналогии применяем к системе (15.2) и т. д. до тех пор, пока не останутся только трехлитерные или двухлитерные уравнения вида a+b+c=1 или d+e=1. Каждое трехлитерное уравнение дает 4 дизъюнкта: a v b v c, Øa v Øb, Øa v Øc, Øb v Øc. Каждое двухлитерное уравнение с+d=1 дает 2 дизъюнкта: c v d, Øc v Ød. Следовательно, рассматриваемый способ построения эквивалентной системы дизъюнктов для (15.1) дает не выше 4(n-1) дизъюнктов (уточнение этой формулы требует принять во внимание четность/нечетность n). Приведем пример.

 

 

x1 + x2+ +x10 =1,

xiÎ{0,1}.

 

Последовательно получаем эквивалентные системы:

 

x1 + x2 + y1 =1,

x3 + x4 + y2 =1,

x5 + x6 + y3 =1, (15.3)

x7 + x8 + y4 =1,

x9 + x10 + y5 =1,

Øy1 + Øy2 + Øy3 + Øy4 + Øy5 =1

 

и

 

x1 + x2 + y1 =1,

x3 + x4 + y2 =1,

x5 + x6 + y3 =1, (15.4)

x7 + x8 + y4 =1,

x9 + x10 + y5 =1,

Øy1 + Øy2 + z1 =1,

Øy2 + Øy3 + z2 =1,

Øy5 + z3 =1,

Øz1 + Øz2 + Øz3 =1.

 

Теперь все уравнения (кроме одного) трехчленные. Каждое из них дает 4 дизъюнкта. Всего дизъюнктов 34, вместо +1 = 46.

Рассмотрим другие важные условия.

 

x1 + x2+ +xn £ 1, (15.5)

xiÎ{0,1}.

 

Это условие трансформируется в эквивалентную систему двухлитерных дизъюнктов

Øx1 v Øx2,

Øx1 v Øx3,

Øx1 v Øxn,

Øx2 v Øxn,

Øxn-1 v Øxn.

 

На практике важно условие вида

 

x1 + x2+ … +xn = k , (15.6)

xiÎ{0,1}, k > 1, k £ n, k - целое.

 

Прямое кодирование этого равенства при k=n/2 (n - четное) требует экспоненциально растущего от n числа дизъюнктов. Поэтому следует вводить новые переменные. В целях ясности обратимся к иллюстративному примеру.

 

x1 + x2+ +x8 =3. (15.7)

 

Равенство (15.7) можно заменить следующей эквивалентной системой равенств

 

x1 + y4+ y5+ y6+ y7+y8 =1,

x2 + z4+ z5+ z6+ z7+z8 =1,

x3 + w4+ w5+ w6+ w7+w8 =1,

y4+ z4+ w4 £ 1,

y5+ z5+ w5 £ 1,

y8+ z8+ w8 £ 1,

x4 º y4 v z4 v w4,

x5 º y5 v z5 v w5,

. . .

x8 º y8 v z8 v w8.

 

 

При этом для k первых переменных из (15.8) записываем k равенств вида

 


x1 + yk+1 + yk+2 + yk+3 + …+ yn = 1,

x2 + zk+1 + zk+2 + zk+3 + …+ yn = 1,

. . . (15.9)

xk + wk+1 + wk+2 + wk+3 + …+ wn = 1.

 

 

Пусть x1 = x2== xk = 0. Тогда, например, ya = zb = wc = 1, причем a ¹ b, a ¹ c, , b ¹ c. Следовательно, в силу наших условий, некоторые k переменных из числа xk+1, xk+2,, xn будут иметь единичные значения, обеспечивая условие (15.9). Если, например, x1 = 1, x2 =…= xk = 0, то некоторые (k - 1) переменных (и только они) из числа переменных xk+1, xk+2,, xn будут иметь единичные значения и т.п. Число дизъюнктов для (15.9) составит порядка 4(n - 1). Общее число дизъюнктов для (15.9) составит порядка 4(n - 1)+ (эквивалентности

 

xk+1 º yk+1 v zk+1 v v wk+1,

xk+2 º yk+2 v zk+2 v v wk+2,

xn º yn v zn v v wn

 

в систему дизъюнктов преобразованной задачи нет необходимости включать).

 

Пример 1.1. В хищении подозреваются A,B и C.

1. Никто, кроме A,B,C в хищении не замешан.

2. A никогда не ходит на дело без соучастников.

3. С не виновен, если виновен B.

Спрашивается, виновен ли A?

 

Нужно составить систему логических уравнений, введя необходимые булевские переменные. Обозначим: xa – виновен A, xb – виновен B, xc – виновен C. Составим следующую базу знаний:

 

1. xa v xb v xc ,

2. xa ® xb v xc ,

3. xb ® Øxc .

 

Эти логические формулы соответствуют условиям задачи. Можно воспользоваться арифметическим представлением логических формул. Этот прием даст связь между логическими формулами и рассмотренными выше условиями формализации. Арифметические представления таковы:

 

f v g v v h º f + g+ + h ³ 1,

Øf º (1- f), (15.10)

f ® g º Ø f v g º (1- f) + g ³ 1,

f & g º f + g = 2 º Øf + Øg = 0 º f×g.

Теперь условия нашей задачи получат следующее представление:

 

1. xa + xb + xc ³ 1,

2. (1-xa ) + xb + xc ³ 1.

3. (1-xa ) + (1- xc ) ³ 1.

 

Относительно этой модели знаний поставлен вопрос: верно ли, что xa = 1?

Рассмотрим описание задач на языке логики. Такое описание потребует формализовать некоторые наиболее часто встречаемые условия.

Прежде всего, таким условием является

 

x1 + x2+ +xn =1, (15.11)

xiÎ{0,1}.

 

Это условие эквивалентно следующей системе логических формул:

 

x1 v x2 v v xn,

Øx1 v Øx2,

Øx1 v Øx3,

Øx1 v Øxn,

Øx2 v Øxn,

Øxn-1 v Øxn.

 

Количество всех дизъюнктов равно +1.

Рассмотрим другие важные условия.

 

x1 + x2+ +xn £ 1, (15.12)

xiÎ{0,1}.

 

Это условие трансформируется в эквивалентную систему двухлитерных дизъюнктов

 

 

Øx1 v Øx2,

Øx1 v Øx3,

Øx1 v Øxn,

Øx2 v Øxn,

Øxn-1 v Øxn.

 

 



Дата добавления: 2022-02-05; просмотров: 269;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.028 сек.