41775

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

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

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

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

Русский

2013-10-25

191.22 KB

6 чел.

Лабораторна робота №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


 

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

34679. УТВОРЕННЯ ТА РУЙНУВАННЯ ОЗОНУ 221.5 KB
  1 Фотохімічна теорія утворення озону оксигенний цикл За Чепменом озон в атмосфері утворюється з молекулярного кисню [3]. В результаті дії цих двох протилежних процесів в атмосфері на деяких висотах встановлюється цілком визначена густина озону. Для формування озону в стратосфері перш за все необхідний атмосферний оксиген який утворюється внаслідок фотодисоціації молекули оксигену по реакції 1: Р.
34680. Фотохімічний смог 103.5 KB
  Незважаючи на формування в останні десятиліття загальної тенденції до покращення стану атмосферного повітря в м. Для утворення фотохімічного смогу необхідна наявність в повітрі таких первинних забруднювачів як оксид азоту NO та NO2 які у значній кількості надходять у повітря із відпрацьованими газами автомобільних двигунів; летких органічних сполук ЛОС таких як пропан нбутан етилен бензол формальдегід які в основному надходять через випаровування та згорання палива і розчинників; Метеорологічними передумовами утворення смогу є...
34681. Хімічний склад атмосфер інших планет 204 KB
  Початок формування атмосфери повязаний з еволюцією Сонця, з процесом його перетворення молодої зірки в дорослу. Цей процес характеризувався гравітаційним ущільненням до планет (космічного пилу) та газів сонячного туману.
34682. Хімічні процеси в стратосфері 99.5 KB
  У стратосфері на висотах менше 50 км відбувається утворення озону за реакцією O2 O → O3 Нестабільна молекула озону в збудженому стані O3 перетворюється в стабільну молекулу озону в результаті реакції з так званою третьою часткою в якості якої виступають молекули кисню і азоту що містяться в повітрі в найбільшій кількості: O3 M → O3 M 107 кДж Швидкість утворення озону пропорційна добутку концентрацій що беруть участь у реакціях частинок. Таким чином існує максимум швидкості утворення озону який припадає на...
34683. Аерозоль і клімат 311.5 KB
  Оцінка прямого впливу аерозолів на радіаційний баланс дає досить широкі Schätzungen der direkten Wirkung von erosolen uf den Strhlungshushlt zeigen eine reltiv große Bndbreite und beruhen weitgehend uf Modellstudien die nicht nur für die vorindustrielle Zeit sondern uch für die Gegenwrt schwer zu verifizieren sind. Die Unsicherheiten beruhen zum einen druf dss selbst der ktuelle tmosphärische Gehlt einzelner erosolrten nicht genu feststeht zum nderen druf dss die Größenverteilung die chemische Zusmmensetzung die Mischung und die...
34684. Водяной пар в атмосфере и гидрологический цикл 44.5 KB
  В отличие от большинства других присутствующих в атмосфере газов содержание водяного пара может очень сильно меняться. По мере того как молекулы воды переходят в воздух давление пара в воздухе увеличивается. Если температура воздуха продолжает увеличиваться то для поддержания насыщенного состояния пара число молекул поступающих в воздух также должно увеличиваться если конечно жидкость еще имеется. Давление пара служит мерой для другой величины также выражающей количество пара содержащегося в воздухе и называемой абсолютной влажностью.
34685. Вплив атмосферної циркуляції на транспорт хімічних речовин 144.5 KB
  Розподіл та концентрація хімічних речовин у атмосфері залежить від особливостей переміщення повітряних мас яке обумовлене загальною циркуляцією атмосфери. Внаслідок цього є постійний річний обмін енергією від низьких до високих широт завдяки океанічним і повітряним течіям рис. Оскільки Земля найсильніше нагрівається на екваторі то потоки нагрітого екваторіального повітря піднімаються високо вгору набагато вище ніж повітря в інших широтах. Під час екваторіального підйому повітря повітряні маси із низьких і високих широт...
34686. ГЛОБАЛЬНІ ЗМІНИ ВМІСТУ ОЗОНУ В АТМОСФЕРІ ЗЕМЛІ 281 KB
  Аналіз накопичених за перші 10 15 років матеріалів спостережень показав що кількість озону в стратосфері зменшується і виникло припущення що причиною цього є виробнича діяльність людини. У заяві містилось перше попередження про зменшення кількості озону і повязаних у звязку з цим небезпечних наслідках. Зменшення кількості озону особливо помітне над холодним антарктичним континентом так звані озонові дірки†було вперше помічено тут.
34687. Джерела формування аерозолів та їх розподіл в атмосфері 99.5 KB
  Класифікація аерозолів за походженням За умовами формування виділяють первинні і вторинні аерозолі. Первинні аерозолі вносяться в атмосферу завдяки диспергуванню матеріалу на поверхні Землі вітрова ерозія спалювання різних видів палива в промислових регіонах пожежі в тропічних лісах винесення морських аерозолів з поверхні морів та океанів космічний пил. Вторинні аерозолі утворюються в результаті хімічних перетворень газоподібних речовинпопередників в атмосфері.