Изучение функций в курсе математики
Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 08.06.2010 |
| Размер файла | 133,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
13
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Комсомольский-на-Амуре государственный
технический университет»
Факультет компьютерных технологий
Кафедра «Информационных систем»
РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ
по дисциплине «Дискретная математика»
Студент группы 9-ПИ Шикер С.А.
2010
Задача 1. Представьте заштрихованные области диаграммы Эйлера-Венна (рис.1) максимально компактным аналитическим выражением, в котором используется минимальное количество операций и букв.
рис.1
Решение
На рис.2 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C?D. На рис.3 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C/B. На рис.4 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C?А.
Рис. 2 Рис. 3 Рис.4
Чтобы получить необходимое множество (рис. 1) необходимо между этими тремя выражениями поставить операцию объединение. В результате получаем:
(C?D) (C/B) (C?A)
Задание 2. Записать высказывание в виде формулы логики высказываний, используя пропозициональные (логические) переменные для обозначения элементарных высказываний, т.е. таких, которые уже не могут быть построены из каких - либо других высказываний:
Неверно, что если Сидоров - не кассир, то Сидоров убил кассира; следовательно, фамилия кассира - Сидоров.
Решение
Введем обозначения:
a - «Сидоров - кассир»
b - «Сидоров убил кассира»
Исходное высказывание содержит связку «если …, то …», которая соответствует импликации, а так же связку «Неверно, что…» и предлог «не», что соответствует отрицанию. Формула имеет вид:
> a
Задание 3. Используя равносильности логики высказываний, упростить исходную формулу
Для исходной формулы и упрощенной построить таблицу истинности.
Решение.
Введем обозначения: F1 =
F2 =
Построим таблицу истинности для F1 и F2:
|
№ |
a |
b |
c |
F1 |
F2 |
||||||
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
|
2 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
|
3 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
|
4 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
5 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
6 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Столбцы, соответствующие F1 и F2, совпадают. Это значит, что аналитические преобразования исходной формулы верны.
Задание 4. Ниже приведена клауза
Необходимо выяснить при помощи алгоритма Вонга и метода резолюции является ли клауза теоремой.
Решение
Метод Вонга.
Построим дерево доказательства.
Все ветви дерева заканчиваются клаузами, в которых по обеим сторонам символа присутствует одна и та же буква. Следовательно, логическая теорема верна.
Метод резолюция.
Необходимо преобразовать клаузу таким образом, чтобы после знака получился ноль, при этом избавимся от импликации.
?
Выпишем по порядку все посылки и далее начнем их «склеивать».
|
1 |
7 |
(2;3)А |
||
|
2 |
8 |
(1;5) |
||
|
3 |
9 |
(7;4) |
||
|
4 |
10 |
(9;6)B |
||
|
5 |
11 |
(10;8)? |
||
|
6 |
Иначе, порядок «склеивания» можно представить в виде цепочки равносильных преобразований:
Задание 5. Заданы номера наборов аргументов, на которых булева функция принимает значение, равное единице. Необходимо:
· Записать булеву функцию в СДНФ и СКНФ;
· Минимизировать функцию с помощью минимизационной карты;
· Построить алгоритм Куайна.
· Выяснить к каким функционально-замкнутым классам принадлежит булева функция;
·
f (x1,x2,x3,x4)=1010010010110011
Решение
1. Запишем СДНФ и СКНФ булевой функции.
СДНФ(1):№ 0,2,5,8,10,11,14,15
f = 123412 3412341234
1234123412341234
СКНФ(0):№ 1,3,4,6,7,9,12,13
f = (1234) (1234) (1234) (1
234) (123 4) (123 4) (1
234) (1234)
2. Строим минимизационную карту и пошагово выполняем алгоритм.
Шаг1.
|
№ |
x1 |
x2 |
x3 |
x4 |
x1x2 |
x1x3 |
x1x4 |
x2x3 |
x2x4 |
x3x4 |
x1x2x3 |
x1x2x4 |
x1x3x4 |
x2x3x4 |
x1x2x3x4 |
f |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
|
|
2 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
2 |
1 |
0 |
2 |
2 |
2 |
1 |
|
|
3 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
3 |
1 |
1 |
3 |
3 |
3 |
0 |
|
|
4 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
2 |
2 |
0 |
2 |
2 |
0 |
4 |
4 |
0 |
|
|
5 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
2 |
3 |
1 |
2 |
3 |
1 |
5 |
5 |
1 |
|
|
6 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
3 |
2 |
2 |
3 |
2 |
2 |
6 |
6 |
0 |
|
|
7 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
3 |
3 |
3 |
3 |
3 |
3 |
7 |
7 |
0 |
|
|
8 |
1 |
0 |
0 |
0 |
2 |
2 |
2 |
0 |
0 |
0 |
4 |
4 |
4 |
0 |
8 |
1 |
|
|
9 |
1 |
0 |
0 |
1 |
2 |
2 |
3 |
0 |
1 |
1 |
4 |
5 |
5 |
1 |
9 |
0 |
|
|
10 |
1 |
0 |
1 |
0 |
2 |
3 |
2 |
1 |
0 |
2 |
5 |
4 |
6 |
2 |
10 |
1 |
|
|
11 |
1 |
0 |
1 |
1 |
2 |
3 |
3 |
1 |
1 |
3 |
5 |
5 |
7 |
3 |
11 |
1 |
|
|
12 |
1 |
1 |
0 |
0 |
3 |
2 |
2 |
2 |
2 |
0 |
6 |
6 |
4 |
4 |
12 |
0 |
|
|
13 |
1 |
1 |
0 |
1 |
3 |
2 |
3 |
2 |
3 |
1 |
6 |
7 |
5 |
5 |
13 |
0 |
|
|
14 |
1 |
1 |
1 |
0 |
3 |
3 |
2 |
3 |
2 |
2 |
7 |
6 |
6 |
6 |
14 |
1 |
|
|
15 |
1 |
1 |
1 |
1 |
3 |
3 |
3 |
3 |
3 |
3 |
7 |
7 |
7 |
7 |
15 |
1 |
Шаг 2. Вычеркиваем строки, в которых функция обращается в нуль.
Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге.
Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем - переменные) и обводим их.
Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного.
Результирующая таблица имеет вид:
|
№ |
x1 |
x2 |
x3 |
x4 |
x1x2 |
x1x3 |
x1x4 |
x2x3 |
x2x4 |
x3x4 |
x1x2x3 |
x1x2x4 |
x1x3x4 |
x2x3x4 |
x1x2x3x4 |
f |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
|
|
2 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
2 |
1 |
0 |
2 |
2 |
2 |
1 |
|
|
3 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
3 |
1 |
1 |
3 |
3 |
3 |
0 |
|
|
4 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
2 |
2 |
0 |
2 |
2 |
0 |
4 |
4 |
0 |
|
|
5 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
2 |
3 |
1 |
2 |
3 |
1 |
5 |
5 |
1 |
|
|
6 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
3 |
2 |
2 |
3 |
2 |
2 |
6 |
6 |
0 |
|
|
7 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
3 |
3 |
3 |
3 |
3 |
3 |
7 |
7 |
0 |
|
|
8 |
1 |
0 |
0 |
0 |
2 |
2 |
2 |
0 |
0 |
0 |
4 |
4 |
4 |
0 |
8 |
1 |
|
|
9 |
1 |
0 |
0 |
1 |
2 |
2 |
3 |
0 |
1 |
1 |
4 |
5 |
5 |
1 |
9 |
0 |
|
|
10 |
1 |
0 |
1 |
0 |
2 |
3 |
2 |
1 |
0 |
2 |
5 |
4 |
6 |
2 |
10 |
1 |
|
|
11 |
1 |
0 |
1 |
1 |
2 |
3 |
3 |
1 |
1 |
3 |
5 |
5 |
7 |
3 |
11 |
1 |
|
|
12 |
1 |
1 |
0 |
0 |
3 |
2 |
2 |
2 |
2 |
0 |
6 |
6 |
4 |
4 |
12 |
0 |
|
|
13 |
1 |
1 |
0 |
1 |
3 |
2 |
3 |
2 |
3 |
1 |
6 |
7 |
5 |
5 |
13 |
0 |
|
|
14 |
1 |
1 |
1 |
0 |
3 |
3 |
2 |
3 |
2 |
2 |
7 |
6 |
6 |
6 |
14 |
1 |
|
|
15 |
1 |
1 |
1 |
1 |
3 |
3 |
3 |
3 |
3 |
3 |
7 |
7 |
7 |
7 |
15 |
1 |
Шаг 6. Сокращенная ДНФ имеет вид
f = 24131234
Строим матрицу покрытий:
|
№ |
Простые импликанты |
Конституенты единицы функции f |
|||||||||||
|
x1 |
x2 |
x3 |
x4 |
0000 |
0010 |
0101 |
1000 |
1010 |
1011 |
1110 |
1111 |
||
|
1 |
- |
0 |
- |
0 |
1 |
1 |
1 |
1 |
|||||
|
2 |
1 |
- |
1 |
- |
1 |
1 |
1 |
1 |
|||||
|
3 |
0 |
1 |
0 |
1 |
1 |
Последовательно выбираем слагаемые 1,2,5
В результате получаем МДНФ:
f = 13241234
3. Построим алгоритм Куайна.
Построим таблицу значений функции
|
х1 |
х2 |
х3 |
х4 |
f |
||
|
0 |
0 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
|
|
2 |
0 |
0 |
1 |
0 |
1 |
|
|
3 |
0 |
0 |
1 |
1 |
0 |
|
|
4 |
0 |
1 |
0 |
0 |
0 |
|
|
5 |
0 |
1 |
0 |
1 |
1 |
|
|
6 |
0 |
1 |
1 |
0 |
0 |
|
|
7 |
0 |
1 |
1 |
1 |
0 |
|
|
8 |
1 |
0 |
0 |
0 |
1 |
|
|
9 |
1 |
0 |
0 |
1 |
0 |
|
|
10 |
1 |
0 |
1 |
0 |
1 |
|
|
11 |
1 |
0 |
1 |
1 |
1 |
|
|
12 |
1 |
1 |
0 |
0 |
0 |
|
|
13 |
1 |
1 |
0 |
1 |
0 |
|
|
14 |
1 |
1 |
1 |
0 |
1 |
|
|
15 |
1 |
1 |
1 |
1 |
1 |
СДНФ (1): № 0, 2, 5, 8, 10, 11, 14, 15
1)
2)
3)
4)
5)
6)
7)
8)
|
Слагаемые |
Склеивание по переменной |
Результат склеивания |
|
|
1, 2 |
x3 |
||
|
1, 4 |
x1 |
||
|
2, 5 |
x1 |
||
|
4, 5 |
x3 |
||
|
4, 6 |
х4 |
||
|
5, 6 |
х4 |
||
|
5, 7 |
х2 |
||
|
6, 8 |
х2 |
||
|
7, 8 |
х4 |
С результатами таблицы повторим операцию склеивания.
1)
2)
3)
4)
5)
6)
7)
8)
9)
|
Слагаемые |
Склеивание по переменной |
Результат склеивания |
|
|
1, 4 |
x1 |
||
|
2, 3 |
x3 |
||
|
6, 9 |
х2 |
||
|
7, 8 |
х4 |
В итоге получим:
f = 13241234
4. Построим таблицу значений функции
|
х1 |
х2 |
х3 |
х4 |
f |
||
|
0 |
0 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
|
|
2 |
0 |
0 |
1 |
0 |
1 |
|
|
3 |
0 |
0 |
1 |
1 |
0 |
|
|
4 |
0 |
1 |
0 |
0 |
0 |
|
|
5 |
0 |
1 |
0 |
1 |
1 |
|
|
6 |
0 |
1 |
1 |
0 |
0 |
|
|
7 |
0 |
1 |
1 |
1 |
0 |
|
|
8 |
1 |
0 |
0 |
0 |
1 |
|
|
9 |
1 |
0 |
0 |
1 |
0 |
|
|
10 |
1 |
0 |
1 |
0 |
1 |
|
|
11 |
1 |
0 |
1 |
1 |
1 |
|
|
12 |
1 |
1 |
0 |
0 |
0 |
|
|
13 |
1 |
1 |
0 |
1 |
0 |
|
|
14 |
1 |
1 |
1 |
0 |
1 |
|
|
15 |
1 |
1 |
1 |
1 |
1 |
1. f(0,0,0,0)?0 0
2. f(1,1,1,1)=1 1
3. f(0,0,0,0)=f(1,1,1,1)?0
4. Поскольку набор (1,1,1,1) больше любого другого набора и f(0,0,1,0)=1, f(0,0,1,1)=0, то
Для того чтобы выяснить, является ли функция линейной построим многочлен Жегалкина (с помощью треугольника Паскаля)
|
слагаемое |
х1 |
х2 |
х3 |
х4 |
f |
Паскаля |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
f=1010010010110011 |
|
|
х4 |
0 |
0 |
0 |
1 |
0 |
111011011101010 |
|
|
х3 |
0 |
0 |
1 |
0 |
1 |
00110110011111 |
|
|
х3 х4 |
0 |
0 |
1 |
1 |
1 |
0101101010000 |
|
|
х2 |
0 |
1 |
0 |
0 |
0 |
111011111000 |
|
|
х2 х4 |
0 |
1 |
0 |
1 |
1 |
00110000100 |
|
|
х2 х3 |
0 |
1 |
1 |
0 |
0 |
0101000110 |
|
|
х2 х3 х4 |
0 |
1 |
1 |
1 |
1 |
111100101 |
|
|
х1 |
1 |
0 |
0 |
0 |
1 |
00010111 |
|
|
х1 х4 |
1 |
0 |
0 |
1 |
1 |
0010100 |
|
|
х1 х3 |
1 |
0 |
1 |
0 |
0 |
011110 |
|
|
х1 х3 х4 |
1 |
0 |
1 |
1 |
0 |
11111 |
|
|
х1 х2 |
1 |
1 |
0 |
0 |
1 |
0000 |
|
|
х1 х2 х4 |
1 |
1 |
0 |
1 |
0 |
000 |
|
|
х1 х2 х3 |
1 |
1 |
1 |
0 |
1 |
00 |
|
|
х1 х2 х3 х4 |
1 |
1 |
1 |
1 |
0 |
0 |
Полином Жегалкина имеет вид:
1+x4+x2+x2x3x4+x1x3x4, f
|
T0 |
T1 |
S |
L |
M |
||
|
f |
- |
+ |
- |
- |
- |
Задание 6. Разбить высказывание на элементарные и записать в виде кванторной формулы логики предикатов, используя наименьшее возможное число предикатов наименьшей местности
Через всякую точку, не лежащую на прямой, можно провести не более одной прямой, параллельной данной.
Решение
1. Введем обозначения:
P(x, y): «точка y принадлежит прямой x»
Q(x, y): «x // y»
Исходное выражение можно записать в виде следующей формулы:
2. Сначала приведем формулу к приведенной нормальной форме, т. е. избавимся от знака импликации, используя равносильности логики высказываний и логики предикатов:
Для приведения к предваренной нормальной форме необходимо вынести все кванторы в начало формулы (используя равносильности логики предикатов):
Задание 7. Построить интерпретацию формулы логики предикатов:
Решение
Данная формула является открытой (первое вхождение переменной у не связано квантором) и формула содержит нульместный предикат (S). Значит, интерпретация будет состоять из четырех шагов.
1. Зададим множество, на котором будем рассматривать все предикаты: М=R, где R - множество действительных чисел.
2. Каждой предикатной букве ставим в соответствие предикат:
P(x, y): “x> y”; R(x,y,z): “xy=z”, S(z): “z=1”;
При данной интерпретации высказывание является ложным (читается: для любых действительных чисел x и y, x>y), - истинное высказывание (читается: существуют такие действительные числа x,y,z, что xy=z), - истинное высказывание (читается: существует такое действительное число z, что z=1). В результате получили высказывание, которое можно записать:
Значит, данная интерпретация обращает формулу логики предикатов в истинное высказывание.
Подобные документы
Операции над логическими высказываниями: булевы функции и выражение одних таких зависимостей через другие. Пропозициональные формулы и некоторые законы логики высказываний. Перевод выражений естественного языка на символическую речь алгебры логики.
контрольная работа [83,3 K], добавлен 26.04.2011Порядок доказательства истинности заключения методом резолюции (с построением графа вывода пустой резольвенты) и методом дедуктивного вывода (с построением графа дедуктивного вывода). Выполнение бинарных операций и составление результирующих таблиц.
курсовая работа [185,3 K], добавлен 24.05.2015Минимизация заданного выражения алгебры множеств на основании известных свойств. Анализ заданного бинарного отношения в общем виде. Вывод формул булевых функций для каждого элемента и схемы в целом. Преобразование формулы булевой функции логической схемы.
контрольная работа [286,7 K], добавлен 28.02.2009Анализ основных понятий, утверждений, связанных с показательной и логарифмической функциями в курсе математики. Изучение методик решения типовых задач. Подбор и систематизация задач на нахождение и использование показательной и логарифмической функций.
курсовая работа [1,5 M], добавлен 20.07.2015Определение формулы исчисления высказываний, основные цели математической логики. Построение формул алгебры высказываний. Равносильность формул исчисления высказываний, конъюнктивная и дизъюнктивная нормальная форма. Постановка проблемы разрешимости.
контрольная работа [34,3 K], добавлен 12.08.2010Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.
лекция [253,7 K], добавлен 01.12.2009Свойства операций над множествами. Формулы алгебры высказываний. Функции алгебры логики. Существенные и фиктивные переменные. Проверка правильности рассуждений. Алгебра высказываний и релейно-контактные схемы. Способы задания графа. Матрицы для графов.
учебное пособие [1,5 M], добавлен 27.10.2013История возникновения и развития математической логики как раздела математики, изучающего математические обозначения и формальные системы. Применение математической логики в технике и криптографии. Взаимосвязь программирования и математической логики.
контрольная работа [50,4 K], добавлен 10.10.2014Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
контрольная работа [178,2 K], добавлен 20.01.2011Понятие предикатов и кванторов, порядок составления логических формул. Запись предиката как множество высказываний, формулы их исчисления. Аксиоматическое и натуральное представление узкого исчисления предикатов, погружение аристотелевской силлогистики.
контрольная работа [35,0 K], добавлен 12.08.2010
