додати матеріал


Алгебра логіки

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

скачати


Лекція. Алгебра логіки

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

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

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

Розглянемо деяку схему і представимо її у вигляді так званого "чорного" ящика.

Будемо вважати, що внутрішній вміст ящика невідомо.

X 1, X 2, X 3 - вхідні сигнали, F - вихідний сигнал.

Вважаємо також, що схема А - елементарна, тобто немає іншої схеми Б, меншою, ніж А, яка б містилася в А.

Побудуємо абстрактне пристрій з елементарних пристроїв, типу А, Б, В і т.д. Очевидно, більш складний пристрій можна побудувати з простих шляхом:

  1. послідовного з'єднання елементів;

  2. паралельного з'єднання;

  3. перестановки входів елементів.

Тоді роль Y 1 для другого елементу Б буде грати:

Y 1 = F А (X 1, X 2, X 3)

Y 2 = F Б (X 1, X 2)

F = F (Y 1, Y 2) = F (F А (X 1, X 2, X 3), F Б (X 1, X 2))

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

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

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

Тому перестановка аргументів впливає на характер функції.

F = F (F А (X 1, X 2, X 3), F Б (X 2, X 3))

F (F Б (X 2, X 3), F А (X 1, X 2, X 3))

Таким чином, довільні, як завгодно складні в логічному відношенні схеми, можна будувати, використовуючи два прийоми:

  1. послідовне з'єднання елементів;

  2. перестановка входів елементів.

Цим двом фізичним прийомам в алгебрі логіки відповідають:

  1. принцип суперпозиції (підстановка у функцію замість її аргументів інших функцій);

  2. підстановка аргументів (зміна порядку запису аргументів функцій або заміна одних аргументів функції іншими).

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

Елементарні функції алгебри логіки

Існує кілька синонімів по відношенню до функцій алгебри логіки:

  1. функції алгебри логіки (ФАЛ);

  2. перемикальні функції;

  3. Булевського функції;

  4. виконавчі функції.

У міру необхідності будемо користуватися всіма цими синонімами.

Розглянемо деякий набір аргументів:

<X 1 ,X 2 ,X 3 ,...Х i ,...X n>

і будемо вважати, що кожен з аргументів приймає тільки одне з двох можливих значень, незалежно від інших

Чому дорівнює число різних наборів?

X i = {0, 1}

Поставимо кожному набору у відповідність деякий двійкове число:

X 1, X 2 ,........... X n

0, 0 ,..........., 0 нульової набір

0, 0 ,..........., 1 перший набір

0, 0 ,.......... 1,0 другий набір

...................

1, 1 ,..........., 1 (2 n -1)-ий набір

Очевидно, що кількість різних X 1, X 2 ,........... X n n-розрядних чисел в позиційній двійковій системі є 2 n.

Припустимо, що деяка функція F (X 1, X 2 ,.... X n) задана на цих наборах і на кожному з них вона приймає або '0'-е, або '1'-е значення.

Таку функцію називають функцією алгебри логіки або перемикальної функцією.

Чому дорівнює число різних перемикальних функцій 'n' аргументів?

Оскільки функція на кожному наборі може прийняти значення '0' або '1', а найбільше різних набору 2 n, то загальне число різних функцій 'n' аргументів є: 2 2n.

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

Число аргументів

1

2

3

4

5

10

Число різних перекл. ф-цій

4

16

256

65536

~ 4 * 10 9

~ 10 300

Різні пристрої ЕОМ містять десятки і сотні змінних (аргументів), тому зрозуміло, що кількість різних пристроїв, що відрізняються один від одного, практично нескінченно.

Отже, потрібно навчитися будувати ці складні функції (а отже, і пристрої), а також аналізувати їх.

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

Таким чином, спочатку необхідно вивчити ці елементарні функції, щоб на їх основі будувати більш складні.

ФАЛ одного аргументу

Щоб задати ФАЛ, потрібно задати її значення на всіх наборах аргументів.

Аргумент Х

значення

Найменування функції


0

1


F 0 (x)

0

0

константа '0'

F 1 (x)

0

1

змінна 'х'

F 2 (x)

1

0

інверсія 'х' (заперечення х)

F 3 (x)

1

1

константа '1'

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

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

Необхідно розглянути більш складні функції, тобто ФАЛ 2х аргументів.

Дамо такі визначення:

  1. ФАЛ, що приймають однакові значення на всіх наборах аргументів, називаються рівними.

  2. ФАЛ істотно залежить від аргументу Х i, якщо

F (X 1, X 2 ,..., Х i-1, 0, X i +1 ,..., X n)

F (X 1, X 2 ,..., Х i-1, 1, X i +1 ,..., X n)



В іншому випадку вона залежить не суттєво, а відповідний аргумент зв. фіктивним.

Наприклад:



Х 1

Х 2

Х 3

F (X 1, X 2, Х 3)

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

1

Видно, що Х 3 - фіктивний аргумент. Це показує, що у функцію можна ввести будь-яке число фіктивних аргументів, від яких вона суттєво не залежить. Цей прийом надалі буде потрібно для виконання низки перетворень.

Всі ФАЛ від 2-х аргументів. Зведемо їх в єдину таблицю 2.1.

Таблиця 2.1.

функції

Значення функції на наборах логічних змінних

Найменування функції

Позначення функції

X 1

0

0

1

1



X 2

0

1

0

1



f 0 (X 1, X 2)

0

0

0

0

Константа "нуль"

f (X 1, X 2) = 0

f 1 (X 1, X 2)

0

0

0

1

Кон'юнкція, твір

f (X 1, X 2) = X 1 & X 2

f (X 1, X 2) = X 1 X 2

f (X 1, X 2) = X 1 · X 2

f (X 1, X 2) = X 1 X 2

f 2 (X 1, X 2)

0

0

1

0

Заборона по X 2

X 1 Δ X 2

f 3 (X 1, X 2)

0

0

1

1

Мінлива X 1

f (X 1, X 2) = X 1

f 4 (X 1, X 2)

0

1

0

0

Заборона по X 1

X 2 Δ X 1

f 5 (X 1, X 2)

0

1

0

1

Мінлива X 2

f (X 1, X 2) = X 2

f 6 (X 1, X 2)

0

1

1

0

Складання по mod2 (нерівнозначність)

f (X 1, X 2) = X 1 X 2

f 7 (X 1, X 2)

0

1

1

1

Диз'юнкція

f (X 1, X 2) = X 1 X 2

f (X 1, X 2) = X 1 + X 2

f 8 (X 1, X 2)

1

0

0

0

Стрілка Пірса

f (X 1, X 2) = X 1 X 2

f 9 (X 1, X 2)

1

0

0

1

Рівнозначність

f (X 1, X 2) = X 1 X 2

f (X 1, X 2) = X 1 ~ X 2

f 10 (X 1, X 2)

1

0

1

0

Інверсія X 2

f (X 1, X 2) = ^ X 2

f (X 1, X 2) = X 2

f 11 (X 1, X 2)

1

0

1

1

Імплікація від X 2 до X 1

f (X 1, X 2) = X 2 X 1

f 12 (X 1, X 2)

1

1

0

0

Інверсія X 1

f (X 1, X 2) = ^ X 1

f (X 1, X 2) = X 1

f 13 (X 1, X 2)

1

1

0

1

Імплікація від X 1 до X 2

f (X 1, X 2) = X 1 X 2

f 14 (X 1, X 2)

1

1

1

0

Штрих Шеффера

f (X 1, X 2) = X 1 | X 2

f 15 (X 1, X 2)

1

1

1

1

Константа "одиниця"

f (X 1, X 2) = 1

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

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

Наприклад:

В = <один плюс один - два>

є справжнє висловлювання.

Розглянемо, яке смислове зміст можна вкласти в деякі складні висловлювання на прикладі ФАЛ 2-х аргументів.

Інверсія

Читається НЕ Х або Х з рисою, заперечення Х.

Візьмемо, наприклад, такий вислів: А = <Київ-столиця Франції>, тоді складне висловлювання НЕ А означає: не вірно, що А, тобто не вірно, що «Київ-столиця Франції>.

З простих висловлювань можна будувати більш складні, застосовуючи так звані зв'язку.

Логічні зв'язки - це ФАЛ, аргументами яких є прості висловлювання.

Кон'юнкція

Візьмемо 2 висловлювання:

А = <Москва - столиця РФ>

В = <двічі два - чотири>

тоді складне висловлювання: А & В буде істинним, так як істинні обидва цих висловлювання.

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

X 1

X 2

f 1 (X 1, X 2)

0

0

0

0

1

0

1

0

0

1

1

1

Функція кон'юнкції істинна тоді, коли істинні одночасно обидва висловлювання.

Диз'юнкція

Це складне висловлювання істинна, коли істинно хоча б одне висловлювання, що входить в нього.

X 1

X 2

f 1 (X 1, X 2)

0

0

0

0

1

1

1

0

1

1

1

1

Читається X 1 АБО X 2: Деякий відміну від сенсу союзу "або", прийнятого в російській мові: в даному випадку цей союз вживається в значенні об'єднання, а не роз'єднання.

Логічна рівнозначність

Це складне висловлювання істинно тоді, коли істинні або помилкові одночасно обидва висловлювання.

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

Наприклад,

А = <двічі два - п'ять>

B = <один плюс два - шість>

А ~ В рівнозначні.

Імплікація

Це складне висловлювання ложно тільки тоді, коли X 1 - істинно, а X 2 - помилково.

X 1

X 2

f 1 (X 1, X 2)

0

0

1

0

1

1

1

0

0

1

1

1

Читається: якщо X 1, то X 2. При цьому X 1 - посилка, X 2 - наслідок.

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

Але насправді, все вірно, тому що змістом висловлювань в алгебрі логіки не цікавляться.

Тоді з помилкової посилки може слідувати помилкове слідство і це можна вважати вірним: <якщо Київ - столиця Франції>, то <2-квадрат 3>.

Еквівалентності

У деяких випадках складне і довге висловлювання можна записати більш коротким і простим без порушення істинності вихідного висловлювання. Це можна виконати з використанням деяких еквівалентних співвідношень.

Диз'юнкція:

х х х х ... х х х = х,



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

- Постійно справжнє висловлювання.

0 x = x

x 1 x 2 = x 2 x 1

- (Переместительному) комунікативний закон.

x 1 х 2 х 3 = (x 1 х 2) х 3 = x 1 2 х 3)

- Сполучний закон.

Кон'юнкція:

х х х х ... х х х = х

правило приведення подібних членів:

- Постійно хибне висловлювання

- Постійно хибне висловлювання



Додавання за mod 2

1

при непарному числі членів, 0 - при парному числі членів

Правило де Моргана

Доведемо для двох змінних за допомогою таблиці істинності:

Х 1

Х 2

1 2

0

0

1

1

0

1

1

1

1

0

1

1

1

1

0

0

Операція поглинання:

Х XY = X

або в загальному вигляді

X X * f (X, Y, Z. ..) = X;

Операція повного склеювання:

(По Y)

(По Х)

Операція неповного склеювання:

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

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

Математика | Реферат
71.2кб. | скачати


Схожі роботи:
Модальні логіки Позитивні логіки
Лінійна алгебра
Булева алгебра
Алгебра та початок аналізу
Алгебра висловлювань на уроках інформатики
Векторна алгебра та аналітична геометрія
Гармонія і алгебра народної іграшки
Векторна алгебра і деякі її застосування
Алгебра матриць Системи лінійних рівнянь
© Усі права захищені
написати до нас
Рейтинг@Mail.ru