Логические сети
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ь линейность булевой функции, заданной этой формулой, с помощью полинома Жегалкина и методом неопределенных коэффициентов:
.
Приведение формулы к ДНФ, КНФ, СДНФ, СКНФ аналитическим способом:
- КНФ.
- СКНФ.
- ДНФ.
- СДНФ.
Приведение формулы к ДНФ, КНФ, СДНФ, СКНФ табличным способом:
XYZЭлемент.
конъюнкцииЭлемент.
дизъюнкции000111110001111001010100110011100010100011001101011110110000001111000110
Пусть и .
СДНФ:
СКНФ:
Проверка линейности булевой функции, заданной этой формулой, с помощью полинома Жегалкина:
Полученный полином Жегалкина является нелинейным, и, следовательно, функция f(X,Y,Z) также нелинейная.
Проверка линейности булевой функции, заданной этой формулой, с помощью метода неопределенных коэффициентов:
III.Минимизировать двумя способами:
a.Методом Квайна;
b.Геометрическим методом.
Методом Квайна:
1)Привести функцию к СДНФ;
2)В СДНФ произвести всевозможные склеивания, а затем поглощения;
)Перейти от сокращенной СДНФ к минимальной, используя импликантную матрицу.
СДНФ:
- сокращенная СДНФ
++----+++--+
Необходимо оставить такие простые импликанты, чтобы в каждом столбце был хотя бы один +, следовательно, - минимальная СДНФ.
Геометрический метод:
- геометрическое представление.
Получаем, что - минимальная СДНФ..Доопределить функции так, чтобы - была монотонной; - была линейной; - была самодвойственной.
XYZfgh000--00010-10101--011-0-100-00101011110---111-0-
Функция называется монотонной, если для любых наборов нулей и единиц А=(а1,…,аn), В=(b1,…,bn) таких, что , выполняется условие
Функция называется линейной , где .
Функция называется самодвойственной, если она совпадает с двойственной к ней.
Пользуясь определениями монотонной, линейной и самодвойственной функций, получим следующую таблицу истинности:
XYZfgh000000001011010110011101100000101011110110111101
V.Составить таблицу истинности. Доказать истинность заключения дедуктивным методом. Нарисовать граф вывода заключения дедуктивным методом. Доказать истинность заключения по методу резолюции и нарисовать граф вывода пустой резольвенты.
+
Используя дедуктивный метод, докажем истинность заключения:
+
Согласно правилу цепного заключения:
+
+
Граф вывода заключения:
Таблица истинности для данного заключения выглядит следующим образом:
ABCDF00001111111000111111110010110110100111111111010010110110101101101101101101101011111111111000011000110010111001101001000011011011100111001010001110110110011110110010111111111111
Пусть , и
Докажем истинность заключения по методу резолюции:
) - КНФ
)
)
)
Граф вывода пустой резольвенты:
VI.Найти формулы ПНФ и ССФ, выполнить унификацию атомов дизъюнктов.
Пусть , тогда:
Пусть y=w, тогда:
- ПНФ.
Приведём к ССФ:
Пусть , тогда:
- ССФ.
VII.Доказать, что функция примитивно рекурсивна:
является простейшей одношаговой рекурсивной функцией - функция константа.
.Найти функции, получаемые из данной числовой функции с помощью операции минимизации по каждой её переменной:
)
y=0 при
в остальных случаях не определена.
)
y=0 при
y=1 при
в остальных случаях не определена.
)
Если набор переменных таков, что левая часть уравнения имеет смысл и уравнение выполнимо, то можно считать, что оно выполнимо при подстановке y=0 на самом первом шаге.
IX.Построить машину Тьюринга, которая правильно вычисляет функцию:
Заключение
Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем, которые лежат в основе работы любого компьютера.
Математическая логика является современной формой, так называемой формальной логики, применяющей математические методы для исследования своего предмета. В формальной логике и, соответственно, в математической логике, собраны результаты законов структуры правильных выводов. Вывод - это мыслительный процесс, в результате которого появляются новые открытия на основании уже имеющихся без практических исследований. В действительности, новое открытие, полученное в результате вывода, в скрытой форме находится в предварительно имеющихся знаниях.