Принцип построения когнитивной карты.

При составлении когнитивной матрицы эксперту потребуется все время отвечать на вопросы:

1) Какой концепт явл. причиной, а какой следствием?

2) Какое действие на один концепт окажет усиление другого концепта (усиление / ослабление)?

3) В какой степени ослабится или усилится концепт? "Усиление–ослабление " носит абстрактный характер, и эксперту необходимо проставить веса у дуг (проинтерпретир. релевантную причинно–следств. связь).

Т. о. эксперт определяет наиб. важные, непосредств. связи между концептами (связи, кот. существуют в представлении экспертов в «явном» виде).

Контуры положит. и отриц. обратной связи.:

Контуры в знаковом орграфе соответствуют контурам обратной связи; контуры, усил. отклонение — контурам положит. обратной связи, а контуры, противодейств. отклонению — контурам отриц. обратной связи.

Контур, усил. отклонение — контур, в кот. увеличение (уменьшение) любой переменной приводит к ее последующему увеличению (уменьшению).

Контур, противодейств. отклонению — контур, в кот. увеличение любой переменной приводит (через другие переменные контура) к ее уменьшению и наоборот.

Неустойчивость системы — когда в ней много контуров, усил. отклонение.

Устойчивость системы проверяется математически:

1) Строится весовая матрица смеж. A (веса = +1 или -1).

2) Находятся все собственные значения λ матрицы A: , где I — единич. матрица.

3) Если все собств. знач. , то система устойчива.

44. Сети Петри. Аналитическое задание. Функционирование сети Петри. Конечные разметки сети. Основные свойства сети Петри: К-ограниченность, безопасность, сохраняемость, достижимость, покрываемость, живость.

Сеть Петри определяется как двудольный граф. Т.е. все вершины графа относятся к одному из двух классов — позициям (местам) и переходам.

Позиции изображаются окружностями, переходы — направленными дугами. Каждая дуга связывает вершины только разных классов.

Аналитическое задание.:

Сеть Петри — набор , где P — множ. вершин, T — множ. переходов, I:T®P* — соответствие между множ. переходов и вершин, задающее входные позиции каждого перехода. О:T®P* — соответствие между множ. переходов и вершин, задающее выходные позиции каждого перехода, M₀ – начальная разметка сети.

Разметку сети до срабатывания любого перехода называют начальной разметкой. Затем срабатывает какой-либо переход и разметка сети меняется. После этого изменения какой-либо переход может перестать срабатывать или наоборот.

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

Разметку сети при завершении процесса срабатывания называют конечной разметкой.

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

Конечные разметки сети.:

Одна из основных проблем в теории сетей Петри — это задача о конечности функционирования сети (т.е. о достижении тупиковой разметки, «смертельные объятия»). Тупиковая разметка — разметка, при которой ни один переход не может сработать.

Основные свойства:

· K-oграниченность — число меток в любой позиции сети не может превысить некоторого значения K.

· Позиция р называется безопасной, если для любой разметки сети M кол-во фишек M(p) £ 1; сеть безопасна, если все ее позиции безопасны. Любая достижимая в безопасной сети разметка представляет собой вектор из 0 и 1.

· Сохраняемость — св-во сети, хар-зующее невозмож. возник. или уничтож. ресурсов в моделир. объекте.

· Разметка М достижима в сети Петри, если существует цепочка срабатываний переходов, ведущая из начального состояния в М.

· Разметка М'=(P₁'...P_n') покрывает состояние М”=(P₁"...P_n"), если для каждого i=1,...,n имеет место P_i' ≥ P_i", т.е. имеет место М' ≥ М”.

· Живость — свойство сети, означающее, что из любого состояния, достижимого из начального, возможен переход в любое другое достижимое состояние.

45. Эквивалентность и включение сетей Петри. Построение дерева достижимости сети Петри.

Сети Петри эквивалентны, если они имеют одинаковое множ. достижимых состояний или множ. реализуемых последовательностей переходов.

Сеть СП1, включается в СП2, если поведение СП1 явл. подмнож. поведения СП2.

Вершинами дерева достижимости явл. разметки сети.

Дерево достижимости представляет все достижимые разметки сети Петри, а также — все возможные последовательности запусков её переходов.

Построение дерева:

3. Если в дереве есть вершина y, с той же маркировкой (m[x]=m[y]), то х — дублирующая вершина.

4. Если для маркировки m[х] ни один из переходов не разрешен, то х — терминальная.

5. В противном случае, для всякого перехода ti разрешенного в m[х], создаётся новая вершина z дерева достижимости. Маркировка m[z] для позиции pi, определяется по следующим правилам:

1) Если m[х](pi)=w, то m[z](pi)=w.

2) Если на пути от корня к z существует вершина y такая, что все позиции имеют маркировки , чем для вершины z, то маркировка позиции pi, для которых m[z](pi) > m[y](pi), следующая m[z](pi)=w.

6. Строится дуга с меткой ti, направ. от вершины x к вершине z. Вершина х становится внутр., а вершина z — граничной.

7. Алгоритмом останавливается если все вершины дерева станут терминальными, дублирующими.

46. Виды сетей Петри: временная, стохастическая, функциональная, цветная, ингибиторная. Использование сети Петри для проверки абстрактного сценария. Сеть Петри для задачи об обедающих философах.

Временная сеть Петри — переходы обладают весом, опред. продолжит. срабатывания (задержку).

Стохастическая сеть Петри — задержки явл. случайными величинами.

Функциональная сеть Петри — задержки определяются как функции аргументов (например, кол-ва меток в позициях, состояния переходов).

Цветная сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.

Ингибиторная сети Петри — возможны ингибиторные дуги, запрещающие срабатывание перехода, если во входной позиции, связанной с переходом ингибиторной дугой находится метка.

Сеть Петри использ. для выявл. ошибок абстрактного сценария системы. С этой целью сценарий трансформир. в сеть Петри и провер. ее св-ва.

Применительно к сценарию проверяются 3 св-ва:

1) Сеть Петри должна быть ограниченной.

2) При работе сети Петри не должны появл. неконечные тупиковые состояния, в которых не активирован ни один переход.

3) При работе сети Петри не должно возникать "ловушек" — циклов без выхода (если объект попал в нее, будет циклич. циркулир., но не сможет выйти).

Сеть Петри для задачи об обедающих философах:

Была предложена Дейкстрой.

5 философов гуляют в саду и размышляют. Когда философ чувствует голод, он заходит в столовую, где стоит круглый стол с 5 стульями и миской спагетти посреди стола. На столе — пять вилок, по одной слева и справа от каждого стула. Философ берет 2 вилки и ест спагетти. Утолив голод, философ кладет вилки на стол и выходит в сад размышлять, пока вновь не почувствует голод.

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

Пример решения: запрет на присутствие в столовой более 2-х философов (доп. позиция с 2-мя маркерами), запрет на соседство 2-х философов (доп. позиция с 1 маркером).

47. Логическое представление исследуемой системы. Простые и сложные высказывания. Логич. операции. Таблица истинности и таблица Кэли. Конверсия, инверсия, контрапозиция. Необходимое, достаточное, необходимое и достаточное условия.

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

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

Высказывание — повествоват. предложение, о кот. имеет смысл говорить, что оно истинно или ложно.

Простые высказывания рассм. в данном контексте как неделимое целое (аналог эл-та множества).

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

Логическая операция – функция, завис. от логических переменных (= 0,1), кот. может быть = 2 знач: 0 и 1.

Логическая операция — функция вида f(x1,x2,…xn): Bⁿ→B, где В — множ., состоящее из 2 эл-тов В={0,1}.

В таблице истинности для бинар. операций первые 2 столбца содержат все возмож. наборы операндов, а последующие столбцы — значения логич. функций.

Таблица Кэли:

&				^

Пусть определена импликация А®В, тогда для этого выражения можно построить:

1) Конверсию В ® А;

2) Инверсию ù А ®ù В;

3) Контрапозицию ù В ® ù А.

Высказывания явл. равносильными, если для всех наборов переменных совпадают их значения.

Равносильны:

1) Конверсия В®А и инверсия ù А ® ù В.

2) Импликация А®В и контрапозиция ù В ® ù А.

Импликации A ® B, кроме очевидных «Если А, то В», «А влечет В», соответствуют следующие словесные обороты:

1) «А достаточно для В»: «Делимость числа на 12 достаточное условие для делимости числа на 6». При выполнении А (делимости на 12) всегда наступает В (делимость на 6) A ® B. Равносильно «Если число делится на 12, то оно делится и на 6».

2) «В необходимо для А»: «Делимость числа на 2 необходимое условие делимости числа на 6». Невыполнение В (на 2 не делится) влечет не выполнение А (на 6 не делится), т.е. выполняется контрапозиция ùВ®ùА. Как показано раннее, контрапозиция равносильна импликации A®B. «Если k делится на 6, то оно делится на 2».

48. Основные схемы логически правильных рассуждений.

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

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

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

Исходные высказывания называются посылками (гипотезами, условиями), а получаемые высказывания — заключением (следствием ).

Для построения логических формул, отражающих логически правильные рассуждения, следует все посылки соединить конъюнкцией & и полученную таким образом обобщенную посылку связать импликацией ® с выводом: ((A®B)&A)®B.

Правило заключ. — утвержд. модус:

Правило отрицания — отриц. модус:

Правило утв.–отриц.:

Правило транзитивности:

Закон противоречия:

Правило контрапозиции:

Сведение к абсурду:

49. Алгебра логики. Бинарные логические операции. Существенные и несущественные (фиктивные) переменные. Функционально полные системы (базисы). Булева алгебра логики. Законы булевой алгебры. Примеры других алгебр логики.

Матем. логика: логика высказ. и логика предикатов.

Логика высказываний может быть представ. 2-мя подходами: алгеброй логики (высказываний) и исчислением высказываний.

Алгебра логики — алгебра, образованная множ. B={0,1} вместе со всеми возможными операциями на нем.

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

Переменная x_i в функции f(x₁,…, x_i–1, x_i, x_i+1, …, x_n) называется несущественной (фиктивной), если f(x₁,…, x_i–1, 1, x_i+1, …, x_n) = f(x₁,…, x_i–1, 0, x_i+1, …, x_n) при любых значениях остальных переменных. В противном случае — существенная переменная.

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

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

Алгебра (Р₂; &, Ú, Ø), основным множ. которой явл. множ. всех логических функций Р₂, а операциями дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических операций. Явл. наиболее изученной. Формулы, содержащие кроме переменных и скобок знаки этих функций называются булевыми.

Законы булевой алгебры:

1) ассоц.: aÚ(bÚc)=(aÚb)Úc, aÙ(bÙc)=(aÙb)Ùc;

2) коммут.: aÚb=bÚa, aÙb=bÙa;

3) дистр.: aÙ(bÚc)=(aÙb)Ú(aÙc); aÚ(bÙc)=(aÚb)Ù(aÚc);

4) иденп.: aÚa=a; aÙa=a;

5) инвол. (двойного отрицания) ØØa=a;

6) св-ва 0: aÚ0=a, aÙ0=0;

7) св-ва 1: aÚ1=1, aÙ1=a.

8) де-Моргана: ØaÚØb=Ø(aÙb), ØaÙØb=Ø(aÚb);

9) св-ва дополнения: aÙØа=0; aÚØа=1;

10) поглощения aÚaÙb=a, aÙ(aÚb)=a;

11) склеивания aÙb Ú aÙØb =a, (aÚb)Ù(aÚØb)=a;

12) обобщенное склеивание aÙc Ú bÙØc Ú aÙb = aÙc Ú bÙØc;

13) a Ú ØaÙb = aÚb

# алгебр логик (функционально полных базисов):

1){&, Ú,1}

2){o} (Функция Вебба),

3){½} (штрих Шеффера);

4){®, 0}, {, 1},

и др.

50. Суперпозиция булевых функций и ее формула. Глубина формулы. Таблицы истинности для сложных формул. Эквивалентность формул. Тождественно истинная, тождественно ложная и выполнимая функция. Единичный и нулевой набор функции.

Суперпозицией F булевых функций f₀ и f₁,...,f_m называется функция F=f₀(g₁(x1,...,xm),...,g_n(x1,...,xm)), где каждая из функций g_i(x1,...,xm) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f₁,...,f_m.

Формулой называется выражение, описывающее эту суперпозицию.

Символы переменных, а также функции const_0 и const_1 считаются формулами глубины 0.

Глубина формулы:

Определить глубину формулы F= ((А→В)&C) ÚA.

1) Вначале выполняется f1= А→В. Глубина которой k1=max(0,0)+1=1

2) Следующей будет выполняться функция f2=f1&C. Функция f2 имеет глубину k2=max(k1,0)+1=max(1,0)+1=2

3) Далее выполнятся функция f3=f2ÚA, глубина которой k3=max(k2,0)+1=max(2,0)+1=3

Таким образом, глубина исходной формулы равна 3.

Таблицы истинности для сложных функций строится поэтапно, путем выделения простых функций согласно последовательности их выполнения.

#: Таблица истинности для формулы F= ((А→В)&C)ÚA:

A	B	C	A→B	f1&C	f2ÚA

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

Формула называется тождественно истинной (общезначимой, тавтологией), если при всех возможных наборах переменных формула равна 1

Формула называется тождественно ложной (противоречием), если при всех возможных наборах переменных формула равна 0.

Формула называется выполнимой, если при некоторых наборах переменных формула равна 1.

Единичным набором переменных называется набор переменных, при которых функция равна 1. Множ. единичных наборов называется единичным множеством.

Нулевым набором переменных называется набор переменных, при которых функция равна 0. Множ. нулевых наборов называется нулевым множеством.

51. Формы записи формул (функций) — инфиксная, префиксная, постфиксная. Преобразования формул: инфиксная в префиксную и постфиксную, префиксная в инфиксную, постфиксная в инфиксную.

___Инфиксная – знак операций стоит между операндами (используемая нами до сих пор) x Ù(y Ú z) или x and (y or z);

___Префиксная (прямая польская запись) – знак операций стоит перед операндами Ù x Ú y z;

__Постфиксная (обратная польская запись) – знак операций стоит после операндов x y z Ú Ù

Дата добавления: 2015-11-16