Кос для промежуточной аттестации по дискретной математике

Департамент образования города Москвы
Государственное бюджетное образовательное учреждение
ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ № 42
Образовательная программа
среднего профессионального образования
Комплект
контрольно-оценочных средств
по учебным дисциплинам
Основы алгоритмизации и программирования
и
Дискретная математика
программы подготовки специалистов среднего звена
230113 «Компьютерные системы и комплексы»
для промежуточной аттестации
Москва, 2014
Одобрена
цикловой комиссией
Компьютерных систем, сетей и телекоммуникаций
Протокол № ____
от «__» _________ 20___ г.
Разработана на основе Федерального государственного образовательного стандарта специальности среднего профессионального образования 230113 Компьютерные системы и комплексы _________________________________

Председатель цикловой комиссии
__________/Журкин М.С./ Заместитель директора по учебно-воспитательной работе
___________/Н.А. Бокатюк/
Составители (авторы): ____Арманова М.В._, Кирсанова Н.Ю.__преподаватели первой квалификационной категории ГБОУ СПО Политехнический колледж № 42_________________
Рецензент:__д. ф-м.н. зав. Кафедрой математики АТиСО Геворкян П.С.________
1. Общие положения
Контрольно-оценочные средства (КОС) являются составной частью образовательной программы среднего профессионального образования по подготовке специалистов среднего звена 230113 Компьютерные системы и комплексы и предназначены для контроля и оценки образовательных достижений обучающихся, освоивших программу учебной дисциплины «Основы алгоритмизации и программирования» и «Дискретная математика»
КОС включают контрольные материалы для проведения промежуточной аттестации в форме экзамена.
КОС разработаны на основании:
Положения о Фонде оценочных средств (ФОС);
Рекомендаций по разработке контрольно-оценочных средств (КОС);
рабочей программы учебной дисциплины.
2. Результаты освоения дисциплины, подлежащие проверке
КОС для промежуточной аттестации направлены на проверку и оценивание результатов обучения, знаний и умений:
Результаты освоения дисциплины «Дискретная математика»
Результаты обучения
(освоенные умения, усвоенные знания) Коды формируемых профессиональных и общих
компетенций Основные показатели оценки № заданий, включенных в КОС
У1
Формулировать задачи логического характера и применять средства математической логики для их решения ОК 1 – ОК 10
ПК1.1,ПК 1.3,
ПК 2.1 Грамотно формулировать задачи логического характера и применять средства математической логики для их решения 3,11,13,2,4,8
У2
Применять законы алгебры логики ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Правильно применять законы алгебры логики для решения задач 6,10,12,14
У3
Определять типы графов и давать их характеристики ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Правильно определять типы графов и давать их характеристики, применять понятие графа для решения задач. 16,18,20
З1
Знание основных понятий и приемов дискретной математики ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Хорошее знание основных понятий и приемов дискретной математики 22,24
З2
Знание логических операций, формул логики, законы алгебры логики ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Хорошее знание логических операций, формул логики, законы алгебры логики 21,23,27
З3
Основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Хорошее знание основных понятий теории множеств, теоретико-множественные операции и их связь с логическими операциями 26,28
З4
Знание основных понятий теории графов, характеристик и видов графов ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1ОК7
ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Хорошее знание основных понятий теории графов, характеристик и видов графов 30,32
Результаты освоения дисциплины «Основы алгоритмизации»
У1
Применять полученные знания в использовании средств и методов автоматизированного проектирования при разработке цифровых устройств ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Уметь правильно применять полученные знания в использовании средств и методов автоматизированного проектирования при разработке цифровых устройств 1,5,7,9
У2
Применять законы алгебры логики ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Правильно применять законы алгебры логики для решения задач 6,10,12,14
У3
Определять показатели надежности и качества проектируемых цифровых устройств ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Уметь правильно определять показатели надежности и качества проектируемых цифровых устройств 15,17,19
З1
Знание логических операций, формул логики, законы алгебры логики ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Хорошее знание логических операций, формул логики, законы алгебры логики 21,23,27
З2
Знание средств и методов автоматизированного проектирования при разработке цифровых устройств ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Хорошее знание использования средств и методовавтоматизированного проектирования при разработке цифровых устройств 25,29
З3
Использовать информационно-коммуникационные технологии для совершенствования профессиональной деятельности ОК 1 – ОК 10
ПК 1.1, ПК 1.3,
ПК 2.1 Хорошее знание и использование информационно-коммуникационных технологий для совершенствования профессиональной деятельности 31,33
3. Распределение КОС по темам учебной дисциплины
Контрольно-оценочные средства представляют собой перечень заданий различного уровня трудности (от 1 до 3).
паспорт оценочного средства
«Основы алгоритмизации и программирования»
Наименование тем Кол-во часов Порядковый номер задания Уровень трудности
**
Тема 1.1
Общая концепция языков программирования. 4 1 1
Тема 1.2
Эволюция языков программирования. 6 10 1
Тема 2.1
Этапы решения задач на ЭВМ 10 9 2
11 2
16 2
Тема 2.2
Основы алгоритмизации. 8 2 2
3 2
4 2
5 2
6 3
7 2
8 2
Тема 3.1 Работа со средой разработки. Создание программ в VisualBasic. 8 20 2
21 2
22 2
23 2
Тема 3.2. Основы VisualBasic 12 15 2
17 2
18 2
26 2
27 2
28 2
Тема 3.3. Работа с кодом и формами 14 12 2
14 2
29 2
30 2
31 2
32 3
33 3
Тема 3.4 Переменные и процедуры 20 13 2
19 3
25 3
«Дискретная математика»
Тема 1.1. Понятие как форма мышления. Операции над понятиями. 8 1 1
2 2
3 2
4 2
5 2
Тема 1.2. Булевы функции 8 6 1
7 2
8 2
9 2
10 2
Тема 2.1. Алгебра множеств 12 11 2
12 2
Тема 2.2. Бинарные отношения 12 13 1
14 2
15 2
16 2
17 3
18 2
19 2
Тема 2.3. Композиция отображений
6 20 2
21 2
22 2
23 2
Тема 3.1. Операции над вычетами 4 24 3
26 3
Тема 4.1. Метод математической индукции. 2 25 3
26 3
Тема 5.1. Генерирование К-элементных подмножеств данного множества 4 27 2
Тема 6.1. Неориентированные графы 8 28 2
29 2
Тема 6.2. Ориентированные графы 4 30 2
31 2
Тема 6.1. Логические элементы и логические схемы 4 32 3
33 3
**
Низкий -1
Средний -2
Высокий-3
4. Содержание КОС
Содержание банка КОС в полной мере отражает требования ФГОС по специальности и содержания рабочей программы учебной дисциплины. В состав банка включены теоретические вопросы и практические задания.
Теоретические задания: по дисциплине «Основы алгоритмизации и программирования»
Основные понятия алгоритмизации. Понятия «алгоритм», «исполнитель алгоритма».
Свойства и формы записи алгоритмов.
Основные алгоритмические конструкции: линейные, разветвляющиеся и циклические.
Логические основы алгоритмизации. Основы алгебры логики.
Логические операции: конъюнкция, дизъюнкция, инверсия, импликация, эквиваленция.
Законы алгебры логики.
Таблицы истинности.
Составление таблиц истинности для сложных логических функций.
Составление блок-схем алгоритмов.
Языки и системы программирования. Языки высокого и низкого уровня.
Правила записи выражений и операций. Типы данных. Синтаксис.
Понятие модуля и формы.
Пользовательские типы данных.
Использование форм, событий и методов.
Использование управляющих элементов.
Составление программ циклической структуры.
Логические операторы и операторы сравнения If...Then, SelectCase.
Обзор структуры цикла. Использование Do...Loop, Использование For...Next.
Работа с логическими операторами и операторами сравнения.
Написание кода с использование операторов и циклов.
Отслеживание и анализ ошибок.
Обзор стандартных элементов.
Дополнительные возможности стандартных элементов.
Использование ComboBox и ListBox.
Написание функций.
Использование в форме графики. PictureBox, ImageList.
Создание программы с использованием полос прокрутки, таймера и заданием даты.
Создание вкладок, индикатора прогресса, ползунка.
Гиперссылки. Список.
Чтение и запись файла. Класс FileStream.
Считывание данных из текстового файла.
Запись данных в текстовый файл.
Открытие и создание файла для чтения и записи.
Практические задания: по дисциплине «Основы алгоритмизации и программирования»
Задачи с решениями.
Задача № 1
Постановка задачи: Составить программу нахождения площади прямоугольника со сторонами Х и У.
Интерфейс задачи:

Листинг программы:
Dim x As Integer, y As Integer, z As Integer
Private Sub Command1_Click()
Text3.Text = Text1.Text + Text2.Text
x = Text1.Text
y = Text2.Text
z = x * y: Text3.Text = z
End Sub
Private Sub Command2_Click()
Form1.Hide: Form2.Show
End Sub
Задача № 2
Постановка задачи: Составить программу перевода строки в нижний регистр.
Интерфейс задачи:

Листинг программы:
Dim x As String, y As String
Private Sub Command1_Click()
x = Text1.Text
y = LCase(x): Text2.Text = y
End Sub
Private Sub Command2_Click()
Form2.Hide: Form3.Show
End Sub
Private Sub Command3_Click()
Form2.Hide: Form1.Show
End Sub
Задача № 3
Постановка задачи: Составить программу перевода температуры из шкалы Фаренгейта в шкалу Цельсия (0 F соответствует -17,8, а 0 C соответствует+32 F ).
Интерфейс задачи:

Листинг программы:
Dim x As Variant, y As Variant
Private Sub Command1_Click()
x = Text1.Text
y = (5 * (32 - x) / 9): Text2.Text = y
End Sub
Private Sub Command2_Click()
Form3.Hide: Form4.Show
End Sub
Private Sub Command3_Click()
Form3.Hide: Form2.Show
End Sub
Задача № 4
Постановка задачи: Составить программу определения, в норме ли вес обследуемого пациента (нормой считается вес, равный (рост(см)-100)5кг).
Интерфейс задачи:

Листинг программы:
Dim x As Integer, y As Integer
Private Sub Command1_Click()
x = Text1.Text
y = Text2.Text
If (y< (x - 100) - 5) Or (y> (x - 100) + 5) ThenMsgBox "Весневнорме" ElseMsgBox "Весвнорме"
End Sub
Private Sub Command2_Click()
Form4.Hide: Form5.Show
End Sub
Private Sub Command3_Click()
Form4.Hide: Form3.Show
End Sub
Задача № 5
Постановка задачи: Составить программу, определяющую сколько раз встречается заданное число (вводится с клавиатуры) в диапазоне от 10 до 352.
Интерфейс задачи:

Листинг программы:
Dim x As String, s As Integer
Private Sub Command1_Click()
x = Text1.Text
k = Len(x)
Select Case k
Case 1
s = 0
For i = 10 To 352
n = Len(i)
For j = 1 To n
For y = 1 To k
If Mid(x, y, 1) = Mid(i, j, k) Then s = s + 1
Next y
Next j
Next i
Case 2
s = 0
For i = 10 To 352
For j = 1 To k
If x = Mid(i, j, 2) Then s = s + 1
Next j
Next i
Case 3
s = 0
For i = 10 To 352
For j = 1 To k
If x = Mid(i, j, 3) Then s = s + 1
Next j
Next i
End Select
Text2.Text = s
End Sub
Private Sub Command2_Click()
Form5.Hide: Form6.Show
End Sub
Private Sub Command3_Click()
Form5.Hide: Form4.Show
End Sub
Задача № 6
1) Постановка задачи: Программа пересчитывает из кубического метра в галлон.
2)Интерфейс задачи:

3) Листинг программы:
Dim S As Integer
Dim T As Integer
If Not IsNumeric(Vvod.Text) Then
MsgBox("Неверныйформатзаписи!", MsgBoxStyle.OkOnly, Title:="Ошибка")
Else
S = Vvod.Text
T = S * 264
Vvod.Text = T
End If
Задача № 7
1) Постановка задачи: Программа пересчитывает из литра в галлон.
2)Интерфейс задачи:

3)Листинг программы:
Dim L, G As Double, dial As DialogResult
If Not IsNumeric(TextBox1.Text) Then
MessageBox.Show("неправильныйформат")
TextBox1.Focus()
Else
L = TextBox1.Text
G = L / 3.78541178
Label4.Text = G
End If
dial = MessageBox.Show("хотитепосчитатьещераз?", "Выйти", MessageBoxButtons.YesNo, MessageBoxIcon.Asterisk)
If dial = DialogResult.Yes Then
TextBox1.Text = ""
Label4.Text = ""
Else
Application.Exit()
EndIf
Задача № 8
1) Постановка задачи: Программа пересчитывает из метров в футы.
2)Интерфейс задачи:

3)Листинг программы:
Dim S As Double
Dim T As Double
If Not IsNumeric(Vvod.Text) Then
MsgBox("Неверныйформатзаписи!", MsgBoxStyle.OkOnly, Title:="Ошибка")
Else
S = Vvod.Text
T = S * 0,305
Vvod.Text = T
End If
Задача № 9
1) Постановка задачи: Программа пересчитывает из аршина в метр.
2)Интерфейс задачи:

3)Листинг программы:
Dim S As Double
Dim T As Double
If Not IsNumeric(Vvod.Text) Then
MsgBox("Неверныйформатзаписи!", MsgBoxStyle.OkOnly, Title:="Ошибка")
Else
S = Vvod.Text
T = S * 1.28
Vvod.Text = T
End If
Задача № 10
1) Постановка задачи: Программа пересчитывает рубли в евро.
2)Интерфейс задачи:

3)Листинг программы:
Dim S As Double
Dim T As Double
If Not IsNumeric(Vvod.Text) Then
MsgBox("Неверныйформатзаписи!", MsgBoxStyle.OkOnly, Title:="Ошибка")
Else
S = Vvod.Text
T = S * 50
Vvod.Text = T
End If
Задача № 11
1) Постановка задачи: Программа пересчитывает из ярда в метр.
2)Интерфейс задачи:

3)Листинг программы:
Dim S As Double
Dim T As Double
If Not IsNumeric(Vvod.Text) Then
MsgBox("Неверныйформатзаписи!", MsgBoxStyle.OkOnly, Title:="Ошибка")
Else
S = Vvod.Text
T = S * 1.905
Vvod.Text = T
End If
Задача № 12
1) Постановка задачи: Программа пересчитывает скорость ветра из м/с в км/ч.
2)Интерфейс задачи:

3)Листинг программы:
Dim SkorostAs Integer
Dim rezult As Integer
If Not IsNumeric(txtVvod.Text) Then
MessageBox.Show("Ошибка!", "ПРоверкаошибки", MessageBoxButtons.OK, MessageBoxIcon.Stop)
Else
Skorost = txtVvod.Text
rezult = Skorost * 360
lblResult.Text = rezult
EndIf
Задача № 13
1) Постановка задачи: Программа рассчитывает площадь квадрата.
2)Интерфейс задачи:

3)Листинг программы:
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim Side As Integer
Side = TextBox1.Text
Label1.Text = Square(Side)
'By value, ByVal, by reference ByRef
End Sub
Function Square(ByVal a As Integer) As Integer
Square = a ^ 2
End Function
Задача № 14
1) Постановка задачи: Программа рассчитывает значение по заданной формуле.S=i=1N (sinx)i2)Интерфейс задачи:

3)Листинг программы:
Dim N As Long, x, S1, S As Single
Dim k As Integer
Dim i As Integer
Dim dial As DialogResult
Public Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
If Not IsNumeric(TextBox1.Text) Or Not IsNumeric(TextBox2.Text) Then
MessageBox.Show("неправильныйформат")
TextBox1.Focus()
TextBox2.Focus()
Else
S1 = 1
N = TextBox1.Text
x = TextBox2.Text
For i = 0 To N
S1 = S1 * MATH.SIN(x)
Next i
Label4.Text = S
End If
EndSub
Задача № 15
1) Постановка задачи: Программа рассчитывает значение по заданной формуле. S=i=0NK=1Ni+xk2)Интерфейс задачи:

3)Листинг программы:
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles ButtonRasschitat.Click
Dim i As Integer
Dim k As Integer
Dim N As Integer
Dim S As Double = 1
Dim S1 As Double
Dim x As Integer
If Not IsNumeric(TextBoxChisloN.Text) Or Not IsNumeric(TextBoxChisloX.Text) Then
MsgBox("Неверныйформатзаписи!")
Else
N = TextBoxChisloN.Text
x = TextBoxChisloX.Text
For i = 0 To N
For k = 1 To N
S = S * ((i + x) / k)
Next k
S1 = S1 + S
Next i
TextBoxOtvet.Text = S1
TextBoxOtvet.Text = (Format(S1, "#.##"))
EndIf
EndSub
Задача № 16
1) Постановка задачи: Программа рассчитывает значение по заданной формуле. S=i=1N1xi2)Интерфейс задачи:

3)Листинг программы:
Dim N As Long, x, S1, S As Single
Dim k As Integer
Dim i As Integer
Dim dial As DialogResult
Public Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
If Not IsNumeric(TextBox1.Text) Or Not IsNumeric(TextBox2.Text) Then
MessageBox.Show("неправильныйформат")
TextBox1.Focus()
TextBox2.Focus()
Else
S1 = 1
N = TextBox1.Text
x = TextBox2.Text
For i = 0 To N
S1 = S1 + (1/x^i)
Next i
Label4.Text = S1
EndIf
EndSub
Задача № 17
1) Постановка задачи: Программа рассчитывает значение по заданной формуле. P=i=1Nx-i2)Интерфейс задачи:

3)Листинг программы:
Dim N As Long, x, S1, S As Single
Dim k As Integer
Dim i As Integer
Dim dial As DialogResult
Public Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
If Not IsNumeric(TextBox1.Text) Or Not IsNumeric(TextBox2.Text) Then
MessageBox.Show("неправильныйформат")
TextBox1.Focus()
TextBox2.Focus()
Else
S1 = 1
N = TextBox1.Text
x = TextBox2.Text
For i = 1 To N
S1 = S1 *(x-i)
Next i
Label4.Text = S1
EndIf
EndSub
Теоретические задания: по дисциплине «Дискретная математика»
Составные высказывания
Основные логические операции. Формулы логики. Дизъюнктивная
конъюнктивная нормальные формы
Построение таблицы истинности для формулы логики
Изучение законов логики. Равносильные преобразования.
Упрощение формул логики с помощью равносильных преобразований.
Булевы функции.
Совершенная дизъюнктивная и конъюнктивная нормальные формы (СДНФ и
СКНФ)
Представление булевой функции в виде совершенной ДНФ и КНФ,
минимальной КНФ, полинома Жегалкина
Понятие полноты множества функций. Замкнутые классы
Проверка булевой функции на принадлежность к замкнутым классам, на
полноту.
Множества и подмножества.
Операции над множествами
Понятие предикат.
Логические операции над предикатами.
Определение логического значения для высказываний
Построение отрицаний к предикатам.
Понятие бинарного отношения и его свойства.
Отношение эквивалентности.
Исследование бинарных отношений на рефлексивность, симметричность и
транзитивность; выделение классов эквивалентности
Композиция отображений
Операции над подстановками
Решение задач на запись циклического разложения подстановки
Выполнение операций и решение простейших уравнений в алгебре подстановок.
Понятие вычета по модулю N. Операции над вычетами. Шифрование
Метод математической индукции
Решение задач на выполнение операций в алгебре вычетов
Генерирование К-элементных подмножеств данного множества
Понятие графа. Способы задания графа. Методика выделения компонента
связности в графе
Распознавание мостов и разделяющих вершин в графе
Нахождение расстояния между вершинами в графе.
Изоморфные графы. Эйлеровы графы
Плоские графы. Деревья и их свойства
Проверка графа на плоскость.
Практические задания: по дисциплине «Дискретная математика»
Задачи с решениями.
Задача №18
Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, К-В, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?
Решение:
Составим схему-граф маршрутов:

Мы видим, что от З до М добраться нельзя.
Задача №19
25 борцов играют по олимпийской системе (проигравший выбывает). За какое наименьшее количество встреч можно определить победителя?
Решение:
После каждой встречи 1 боец выбывает, в конце останется только один боец, значит наименьшее количество встреч 24.
Задача № 20
Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Решение:
Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена.
Если подсчитать число ребер графа, изображенного на рисунке справа, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Задача № 21
Кенигсбергские мосты.
К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города 0158750(см.рисунок)
Задача заключается в следующем: нужно пройти (если это возможно) по всем семи мостам так, чтобы на каждом из них побывать лишь по одному разу и вернуться к тому месту, откуда начал маршрут.
Решение:
Решить эту задачу удалось в 1736 г. Леонарду Эйлеру . В ходе решения задачи (после интерпретации условия задачи в виде графа, где вершины - острова и берега, а ребра - мосты, представленного на рисунке.)
22860088900
Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа, представленного на рисунке. Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то, согласно закономерности 7 такой граф начертить «одним росчерком» невозможно. Значит, и пройти по кенигсбергским мостам, соблюдая заданные условия,нельзя.
Задача № 22
В трех различных домах живут три поссорившиеся между собой соседа. Недалеко от их домов имеются три колодца. Можно ли от каждого дома проложить к каждому из колодцев тропинку так, чтобы никакие две из них не пересекались?

Решение:
Построим граф, вершины которогоА, Б, В, 1, 2, 3соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку — ребро графа, не пересекающее остальные ребра, провести нельзя.

Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).Таким образом, ответ на вопрос задачи будет таким: «Нельзя!»
Задача № 23
В городе Н от каждой площади отходит ровно 5 улиц, соединяющих площади. Докажите, что число площадей чётно, а число улиц кратно 5.
Решение:
По теореме, что число нечётных вершин любого графа чётно, следует, что число площадей (вершин графа) 2n, а число улиц (рёбер графа) будет (2n·5):2, а значит, число площадей чётно, а число улиц кратно 5.
Задача № 24
Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый – с тремя чёрными и тремя белыми. Сколько лоскутов белого цвета?
Решение:
Пусть на мяче число белых лоскутов х шт., а чёрных будет (32 – х) шт. Тогда границ белых лоскутов с чёрными 5(32-х)=3х, значит, х=20 и белых лоскутов 20 шт.
Задача № 25
В государстве система авиалиний устроена таких образом, что любой город соединён авиалиниями не более чем с тремя другими и из любого города в любой другой можно проехать, сделав не более одной пересадки. Какое максимальное число городов может быть в этом государстве?
Решение:
Пусть существует некоторый город А. Из него можно добраться не более, чем до трёх городов, а из каждого из них ещё не более чем до двух (не считая А). Тогда всего городов не более 1+3+6=10. Значит всего городов не более 10. Пример на рисунке (его ещё называют графом Петерсона) показывает существование авиалиний.

Задача № 26
Можно ли нарисовать графы изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

Решение:
Можно, т. к. только 2 нечетные вершины.
Нельзя, т. к. 4 нечетные вершины.
Задача № 27
Доказать: (AB, A).
Доказательство:
A B AB A
И И И Л Л Л
И Л Л И И Л
Л И И Л И И
Л Л И И И И
Из определения следует, что противоречие логически влечет любую формулу, а тавтология логически следует из любой формулы логики.
Определение. Формулы F и G называются равносильными, если они являются логическими следствиями друг друга. Обозначение: .
Проанализировав последнее определение, получаем, что формулы равносильны, если они на всех наборах значений переменных превращаются в одинаковые по истинностному значению высказывания.
Задача № 28
Доказать закон отрицания конъюнкции ()
Доказательство:
Найдем значения для и и сравним их.
A B
И И И Л Л Л Л
И Л Л И Л И И
Л И Л И И Л И
Л Л Л И И И И
Задача № 29
Найти значение и убедиться, что при всех значениях A и B - это истинное значение.
Решение:
A B
И И И Л Л Л Л И
И Л Л И Л И И И
Л И Л И И Л И И
Л Л Л И И И И И
Задача № 30
С помощью основных равносильностей доказать закон обобщенного склеивания .
Решение. Применяя закон склеивания (в обратном порядке, то есть ) и дистрибутивность (то есть вынесем за скобки и ), получим
.
Задача № 31
Записать предложение: прямая а параллельна прямой b с помощью предиката.
Решение:
Предметная область – множество прямых.
Введем предикат Р (х), х – прямая. Предикат параллельности х||у
Тогда предложение можно записать в виде: Р (а) Р(b) (а||b) .
Задача № 32
Записать с помощью предиката:
Аксиома: через две различные точки проходит единственная прямая. (Ели две точки принадлежат двум прямым, то эти прямые совпадают).
Решение:
Введем предикаты
Т (х), х – точка; Р (х), х – прямая; J(x,y) - x у. Тогда можно записать:
Т (А)Т (В)(А ≠ В)Р (а)Р(b)J(A,a)J(B,а)J(A,b)J(B,b) (a=b).
Задача № 33
Установить последнюю цифру степени y=2 2007
Решение.
Имеем 2007=501·4+3, значит f (2007)=f (3)=23=8. Ответ: 8
5. Описание процедуры экзамена
Комплексный экзамен по дисциплинам «Основы алгоритмизации и программирования»
и «Дискретная математика» проводится в соответствии с расписанием по экзаменационным билетам, согласованным с ПЦК и утвержденным заместителем директора по КОД.
Количество экзаменационных билетов превышает количество обучающихся.
В билете – 2 теоретических вопроса и 1 практическое задание На подготовку к ответу обучающемуся отводится до 30 минут.
Обучающийся предъявляет ответы в устной (письменной, смешанной) форме: устно раскрывает теоретические вопросы; решение задачи представляется в письменном виде с устными комментариями (пояснениями).
Требования охраны труда: инструктаж по технике безопасности, правилам поведения на занятии, по соблюдению дисциплины, наличие инструктора (преподаватель).
6. Критерии оценки:
Оценка "отлично" ставиться обучающемуся, обнаружившему всестороннее, систематическое и глубокое знание учебно-программного материала, умение свободно выполнять задания, предусмотренные программой, усвоившему основную литературу, рекомендованную программой, взаимосвязь основных понятий дисциплины в их значении для приобретаемой профессии, проявившему творческие способности в понимании, изложении и использовании учебно-программного материала.
Оценка "хорошо" ставиться обучающему, показавшему полное знание учебно-программного материала, успешно выполняющему предусмотренные в программе задания, усвоившему основную литературу, рекомендованную в программе, показавшему систематический характер знаний по дисциплине и способному к их самостоятельному пополнению и обновлению в ходе дальнейшей учебной работы и профессиональной деятельности.
Оценка "удовлетворительно" ставиться обучающему, показавшему знания основного учебно-программного материала в объеме, необходимом для дальнейшей учебы и предстоящей работы по специальности, справляющемуся с выполнением заданий, предусмотренных программой, знакомому с основной литературой, рекомендованной программой. Оценка "удовлетворительно" выставляется обучающемся, допустившим погрешности в ответе на экзамене и при выполнении экзаменационных заданий, но обладающим необходимыми знаниями для их устранения под руководством преподавателя.
Оценка "неудовлетворительно" выставляется обучающемуся, обнаружившему пробелы в знаниях основного учебно-программного материала, допустившему принципиальные ошибки в выполнении предусмотренных программой заданий, оценка "неудовлетворительно" ставится обучающимся, которые не могут продолжить обучение или приступить к профессиональной деятельности по окончании колледжа без дополнительных занятий по соответствующей дисциплине.
7. Перечень материалов, оборудования и информационных источников, используемых при проведении промежуточной аттестации
При проведении промежуточной аттестации обучающимся могут пользоваться конспектом лекций, ПК, справочными материалами.
8. Эталоны ответов на теоретические вопросы:
Эталоны ответов на теоретические задания: по дисциплине «Основы алгоритмизации и программирования»
Основные понятия алгоритмизации. Понятия «алгоритм», «исполнитель алгоритма».
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.
Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.
Свойства и формы записи алгоритмов.
Основные свойства алгоритмов следующие:
1.  Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.
2.   Дискpетность (прерывность, раздельность) — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).
3.   Опpеделенность — каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола. Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче.4.   Pезультативность (или конечность) состоит в том, что за конечное число шагов алгоpитм либо должен пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
Массовость означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.
На практике наиболее распространены следующие формы представления алгоритмов:
- словесная (запись на естественном языке);
- графическая (изображения из графических символов);
- псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы -естественного языка, общепринятые математические обозначения и др.);
- программная (тексты на языках программирования).
Основные алгоритмические конструкции: линейные, разветвляющиеся и циклические.
1.Базовая структура  "следование". Образуется последовательностью действий, следующих одно за другим.
2.Базовая структура  "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:
если—то;
если—то—иначе;
выбор;
выбор—иначе.
3.Базовая структура  "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Логические основы алгоритмизации. Основы алгебры логики.
Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями.
Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее  основные положения. В булевой  алгебре высказывания принято обозначать прописными латинскими буквами: A, B, X, Y. В алгебре Буля введены три основные логические операции с высказываниями? Сложение, умножение, отрицание. Определены аксиомы (законы) алгебры логики для выполнения этих операций. Действия, которые производятся над высказываниями, записываются в виде логических выражений.
Логические операции: конъюнкция, дизъюнкция, инверсия, импликация, эквиваленция.
Операция И — логическое умножение (конъюнкция)
Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Операция ИЛИ — логическое сложение (дизъюнкция, объединение)
Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое бу¬дет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Операция НЕ — логическое отрицание (инверсия)
Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение.
Операция «ЕСЛИ-ТО» — логическое следование (импликация)
Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.
Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
Законы алгебры логики.
1. Закон одинарных элементов
2. Законы отрицания
a. Закон дополнительных элементов
 b. Двойное отрицание
  c. Закон отрицательной логики
3. Комбинационные законы
a. закон тавтологии (многократное повторение)
b. закон переместительности
c. закон сочетательности
d. закон распределительности
4. Правило поглощения (одна переменная поглощает другие)
5. Правило склеивания (выполняется только по одной переменной)
Таблицы истинности.
Таблица истинности — это таблица, описывающая логическую функцию.
Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь».
Конъюнкция




Дизъюнкция




Сложение по модулю 2




Импликация




Эквиваленция




Штрих Шеффера




Стрелка Пирса




Отрицание


Составление таблиц истинности для сложных логических функций.
Алгоритм построения таблиц истинности для сложных выражений:
Определить количество строк:
количество строк = 2n + строка для заголовка,
n - количество простых высказываний.
Определить количество столбцов:
количество столбцов = количество переменных + количество логических операций;
определить количество переменных (простых выражений);
определить количество логических операций и последовательность их выполнения.
3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
Составление блок-схем алгоритмов.
Блок-схемой называют графическое представление алгоритма, в котором он изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
Приведем наиболее часто употребляемые символы.
Название Элемент Комментарий
Процесс Вычислительное действие или последовательность вычислительных действий
Решение Проверка условия
Модификация Заголовок цикла
Предопределенный процесс Обращение к процедуре
Документ Вывод данных, печать данных
Перфокарта Ввод данных
Ввод/Вывод Ввод/Вывод данных
Соединитель Разрыв линии потока
Начало, Конец Начало, конец, пуск, останов, вход и выход во вспомогательных алгоритмах
Комментарий Используется для размещения надписей
Горизонтальные и вертикальные потоки Линии связей между блоками, направление потоков
Слияние Слияние линий потоков
Межстраничный соединитель Нет
Языки и системы программирования. Языки высокого и низкого уровня.
Язы́к программи́рования — формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, задающих внешний вид программы и действия, которые выполнит исполнитель (компьютер) под её управлением.
Языки программирования низкого уровня.
Первые компьютеры приходилось программировать двоичными машинными кодами. Однако программировать таким образом - довольно трудоемкая и тяжелая задача. Для упрощения этой задачи начали появляться языки программирования низкого уровня, которые позволяли задавать машинные команды в понятном для человека виде. Для преобразования их в двоичный код были созданы специальные программы - трансляторы.
Языки программирования высокого уровня.
Особенности конкретных компьютерных архитектур в них не учитываются, поэтому созданные приложения легко переносятся с компьютера на компьютер. В большинстве случаев достаточно просто перекомпилировать программу под определенную компьютерную архитектурную и операционную систему. Разрабатывать программы на таких языках значительно проще и ошибок допускается меньше. Значительно сокращается время разработки программы, что особенно важно при работе над большими программными проектами.
Правила записи выражений и операций. Типы данных. Синтаксис.
Типы данных Visual Basic.
Тип данных Объем занимаемой памяти Краткая запись
Целые типы    
Integer (целое) 2 байта %
Long (целое двойной длины) 4 байта &
Byte (Байт) 1 байт  
Boolean (булево) 2 байта  
Плавающие типы  
Single
Десятичные числа 4 байта !
Double
Десятичные числа 8 байт #
Строковые типы  
StringТекстовая информация 1 байт на каждый символ $
Объектные типы    
Object
Рисунки или ссылки на любой другой объект 4 байта  
Variant-типы    
Variant
(числовые типы) 16 байт  
Variant(строковые типы) 22 байта +длина строки  
Прочие типы    
Currency
Число в денежном формате 8 байт @
Date
Дата 8 байт  
Синтаксис.
Dim a as Integer
Понятие модуля и формы.
В Visual Basic весь программный код находится внутри процедур (подпрограмм). Общая структура описания подпрограммы Visual Basic:
Sub <имя_подпрограммы> [(<параметры>)] <операторы> End Sub
Такие процедуры могут вызываться или самим Visual Basic, или другими процедурами. Вызов подпрограммы выполняется с помощью следующих операторов:
Call <имя_подпрограммы> [(<параметры>)];
<имя_подпрограммы> [<параметры>]. Функция построена точно так же, как и процедура, однако результатом работы функции является возвращаемое значение (только одно).
Общая структура описания функции следующая:
Function <имя_функции> [(<аргументы>)] [As <Тип>] <операторы> <имя_функции> = <выражение> End Function
Вызов функции выполняется с помощью оператора; присваивания:
<переменная> = <имя_функции> {(<аргументы>)].
Пользовательские типы данных.
Содержит данные в определенном пользователем формате. Оператор Structure определяет формат.
Формат объявления
Объявление структуры начинается с оператора Оператор Structure и завершается оператором EndStructure.Оператор Structure содержит имя структуры, которая является также идентификатором типа данных, определяемых структурой. Другие части кода могут использовать этот идентификатор для объявления переменных, параметров и возвращаемых значений функций в качестве типа данных структуры.
Объявления между операторами Structure и EndStructure определяют члены структуры.
Уровни доступа к членам
Каждый член необходимо объявить с помощью оператора Оператор Dim (Visual Basic) или оператора, определяющего уровень доступа, например, Public (Visual Basic) или Friend (Visual Basic) или Private (Visual Basic). Если используется оператор Dim, то уровень доступа по умолчанию является открытым (Public).
Использование форм, событий и методов.
Как объекты, так и формы могут выполнять методы и реагировать (откликаться) на события.
При каждом изменении размера формы в результате действий пользователя или программным способом инициируется событие Resize (Изменить размер) формы. Это позволяет изменять размеры элементов управления на форме или перемещать их, когда изменены размеры самой формы.
Событие Activate (Активизировать) происходит всегда, когда форма становится активной, а событие Deactivate (Деактивировать) - когда активной становится другая форма приложения. Эти события удобны для организации поведения формы при ее инициировании и завершении работы с ней. Например, можно написать код, который в случае события Activate выделит текст в каком-нибудь тeкcтoвoм окне, а в случае события Deactivate внесенные изменения будут сохранены в файле или базе данных.
Чтобы сделать форму видимой, следует вызвать метод show (Показать):
Form2.Show
Вызов метода show имеет тот же эффект, что и установка значения свойства visible (Видимый) формы в True (Истина).
Многие из методов формы работают с текстом или графикой. Методы Print (Печатать), Line (Линия), Сircle (Окружность) и Refresh (Обновить) полезны для печати или рисования непосредственно на поверхности формы.
Свойство Container
Свойство container (Набор) используется для изменения набора объектов внутри формы. Следующие элементы управления могут содержать другие элементы управления:
 Рамка
 Графическое окно
Использование управляющих элементов.
Элемент управления ADO Data
Элемент управления ADO Data (рис. 1) обеспечивает связь между поставщиком данных OLE DB (OLE DB Provider) и элементами управления, обладающими свойством DataSource (CheckBox, ComboBox, Image, Label, ListBox, PictureBox и TextBox).

Рис. 1
ADO Data может применяться в следующих случаях:
для связи с локальной или удаленной базой данных;
для открытия (просмотра) заданной таблицы в базе данных или определения группы записей, основанных либо на SQL-запросе, либо на хранящейся процедуре;
для передачи значений полей данных в связанные с данными элементы управления;
для обновления базы данных.
ADO Data добавляется к формам аналогично любому другому элементу управления, причем их количество в форме не ограничено. Однако следует помнить о том, что данный элемент управления является ресурсоемким: ему требуется по крайней мере два соединения для первого компонента и по одному для каждого последующего.
Составление программ циклической структуры.
Операторы циклов
В языке VB существует 3 вида циклов: 1) цикл с параметром или цикл типа for; 2) цикл с предусловием или цикл типа while, 3) цикл с постусловием или цикл типа do ... while . Во всех этих циклах условие продолжения цикла заключается в круглые скобки. В циклах типов for и while повторяющаяся часть  состоит из одного оператора, если требуется выполнить в цикле несколько операторов, они заключаются в фигурные скобки,  образуя составной оператор. В цикле с постусловием тело цикла помещается между  словами  do и while.  В отличие от цикла с предусловием, цикл с постусловием выполнится хотя бы один раз. Циклы с пред- и  постусловием   продолжаются, если условие  продолжения  истинно. 
Логические операторы и операторы сравнения If...Then, SelectCase.
Конструкция If...Then...Else аналогична конструкции If...Then, но позво-ляет задать действия, исполняемые как при выполнении условий, так и в слу-чае их невыполнения.
Конструкция имеет следующий синтаксис:
If условиеThen
конструкции для обработки истинного условия
Else
конструкции для обработки ложного условия
End If
Ключевые слова If и End If имеют тот же смысл, что и в конструкции
If...Then. Если заданное в конструкции условие не выполняется (результат
проверки равен False) и конструкция содержит ключевое слово Else, Visual
Basic выполнит последовательность конструкций, расположенных следом за
Else. После чего управление перейдет к конструкции, следующей за End If.
Например:
If x >= 0 Then
Label1.Text = "Значение больше или равно 0"
Else
Label1.Text = "Значение меньше 0"
End If
Конструкция Select Case позволяет обрабатывать в программе несколько условий. Она аналогична блоку конструкций If...Then...Else. Эта конструкция состоит из анализируемого выражения и набора операторов Caseна каждое возможное значение выражения. Работает данная конструкция следую-
Основы программирования в Visual Basic 2010 65
щим образом. Сначала Visual Basic вычисляет значение заданного в конструкции выражения. Затем полученное значение сравнивается со значениями,
задаваемыми в операторах Case конструкции. Если найдено искомое значение, выполняются команды, приписанные данному оператору Case. После
завершения выполнения конструкций управление будет передано конструкции, следующей за ключевым словом End Select.
Синтаксис конструкции Select Case следующий:
Select Case сравниваемоеЗначение
Case значение1
операторы1
Case значение2
операторы2
...
Case Else
операторыN
End Select
В начале конструкции расположены ключевые слова Select Case, указываю-щие, что находящийся рядом с ними параметр сравниваемоеЗначение будет
проверяться на несколько значений. Затем в конструкции размещены группы
команд, начинающиеся с ключевого слова Case. Если параметр сравниваемое-Значениеравно значению, указанному в текущем операторе Case, то будут
выполняться команды, расположенные между этим и следующим ключевым
словом Case. Конструкция может содержать любое количество ключевых
слов Caseс соответствующими им блоками операторов. Если ни одно значе-ние не подошло, будут выполнены операторы, следующие за ключевыми
словами Case Else. Ключевые слова Case Elseмогут быть опущены.
Обзор структуры цикла. Использование Do...Loop, Использование For...Next.
Цикл, задаваемый конструкцией Do...Loop, выполняется до тех пор, пока ис-тинно задаваемое в цикле условие.
Синтаксис конструкции Do...Loop имеет следующий вид:
Do While условие
операторы
Loop
Аргумент конструкции условиеявляется логическим выражением, значение
которого проверяется перед каждым проходом цикла. Если это значение рав-но True, выполняется последовательность команд, которые расположены ме-жду Do Whileи ключевым словом Loop. Эти конструкции образуют тело цик-ла. Если при очередном проходе цикла условиеравно False, происходит вы-ход из цикла и управление передается конструкции, следующей за Loop.
Возможна ситуация, при которой операторы цикла не выполняются ни разу.
Она возникает в том случае, если при первой проверке условие оказывается
ложным.
Конструкция For...Next выполняет последовательность команд определенное
число раз. Такую конструкцию называют циклом, а выполняемые ею про-граммные коды — телом цикла.
Синтаксис конструкции For...Nextследующий:
For счетчик[As типДанных] = начЗначениеTo конЗначение[Step шаг]
операторы
Next [счетчик]
Первый аргумент конструкции счетчикопределяет имя переменной, которая
будет "считать" количество выполненных циклов. Эту переменную можно
объявить прямо в конструкции. Параметр начЗначение указывает числовое
значение, которое присваивается переменной-счетчику перед первым прохо-дом цикла. Цикл выполняется до тех пор, пока значение счетчика не превы-сит конечное значение, указанное после ключевого слова To. После каждого
прохода значение счетчика изменяется на величину шаг, указанную после
ключевого слова Step. Ключевое слово Next обозначает конец тела цикла и
является обязательным.
Перед каждым проходом цикла Visual Basic сравнивает значения счетчика и
аргумента конЗначение. Если значение счетчика не превышает установленно-го значения конЗначение, выполняются конструкции тела цикла. В противном
случае управление переходит к следующей за Next конструкции.
Работа с логическими операторами и операторами сравнения.
Над условными выражениями можно выполнять действия логической мате-матики (логические операции), а именно:
AND(И) — возвращает значение True, если все участвующие в операции
выражения имеют значение True. В остальных случаях возвращается зна-чение False;
OR(ИЛИ) — возвращает значение True, если хотя бы одно из участвующих
в операции выражений имеет значение True. В случае, когда все выраже-ния имеют значение False, возвращается значение False;
XOR(исключающее ИЛИ) — возвращает значение True, если только одно
из участвующих в операции выражений имеет значение True. В остальных
случаях возвращается значение False;
NOT(НЕ) — операция отрицания. Возвращает обратное значение для зна-чения выражения, т. е. если выражение равно True, то возвращается False,
и наоборот, если значение выражения равно False, то возвращается значе-ние True.
Написание кода с использование операторов и циклов.
Разложить по этапам написание программ с использованием циклов.
Какие циклические конструкции бывают.
Операторы, какие они бывают.
Отслеживание и анализ ошибок.
Ошибки в программе могут быть синтаксическимиили смысловыми. Синтак-сические ошибки наиболее очевидны. Они возникают, если код написан без
соблюдения правил языка программирования. Эти ошибки обнаруживают-
ся компилятором, который выдает соответствующее сообщение. В Visual
Basic 2010 такие сообщения отображаются в окне Error List(Список оши-бок). В них указаны номер строки, файл, в котором обнаружена ошибка, и
краткое ее описание. Обнаружение и исправление данных ошибок является
достаточно легким и быстрым.
В набор инструментария отладки Visual Basic 2010 входят такие основные
инструменты, как:
панель инструментов Standard(Стандартная), а также Debug(Отладка)
с кнопками выполнения команд для отладки приложения;
окно Immediate Window(Окно непосредственного выполнения), предна-значенное для непосредственного ввода команд, требующих немедленного
выполнения;
окно Watch (Наблюдение), служащее для просмотра значений выражений,
включенных в список просмотра;
окно Locals(Локальные переменные), предназначенное для просмотра
значений переменных;
редактор кода со встроенными возможностями просмотра переменных,
констант, свойств, выражений при отладке приложения в точках останова
и пошаговом выполнении приложения;
окно Call Stack(Стек вызовов) для просмотра вызванных, но незавершен-ных процедур.
Обзор стандартных элементов.
Помимо индивидуальных свойств, каждый элемент управления содержит
общие для большинства свойства. В табл. 4.1 перечислены наиболее часто
используемые свойства элементов управления.


Дополнительные возможности стандартных элементов.
А. Использование в форме графики.
Б. Полосы прокрутки.
В. Таймер.
Г. Задание даты.
Д. Вкладки.
Е. Элемент управления SplitContainer.
Ж. Элемент управления TabelLayoutPanel.
З. Индикатор прогресса.
И. Ползунок.
К. Гиперссылка.
Л. Элемент управления NotifyIcon.
М. Элемент управления TreeView и ListView.
Использование ComboBox и ListBox.
Списки типа ComboBox называют раскрывающимися или полями со спи-ском. Оба названия верны. Раскрывающимися их называют потому, что для
выбора значения из списка сначала необходимо список открыть, нажав кноп-ку со стрелкой, расположенную с правой стороны поля ввода. Второе назва-ние — поле со списком — они получили из-за того, что по своим функциям
список типа ComboBox совмещает функции списка ListBox и поля ввода
TextBox.Иными словами, из списка ComboBox данные можно не только выби-рать, но и вводить новое значение в находящееся в верхней части поле ввода.
Использование списков ComboBox позволяет представлять большой объем
информации, экономя при этом место в форме.
Элемент управления ListBox, размещенный в форме, представляет собой
список, из которого пользователь может выбрать одно из предложенных значений. Значения в списке могут размещаться в одну или несколько колонок в
зависимости от значения свойства MultiColumn. Если элементы списка распо-ложены в нескольких колонках, с помощью свойства ColumnWidth можно из-менить заданную по умолчанию ширину колонок.
В том случае, если элементы списка не помещаются в выделенную для них
в форме область, появляются полосы прокрутки, позволяющие просмот-
реть весь список. Чтобы полоса прокрутки элемента управления ListBox
всегда отображалась, необходимо присвоить значение Trueсвойству
ScrollAlwaysVisible.
Возможность частичного отображения элемента списка задается с помощью
свойства IntegralHeight. Если указано значение True, то в списке может ото-бражаться только строка целиком.
Написание функций.
Процедуры Functionв отличие от процедур Subмогут возвращать значение в
вызывающую процедуру. Синтаксис процедуры Functionимеет следующий
вид:
уровеньДоступностиFunction имяПроцедуры(аргументы) [As тип]
операторы
End Function
В качестве уровня доступности может быть указано Public, Protected, Friend,
Protected Friendили Private.
Процедуры Function, как и переменные, имеют тип, задаваемый с помощью
ключевого слова As. Если тип процедуры не задан, по умолчанию ей при-сваивается тип Object.
Тип процедуры определяет в свою очередь тип возвращаемого ею значения.
Возвращаемым значениемназывается значение, которое функция передает
обратно в вызвавшую ее программу.
значение присваивается самому имени функции один или несколько раз
по ходу выполнения процедуры. Управление (и, соответственно, возвра-щаемое значение) не будет передано в программу, вызвавшую функцию,
до тех пор, пока не выполнится Exit Functionили End Function;
использованием оператора Return, чтобы определить возвращаемое значе-ние с немедленной передачей управления программе, вызвавшей функ-цию.
Function Square(ByVal a As Integer) As Integer
Square = a ^ 2
End Function
Использование в форме графики. PictureBox, ImageList.
В Visual Basic для отображения в форме графики используются элементы
управления PictureBoxи ImageList. Объект PictureBoxпозволяет разместить
на форме графические изображения, а объект ImageListслужит для хранения
списка изображений, которые можно расположить на элементах управления
формы.
Для размещения изображения в форме выполните следующие действия:
1. Перетащите на форму элемент управления PictureBox . С помощью
мыши или свойства Sizeзадайте необходимый размер изображения.
2. Для задания имени графического файла предназначено свойство Image.
Выберите это свойство в окне Properties(Свойства) и нажмите кнопку
с тремя точками, расположенную в правом столбце. Откроется диалоговое
окно, позволяющее выбрать графический файл.
Элемент управления ImageList является хранилищем графических изо-бражений, для отображения которых в форме необходимо использовать дру-гие элементы управления.
Для создания списка графических изображений следует перетащить элемент
управления ImageList на форму. Он не будет виден на форме, а разместится в
нижней части конструктора формы.
Для добавления изображений в список применяется свойство Images элемента
управления ImageList. При нажатии кнопки с тремя точками, расположенной
справа от названия свойства, открывается диалоговое окно Images Collection
Editor(Редактор изображений) — рис. 5.3. В этом окне находятся кнопки
Add(Добавить) и Remove(Удалить), позволяющие добавлять графические
изображения в список или удалять их из него. При нажатии кнопки Add(Добавить) открывается диалоговое окно открытия файла для выбора соответст-вующего рисунка. После добавления элемента в список он располагается в
поле Members(Элементы) окна Images Collection Editor(Редактор изобра-жений). Слева от названия элемента указан его индекс, а в правой части окна
выводятся свойства изображения, такие как разрешение, размер и формат.
Для изменения индекса того или иного рисунка необходимо выбрать его
в поле Members(Элементы) и с помощью кнопок и переместить
в нужное место.
Создание программы с использованием полос прокрутки, таймера и заданием даты.
На форме можно размещать горизонтальные и вертикальные полосы
прокрутки с помощью элементов управления HScrollBarи VScrollBar. Полосы прокрутки встречаются при работе с документами программы Microsoft Word и другими программными продуктами, работающими
в среде Windows. Они также используются в многострочных текстовых полях
и списках, в которых информация целиком не помещается. Элементы управ-ления VScrollBar и HScrollBar отличаются от полос прокрутки, встроенных
в перечисленные элементы, т. к. они существуют самостоятельно и применя-ются для элементов, не имеющих собственных полос прокрутки, или группы
элементов.
В Visual Basic существует элемент управления, который обрабатывает дан-ные системных часов. Этот объект называется таймером. Его можно приме-нять для выполнения определенных действий через заданный интервал вре-мени.
Для размещения в форме таймера используется элемент управления Timer.
Событие Tick таймера наступает через каждый установленный в свойстве
Intervalпромежуток времени. В процедуре обработки данного события не-обходимо определить действия, выполняемые с заданной частотой.
Для запуска и останова таймера помимо свойства Enabledможно использо-вать методы Startи Stop.
В Visual Basic существуют элементы управления MonthCalendarи
DateTimePicker, позволяющие работать с датами. Объект MonthCalendarпред-ставляет собой календарь, с помощью которого можно выбрать некоторый
диапазон дат. Элемент управления DateTimePickerимеет вид текстового поля
с расположенной справа кнопкой, при нажатии которой открывается кален-дарь. Этот элемент управления, как правило, используют для экономии места
на форме и при выборе одной даты.
Создание вкладок, индикатора прогресса, ползунка.
Visual Basic позволяет создавать формы, содержащие несколько вкладок.
Объекты данного типа удобно использовать в том случае, когда необходимо
разместить большой объем информации или когда для удобства работы тре-
буется основную, наиболее часто используемую информацию, сгруппировать
в одном месте, отделив ее от менее важной информации.
Для создания вкладок в форме предназначен элемент управления TabControl
.Рассмотрим размещение данного элемента в форме и настройку его
свойств:
1. Откройте форму, в которой хотите создать вкладки.
2. Нажмите кнопку TabControlна панели элементов управления.
3. Установите указатель в форму и, удерживая кнопку мыши в нажатом со-стоянии, переместите курсор по диагонали так, чтобы получилась рамка
размером с форму.
4. Откройте окно свойств созданного объекта. Для добавления вкладок вы-берите свойство TabPagesи нажмите кнопку с тремя точками, расположен-ную справа.
5. В открывшемся диалоговом окне TabPage Collection Editor(Редактор
вкладок) с помощью кнопки Add(Добавить) добавьте необходимое коли-чество вкладок.
6. В этом же окне можно настроить свойства вкладок. Для этого выберите в
поле Members(Элементы) нужную вкладку, а с помощью расположенной
справа области задайте требуемые значения для свойств. Например, ис-пользуя свойство Text, задайте заголовки вкладок.
7. Нажмите кнопку OKдля закрытия диалогового окна.
Некоторые операции вашего приложения могут выполняться довольно про-должительное время. Это может быть, например, обработка большого масси-ва данных или сложная выборка из базы данных, содержащей огромное ко-личество записей. В подобной ситуации пользователь начнет нервничать, не
зависла ли программа. Работу продолжительных задач можно сопровождать
отображением на экране индикатора процесса выполнения, используя для
этого стандартный элемент управления ProgressBar.
Элемент управления TrackBar представляет собой ползунок, позволяю-щий вводить в программу числовые значения.
Свойство TickStyle задает расположение делений на линейке ползунка и может принимать следующие значения:
Both— деления расположены по обеим сторонам ползунка;
BottomRight— у горизонтального ползунка деления расположены снизу,
у вертикального — справа;
None— деления у ползунка отсутствуют;
TopLeft— у горизонтального ползунка деления расположены сверху,
у вертикального — слева.
Гиперссылки. Список.
Для создания гиперссылок используется элемент управления LinkLabel ,
представляющий собой усовершенствованный элемент Label, т. е. обладаю-щий всеми свойствами элемента Labelи имеющий специфичные, предназна-ченные для создания гиперссылок, свойства. Каждая гиперссылка может вы-полнять различные функции в приложении. Например, она может использо-ваться в качестве ссылки на сайт в Интернете или для открытия новой
формы.
Элемент управления LinkLabelможет содержать одну или более ссылок и в
зависимости от этого различают способы настройки данного элемента. Рас-смотрим каждый случай отдельно.
Элемент управления ListView представляет собой список элементов с ис-пользованием пиктограмм, аналогичный используемому в правой части окна
Проводника.
В зависимости от свойства Viewсписок может принимать следующий вид:
Details(Таблица), LargeIcon(Крупные значки), List(Список), SmallIcon
(Мелкие значки), Tile(Плитка).
Чтение и запись файла. Класс FileStream.
Для выполнения основных операций с файлами, такими как получение ин-формации о файле, создание нового файла, удаление, копирование и переме-щение, предназначены классы Fileи FileInfo.
Класс Fileсодержит статические методы, при вызове которых требуется ука-зание в качестве параметра имени файла. При работе с классом FileInfo
с помощью конструктора создается представляющий конкретный файл
экземпляр класса.
При работе с текстовыми файлами, например, при записи в них информации
и считывании данных, используются классы FileStream, StreamReader,
StreamWriter. Для выполнения бинарных операций с файлами применяются
классы BinaryReaderи BinaryWriter.
Класс FileStream, который является производным от абстрактного класса
Stream, поддерживает операции синхронного и асинхронного открытия, чте-ния и записи последовательности байтов в файл. Класс имеет следующий
конструктор:
Sub New(ByVal pathAs String, ByVal modeAs FileMode,
ByVal accessAs FileAccess, ByVal shareAs FileShare,
ByVal bufferSizeAs Integer, ByVal useAsyncAsBoolean) _
As FileStream
где:
path— полное имя файла, включающее само имя файла и путь к нему;
mode— режим доступа к файлу. Может принимать значения, указанные
в табл. 7.4;
access— тип доступа к файлу. Определяет характер действий с файлом
(чтение или запись данных). Может принимать значения: Read(Чтение),
Write(Запись) или ReadWrite(Чтение и запись). Этот параметр можно
238 Глава 7
опустить, тогда по умолчанию тип доступа будет принимать значение
ReadWrite;
Считывание данных из текстового файла.
Для считывания данных из текстового файла используется класс
StreamReader, наследуемый от абстрактного класса TextReader. Он имеет сле-дующие основные конструкторы:
Sub New(ByVal pathAs String, ByVal encoding As Encoding)
Sub New(ByVal streamAs Stream, ByVal encoding As Encoding)
где:
path— полное имя файла, включающее само имя файла и путь к нему;
stream— поток для чтения;
encoding— кодировка знаков. Может принимать одно из значений пере-числения Encoding: ASCIIEncoding (Кодировка 7-разрядными ASCII-зна-ками), UnicodeEncoding (Кодировка в виде двух последовательных симво-лов), UTF7Encoding (Кодировка UTF-7) и UTF8Encoding(Кодировка UTF-8).
Параметр можно опустить.
Продемонстрируем примеры создания объекта класса:
Dim streamReader1 As New StreamReader ("C:\MyFile.txt")
Dim fileStream As New FileStream("C:\MyFile.txt", FileMode.Open)
Dim streamReader2 As New StreamReader(fileStream)
Запись данных в текстовый файл.
Класс StreamWriter, производный от абстрактного класса TextWriter, предна-значен для записи текстовых данных и имеет следующие основные конструк-торы:
Sub New(ByVal pathAs String, ByVal appendAs Boolean,
ByVal encodingAs Encoding)
Sub New(ByVal streamAs Stream, ByVal encoding As Encoding)
где:
path— полное имя файла, включающее само имя файла и путь к нему;
stream— поток для записи;
append— определяет, будет ли файл перезаписываться в случае указания
существующего файла. Если указано значение True, файл создается или
дописывается. Параметр можно опустить;
encoding— кодировка знаков. Может принимать одно из значений пере-числения Encoding: ASCIIEncoding(Кодировка 7-разрядными ASCII-зна-ками), UnicodeEncoding(Кодировка в виде двух последовательных симво-лов), UTF7Encoding(Кодировка UTF-7) и UTF8Encoding(Кодировка UTF-8).
Параметр можно опустить.
Продемонстрируем примеры создания объекта класса StreamWriter:
Dim streamWriter1 As New StreamWriter("C:\MyFile.txt", true)
Dim fileStream As New FileStream("C:\MyFile.txt", FileMode.Append)
Dim streamWriter2 As New StreamWriter(fileStream)
Открытие и создание файла для чтения и записи.
Для получения объектов классов FileStream, StreamReaderи StreamWriter
можно воспользоваться перечисленными в табл. 7.8 методами класса File.
Класс FileInfo имеет аналогичные методы за тем исключением, что имя фай-ла задается при создании экземпляра класса, и поэтому в методах параметр
Path отсутствует.
Эталоны ответов на теоретические задания: по дисциплине «Дискретная математика»
Составные высказывания
В формально-логических выводах используются истинные и ложные предложения.
Определение: повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно, называется высказыванием.
Примеры высказываний: "кит - животное", "все углы - прямые" и т. п. Первое из этих высказываний является, очевидно, истинным, а второе - ложным. Предложение "реши задачу", также как и "2+2", не является высказыванием.
Определения математических понятий не являются высказываниями, т.к. это принятые соглашения.
Будем обозначать высказывания большими латинскими буквами: A, B, C,….
Элементарные, нерасчленяемые высказывания будем называть атомами.Употребляемые в обычной речи логические связки "и", "или", "если..., то...", "эквивалентно", частица "не" и т. д. позволяют из уже заданных высказываний строить новые, более "сложные" высказывания.
Аналогично тому, как в языке из простых предложений с помощью логических связок образуются сложные предложения, так и в логике высказываний из атомов можно образовывать составные высказывания.
Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями.
Основные логические операции. Формулы логики. Дизъюнктивная
конъюнктивная нормальные формы
Отрицанием высказывания A называется высказывание (A), которое истинно, если A – ложно, и ложно, если A – истинно.
Таблица истинности отрицания:
A
И Л
Л И
Конъюнкцией высказываний A и B называется высказывание AB (читается "A и B"), которое истинно тогда и только тогда, когда A, B – истинно.
Таблица истинности конъюнкции:
A B AB
И И И
И Л Л
Л И Л
Л Л Л
Дизъюнкцией высказываний A и B называется высказывание AB (читается "A или B"), которое ложно тогда и только тогда, когда A, B – ложны.
Таблица истинности дизъюнкции:
A B AB
И И И
И Л И
Л И И
Л Л Л
Импликацией высказываний A и B называется высказывание A→B (читается "если A, то B"), которое ложно тогда и только тогда, когда A – истинно, а B – ложно.
Таблица истинности импликации:
A B A→B
И И И
И Л Л
Л И И
Л Л И
Эквиваленцией высказываний A и В навивается высказывание, обозначаемое AB (читается :"A тогда и только тогда, когда В" или короче: "A эквивалентно В"), которое считается истинным только тогда, когда оба высказывания A и В имеют одинаковое истинностное значение.
Эквивалентность АВ читается также следующим образом: "Для того, чтобы A, необходимо и достаточно, чтобы В".
Таблица истинности эквиваленции:
A B AB
И И И
И Л Л
Л И Л
Л Л И
Построение таблицы истинности для формулы логики
7 – число простое; и.в. В: в равнобедренном треугольнике при основании углы равны, и.в. AВ - и.в.Логическая операция задается таблицей:
р q р ↓ q
1 1 0
1 0 0
0 1 0
0 0 1
Изучение законов логики. Равносильные преобразования.
Законы логики (свойства логических операций)Следующие формулы являются законами логики.
- закон двойного отрицания.
- закон коммутативности конъюнкции.
- закон коммутативности дизъюнкции.
- закон ассоциативности конъюнкции.
- закон ассоциативности дизъюнкции.
- закон дистрибутивности конъюнкции относительно дизъюнкции.
- закон дистрибутивности дизъюнкции относительно конъюнкции.
- закон отрицания дизъюнкции.
- закон отрицания конъюнкции.
- закон отрицания импликации.
- закон выражения эквивалентности через конъюнкцию и импликацию.
- закон контрапозиции.
- закон силлогизма.
Упрощение формул логики с помощью равносильных преобразований.
Определение. Формула B есть логическое следствие формул A1, A2, .., An, если формула B принимает истинное значение при тех же значениях, при которых истинна каждая из формул A1, A2, .., An.
Запись (A1, A2, .., An)B означает, что B – логическое следствие формул A1, A2, .., An.
Пример. (AB, A).
Докажем данное следствие.
A B AB A
И И И Л Л Л
И Л Л И И Л
Л И И Л И И
Л Л И И И И
Булевы функции.
Переменная х, принимающая значения 0 или 1, называется булевой (или логической, двоичной). Функция F, зависящая от булевых переменных и принимающая также значения 0 или 1, называется булевой (или логической, двоичной) и обозначается .
Булевы функции F от n переменных могут быть заданы посредством таблицы истинности, содержащей строк и столбцов. В левой части таблицы содержатся наборы значений n переменных, расположенные в порядке возрастания их десятичного эквивалента, а в правой ее части значения функции F на соответствующих наборах значений переменных.
В качестве примера рассмотрим таблицу истинности некоторой булевой функции F, зависящей от переменных , и .
F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Совершенная дизъюнктивная и конъюнктивная нормальные формы (СДНФ и
СКНФ)
Определение. Элементарной конъюнкцией называется конъюнкция литералов (переменных или их отрицаний), взятых не более чем по одному разу.
Например, конъюнкции , , 1 являются элементарными. Причем первая элементарная конъюнкция имеет ранг (число литералов) 2, вторая 3, а третья 0.
Следующие конъюнкции: , , , , 0 не являются элементарными.
Определение. Элементарная конъюнкция булевой функции , содержащая n литералов, называется полной (или минтермом).
Определение. Дизъюнкция любого конечного множества элементарных конъюнкций булевой функции F называется дизъюнктивной нормальной формой (ДНФ) функции F. Число элементарных конъюнкций (слагаемых, термов), составляющих ДНФ, называется длиной ДНФ.
Например, ДНФ имеет длину, равную 3.
Для произвольной булевой функции F существует, вообще говоря, много различных реализующих ее ДНФ, отличающихся друг от друга длиной, числом вхождений литералов и т.д.
Определение. Две (или несколько) ДНФ, реализующих одну и ту же булеву функцию F , называются эквивалентными (или равносильными).
Например, для функции , заданной булевым вектором w(F)=(00100111), существуют следующие эквивалентные ДНФ:
, (1)
, (2)
, (3)
, (4)
.(5)
Определение. ДНФ булевой функции F, состоящая только из полных элементарных конъюнкций, называется совершеннойДНФ(СДНФ).
Например, (1) СДНФ функции F.
Отметим, что СДНФ является единственной (с точностью перестановки слагаемых) для конкретной булевой функции F .
Любую булеву функцию F, заданную формулой, можно с помощью основныхравносильностей преобразовать к ДНФ, а затем к СДНФ.
Представление булевой функции в виде совершенной ДНФ и КНФ,
минимальной КНФ, полинома Жегалкина
Для булевой функции, заданной в виде ДНФ , составить СДНФ и выполнить проверку по таблице истинности.
Решение: Применяя закон склеивания (в обратном порядке: ), дополняем конъюнкции, до полных элементарных конъюнкций. Конъюнкцию дополняем в два этапа, так как не является элементарной конъюнкцией:

.
Так как , после сокращения одинаковых конъюнкций получаем СДНФ:
.
Таблица истинности СДНФ
Элементарные конъюнкции СДНФ
0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1
0 1 1 0 0 0 1 0 0 1 1 1
1 0 1 0 0 1
1 1 0 1 1 1
1 1 1 0 0 1
Определение.Полином булевой функции F, в слагаемые которого все переменные F входят только без отрицания или только с отрицанием, называется монотонно-поляризованным. Причем в первом случае полином функции F называется положительно-поляризованный и обозначается через P(F), а во втором случае - отрицательно-поляризованным и обозначается через Q(F). Полином P(F) иначе называется каноническим полиномом Жегалкина (или в зарубежной научно-технической литературе - формой Рида-Мюллера).
Например, для булевой функции, заданной вектором значений таблицы истинности w(F)=(00100111) полиномы P(F) и Q(F) имеют вид:
,
.
Отметим некоторые свойства монотонно-поляризованных полиномов P(F) и Q(F) булевой функции :
1. Полиномы P(F) и Q(F) являются для булевой функции F единственными.
2. Полиномы P(F) и Q(F) имеют степень n тогда и только тогда, когда
таблица истинности функции F содержит нечетное число единиц.
3. Число слагаемых полинома P(F) (Q(F)) четно тогда и только тогда, когда
(соответственно ).
Понятие полноты множества функций. Замкнутые классы
Определение. Множество логических функций называется замкнутым классом, если любая суперпозиция функций из множества снова принадлежит .
Всякая система логических функций порождает некоторый замкнутый класс, а именно класс всех функций, которые можно получить суперпозициями функций . Такой класс называется замыканием и обозначается . Если множество - функционально полная система, то .
Теорема. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний.
Из данной теоремы и того очевидного факта, что подстановка нескольких формул без отрицаний в формулу без отрицаний снова даёт формулу без отрицаний, вытекает следующая теорема.
Теорема. Множество всех монотонных функций является замкнутым классом.
Но поскольку всякая булева формула без отрицаний является суперпозицией дизъюнкций и конъюнкций, из данной теоремы непосредственно получаем следствие.
Следствие. Класс монотонных функций является замыканием системы функций
Проверка булевой функции на принадлежность к замкнутым классам, на
полноту.
Теорема. Если все функции функционально полной системы представимы формулами над системой , то система также функционально полна.
Пример. а) Системы и функционально полны. Действительно, с помощью законов Де Моргана и двойного отрицания можно выразить в каждой из этих систем функцию, недостающую до через остальные две:
.
С точки зрения функциональной полноты систему следует считать избыточной: она сохраняет свойство полноты и при удалении из неё конъюнкции или дизъюнкции. Однако легко видеть из приведённого примера, что, хотя системы и не являются избыточными, зато формулы в них получаются гораздо длиннее: замена одной операции на другую вносит в формулу сразу три лишних отрицания.
б) Системы (штрих Шеффера) и (стрелка Пирса) являются функционально полными.
.
Таким образом, система сводится к системе , а система - к системе .
в) Система (умножение по модулю 2, сложение по модулю 2 – см. пункт 1 лекции № 8)) является функционально полной. Поскольку , данная система сводится к .
Множества и подмножества.
Понятие множество принадлежит к числу фундаментальных неопределяемых понятий математики.
Множество можно представить себе как совокупность объектов, обладающих общим свойством. Объекты, из которых составлено множество, называются его элементами.
Множества обычно обозначают большими латинскими буквами (например, A, S, D), а их элементы - строчными (например, a, s, d).
Если элемент х принадлежит множеству А, то это обозначается: хА; в противном случае говорят, что элемент не принадлежит множеству, это обозначается: хА.
Примеры множеств.
Множество N - множество натуральных чисел. 1N. -1N.
Множество L - множество букв русского алфавита.фL. vL.
Множество не содержащие элементов называется пустым. Это множество обозначается .
Множества можно задавать следующими способами.
Перечисление элементов: P={точка, прямая, плоскость, тело}, S={0,1,2}.
Задание характеристического свойства: L={n|nN и n<7}.
Операции над множествами
Объединение двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А или множеству В. Обозначение: АВ.
АВ={x| хА или хВ}.
Пересечение двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А и множеству В. Обозначение: АВ.
АВ={x| хА и хВ}.
Разность двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А и не принадлежащие множеству В. Обозначение: А \ В.
А \ В={x| хА и хВ}.
Обычно элементы множеств выбираются из некоторого достаточно широкого множества U, которое называется универсум. В связи с этим понятием можно ввести операцию дополнение.
Дополнением множества А называется множества, которое состоит из элементов универсума, не принадлежащих множеству А. Обозначение: .
=U \ A или ={x| хА и хU}.
Понятие предикат.
Под предикатом предметной переменной х А будем понимать функцию Р(х) на {0,1}. Предикат р (х) называется одноместным предикатом
Например:
Предикат х > 5, xR: при х = 4 предикат обращается в ложное высказывание. При х = 7 предикат обращается в истинное высказывание.
Функция Р (х, у), где х, уА, принимающая значения во множестве {0,1} называется двухместным предикатом.
Например: х<у
Логические операции над предикатами.
1) Отрицание. - предикат, множеством истинности которого является множество, для которого предикат Р – ложный.
Mp (x)

Рис. 1. Область истинности отрицания предиката
2) Конъюнкция Р (х) Q(х) – это предикат, область истинности которого равна М∩ М.
914400-114300
Рис. 2. Область истинности конъюнкция предикатов
Дизъюнкция Р (х) Q(х) – предикат, область истинности которого равна ММ.
Mp
Mq
U

Рис. 3. Область истинности дизъюнкции предикатов
ИмпликацияР (х)Q(х) – предикат, у которого область истинности совпадает с дополнением разности М и М, т.е. равна ().
Mp
U

Рис. 3. Область истинности импликаци предикатов
Эквиваленция Р (х) Q(х) – предикат, область истинности которого совпадает с объединением пересечения М с Ми дополнения к их объединению, т.е. равна - М∩М.
914400-114300
Определение логического значения для высказываний
Рассмотрим предложения:
В любой треугольник можно вписать окружность.
Всякое число, оканчивающееся на четную цифру, делится на 2.
В этих предложениях встречаются слова «любой», «всякое». Эти слова заменяют специальным символом. Значок называется квантором всеобщности.
- всякий, любой, каждый.
(х) Р (х), где хU – запись, говорящая о том, что любой х из предметной области U обладает свойством Р.
Например. Пусть Р (х) предикат, выражающий для х N свойство быть простым числом. Тогда (х) (х N) Р (х) - ложное высказывание «любое натуральное число является простым».
Наряду с квантором всеобщности в логике предикатов рассматривается квантор существования: Его значок .
(х) Р (х) – существует такой х, который обладает свойством Р.
Например. Пусть Р (х) предикат, выражающий для х N свойство быть простым числом. Тогда, (х) (х N) Р (х) - истинное высказывание «существует натуральное число, которое является простым».
Операция введения квантора называется операцией навешивания квантора. Навешивание квантора по какой-нибудь переменной понижает местность предиката.
Переменная, по которой навешен квантор, называется связанной.
Например.х<у - двухместный предикат. Навесим квантор:
(х) (х N) (х<у) предикат одноместный по переменной у.
Таким образом, понизить местность предиката можно двумя способами.
задать предметной переменной конкретное значение.
навесить кванторы по одной или нескольким переменным.
Квантор всеобщности можно рассматривать как обобщение конъюнкции для конечных и бесконечных множеств.
Квантор существования можно рассматривать как обобщение дизъюнкции для конечных и бесконечных множеств.
Построение отрицаний к предикатам.
Отрицание. - предикат, множеством истинности которого является множество, для которого предикат Р – ложный.
Mp (x)

Область истинности отрицания предиката
Понятие бинарного отношения и его свойства.
Отношения на множестве.Если в декартовом произведении в качестве множества В выбрать множество А ( то есть А Х А= А), то отношение k из А называется отношением на множестве.
Для отношений на множестве вводятся понятия:
Обратное отношение-это множество пар (а,b) таких, что (b,a) А.

Дополнение-это множество пар (а,b) k.

Тождественное отношение-множество пар (а, а) таких, что, аА,
I= {(a, a), aA}
Универсальное отношение U={(a,b),aA, bА}
Виды отношений:Инъекция.
1746250396240Если каждый элемент множества А соответствует элементу из множества В, то отношение f называется инъективным.
Рис.2. Инъекция.
Сюръекция.
Если для каждого элемента y множества В существует элемент х А, соответствующий элементу y, то такое отношение f называется сюръекцией.
17462500
Рис.3.Сюръекция.
Биекция.
Если для каждого элемента yB существует ровно один элемент хА, которому соответствует y , то такое отношение называется биективным.
Биективное отношение инъективно и сюръективно.
Биективное отношение имеет обратное отношение.
1885950127000
Рис.4. Биекция.
Отношение эквивалентности.
Определение.Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно.
Эта система обладает следующими свойствами:
она образует разбиение множества , то есть классы попарно не пересекаются;
любые два элемента из одного класса эквивалентны;
любые два элемента из разных классов не эквивалентны.
Все эти свойства прямо следуют из определения отношения эквивалентности.
Исследование бинарных отношений на рефлексивность, симметричность и
транзитивность; выделение классов эквивалентности
Определение 1. Отношение называется отношением нестрогого порядка, если оно является рефлексивным, антисимметричным и транзитивным.
Определение 2. Отношение называется отношением строгого порядка, если оно является антирефлексивным, антисимметричным и транзитивным.
Оба типа отношений вместе называются отношениями порядка. Элементы сравнимы по отношению порядка , если выполняется одно из двух отношений или . Множество , на котором задано отношение порядка, называется полностью упорядоченным, если любые два его элемента сравнимы. В противном случае, множество называется частично упорядоченным.
Композиция отображений
Определение.Пусть нам даны соответствия fАхВ, gCхD, то композицию соответствия gf будет представлять собой gf АхD и действовать так: а А: (gf)(а)= g(f(а))
Пример.fRх[-1;1]g [-1;2]х[-4;8]
f(х)=sinхg(х)=4х
Нужно построить gf и fg.
gfRх[-4;8]fg [-1;2]х[-1;1]
1) фиксируем элемент хR
(gf)(х)= g(f(х))= 4sinх
2) фиксируем элемент х[-1;2]
(fg)(х)=f(g(х))= 4sinх
Операции над подстановками
Операция над (на) множеством M это функция [7]:

Из определения операции видно, что она замкнута на множестве М, т.е. результат операции не выходит за пределы этого множества.
Еще одно свойство операции – однозначность результата, т.е.
упорядоченный набор n элементов (операндов) дает в результате операции только один элемент.
Порядок операции – это количество ее операндов: n = 1 соответствует унарной (монадической) операции, n = 2 – бинарной (диаедической) операции и т.д.
Далее рассматриваются только бинарные операции. Они могут быть заданы в одной из трех форм:
infix ( например, x + y);
prefix ( +xy );
postfix ( xy+ ).
Последние две формы дают бесскобочную запись (скобки вводятся, в инфиксной форме, для явного указания порядка выполнения операций).
Решение задач на запись циклического разложения подстановки
Подстановка на множестве M – это биекция [7]:
MNn, n = |M| N.
В случае конечного множества M (как выше) количество подстановок определяется как количество перестановок из n элементов:

Можно считать, n ящиков заполняются объектами x1, …, xn, xiM.
Поскольку MбиективноNn, можно определить подстановку как NnNn, т.е. иметь дело только с натуральными числами:

{i1, i2, … , in} = Nn.
Обычно подстановка задается в форме стандартной таблицы, имеющей две строки. Верхняя строка всегда содержит последовательные натуральные числа, начиная с 1. В нижней строке, конечно, не должно быть повторений.
Например:

Подстановка, как и любое бинарное отношение, может быть составной

.
Видно, что в «контрпримере» , т.е. «произведение» подстановок некоммутативно.
В составе любой подстановки можно выделить циклы. Их длина может составлять 1, 2,…, n. Цикл длины 1 – это фактически вырожденный цикл, стационарный элемент.
Выполнение операций и решение простейших уравнений в алгебре подстановок.
1: Коммутативность.
xy = yx, x, yM.
Например, на множестве целых чисел Zоперация сложения коммутативна – в отличие от операции вычитания.
2: Ассоциативност ь.
(xy) z = x (yz), x, y, zM.
Фактически речь идет об изменении порядка действий (задаваемого скобками).
Например, операция вычитания не ассоциативна.
3: Единица.
lx = x, l, xM, l– леваяединица.
xr = x, r, xM, r – правая единица.
ex = xe = x, e, xM, е – двусторонняя или просто единица.
Например, сложение на множестве вещественных чисел Rимеет единицу (аддитивную):
a + 0 = 0 + a = a.
Вычитание имеет только правую единицу:
a – 0 = a, но 0 – a a (если a 0).
Единица операции умножения (типа умножения) – мультипликативная, обозначается обычно «1» .
4: Обратный элемент.
х – левый обратный элемент по отношению к у, а у – правый по отношению х, если
х у = е.
«Просто» обратный элемент (взаимно обратные элементы), если
х у = у х = е.
Существование и единственность единицы и обратного элемента позволяет решать простейшие уравнения (п.4).
5: Идемпотентность.
х х = х, х М.
Вообще-то количество одинаковых элементов в выражении может быть любым. Идемпотентность позволяет в необходимых случаях сжимать или, наоборот, растягивать выражение. То же, кстати, было и в алгебре логике для операций дизъюнкция и конъюнкция.
6: Дистрибутивность.
Здесь уже требуются две операции, обозначаемые, например, (операция типа умножение) и (операция типа сложение).
Дистрибутивность по отношению к:
х (у z) = (х у) (х z),
(х у) z= (х z) (у z),
x, y, zM.
Понятие вычета по модулю N. Операции над вычетами. Шифрование
Вычетом числа a по модулюm называется остаток от деления a на m
Из определения видно, что вычеты связаны с делением с остатком.
Разделить натуральное число aна натуральное число b с остатком означает yнайти неотрицательные числа два числа qи г, причем г <b такие, что выполняется равенство
а = q·b + г
Метод математической индукции
Метод математической индукции - не просто распространенный метод решения олимпиадных задач, но и способ доказательства многих утверждений в математической науке.1.)База индукции: первое утверждение ряда верно.
2.) Переход индукции: если верно какое-то утверждение ряда (неважно, какое именно), то верно и следующее за ним утверждение ряда.
Решение задач на выполнение операций в алгебре вычетов
Для степени y=2n(n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.
Решение и комментарии.
Как известно, натуральные степени числа 2 оканчиваются цифрами {2, 4, 8, 6}. См. таблицу нескольких степеней числа 2.
Определим функцию, которая ставит в соответствие каждому натуральному числу ппоследнюю цифру числа 2я:
n 2n Последняя
цифра 2т
1 2 2
2 4 4
3 8 8
4 16 6
5 32 2
6 64 4
7 128 8
8 256 6
f: N{2, 4, 8, 6},
Эта функция f(n) периодична с периодом 4. Это значит, что для целого числа k: f(n)=f(n+4)= f(n+4k),.
Причем справедливы так же равенства: f(n)=f(n-4)= f(n-4k)
Последнее равенство означают, что для любого пнужно найти минимальное натуральное т, такое, что f(m) = f(m + 4k) = f(n).
Но это задача на делении с остатком числа n на 4:
n=4k+m, k-частное, т - остаток.
Очевидно, последняя цифра числа 2" зависит от остатка, полученного при делении показателя n степени 2 n на 4.
Отразим этот факт в записи функции: f(n)= f(nmod 4)
Из этой формулы можно установить, если f(nmod 4)=0, то
При делении чисел на 4 nN, останки могут быть: 0,1,2,3. Таким образом, в частности, множество всех возможных показателей степени 2 n для любого n состоит из четырех подмножеств: 4k, 4k+ 1, 4k+ 2, 4k+3.
Генерирование К-элементных подмножеств данного множества
Для каждого сгенерированного элемента затем проверяются какие-то свойства для конкретной задачи. Задачи, в которых требуется определить количество возможных операций, называется комбинаторными. Пусть имеется группа некоторых объектов ,, которые мы будем называть элементами.
Из этой группы элементов будем образовывать подгруппы. Такие подгруппы будем называть соединениями.
Из этих соединений выделим классы, которые будем называть размещениями.
Размещения.Размещениями из m-элементов по n называются соединения, каждое из которых содержит n элементов, взятых из данных m и которые отличаются друг от друга или элементами, или их порядком.
Предполагается, что элементы водном размещении не повторяются.
Понятие графа. Способы задания графа. Методика выделения компонента
связности в графе
Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е - множество ребер).
G(V,E): , EVxV.
Число вершин графа G обозначим р, а число ребер – q.
р(G) = |V| q(G) = |E|.
Часто рассматриваются следующие родственные графам объекты.
1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества - дугами (G(V, )).
2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).
3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.
Далее выражение: граф G(V,E) означает неориентированный граф без петель и кратных ребер.
Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями.
Распознавание мостов и разделяющих вершин в графе
1. . .
Т.о. это неориентированный граф с петлей и кратными ребрами.
v1
v2
v3
e1
e2
e3
e4
e5
2. . .
Рис. 1. Неориентированный граф с петлей и кратными ребрами.
Т.о. это ориентированный граф с петлей и кратными ребрами.
v1
v2
v3
e1
e2
e3
e4
v4

Рис. 2. Ориентированный граф с петлей и кратными ребрами.
1
4
2
3
3. . , т.о.
Нахождение расстояния между вершинами в графе.
Пусть v1, v2 - вершины, е = (v1, v2) - соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Степенью вершины v графа G(V,E) называется число ребер, инцидентных данной вершине. Обозначение: .
Вершина, имеющая степень 0 называется изолированной, имеющая степень 1 – висячей.
Изоморфные графы. Эйлеровы графы
Изоморфизм графов Говорят, что два графа G1(V1,E1) и G2(V2,E2) изоморфны (обозначается G1~ G2), если существует биекция h: V1 V2, сохраняющая смежность.
Графы рассматриваются с точностью до изоморфизма.
Пример
Три внешне различные диаграммы, приведенные на рис. 1, являются диаграммами одного и того же графа К3,3.

Рис. 1. Диаграммы изоморфных графов
Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, p(G) и q(G) - инварианты графа G.
Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.

Цикл, содержащий каждое ребро ровно один раз, называется эйлеровым. Граф, содержащий эйлеровый цикл, называется эйлеровым графом.
Плоские графы. Деревья и их свойства
Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. На рисунке 1 изображены все деревья шестого порядка.

Проверка графа на плоскость.
Матрицей смежностей А(D) орграфа D называется (р×р)-матрица ||aij||, у которой aij= 1, если ViVj- дуга орграфа D, и aij=0 в противном случае. Матрица смежностей которого имеет вид (рис. 6):

Матрица смежности графа
Легко проверить, что суммы элементов по строкам матрицы A(D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам - полустепеням захода.
Как и в случае графов, степени матрицы смежностей А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Теорема. (i, j)-й элемент аijn матрицы А" равен числу маршрутов длины n, идущих из вершины vi в вершину vj.
8. ПРИЛОЖЕНИЕ-ВАРИАНТЫ БИЛЕТОВ