Вивчення функцій в курсі математики

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство освіти і науки Російської Федерації

Федеральне агентство з освіти

Державна освітня установа

вищої професійної освіти

«Комсомольський-на-Амурі державний

технічний університет »

Факультет комп'ютерних технологій

Кафедра «Інформаційних систем»

РОЗРАХУНКОВО-ГРАФІЧНЕ ЗАВДАННЯ

з дисципліни «Дискретна математика»

Студент групи 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. Використовуючи равносильности логіки висловлювань, спростити вихідну формулу

Для вихідної формули та спрощеної побудувати таблицю істинності.

Рішення.

Введемо позначення: F 1 =

F 2 =

Побудуємо таблицю істинності для F 1 і F 2:

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

Стовпці, відповідні F 1 і F 2, збігаються. Це означає, що аналітичні перетворення початкової формули вірні.

Завдання 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 (x 1, x 2, x 3, x 4) = 1010010010110011

Рішення

  1. Запишемо СДНФ і СКНФ булевої функції.

СДНФ (1): № 0,2,5,8,10,11,14,15

f = 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

СКНФ (0): № 1,3,4,6,7,9,12,13

f = ( 1 2 3 4) ( 1 2 3 4) ( 1 2 3 4) ( 1

2 3 4) ( 1 2 3 4) ( 1 2 3 4) ( 1

2 3 4) ( 1 2 3 4)

  1. Будуємо мінімізаціонную карту і крок за кроком виконуємо алгоритм.

Шаг1.

x 1

x 2

x 3

x 4

x 1 x 2

x 1 x 3

x 1 x 4

x 2 x 3

x 2 x 4

x 3 x 4

x 1 x 2 x 3

x 1 x 2 x 4

x 1 x 3 x 4

x 2 x 3 x 4

x 1 x 2 x 3 x 4

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. Якщо в одному стовпці обведено кілька однакових чисел, то викреслюємо все, крім одного.

Результуюча таблиця має вигляд:

x 1

x 2

x 3

x 4

x 1 x 2

x 1 x 3

x 1 x 4

x 2 x 3

x 2 x 4

x 3 x 4

x 1 x 2 x 3

x 1 x 2 x 4

x 1 x 3 x 4

x 2 x 3 x 4

x 1 x 2 x 3 x 4

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 = 2 4 1 3 1 2 3 4

Будуємо матрицю покриттів:

Прості імпліканти

Констітуенти одиниці функції f


x 1

x 2

x 3

x 4

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 = 1 3 2 4 1 2 3 4

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

x 3

1, 4

x 1

2, 5

x 1

4, 5

x 3

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

x 1

2, 3

x 3

6, 9

х 2

7, 8

х 4


В результаті отримаємо:

f = 1 3 2 4 1 2 3 4

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

D Паскаля

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 + x 4 + x 2 + x 2 x 3 x 4 + x 1 x 3 x 4, f


T 0

T 1

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). В результаті отримали висловлювання, яке можна записати:

Значить, дана інтерпретація звертає формулу логіки предикатів в істинне висловлення.

Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Контрольна робота
162.8кб. | скачати


Схожі роботи:
Методика вивчення функцій у шкільному курсі математики
Рішення рівнянь і нерівностей з використанням властивостей функцій на елективної курсі з математики 2
Рішення рівнянь і нерівностей з використанням властивостей функцій на елективної курсі з математики
Вивчення функцій та їх графіків на елективної курсі з алгебри у 9 класі
Вивчення тригонометричного матеріалу в шкільному курсі математики
Методика вивчення елементів математичного моделювання в курсі математики 5-6 класів
Методика вивчення елементів математичного моделювання в курсі математики 5 6 класів
Вивчення елементів теорії множин в початковому курсі навчання математики
Методика вивчення елементів математичного моделювання в курсі математики 5-6 класів 2
© Усі права захищені
написати до нас