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

Основи теорії множин

Множина - це деякий набір об’єктів, які не повторюються і називаються елементами.

Вона позначається в такий спосіб

де - множина, - її елементи .

Будь який набір, кожний елемент якого належить множині , є його підмножиною. Наприклад, множина  має свою підмножину , та позначається .

Якщо , то кажуть, що  - порожня множина: пишуть =Ø.

Якщо серед предметів, що входять у сукупність , є однакові, то таку сукупність називають мультимножиною.

Множину, яка складається з кінцевого числа елементів, має кінцеву потужність, називають кінцевою, множину, що не є кінцевою, називають нескінченною.

Над множинами можливо виконувати такі дії.

Рівність множин. Множини  рівні тоді, коли кожний елемент множини  є елементом множини , і навпаки, кожний елемент множини  є елементом множини :

Рівність множин  і  показана за допомогою діаграми Ейлера-Вена (рис.1)

Рис. 1. Рівність множин

Об’єднання множин. Об’єднанням або сумою двох множин  і  називається множина, що складається з усіх елементів, кожний із яких належить хоча б одному з даних множин (рис.2)

Рис. 2. Об’єднання множин

         Як правило виконуються наступні закони [1]: 

1. Асоціативний

2. Комутативний

Ø

якщо .

Перетинання множин. Перетинання двох множин називається множина, що складається із усіх тих елементів, які належать обом множинам (рис. 3). Для цієї операції використовується комутативний і асоціативний закони.

Рис. 3 Перетинання множин.

.

Дві множини  і  є взаємовиключальними, або несумісними, якщо Ø

     Різниця множин. Різниця  /  множин  і  є множина, що складається з елементів множини , які належать множині . (рис.4) 

читається „ ”

Рис. 4. Різниця множин

     Доповнення множин. Доповнення множини  називається множина, у якій містяться всі елементи простору , крім тих, що належать множені . Воно визначається через  (рис. 5)

Рис. 5. Доповнення множин.

Індивідуальне завдання. Спростити множини.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30. .

Графи. Дії над ними

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

Рис.2.1.

Аналітично граф задається множинами вершин:

та відображеннями кожної вершини графа (рис 2.1):

;     ;

     Матричний засіб зображення графів використовується при обробці їх на ЕОМ.

     Матрицею суміжності називається квадратна матриця , де - кількість вершин графа. У цієї матриці , якщо вершина суміжна з вершиною , тобто має відображення на цю вершину. Якщо вершина не суміжна з вершиною . Для рис 2.1

.

     Над графами можливо виконувати слідуючи основні дії:

1. Об’єднанням графів є новий граф, вершини якого є об’єднанням множин вершин першого і другого графів, а відображення кожної вершини нового графа є об’єднання відображень цієї вершини на першому і другому графах:

                (2.1)

                                                   (2.2)

                                              (2.3)

     Наприклад надані два графа (ріс. 2.2 і 2.3) .

Рис. 2.2                                                 Рис. 2.3

Ø =

Граф рис. 2.4 є об’єднання графів рис. 2.2 і 2.3

Рис. 2.4

2. Перетинання графів – це новий граф

                                  (2.4)

вершини якого є перетинання вершин першого і другого графів

                                            (2.5)

а відображення кожної вершини нового графа є перетинання відображень цієї вершини на першому і другому графах

                                        (2.6)

Для рис. 2.2 і 2.3

Ø

Граф рис. 2.5 є перетинання початкових графів

Рис. 2.5

3. Декоративний добуток графів є добуток матриць суміжності  і  початкових графів.

Граф рис. 2.2 можливо зобразити матрицею

,

а рис. 2.3 матрицею . Тоді матриця суміжності нового графа

Кожний елемент матриці  необхідно помножити на матрицю . При цьому одержана правильна кліточна матриця (ПКМ), клітини якої є нульові, або дорівнюють матриці .

Графічно декартовий добуток можливо показати на рис. 2.6:

Рис. 2.6

4. Сума графів виконується з використанням матричного рівняння:

,                                     (2.8)

де - одиничні матриці розмірністю матриць  та .

     Для розглянутого вище прикладу:

.

     Отримана регулярна клітиночна матриця, яка побудована з 4 видів кліток. Якщо елемент матриці  розташтований на головній діагоналі , то відповідна клітка матриці  дорівнює

     Якщо  не знаходиться на головній діагоналі

Графічно сума графів для наведеного прикладу буде виглядати рис. 2.7

0

Рис. 2.7

     Індивідуальне завдання. Знайти декартовий добуток і суму графів, заданих матрицями суміжності.

      Варіант 1       .

     Варіант 2        .

     Варіант 3        .

     Варіант 4       

     Варіант 5       

     Варіант 6       

     Варіант 7        .

     Варіант 8       

     Варіант 9       

     Варіант 10     

     Варіант 11     

     Варіант 12     

     Варіант 13     

     Варіант 14     

     Варіант 15     

     Варіант 16     

     Варіант 17     

     Варіант 18

     Варіант 19

     Варіант 20

     Варіант 21

     Варіант 22

     Варіант 23

     Варіант 24

     Варіант 25

Варіант 26

     Варіант 27

     Варіант 28

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

     Розглянемо цей алгоритм на прикладі.

     Наданий орієнтований граф (рис. 2.8).

Рис. 2.8

     Присвоїмо навчальній вершині графа постійну мітку , останні вершини мають тимчасові мітки .

     Знаходимо нові тимчасові мітки вершини 1,2,3 по формулі:

,                                            (2.9)

де  означає, що вершина є попередньою для вершини ; - оцінка дуги .

Нові оцінки цих вершин

,

,

.

     Вершини з найменшою оцінкою присвоюється постійна мітка

.

Далі по формулі (2.9) знаходимо нову мітку вершини 4:

найменшу тимчасову мітку має вершина 1. Присвоюємо їй постійну мітку .

     По формулі (2.9) знаходимо нові мітки вершин 3 і 4, в які входять дуги з вершин з постійними мітками:

,

.

     Вершині 4 присвоюємо постійну мітку  По формулі (2.9):

.

Найменшу тимчасову мітку має вершина графа 3. Їй присвоюємо постійну мітку

     Тоді , це є її постійна мітка Це є довжина найкоротшого шляху графа. Таких шляха 2: 0-1-4-5 або 0-2-4-5.

Індивідуальне завдання

     У таблицях 1-5 наведені вартість купівлі устаткування та підтримання його у робочому стані з урахуванням інфляції та його модернізації. Заміна устаткування може бути зроблена не раніше чим через 4 роки. Розглядаємо період експлуатації 5-9 років (для різних варіантів).

     Знайти найкращу стратегію зміни та підтримки устаткування у робочому стан, при якої сумарні витрати будуть найменшими  :

Таблиця 1

Таблиця 2

Таблиця 3

Таблиця 4

Таблиця 5

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

Логіка – наука про форми та закони мислення.

Математична логіка використовує математичні методи та спеціальний апарат символів для рішення логічних задач.

У цьому розділі дискретної математики особливу роль будуть грати двійкові елементні множини і двійкові змінні. Ці елементи позначають Ø і 1, проте вони не є числами в звичайному значенні.

Алгебра, утворена множиною разом із усіма можливими операціями на ньому, називається алгеброю логіки. Логічною функцією від змінних називається - арна операція. Таким чином, логічна функція f(x₁, x₂, …, x_n) – це функція, що набуває значення Ø, 1.

Таблиця істинності логічних функцій двох змінних.

	0	1	0	1	Пояснення
	0	0	1	1
	0	0	0	0	константа 0
	1	0	0	0	стрілка Пірса x1↓x2
	0	1	0	0	заборона x1←x2
	1	1	0	0	заперечення    2
	0	0	1	0	заборона x1←x1
	1	0	1	0	заперечення 1
	0	1	1	0	додавання по модулі
	1	1	1	0	штрих Шефера
	0	0	0	1	кон’юнкція
	1	0	0	1	Эквиваленція x1∞x2
	0	1	0	1	повторення              x1
	1	1	0	1	імплікація x2→x1
	0	0	1	1	повторення     x2
	1	0	1	1	імплікація x1→x2
	0	1	1	1	диз'юнкція
	1	1	1	1	константа I

1.Закон переміщення:

2.Закон сполучення:

3.Розподільний:

.

Всі закони логіки можливо доказати за допомогою таблиці 1:

Із розподільного закону для кон’юнкція можна зробити два слідства:

– правило зникнювання

– правило поглощение

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

4.Закон інверсії (правило де-Моргана)

.

В алгебрі логіки використовуються наступні логічні тождества:

Приклади рішення завдань

3.1. Спростити логічне вираження

Рішення. Замінимо операцію імплікації найпростішими логічними функціями (диз'юнкція, конъюнкция, заперечення) на підставі таблиці 2

.

Звільнимося від заперечення над комплексом перемінних

3.2. Логічна функція задана аналітично

.

Задати неї за допомогою таблиці істинності.

Рішення. Перетворимо дане логічне рівняння в СКНФ, додаючи до неповних співмножників 0 у виді тотожності .

	0	1	0	1	0	1	0	1
	0	0	1	1	0	0	1	1
	0	0	0	0	1	1	1	1
y	0	0	1	1	0	0	1	1

На підставі отриманого рівняння складемо таблицю істинності.

Нуль “y” приймає в чотирьох стовпчиках (крапках логічного простору) по числу співмножників у правій частині отриманого рівняння ,причому аргументові без заперечення відповідає 0,із запереченням – 1 у шуканому стовпці. В інших стовпцях “y” приймає щире (одиничне) значення.

3.3. Мінімізувати логічне рівняння

.

Рішення. Для мінімізації цього рівняння використовуємо метод Квайна (правило склеювання). Мінімізуємо доданки візьмемо в квадратні дужки, повтор двічі доданок

Для мінімізації цього рівняння можна використовувати діаграму Вейча.

	0		0					0
						1
	1			1		1			1

Об'єднати “одиниці” у діаграмі можна іншим способом (табл.5).

	0		0				0
					1
		1	1		1		1

При цьому .

3.4. Мінімізувати логічне рівняння

Рішення. Для мінімізації конъюнктивних норрісьних форм використовуємо співвідношення, що випливає з розподільного закону для диз'юнкції  

Мінімізирувані співмножники об'єднаємо в квадратні дужки, дописавши співмножник  

Для мінімізації заданого рівняння можна використовувати діаграму Вейча.

Таблиця 6.

	0					1	0
						1	0
		1	1

Індивідуальне завдання. Преобразовати

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.