41775

Логічні функції двох змінних

Лабораторная работа

Математика и математический анализ

Операції f: BnB називаються функціями алгебри логіки або логічні функції булевими БФ. Усяка логічна функція fx1x2. Функція називається кон’юнкцією логічним множенням й ; її позначення: або . Функція .

Русский

2013-10-25

191.22 KB

5 чел.

Лабораторна робота №4

Тема: Логічні функції  двох змінних.

Мета: вивчити логічні функції двох змінних, навчитися одержувати досконалу диз'юнктивну нормальну форму й досконалу кон’юктивну нормальну форму та  приводити функцію до заданого базису.

Теоретичні основи:

Функції двох змінних алгебри логіки

Алгебра A = <B, F>, у якій множина B={0,1}, а  F є множина операцій  f: BnB, n=1, 2,...,m, називається алгеброю логіки або булевою.  

Операції  f: BnB називаються функціями алгебри логіки або логічні функції, булевими (БФ).

Усяка логічна функція  f(x1,x2,..., xn) може бути задана таблицею, що називається таблицею істинності.

Логічних функцій двох змінних – 16,  вони наведені в табл. 1

Таблиця 1 Функції двох змінних алгебри логіки

x1

x2

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

БФ й   - константи 0 й 1, тобто функції із двома несуттєвими змінними.

Функція називається кон’юнкцією, логічним множенням й ; її позначення:  ,  або  . Вона дорівнює 1, тільки якщо й рівні 1.

Функція   .

Функція  .

Функція   .

Функція   .

Функція   – це додавання по модулю 2. Її позначення: . Вона дорівнює 1, коли значення її аргументів різні.

Функція   називається диз'юнкцією, логічною сумою   й ;  її позначення: ,  . Вона дорівнює 1, якщо х1 або х2 дорівнює 1.

Функція   називається функцією Вебба або стрілкою Пірса; її позначення: . Вона дорівнює 1 тоді й тільки тоді, коли обидва аргументи рівні 0.

Функція   називається еквівалентністю; її позначення: , . Вона дорівнює 1,  коли значення її аргументів рівні.

Функція   .

Функція   – імплікація; її позначення: .

Функція  .

Функція   -  імплікація; її позначення: . Вона дорівнює 0 тільки тоді, коли   а  .

Функція   – штрих Шеффера або І-НІ (NAND); її позначення: або . Вона дорівнює 0 тоді й тільки тоді, коли обидва аргументи рівні  1.

Реалізація функцій формулами

Суперпозицією функцій називається функція отримана за допомогою підстановок цих функцій друг у друга й перейменування змінних.  Формулою називається вираження, що описує  суперпозицію функцій.

Нехай дана множина (кінцевих або нескінченних) вихідних логічних функцій . Всі формули, які містять тільки символи змінних, дужки й знаки функцій з множини , називаються формулами над .

Суперпозиція елементарних булевих функцій - формула.

Приклад:  

Таким чином, формула кожному набору значень аргументів ставить у відповідність значення функції й служить поряд з таблицею способом завдання й обчислення функції.

Формули, що представляють одну й ту саму функцію,  називаються еквівалентними або рівносильними. Еквівалентність формул позначається знаком або . Стандартний метод визначення еквівалентності двох формул полягає в наступному: по кожній формулі будується таблиця істинності функції, а потім отримані дві таблиці порівнюються. Інший метод називається методом  еквівалентних перетворень і складається в перетворенні однієї з формул (або обох) до тих пір, поки не прийдемо до однакової форми.

Нормальні форми булевих функцій.

Алгоритм приведення до ДДНФ і ДКНФ довільної логічної функції

Досконала диз'юнктивна й кон’юктивна нормальна форми дають спосіб подання булевої функції за допомогою суперпозиції кон’юнкції, диз'юнкції й заперечення, якщо в нас є таблиця значень функції.

Подання булевої функції у вигляді

           ,                           

                  

де диз'юнкція береться по всім , на яких , називається  досконалою диз'юнктивною нормальною формою (ДДНФ). Усяка булева функція (крім 0) має єдину СДНФ.

Щоб одержати досконалу диз'юнктивну нормальну форму, треба взяти всі набори, на яких значення функції дорівнює 1 і записати для кожного з них кон’юнкцію змінних й їхніх заперечень. Якщо в наборі значення змінної 0 - то змінну треба взяти із запереченням, якщо 1 - без заперечення. З наборів  кон’юнкцій змінних  треба побудувати диз'юнкцію.

Приклад 1 .(Досконала диз'юнктивна нормальна форма).

Побудуємо досконалу диз'юнктивну нормальну форму функції, заданою наступною таблицею.

Таблиця 2. Функція задана за допомогою таблиці.

x

y

z

f

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

Набори, на яких функція дорівнює 1 – це (0,1,1), (1,0,1), (1,1,0), (1,1,1). Перший набір дає кон’юнкцію ¬x & y & z, другий – x & ¬y & z, третій – x & y & четвертий – x & y & z.

У результаті одержуємо (¬x & y & z) √ (x & ¬y & z) √ (x & y & ¬z√ (x&y&z).

Щоб одержати досконалу кон’юктивну нормальну форму, треба взяти всі набори, на яких значення функції дорівнює 0 і записати для кожного з них диз'юнкцію змінних й їхніх заперечень. Якщо в наборі значення змінної 0 - то змінну треба взяти без заперечення, якщо 1 - із запереченням. З диз'юнкцій, що вийшли, треба побудувати кон’юнкцію.

Завдання:

Для заданого варіанта (табл. 3) логічної функції потрібно скласти алгоритм та програму, що дозволяють виконувати наступні дії:

а) реалізовувати всі логічні функції двох змінних;

б) побудувати таблицю істинності для заданої функції;

в) побудувати досконалу диз'юнктивну нормальну форму (ДДНФ) і досконалу кон’юктивну нормальну форму (ДКНФ) для заданої у індивідуальних завданнях функції;

Зробити аналіз роботи програми за допомогою розрахунку таблиці істинності заданої функції.

Склад звіту:

  1.  Титульний лист
  2.  Мета, завдання до виконання л/р
  3.  Короткі теоретичні відомості
  4.  Блок-схема алгоритму
  5.  Лістинг програми
  6.  Роздруківка результатів роботи програми:

x1

x2

x3

x4

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

f16

Fинд.

ДДНФ: …

ДКНФ: …

  1.  Ручний розрахунок

x1

x2

x3

x4

1

2

3

4

Fинд.

  1.  Аналіз результатів і висновки.


Таблиця 3 - Варіанти завдань до лабораторної роботи 2

N

Функція

N

Функція

1

25

2

26

3

27

4

28

5

29

6

30

7

31

8

32

9

33

10

34

11

35

12

36

13

37

14

38

15

39

16

40

17

41

18

42

19

43

20

44

21

45

22

46

23

47

24

48


N

Функція

N

Функція

49

75

50

76

51

77

52

78

53

79

54

80

55

81

56

82

57

83

58

84

59

85

60

86

61

87

62

88

63

89

64

90

65

91

66

92

67

93

68

94

69

95

70

96

71

97

72

98

73

99

74

100


 

А также другие работы, которые могут Вас заинтересовать

27991. Направления природоохранной деятельности в системе агропромышленного комплекса 2.98 KB
  Алгоритм реализации природоохранной деятельности: 1 природноэкономические особенности хозяйства; 2 прогноз антропогенных изменений природного комплекса и их влияния на развитие хозяйства; 3 система мер комплексной охраны природы на территории хозяйства. Система мер охраны природы на территории хозяйства: сохранение и создание зеленых насаждений в населенных пунктах вдоль рек дорог постройка очистных сооружений предотвращение смыва удобрений в водоемы меры по экономному использованию земель под...
27992. Оптимизация аграрного производства. Баланс биогенных веществ и агробиоценозов 4.71 KB
  Для успешного функционирования данная форма земледелия должна быть дополнена организационными ландшафтноструктурными и законодательными отношениями направленными на создание благоприятных условий хозяйствам решившим перейти на экологическую форму. А именно: обеспечением финансовой поддержки для приобретения необходимого инвентаря биологических средств защиты растений и компенсации потери урожайности в переходный период; оказанием помощи в разработке правовой и нормативной документации и регламентов сертификации...
27993. Оптимизация использования минеральных удобрений и химических средств повышения плодородия 6.59 KB
  Применение органических и минеральных удобрений одно из основных условий повышения урожайности сельскохозяйственных культур а также важное звено технологий их выращивания. Использование удобрений особенно органических позволяет возвращать и вовлекать в круговорот питательные вещества взамен изъятых из агроценозов с основной и побочной продукцией обеспечивая таким образом определенную устойчивость продукционных процессов. Основными причинами загрязнения окружающей среды удобрениями считают несовершенство...
27994. Оптимизация ландшафта с х территорий, как фактор повышения устойчивости агроэкосистем 10.68 KB
  Агроландшафты являются целостными генетически однородными пространственновременными единицами несмотря на то что определенная часть их естественного растительного покрова замена агроценозами Целевая установка сельского хозяйства объективно направлена на получение максимума биологической продукции. Важное условие экологизации сельского хозяйства использование биоценологических экосистемных принципов. В противном случае несоответствие сложившейся специализации сельского хозяйства потенциальным...
27995. Основные виды токсикантов, содержащиеся в пищевых продуктах, тяжелые металлы, остаточное каличество пестицидов, нитриты, радиоактивные элементы, действие токсикантов на человека и теплокровных животных 20.2 KB
  Отравления вызванные живыми микробами попавшими в организм с пищей называют пищевыми токсикоинфекциями. Это сальмонелла кишечная палочка и условно патогенные микроорганизмы. При этих заболеваниях образование микроорганизмами яда токсина происходит в организме. Токсическое действие некоторых соединений на организм человека заключается в способности токсических веществ вызывать отравление организма выражающееся в различных клинико анатомических проявлениях.
27996. Основные с/х ресурсы и их характеристика по зонам Западной Сибири 12.22 KB
  Рациональное использование природноресурсного потенциала с х производства.Для учета и рационального использования климатических ресурсов важно соблюдать соответствие классификаций климата; классификациям сельскохозяйственного производства т. Значение воды на всех стадиях производства сельскохозяйственной продукции общеизвестно. Предотвратить истощение и загрязнение водных ресурсов призваны экологизация промышленного и сельскохозяйственного производства и городского хозяйства очистка природных и сточных вод мелиоративные...
27997. Отрицательное воздействие промышленного животноводства на природные комплексы и их компоненты 3.22 KB
  При переходе животноводства на промышленную основу возникла проблема утилизации навозных стоков и безподстилочного навоза. Вблизи животноводческих ферм образуется огромное скопление навоза происходит нитратное и микробное загрязнение почв растительности поверхностных и грунтовых вод которое в 810 раз превышает естественный фон загрязнения почвенного и снежного покрова. При выборе места для размещения живких комплексов должны быть учтены возможности утилизации навоза и производственных стоков с учетом...
27998. Оценка изменения агроэкологических показателей плодородия почв и их функций: природная сопротивляемость, буферность, способность к биологическому, физическому и химическому самоочищению 5.3 KB
  Это связано со следующими обстоятельствами: охватом антропогенными нагрузками больших площадей иногда практически на 100; малой лесистостью и небольшими площадями луговостепных участков; значительной обнаженностью дефдированностью и эродированностью почвенного покрова; преобладанием определенных видов загрязнения в почве воде и грунтах связанных с удобрениями. Наибольшей буферной емкостью и способностью снижать негативное влияние загрязняющих веществ на растительные и животные организмы обладают почвы с...
27999. Поллютанты в почве и с/х продукции. Основные факторы, влияющие на их поведение в системе «почва-растение-животное-человек» 9.67 KB
  Главным природным источником тяжелых металлов являются породы магматические и осадочные и породообразующие минералы. Поступление тяжелых металлов в биосферу вследствие техногенного рассеивания осуществляется разнообразными путями. Кроме того источником загрязнения биоценозов могут служить орошение водами с повышенным содержанием тяжелых металлов внесение осадков бытовых сточных вод в почвы в качестве удобрения. Вторичное загрязнение происходит также вследствие выноса тяжелых металлов из отвалов рудников или...