test4 - answers (1133188)

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

Текст из файла

Тест 4. Ответы.

Дать определение тождества для формул, и его подстановки

Формулы F’ и F’’, реализующие равные функции f’ и f’’, называются равными или, иначе, эквивалентными. При этом равенство вида t : F’ = F’’ считается тождеством.

формула F (F1, . . . , Fn) реализует ФАЛ f (f1, . . . , fn), где ФАЛ f (ФАЛ fj) — ФАЛ, реализуемая формулой F (соответственно Fj, j = 1, . . . , n). Отсюда следует, что если указанную подстановку применить к обеим частям тождества t : F’ = F’’, где F’ = F’ (x) и F’’ = F’’(x), мы получим тождество t~: F~’ = F~’’, где F~’ = F’ (F1, . . . , Fn) и F~’’ = F’’ (F1, . . . , Fn), которое называется подстановкой для тождества t.

Дать определение подсхемы КС и указать правила применение к ней тождеств

Схема E’ называется подсхемой схемы E, если V(E’) [принадлежит] V(E), E(E’) [принадлежит] E(E) и любая вершина u, v [принадлежит] V (E’), которая либо относится к

множеству входов (выходов) E, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(E)\E(E’), является входом (соответственно, выходом) E’.

???

Привести основные тождества, связанные с:

1. законом де Моргана для конъюнкции – в классах формул и СФЭ;

2. ветвлением выхода ФЭ отрицания – в классе СФЭ;

3. введением фиктивной БП в контакт – в классе КС.

a)

b)

c)

Сформулировать утверждение о переходе от КПСТ для ЭП формул к КПСТ для ЭП СФЭ

Дать определение тождества для СФЭ, и его подстановки

СФЭ считаются эквивалентными, если они реализуют равные системы ФАЛ.

Тождество T` : E`’ ~ E`’’, которое получается в результате применения одной и той же подстановки к обеим частям тождества t : E’ ~ E’’, называется подстановкой тождества t.

Дать определение подформулы данной формулы и указать правила применения к ней тождеств.

Формулы, полученные в процессе индуктивного построения формулы F, называются

ее подформулами.

Если подформулу F’ (подформулу F’’) формулы F заменить, учитывая тождество t эквивалентной ей формулой F’’ (соответственно F’), то полученная в результате такой замены формула F* будет эквивалентна формуле F, то есть будет справедливо тождество t : F = F*.

Привести основные тождества, связанные с:

1. подстановкой константы 0 в конъюнкцию – в классах формул и СФЭ;

2. снятием “висячего” входа – в классе СФЭ;

3. формульным тождеством вида – в классе КС.

1. {обозначается tau в верхнем индексе ПК, в нижнем 0, &}x1&(x2&(!x2)) = x2&(!x2) {в СФЭ это нарисовать несложно… на бумаге}

b) Вершина СФЭ называется висячей, если она является стоком, но не является выходом схемы. {исходя из этого и нарисовать СФЭ с отдельным входом и без него}

c)

Дать определение разделяющей КС и сформулировать лемму Шеннона

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

Пусть КС E является результатом стыковки вида E = E’’ (E’), а F, F’ и F’’ — матрицы, реализуемые КС E, E’ и E’’ соответственно. Тогда F >= F’ · F’’ и F = F’ · F’’, если КС E’’ разделительна по входам или КС E’ разделительна по выходам.

Дать определение тождества для КС, и его подстановки

Схемы E’ и E’’ считаются изоморфными, если изоморфны соответствующие им графы, и эквивалентными, если они реализуют равные системы ФАЛ. Изоморфные КС, очевидно, эквивалентны.

Определим подстановку для КС как переименование (с возможным отождествлением и инвертированием) БП, а также переименование (с возможным отождествлением и

снятием) полюсов.

Дать определение подсхемы СФЭ и указать правила применения к ней тождеств

Схема E’ называется подсхемой схемы E, если V(E’) [принадлежит] V(E), E(E’) [принадлежит] E(E) и любая вершина u, v [принадлежит] V (E’), которая либо относится к

множеству входов (выходов) E, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(E)\E(E’), является входом (соответственно, выходом) E’.

Привести основные тождества, связанные с:

1. дистрибутивностью конъюнкции относительно дизъюнкций – в классах формул и СФЭ;

2. снятием “висячего” ФЭ отрицания – в классе СФЭ;

3. перебрасыванием контакта в трюхполюсной схеме - в классе КС.

1. (a|b)&c = a&c | b&c

2. {нарисовать схемку с висячим ФЭ отрицания и без него}

Дать определение суммарного цикломатического числа КС и сформулировать утверждение о его изменениях при применении основных тождеств.

|E (G)| - |V (G)| + |c (G)| - цикломатическое число графа {E – ребра, V – вершины, C – компоненты связности}

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов ответов (шпаргалок)