1. Таблицы истинности.

1. (X→Y)۸Z→X

X	Y	Z	X→Y	(X→Y)۸Z	(X→Y)۸Z→X
0	0	0	0	0	1
0	0	1	1	1	0
0	1	0	0	0	1
0	1	1	1	1	0
1	0	0	0	0	1
1	0	1	0	0	1
1	1	0	0	0	1
1	1	1	1	1	1

2. X۸Y↔Y۷X→X→Y

1	2	3	4	5	6	7	8	9
X	Y	Y	X۸Y	4	5↔Y	6۷X	7→X	8→Y
1	1	0	0	1	0	1	1	1
1	0	1	1	0	0	1	1	1
0	1	0	0	1	0	0	1	0
0	0	1	0	1	1	1	0	1

2. Электрическая цепь с одной электрической лампой и ключами.

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

(X۸Y)۷(X۸Z)۷(Y۸X)۷(Y۸Z)۷(Z۸X)۷(Z۸Y)

3. Конспект.

1. Определение графов

Граф - это совокупность двух конечных множеств: множества точек, которые называются вершинами, и мно­жества пар вершин, которые называются ребрами.

На рис. 1 изображен граф, имеющий пять вершин и шесть ребер.

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

Рис. 1 Рис. 2

Ребра, имеющие одинаковые концевые вершины, назы­ваются параллельными.

Ребро, концевые вершины которого совпадают, назы­вается петлей. На рис. 1 а₄ и а₅ - параллельные ребра, а а₂ - петля.

Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. На рис. 1 вершина р₃ и ребро а₃ инцидентны друг другу.

Две вершины, являющиеся концевыми для некоторого ребра, называются смежными вершинами. Два ребра, инцидентные одной и той же вершине, называются смежными ребрами. На рис. 1 р₁, р ₂ - смежные вершины, а а₁, а₄ - смежные ребра.

Степенью вершины называется число ребер, инцидент­ных ей. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной. На рис. 1 степень вершины р₁ равна трем, р₄ - висячая вершина, р₅ - изолированная.

Теорема 1. В графе сумма степеней всех его вер­шин - число четное, равное удвоенному числу ребер графа:

где n – число вершин графа, а т - число его ребер.

Теорема 2. Число нечетных вершин любого графа, т. е. вершин, имеющих нечетную степень, четно.

Граф называется полным, если любые две его раз­личные вершины соединены ребром, и он не содержит параллельных ребер.

Дополнением графаG называется граф G с теми же вершинами, что и граф G, и содержащий только те ребра, которые нужно добавить к графу G, чтобы получился полный граф. На рис. 2 изображены следующие графы: G₁ - полный граф с пятью вершинами, G₂ - некоторый граф, имеющий пять вершин, G₂ - дополнение графа G₂

Путем в графе называется такая последовательность ребер, ведущая от некоторой начальной вершины р₁ в ко­нечную вершину р_п, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Например, в графе, изображенном на рис. 1, последовательность ребер (а₁, а₂, а₃, а₄, а₅, а₆) образует путь, ведущий от вершины р₁ к вершине р₄.

Циклом называется путь, начальная и конечная вершины которого совпадают. На рис. 1 ребра (а₁, а₃, а₄) образуют цикл.

Цикл графа называется простым, если он не про­ходит ни через одну вершину графа более одного раза.

Длиной пути, или цикла называется число ребер этого пути или цикла.