Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n!




Скачать 249.94 Kb.
НазваниеPn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n!
страница2/3
Дата публикации01.04.2013
Размер249.94 Kb.
ТипДокументы
vbibl.ru > Математика > Документы
1   2   3

Пример


Дана функция f:



R (ранг) = 8 * 4 = 32

Шаг 1


На первом этапе склеиваются те конъюнкции (4-го ранга), которые при склейке дают конъюнкции 3-го ранга. Склеиваемые конъюнкции должны различаться только одной буквой: в одну из конъюнкций эта буква входит с отрицанием, в другую – без отрицания. Т.о., для данной функции получаем 7 конъюнкций – первичных импликант.



R = 7 * 3 = 21

Шаг 2




^

Шаг 3


Отмечаем столбцы, которые имеют по одной метке, стрелками (4, 6 ,8).

Шаг 4


Вычеркиваем все строки (5, 6, 7), соответствующие меткам в этих столбцах, и все столбцы (4, 5, 6, 7, 8), имеющие метки в вычеркнутых строках.

Шаг 5


Оставляем только один столбец из тех, которые имеют одинаковые метки. В данном случае все столбцы уникальные – ничего не вычеркиваем.
^

Шаг 6


Вычеркиваем строки, в которых нет меток. В данном случае таких строк нет.

Шаг 7


Строим новую таблицу – из оставшихся строк (1, 2, 3, 4) и столбцов (1, 2, 3).


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

В данном случае есть альтернативы: (2 и 3), (1 и 4)…

Ответ:

^
Модификация Мак Класки

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


^ Для рассмотренного ранее примера:

0










1

0100

1000

0010

2

0101

1001

0110

3

1101




1110

4










Такое упорядочение сокращает перебор – снижает трудоемкость.

1

010–

01–0

100–

0–10

2

–101

1–01

–110






Применение карт Карно для минимизации ФАЛ



Каждой клетке соответствует двоичный набор, с рангом равным 4.

Легко видеть, что при выбранной кодировке клеток в соседнем столбце или строке клеткам соответствуют склеивающиеся конъюнкции.

1 клетка – конъюнкция 4-го ранга;

2 клетки – конъюнкция 3-го ранга;

4 клетки – конъюнкция 2-го ранга;



Минимизация на карте Карно заключается в выборе покрытия клеток с единицами конъюнкциями минимального ранга, т.е. необходимо объединять единичные клетки в блоки, чем больше единиц входит в блок, тем меньше ранг. Число клеток, входящих в блок, равно степени двойки. Импликанты могут покрывать одновременно несколько единиц, одна и та же единица может покрываться несколькими импликантами. Этот метод удобен при ручной минимизации.

^ Метод Класки – минимизация не полностью определенных ФАЛ

Если значения ФАЛ заданы на числе наборов, меньшем чем 2n, то такая функция определена не полностью. Такая ситуация часто встречается на практике – если некоторые наборы просто не могут появляться при кодировании.

Пример

Для десятичных цифр (0..9) ФАЛ f принимает значение 0, если цифра четная и 1 – если нечетная. Т.о., f определена на наборах 0000..1001 и не определена на наборах 1010..1111.

Построим карту Карно и обозначим неопределенные наборы *.







x3x4







00

01

11

10

x1x2

00

0

1

1

0

01

0

1

1

0

11

*

*

*

*

10

0

1

*

*

Для того, чтобы получить аналитическое выражение для неполной ФАЛ, ее необходимо доопределить, т.е. задать на запрещенных наборах некоторые значения.

6 запрещенных наборов – 26=64 различные доопределения – 64 различные функции.

Будем доопределять ФАЛ так, чтобы получить минимальную ДНФ.







x3x4







00

01

11

10

x1x2

00

0

1

1

0

01

0

1

1

0

11

0

1

1

0

10

0

1

1

0

fmin=x4 R(ранг)=1

Выполнив такую склейку, мы доопределили функцию следующим образом: на запрещенных наборах, участвующих в склеивании, функция доопределена 1-ми, на не участвующих – доопределена 0-ми.

^ МНОЖЕСТВА, ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Элемент – это некоторая сущность, которая в рамках рассматриваемой задачи обладает свойством неделимости на части.

Множество – это совокупность элементов, которые обладают двумя свойствами:

  • элементы различаемы;

  • принадлежат множеству.

Способы задания множеств:

  1. перечисление элементов;

  2. описание свойств элементов.

Например

  1. A = {a,b,c,d,e} B = {c,d,f}

  2. N = {целые натуральные числа} = {1,2,3…}

a  A;  g  A;

Множество наборов, на которых ФАЛ (функция алгебры логики) от n аргументов обращается в 0: T0={…} Множество наборов, на которых ФАЛ (функция алгебры логики) от n аргументов обращается в 1: T1={…}. Множество наборов, на которых ФАЛ (функция алгебры логики) от n аргументов не определена: T*={…}. Универсальное множество (U) – это множество всех элементов, рассматриваемых в рамках исследуемой задачи. Множества могут содержать в качестве элементов другие множества:

H = {A,B} = {{a,b,c,d,e},{c,d,f}}

A  H;  B  H

a  H !!!

Предполагают, что множество всегда состоит из уникальных элементов. Если в множестве появляются “одинаковые” элементы, то это должно быть обосновано. Например, бригада студентов, выполняющих один курсовой проект: (Мануйленко, Мануйленко, Иванов, Петров).
^
Операции над множествами

Знак “:” = “такой, что”

  1. Пересечение множеств

A  B = {x : xA и xB}

  1. Объединение множеств

A  B = {x : xA или xB}

(включающее или)

  1. Разность множеств

A \ B = {x : xA или xB}

  1. Симметрическая разность множеств

A  B = (A  B) \ (A  B)

  1. Дополнение множества

A’ = U \ A = {x: xU и xA}

Пример

A = {a,b,c,d,e} B = {c,d,f}

A  B = {c,d}

A  B = {a,b,c,d,e,f}

A \ B = {a,b,e}

B \ A = {f}

A  B = {a,b,e,f}

^ Пример дополнения множества




f

000

001

010

011

100

101

110

111

*

*

1

0

0

*

1

0

T0, T1, T*     U = {0,1,2,3,4,5,6,7}

T0’ = U \ T0 = U \ (T1  T*)’

T0 = {3,4,7}

T1 = {2,6}

T* = {0,1,5}

T0’ = U \ T0 = {0,1,5,2,6}

Мощность

Мощность множества – это количество элементов

Например: | A | = 5     | B \ A | = 1

Пустое множество - Это множество, которое не содержит элементов. Пустое множество считается входящим в любое другое множество.

 = {x, x}

A \ A = 

A   = A

^ Диаграммы Венна-Эйлера

Графическая форма представления операций над множествами



Заштриховано – A \ B 

Рассмотрим A, B:




A  B – отношение включения

A  B – отношение строгого включения, это значит, что существует хотя бы один x, который принадлежит B, но не принадлежит A. Говорят, что A является собственным подмножеством B.
^
Эквивалентность множеств

A, B называется эквивалентными, если A  B и B  A:

(A  B и B  A)=>(A=B)

A \ B = ; B \ A = .

Множества не являются эквивалентными, если хотя бы одна из разностей A \ B или B \ A не является . Термин эквивалентности имеет более глубокий смысл, чем термин равенства.

^ Произведение множеств

( ) – обозначают упорядоченность

A1, A2 … An – множества

(x1, x2, … xn): x1A1, x2A2, … xnAn

Рассмотрим множество всех таких наборов – произведение множеств.



Операция произведения множеств не коммутативна

Пример

B = {c,d,f}     C = {g,h}

B * C = {(c,g), (c,h), (d,g), (d,h), (f,g), (f,h)}

^ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

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

1. Все коты любят рыбу

Кузма – кот

Следовательно: Кузьма любит рыбу

2. Все программы содержат ошибку

Windows 95 – программа

Следовательно: Windows 95 содержит ошибку

Все A есть B

C есть A

Следовательно: C есть B

Математическая логика изучает структуру рассуждения, форму, отвлекаясь от смыслового содержания этих структур. В исчислении высказываний рассматриваются следующие операции над высказываниями:
A B

A

AB

AB

A&B

AB

AB

AB

AB

0 0

0 1

1 0

1 1

1

1

0

0

0

1

1

1

0

0

0

1

1

1

0

1

1

0

0

1

0

1

1

0

A, B – пропозициональные буквы (переменные)

Операция: функция, которая отображает … (???)

f: AA…AA

Существуют функции, не являющиеся операциями:

f={Истина, если x0; Ложь, если x<0}

Импликация: если A, то B

Тождество: тогда и только тогда

Или: часто в речи, говоря “или”, мы подразумеваем разделительную операцию ().

Логические операции в математической логике – связки (пропозициональные связки)

Если Бим сыт, то Кузьма голоден или если Бим голоден, то Кузьма сыт

a = Бим сыт

b = Кузьма сыт

(a  b)  (a  b) – пропозициональная форма (ПФ), формула высказывания

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

Обозначение: = A

x  x – тавтология

x  (y  x) – тавтология

Если Бим сыт, то Кузьма голоден, если Бим голоден, то Кузьма голоден подавно.

(a  b)  (a  b)

Студент счастлив тогда и только тогда, когда тепло, выдали стипендию, до сессии далеко.

x  a & b & c

необходимым и достаточным условием x является a & b & c

Если A и B – формулы и AB является тавтологией, то говорят, что A логически влечет B, иначе говоря, B является следствием A.

Если AB является тавтологией, то говорят, что A и B логически эквивалентны.

Противоречие – формула, принимающая значение “ложь” при любых значениях входящих в нее букв. Если A тавтология, то A – противоречие и наоборот. Если в тавтологию подставить вместо букв логические высказывания, то получится логически истинное высказывание. A  A – снег идет или снег не идет (закон исключения третьего). Если в противоречие подставить вместо букв логические высказывания, то получится логически ложное высказывание. A & A – снег идет и снег не идет

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

^ Свойства тавтологий

  1. Если =A и = (A  B), то =B.
1   2   3

Похожие:

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconСварка с помощью нагревательных элементов
По ошибке сваркой называют способ холодного соединения или соединения с набуханием пластика, который не подпадает под данное понятие,...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconФедеральное агентство железнодорожного транспорта
Так же с помощью наружной рекламы можно выработать у потенциального потребителя позитивное (или не очень) отношение к бренду или...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconПермский государственный технический университет
Выполните задания 1-4 с помощью двойного интеграла, задания 5-7 с помощью тройного интеграла, задания 8-11 с помощью криволинейных...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconО программе iTunes
Создавайте плейлисты на любой случай жизни. Записывайте плейлисты на компакт-диск и воспроизводите их на домашней или автомобильной...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconФорматирование текста
Текстовый курсор и символ конца текста. Текстовый курсор передвигается с помощью клавиш управления курсором или с помощью щелчка...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconУрока, дата Главная тема Важнейшие подтемы
Умение работать с историческими источниками- работа и анализ текста с помощью маркировки ( статьи о новых научных открытиях или просмотр...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconЙогическая садхана под редакцией уттара йоги
Волю, с помощью Воли воспитайте знание, с помощью знания очистите сердце, установите контроль над энергиями тела и успокойте ум....

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconШаг Утечка информации
Раскрутка нового бренда с помощью рекламы и с помощью пиара совсем не одно и то же. Если вы хотите раскрутить бренд с помощью пиара,...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconУслуги междугородной и международной телефонной связи Orange Business...
Автоматическая телефонная связь позволяет абоненту без предварительного заказа, в любой момент времени установить соединение по телефону...

Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n! iconМногие дети проходят период между двумя и четырьмя годами, когда...
Дети, которые, подрастая, не научатся подавлять свою агрессивность и общаться с окружающими с помощью устной речи, часто превращаются...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница