Федеральное агентство по образованию
ГОУ ВПО Тульский государственный университет
Кафедра
Автоматизированных информационных и управляющих систем
Варианты заданий для контрольно-курсовой работы
по дисциплине
«Дискретная математика»
(Часть №2)
Специальность: 230101 Вычислительные комплексы, системы и сети
Формы обучения – очно-заочная (вечерняя)
Направление: 230100 Информатика и вычислительная техника
Специальность: 230105 Программное обеспечение, вычислительная техника и автоматические системы
Форма обучения – заочная
Разработчик:
к. т. н., доц. каф. АИУС Баранова Е. М.
Тула, 2008 г.
Варианты заданий составлены к. т. н., доц. Барановой Е.М. и обсуждены на заседании кафедры «Автоматизированные информационные и управляющие системы» факультета «Экономика и право»,
протокол №___ от «___»____________ 2008 г.
Зав. кафедрой _____________________ В.А. Фатуев
Варианты заданий пересмотрены и утверждены на заседании кафедры «Автоматизированные информационные и управляющие системы» факультета «Экономика и право»,
протокол №___ от «___»____________ 200 г.
Зав. кафедрой _____________________ В.А. Фатуев
ВАРИАНТ 1
1. Доказать или опровергнуть эквивалентность (равносильность) формул:
а)
=
;
б)
.
2.
Доказать или опровергнуть функциональную
полноту набора операций {|},
через функционально полный набор
операций {
,
┐},
проверив соотношения на эквивалентность
,
.
3. Получить совершенную дизъюнктивную нормальную форму (СДНФ), дизъюнктивную нормальную форму (ДНФ) и совершенную конъюнктивную нормальную форму (КНФ) функции, заданной в префиксной форме:
,
если
- унарная операция,
- бинарные операции,
- отрицание,
- дизъюнкция,
- стрелка Пирса.
4.
Даны 2 подстановки
и
.
а) Привести подстановки к каноническому виду;
б)
Найти произведение подстановок
;
в)
Найти произведение подстановок
;
г) Определить степени подстановок;
д) Получить обратные подстановки и привести их к каноническому виду;
е)
Определить
;
ж) Найти число инверсий и четность подстановок.
з)
Привести подстановку
к единичной с помощью транспозиций.
5. Рассмотреть варианты навешивания кванторов на предикат Р(х), определенный на множестве натуральных чисел с нулем N0. Дать словесную формулировку полученных высказываний и определить истинность или ложность получаемых выражений, если
а)
;
б)
,
где
S – сумма, П – произведение.
ВАРИАНТ 2
1. Доказать или опровергнуть эквивалентность (равносильность) формул:
а)
=
;
б)
.
2.
Доказать или опровергнуть функциональную
полноту набора операций {
},
через функционально полный набор
операций {
,
┐},
проверив соотношения на эквивалентность
,
.
3. Получить совершенную дизъюнктивную нормальную форму (сднф), дизъюнктивную нормальную форму (днф) и совершенную конъюнктивную нормальную форму (кнф) функции, заданной в префиксной форме:
,
если
- бинарные операции,
- импликация,
- дизъюнкция,
- стрелка Пирса.
4. Даны 2 подстановки и .
а) Привести подстановки к каноническому виду;
б) Найти произведение подстановок ;
в) Найти произведение подстановок ;
г) Определить степени подстановок;
д) Получить обратные подстановки и привести их к каноническому виду;
е)
Определить
;
ж) Найти число инверсий и четность подстановок.
з) Привести подстановку к единичной с помощью транспозиций.
5. Рассмотреть варианты навешивания кванторов на предикат Р(х), определенный на множестве натуральных чисел с нулем N0. Дать словесную формулировку полученных высказываний и определить истинность или ложность получаемых выражений, если
а)
;
б)
,
где
S – сумма, П – произведение.
ВАРИАНТ 3
1. Доказать или опровергнуть эквивалентность (равносильность) формул:
а)
=
;
б)
.
2.
Доказать или опровергнуть функциональную
полноту набора операций {
},
называемого алгеброй Жегалкина, через
функционально полный набор булевого
базиса, проверив соотношения на
эквивалентность
,
.
3. Получить совершенную дизъюнктивную нормальную форму (сднф), дизъюнктивную нормальную форму (днф) и совершенную конъюнктивную нормальную форму (кнф) функции, заданной в префиксной форме:
,
если
- бинарные операции,
- эквивалентность,
- дизъюнкция,
- импликация.
4. Даны 2 подстановки и .
а) Привести подстановки к каноническому виду;
б) Найти произведение подстановок ;
в) Найти произведение подстановок ;
г) Определить степени подстановок;
д) Получить обратные подстановки и привести их к каноническому виду;
е) Определить ;
ж) Найти число инверсий и четность подстановок.
з)
Привести подстановку
к единичной с помощью транспозиций.
5. Рассмотреть варианты навешивания кванторов на предикат Р(х), определенный на множестве натуральных чисел с нулем N0. Дать словесную формулировку полученных высказываний и определить истинность или ложность получаемых выражений, если
а)
;
б)
,
где
S – сумма, П – произведение.
ВАРИАНТ 4
1. Доказать или опровергнуть эквивалентность (равносильность) формул:
а)
=
;
б) .
2.
Доказать или опровергнуть функциональную
полноту набора операций {
,┐}
через функционально полный набор
булевого базиса, проверив соотношение
на эквивалентность
.
3. Получить совершенную дизъюнктивную нормальную форму (сднф), дизъюнктивную нормальную форму (днф) и совершенную конъюнктивную нормальную форму (кнф) функции, заданной в префиксной форме:
,
если
- бинарные операции,
- эквивалентность,
- конъюнкция,
- импликация.
4. Даны 2 подстановки и .
а) Привести подстановки к каноническому виду;
б) Найти произведение подстановок ;
в) Найти произведение подстановок ;
г) Определить степени подстановок;
д) Получить обратные подстановки и привести их к каноническому виду;
е)
Определить
;
ж) Найти число инверсий и четность подстановок.
з) Привести подстановку к единичной с помощью транспозиций.
5. Рассмотреть варианты навешивания кванторов на предикат Р(х), определенный на множестве натуральных чисел с нулем N0. Дать словесную формулировку полученных высказываний и определить истинность или ложность получаемых выражений, если
а)
;
б)
,
где
S – сумма, П – произведение.
ВАРИАНТ 5