Задачи для самостоятельной работы. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ 1) Сколько Имеется Различных Двоичных Наборов ...
1) Сколько имеется различных двоичных наборов длины ?
2) Сколько имеется различных функций алгебры логики от переменных?
3) Сколько имеется различных функций от переменных, сохраняющих 0 (т.е. равных нулю на нулевом наборе: )?
4) Доказать равносильности алгебры логики:
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
5) Показать, что функция является самодвойственной.
6) Найти все самодвойственные функции от двух переменных.
7) Сколько имеется самодвойственных функций от переменных?
8) Дать определение несамодвойственной функции.
9) Дана произвольная несамодвойственная функция. Отождествить у нее переменные так, чтобы получилась несамодвойсвенная функция от возможно меньшего числа переменных. Каким может быть это число?
10) Представить функцию в виде СДНФ, СКНФ; найти .
11) Представить многочленами Жегалкина:
а) основные логические операции;
б) ;
в) ;
г)..
12) Сколько имеется линейных функций от переменных?
13) Какие из линейных функций являются самодвойственными?
14) Доказать, что функция, представленная полиномом Жегалкина, существенно зависят от всех входящих в них переменных.
15) Дать определение немонотонной функции.
16) Какие из основных логических операций являются монотонными?
17) Какие из линейных функций являются монотонными?
18) Перечислить все монотонные функции от двух переменных.
19) Какие из указанных функций являются монотонными:
а) ;
б) ;
в) ;
г) ;
д) .
20) Доказать полноту следующих систем функций:
а) ;
б)
в) ;
г) ;
д) ;
е) ;
ж) ;
з) ;
и) .
21) Решить задачу, используя таблицы Поста. Какие из следующих систем функций являются функционально замкнутыми классами:
а) функции от одной переменной;
б) функции от двух переменных;
в) все функции алгебры логики;
г) линейные функции;
д) самодвойственные функции;
е) монотонные функции;
ж) монотонно убывающие функции;
з) функции, сохраняющие ноль;
и) функции, сохраняющие единицу;
к) функции, сохраняющие и нуль, и единицу;
л) функции, сохраняющие нуль, но не сохраняющие единицу?
22) Доказать, что пересечение функционально замкнутых классов — функционально замкнутый класс.
23) Является ли объединение функционально замкнутых классов функционально замкнутым классом?
24) Доказать, что дополнение собственного функционально замкнутого класса (совокупность функций, в него не входящих) не может быть функционально замкнутым классом.
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Фесенко Т Н...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Задачи для самостоятельной работы.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Представление бинарных отношений графами.
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов