Основы дискретной математики

МІНІСТЕРСТВО  ОСВІТИ І НАУКИ УКРАЇНИ

ХЕРСОНСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

КАФЕДРА ТЕХНІЧНОЇ КІБЕРНЕТИКИ

 

 

 

 

 

Курсова робота

з дисципліни «Основи дискретної математики»

 

 

Варіант № 2

 

 

 

 

 

 

 

Виконав

студент групи 2СУ  _______________  Борохович И.И.

Керівник

Проф.    _______________  Марасанов В.В.

 

 

 

Херсон 2011

 

РЕФЕРАТ

Курсовая  работа содержит __ страниц, __ рисунков, __ таблиц.

В работе выполнены:

1) формализованное  описание графа с помощью таблицы,  фактор – множества, матриц  инциденции, смежности вершин, циклов, разрезов и путей; 

2) поиск его  числовых характеристик, таких  как, степени вершин, вершинная  и реберная связность, цикломатическое  число, вершинное и реберное  числа независимости, числа вершинного  и реберного покрытий, вершинное  и реберное числа внешней устойчивости, радиус и диаметр графа; 

3) решена задача  на самый короткий путь;

4) составление  таблицы истинности функции алгебры  логики и записаны её совершенные  дизъюнктивная и конъюнктивная  нормальные формы; 

5) анализ функции  на принадлежность к классам; 

6) минимизация  логической функции методом Квайна-МакКласски  или с помощью карт Карно;

7) синтез логической  схемы методом каскадов и реализация  её в базисе и-или-не с использованием  двухвходовых элементов.

НЕОРИЕНТИРОВАНЫЙ  ГРАФ, ИНЦИДЕНТНОСТЬ, ФАКТОР МНОЖЕСТВА,  ФУНКЦИЯ АЛГЕБРЫ ЛОГИКИ, ТАБЛИЦА  ИСТИННОСТИ,  МИНИМИЗАЦИЯ,  МЕТОД  КАСКАДОВ.

 

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ  И СОКРАЩЕНИЙ

ДМ – дискретная математика

CДНФ – совершенная дизъюнктивная нормальная форма

CКНФ – совершенная конъюнктивная нормальная форма

МДНФ – минимальная дизъюнктивная нормальная форма

ФАЛ – функция  алгебры логики

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

Дискретная  математика – область математики, которая занимается исследованиями структур и задач на конечных множествах. Она представляет собой важное направление, имеющее характерные для него предмет исследований, методы и задачи. Специфика задач ДМ в первую очередь  предполагает отказ от основных понятий  классической математики – предела  и непрерывности. Поэтому для  задач ДМ обычные средства классического  анализа являются вспомогательными.

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

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

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

Еще в доньютоновский период появились простейшие понятия  комбинаторики (П.Ферма, Б.Паскаль, Франция, XVIII в.). Комбинаторика возникла как основа дискретной теории вероятностей в связи с исследованиями в области азартных игр.

Л.Эйлер в  середине XVIII века закладывает основы теории графов; в середине XIХ века Дж.Буль, опираясь на некоторые идеи Г.Лейбница, придумывает свою «универсальную алгебру» в продолжение наметившегося еще в середине века стремления к формализации Аристотелевой логики. Конец XIХ века дает толчок к созданию и быстрому расцвету математической логики.

Основным  поставщиком задач и идей для  ДМ в ХХ веке становится кибернетика, а универсальным вычислительным средством – ЭВМ. Задачи анализа  и конструирования сложных систем послужили стимулом для разработки теории графов; задачи хранения, обработки  и передачи информации привели к  теории кодирования; задачи оптимизации  вызвали появление дискретного  программирования; исследование основных понятий вычислительной математики – вычислимости и алгоритма –  стимулировало появление теории алгоритмов и теории сложности.

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

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

 

1. ЗАДАЧИ ТЕОРИИ ГРАФОВ

 

Графами называют геометрические схемы, представляющие собой системы точек и соединительных линий. Учение о графах соединяет  исключительную геометрическую наглядность, математическую содержательность и  возможность обходиться без громоздкого  аппарата. [1]

Геометрический  граф в пространстве jⁿ (Евклидово пространство) – это множество V={v_i} точек  пространства jⁿ и множество Е={e_k} простых кривых удовлетворяющих следующим условиям.

1)Каждая  замкнутая  прямая из множества Е содержит  только одну точку v множества V;

2)Каждая незамкнутая  прямая из множества Е содержит  только 2 точки v из множества V, которые являются ее границами.

3)Кривые Е  не имеют общих точек за  исключением точек из множества  V

Граф –  это совокупность не пустого множества  V, изолированного от него множества Е и отображения f: Е~V&V.

Если граф не имеет ребер, он называется вырожденным. Если множества Е и V конечные, то граф называется конечным [2].

1.1.   Формализованное  задание графа

Граф задается на множестве вершин V и множестве ребер Е. Наиболее простое описание графа – составление таблицы соответствия ребер и вершин.

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

 

Рис. 1.1 – Исходный граф G для варианта №2

1.1.1 Описание графа с помощью таблицы

Данное описание графа представлено таблицей 1.1 соответствия множества вершин и множества  ребер графа

Табл.1.1

E	e1	e2	e3	e4	e5	e6	e7	e8	e9
V	v1, v2	v1, v3	v3, v2	v2, v4	v3, v4	v3, v5	v5, v4	v4, v6	v5, v6

1.1.2  Описание графа с помощью фактор – множества

1.1.3  Описание графа с помощью матриц

Матрица инциденций для графа G, имеющего n вершин и m ребер  имеет размерность n x m. Строки этой матрицы соответствуют вершинам, а столбцы – ребрам графа. Элемент  а_ij=1, если j-ое ребро инцидентно i-ой вершине и а_ij=0 в противном случае.

Для графа  на рис.1.1 матрица инциденций имеет  вид:

 

 

Матрица смежности  вершин для графа G, имеющего n вершин имеет размерность n x n. Элемент v_ij этой матрицы равен числу ребер, инцидентных одновременно i-ой и j-ой вершинам графа.

Для графа  на рис.1.1 матрица смежности вершин имеет вид:

 

Матрица циклов для графа G, имеющего n вершин и m ребер, имеет размерность к x m, где к – число циклов в графе. Элемент этой матрицы с_ij=1, если j-ое ребро входит в i-ый цикл и с_ij=0 в противном случае. Циклы в заданном графе представлены на рисунке 1.2.

Рис. 1.2 – Циклы графа G.

Для графа на рис.1.2 матрица циклов имеет  вид:

 

 

Если  задан связный граф G=(V, E) и множество его вершин разбито на два непустых подмножества W и W^/, то множество ребер, соединяющих W с W^/ называют разрезом. Простым называют разрез, разбивающий связный граф только на две компоненты связности.

С использованием простых разрезов можно построить  матрицу разрезов графа. Для графа  G, имеющего n вершин и m ребер, матрица разрезов имеет размерность l x m, где l – число разрезов на графе. Элемент этой матрицы к_ij=1, если j-ое ребро входит в i-ый разрез и к_ij=0 в противном случае. Простые разрезы для графа G изображены на рисунке 1.3.

Рис. 1.3 – Разрезы графа G

Для графа на рис.1.3 матрица разрезов имеет вид:

 

 

Выбрав в  связном графе начальную (v₁) и конечную (v₂) вершину, для него можно составить матрицу путей (матрицу цепей). Строки этой матрицы соответствуют цепям между вершинами v₁ и v₂, а столбцы соответствуют ребрам графа. Элемент матрицы р_ij=1, если j-ое ребро принадлежит i-ой цепи и р_ij=0 в противном случае.

Для графа  на рис.1.1 матрица путей из вершины 1 в вершину 6 имеет вид:

1.2.   Числовые характеристики графа

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

1.2.1 Степени всех вершин графа

Число ребер  неориентированного графа инцидентных  вершине v, называется степенью вершины v и обозначается d(v).

Степени всех вершин графа, изображенного на рис.1.1:

;

;

;

;

;

.

Минимальная степень вершины 

1.2.2 Вершинная  и реберная связность графа

Минимальное число вершин (ребер), удаление которых  делает граф несвязным, называется вершинной  (реберной g(G)) связностью графа G.

Вершинная и  реберная связность графа на рис.1.1:

 (вершины v₃, v₄ или v₂, v₃ или v₅, и v₄).

 (ребра e₁, e₂, или e₈, e₉).

1.2.3 Цикломатическое число графа

Пусть G=(V, E) – неориентированный граф, имеющий n вершин, m ребер и r компонент связности. Цикломатическим числом графа G называют число n(G)=m – n + r. Цикломатическое число равно наибольшему числу независимых циклов в графе.

Цикломатическое число графа на рис.1.1:

(из 10 контуров 4 независимые).

1.2.4 Хроматическое число

Пусть p – натуральное число. Граф G = (V, E) называют p-хроматическим, если его вершины можно раскрасить p разными цветами, так, чтобы никакие две смежные вершины не были раскрашены в тот же цвет. Наименьшее число p, при котором граф является р – хроматическим, называют хроматическим числом графа (обозначается . Если , граф называют бихроматическим. Необходимым и достаточным условием бихроматичности графа является отсутствие в нем циклов непарной длины (теорема Кенига).

(, т.к. цикл охватывает 3 ребра (3 вершины)).

1.2.5 Вершинное и реберное числа независимости

Множество S V графа G = (V, Г) называют внутренне устойчивым, если никакие две вершины из S не смежные, т.е. для любого х S имеет место Гх S¹Æ.

Множество внутренней устойчивости, содержащее наибольшее число элементов, называют наибольшим внутренне устойчивым множеством, а число элементов этого множества – числом внутренней устойчивости e₀(G) графа G (это число называют также вершинным числом независимости графа).

Два ребра  графа называют смежными, если они  инцидентны одной и той же вершине. Максимальное число попарно несмежных  ребер графа называется его реберным числом независимости e₁(G).

Вершинное и  реберное числа независимости графа  на рис.1.1:

(вершины v₁ и v₅; v₁ и v₄; v₂ и v₆; v₂ и v₅; v₁ и v₆).

(ребра e₁, e₆, e₈ или e₂, e₄, e₉ или e₁, e₅, e₉).

1.2.6 Числа вершинного и реберного покрытий графа

Если ребро  графа инцидентно его вершине, то говорят, что они покрывают друг друга. Множество вершин, покрывающих  все ребра графа, называют вершинным  покрытием графа G, а минимальную мощность этого множества - числом вершинного покрытия графа p₀(G).

Аналогично, множество ребер, покрывающих все  вершины графа, называют реберным покрытием  графа G, а минимальную мощность этого множества – числом реберного покрытия графа p₁(G).

Числа вершинного и реберного покрытий графа на рис.1.1:

(вершины v₂, v₃, v₄, v₅ или v₂, v₃, v₄, v₆ или v₁, v₃, v₄, v₆ или v₁, v₃, v₄, v₅ или v₁, v₂, v₄, v₅).

(ребра e₁, e₅, e₉ или e₁, e₆, e₈).

1.2.7 Вершинное и реберное число внешней устойчивости графа

Множество ТÌV графа G=(V, Г) называют внешне устойчивым, если любая вершина, не принадлежащая Т, соединена ребрами с вершинами из Т, т.е. для любого хÏТ имеет место ГхÇТ¹Æ.

Множество внешней  устойчивости, содержащее наименьшее число элементов, называется наименьшим внешне устойчивым множеством, а число  элементов этого множества –  вершинным числом внешней устойчивости b₀(G) графа G.

Минимальная мощность множества ребер, покрывающих  все ребра графа, называется реберным числом внешней устойчивости b₁(G) графа G.

Вершинное и  реберное числа внешней устойчивости графа на рис.1.1:

b₀(G)=2 (вершины v₂, v₅; v₂, v₆; v₃, v₄)

b₁(G)=2 (ребра )

1.2.8 Радиус и диаметр графа

Для фиксированной  вершины v целое число R(v)=max d(v, w), wÎV соответствует расстоянию от v до наиболее удаленной вершины.

Радиус R₀= min R(v)= R(v₀), vÎV, вершину v₀ считают центром графа.

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

1. Радиус графа G:

Считая точку v₄ центром графа R₀ (G) = 7.

2. Диаметр графа G:

T(G) = 15 (расстояние между парами вершин v₁ и v₆)

 

1.3 Задача теории графов.

Задача  на самый короткий путь

Решение задачи с помощью алгоритма Флойда – Уоршелла.

Алгоритм  Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами  взвешенного ориентированного графа. Этот алгоритм частично реализует метод динамического программирования. Алгоритм пошаговый, состоит из n+1 этапа, где n – число вершин.

Основная  идея метода Флойда. Пусть есть три узла i, m и j и заданы расстояния между ними (рис. 2). Если выполняется неравенство d_im + d_mj < d_ij, то целесообразно заменить путь i -> j путем i -> m -> j. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис.2. Треугольный оператор

Пусть вершины графа  пронумерованы от 1 до n.

Обозначим через длину кратчайшего пути от i до j, который кроме самих вершин проходит только через вершины (это расстояние между i-ой и j-ой вершинами, где присутствует m промежуточных вершин).

Очевидно, что  — длина (вес) ребра , если таковое существует. Если не существует прямого пути из вершины i в вершину j, его длина обозначается как . Расстояние от вершины до ее самой равно 0 ().

Существует два варианта значения :

1. Кратчайший путь между не проходит через вершину m, тогда
2. Существует более короткий путь между , проходящий через m, тогда он сначала идёт от i до m, а потом от m до j. В этом случае, очевидно,

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

Тогда рекуррентная формула для  имеет вид:

 — длина ребра

 

Алгоритм Флойда — Уоршелла последовательно  вычисляет все значения , для m от 1 до n. Полученные значения являются длинами кратчайших путей между вершинами .

Построим начальную матрицу расстояний , содержащую элементы , т.е матрицу начальных расстояний между всеми вершинами графа (между 1-й вершиной и остальными, между 2-й вершиной и остальными и т.д.)

 

На основе матрицы  построим матрицу , элементы которой вычисляются по формуле

 

В этой матрице первые строка и  столбец переписываются без изменения.

Далее, построим матрицу  , элементы которой удовлетворяют условию . (Вторые строку и столбец переписываем).

 

Обозначим m-ю строку и m-й столбец (в матрицах выделены серым) как ведущую строку и ведущий столбец. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:

Рис.3. Иллюстрация  алгоритма Флойда

 

 

Аналогично построению матрицы , используя треугольный оператор построим матрицы :

 

 

 

Результатом расчетов будет самый  короткий путь из вершины v₁ в вершину v₆, равный 13

 

2. . СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ

Формальная  логика делится на три подраздела: логику Буля, логику высказываний и  логику предикатов. «Логика Буля»  основывается на отношении эквивалентности, при котором правая часть равенства  всегда содержит ровно столько же «истины», сколько и левая. Два  последующих раздела базируются уже на отношении порядка, при  котором правая часть выражения  содержит больше «истины», чем левая  [3].

Логической  называют переменную, которая может  принимать одно из двух возможных  значений – «1» или «0» («истина» или «ложь», «да» или «нет»). Логические переменные обозначаются Х_i. Чаще всего под индексом подразумевают разряд двоичного числа, соответствующего набору логической переменной.

Функция, определенная на наборах (x_n-1, …, х_i, …, x₁, x₀) и принимающая на этих наборах значения 0 или 1, называется функцией алгебры логики (ФАЛ, логической функцией, булевой функцией)[2].

2.1 Таблица истинности для заданной  функции алгебры логики

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

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

 

Рассмотрим  заданную функцию:

 

Cоставим таблицу истинности (табл.2.1):

Таблица 2.1

							(1)	(2)	(3)	(4)	(5)	(6)
	x4	x3	x2	x1	x0
1	0	0	0	0	0	1	0	0	1	1	1	0	0
2	0	0	0	0	1	1	0	0	1	1	1	0	0
3	0	0	0	1	0	0	1	0	1	1	1	0	1
4	0	0	0	1	1	0	1	0	1	1	1	0	1
5	0	0	1	0	0	1	0	1	0	1	1	0	0
6	0	0	1	0	1	1	0	1	0	1	1	0	0
7	0	0	1	1	0	0	1	1	0	1	1	0	1
8	0	0	1	1	1	0	1	1	0	1	1	0	1
9	0	1	0	0	0	1	1	0	1	0	1	0	1
10	0	1	0	0	1	1	1	0	1	0	0	1	1
11	0	1	0	1	0	0	1	0	1	0	1	0	1
12	0	1	0	1	1	0	1	0	1	0	0	1	1
13	0	1	1	0	0	1	1	1	0	1	1	0	1
14	0	1	1	0	1	1	1	1	0	1	1	0	1
15	0	1	1	1	0	0	1	1	0	1	1	0	1
16	0	1	1	1	1	0	1	1	0	1	1	0	1
17	1	0	0	0	0	1	0	1	0	1	1	0	0
18	1	0	0	0	1	1	0	1	0	1	1	0	0
19	1	0	0	1	0	0	1	1	0	1	1	0	1
20	1	0	0	1	1	0	1	1	0	1	1	0	1
21	1	0	1	0	0	1	0	1	0	1	1	0	0
22	1	0	1	0	1	1	0	1	0	1	1	0	0
23	1	0	1	1	0	0	1	1	0	1	1	0	1
24	1	0	1	1	1	0	1	1	0	1	1	0	1
25	1	1	0	0	0	1	1	1	0	1	1	0	1
26	1	1	0	0	1	1	1	1	0	1	1	0	1
27	1	1	0	1	0	0	1	1	0	1	1	0	1
28	1	1	0	1	1	0	1	1	0	1	1	0	1
29	1	1	1	0	0	1	1	1	0	1	1	0	1
30	1	1	1	0	1	1	1	1	0	1	1	0	1
31	1	1	1	1	0	0	1	1	0	1	1	0	1
32	1	1	1	1	1	0	1	1	0	1	1	0	1

 

 

2. Совершенные дизъюнктивная и конъюнктивная нормальные формы

Логические  функции для удобства записи выражают в виде суммы произведений логических переменных или в виде произведений их сумм. Первая запись называется дизъюнктивной  нормальной формой, а вторая конъюнктивной  нормальной формой. Для каждой  логической функции может существовать несколько  равносильных дизъюнктивных и конъюнктивных  форм, однако существует только один вид  нормальной формы, в котором функция  может быть записана единственным образом  совершенные дизъюнктивные и  конъюнктивные нормальные формы (СДНФ и СКНФ). В СДНФ функция записывается в виде логической суммы конститутиент единицы (минтермов), а в СКНФ – в виде логического произведения конститутиент нуля (макстермов). Конститутиент единицы и нуля – это комбинации переменных, при которых функция соответственно обращается в единицу или нуль.

Напишем совершенные  дизъюнктивную и конъюнктивную  нормальные формы для заданной функции:

Сложность функции 

 

Сложность функции  

2. Анализ функции алгебры логики на принадлежность к классам

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

1. Класс функций сохраняющих ноль

Логическая  функция f(x_n-1, …, x₁, x₀) принадлежит к классу ФАЛ, сохраняющих константу нуля К₀, если при всех x_i=0, где i=0, 1, …, (n-1), выполняется равенство .

Проверим  принадлежность заданной функции к  этому классу ФАЛ:

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

1. Класс функций сохраняющих единицу

Логическая  функция f(x_n-1, …, x₁, x₀) принадлежит к классу ФАЛ, сохраняющих константу единицы К₁, если при всех x_i=1, где i=0, 1, …, (n-1), выполняется равенство .

Проверим  принадлежность заданной функции к  этому классу ФАЛ:

так как , то данная функция алгебры логики принадлежит к классу функций сохраняющих единицу, т.е..

2. Класс линейных функций

Логическая  функция f(x_n-1, …, x₁, x₀) принадлежит к классу линейных ФАЛ К_л в том случае, когда её можно описать выражением

;     где Å, - знаки операции сложения по модулю 2.

Проверим  принадлежность заданной функции к этому классу ФАЛ:

 

Коэффициент С находим на наборе <0,0,0,0,0>

 

Коэффициент находим на наборе <0,0,0,0,1>

 

Коэффициент находим на наборе <0,0,0,1,0>

 

Коэффициент находим на наборе

 

Коэффициент находим на наборе

 

Коэффициент находим на наборе 

 

 

Сравниваем  наборы функции:

…

В 13-й строке идет несовпадение, значит функция не линейная, т.е. .

3. Класс самодвойственных функций

Логическая  функция f(x_n-1, …, x₁, x₀) принадлежит к классу самодвойственных ФАЛ К_с, если для неё справедливо выражение

 

Проверим принадлежность заданной функции к этому классу ФАЛ:

Исходная функция:

 

Самодвойственная функция:

 

Табл.2.2

										(1)	(2)	(3)	(4)	(5)	(6)	(7)
	x4	x3	x2	x1	x0
1	0	0	0	0	0	1	1	1	1	1	1	0	1	1	0	1	0	0
2	0	0	0	0	1	1	1	1	0	1	1	0	1	1	0	1	0	0
3	0	0	0	1	0	1	1	1	1	1	1	0	1	1	0	1	0	1
4	0	0	0	1	1	1	1	1	0	1	1	0	1	1	0	1	0	1
5	0	0	1	0	0	1	1	0	1	1	1	0	1	1	0	1	0	0
6	0	0	1	0	1	1	1	0	0	1	1	0	1	1	0	1	0	0
7	0	0	1	1	0	1	1	0	1	1	1	0	1	1	0	1	0	1
8	0	0	1	1	1	1	1	0	0	1	1	0	1	1	0	1	0	1
9	0	1	0	0	0	1	0	1	1	1	1	0	1	1	0	1	0	1
10	0	1	0	0	1	1	0	1	0	1	1	0	1	1	0	1	0	1
11	0	1	0	1	0	1	0	1	1	0	1	0	1	1	0	0	1	1
12	0	1	0	1	1	1	0	1	0	0	1	0	1	1	0	0	1	1
13	0	1	1	0	0	1	0	0	1	1	1	0	1	1	0	1	0	1
14	0	1	1	0	1	1	0	0	0	1	1	0	1	1	0	1	0	1
15	0	1	1	1	0	1	0	0	1	0	1	0	1	1	0	0	1	1
16	0	1	1	1	1	1	0	0	0	0	1	0	1	1	0	0	1	1
17	1	0	0	0	0	0	1	1	1	1	1	0	1	1	0	1	0	0
18	1	0	0	0	1	0	1	1	0	1	1	0	1	1	0	1	0	0
19	1	0	0	1	0	0	1	1	1	1	1	0	1	1	0	1	0	1
20	1	0	0	1	1	0	1	1	0	1	1	0	1	1	0	1	0	1
21	1	0	1	0	0	0	1	0	1	1	0	1	0	0	1	1	0	0
22	1	0	1	0	1	0	1	0	0	1	0	1	0	1	0	1	0	0
23	1	0	1	1	0	0	1	0	1	1	0	1	0	0	1	1	0	1
24	1	0	1	1	1	0	1	0	0	1	0	1	0	1	0	1	0	1
25	1	1	0	0	0	0	0	1	1	1	1	0	1	1	0	1	0	1
26	1	1	0	0	1	0	0	1	0	1	1	0	1	1	0	1	0	1
27	1	1	0	1	0	0	0	1	1	0	1	0	1	1	0	0	1	1
28	1	1	0	1	1	0	0	1	0	0	1	0	1	1	0	0	1	1
29	1	1	1	0	0	0	0	0	1	1	0	1	1	1	0	1	0	1
30	1	1	1	0	1	0	0	0	0	1	0	1	1	1	0	1	0	1
31	1	1	1	1	0	0	0	0	1	0	0	1	1	1	0	0	1	1
32	1	1	1	1	1	0	0	0	0	0	0	1	1	1	0	0	1	1